- 1、本文档共7页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《数据结构》试题答案
A 卷
姓名
班级
题
号
一
二
三
总分
题
分
40
30
30
100
得
分
得 分
一、回答下列问题
( 每题 5 分,共 40 分)
1.给定序列( 67,45,87,19,55,32,70,60,90,23),写出它的初始堆序列。
答:调整后的初始堆序列 (小根堆 )为: 19, 23, 32, 45, 55, 87, 70, 60, 90, 67
或者是大根堆: 90, 67, 87, 60, 55, 32, 70, 45, 19, 23
19
23 32
45 55 87 70
60 90 67
2.设一个序列奇数项和偶数项分别由小到大有序,用什么方法可以最快得到一个有序序列,分析它的时间复杂度。
答:把奇数项和偶数项分为 2 个有序序列,然后进行合并,时间复杂度为 O(n) 。实际上就
是把 2 个有序表合并为一个有序表。见教科书算法 2.7。
3.二叉排序树中的最大值在二叉排序树的何处?
答:最大值应该位于二叉排序树中根的右子树的最右叶子上。
1
4.在 2048 个互不相同的关键码中选择最小的
5 个关键码,用堆排序是否比用锦
标赛排序更快?为什么?
答:此题用锦标赛排序比堆排序要快。理由是;
①在首次求最小值时,锦标赛排序对
2048 个结点建树得到最小码只需比较
n-1(即 2047) 次,
而此时堆排序建初始堆得到最小码却可能需要比较
4072 次 (因为每个结点的调整都要与左
右两边的孩子相比。从第 1024 个结点往前调整,有
512 个结点可能调整
1 次,但要与左右
孩子都比较, 有 256 个结点可能调整
2 次,每次都要与左右孩子比较, 有 128 个结点可能调
整 3 次, 有 32 个结点调整 5 次, 根结点可能要调整
10 次,每次都会与左右孩子比
较,所以可能会比较
2036×2=4072 次) 。
而两种算法对求后面
4 个次小码的平均效率相同,都是
log 2n,所以,此题用锦标赛排序会
比堆排序快。
5. n 个顶点、 m 条边的全连通图,至少去掉几条边才能构成一棵树?
答:因为树的结构是一对多,即 n 个结点的树只有 n-1 条边与双亲结点相连。只要再多添一条边就会成为图结构。所以, m 条边的图要去掉 m-(n-1)=m-n+1 条边才能构成一棵树。这棵树也就是最小生成树。
6.设模式串为: liuwenliuyuliuyingliyu, 求该模式串的 next 函数。
答: Next[j]=0 1 1 1 1 1 1 2 3 4 1 1 2 3 4 1
7.一个二叉树按层次遍历的顺序存储结构如下,请画出该二叉树 (φ为空 ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B D φ C φ E φ φ F G φ φ H φ
答:画出二叉树如下:
8. 设数组 A[ 1..10, 1..8 ] 的基地址为 2000,每个元素占 2 个存储单元,若以列序为主序存储(按列存储) ,则元素 A[ 4, 5 ] 的存储地址是多少?
答: A[ 4,5 ] 的存储地址是 2086
2
得
分
二、综合题(每题
10 分,共 30 分)
1. 输入一序列( 58,18,29, 22,38, 81,19,14),现分别采用顺序查找和
二叉排序树查找,求等概率条件下二者的平均查找长度 ASL ;若改用哈希查找(哈希函数为: Hash(key)=key mod 11,哈希表的大小为 11,采用线性探测法进行冲突处理),求等概率条件下的平均查找长度 ASL,并对这三种查找方法进行比较。
答:采用二叉排序树查找时,二叉排序树为:
58
18
81
29
22 38
19
14
采用二叉排序树查找时, ASL=1/8[1 × 1+2× 2+3 ×1+4 × 2+5× 1+6 ×1]=27/8= 3.375
采用顺序查找时, ASL=1/2 ( 8+1 )=4.5
采用哈希查找时,查找表为:
0
1
2
3
4
5
6
7
8
9
10
22
58
81
38
14( 3) 18
29( 1) 19(1)
ASL=1/8 ( 5× 1+2 ×2+1× 4) =13/8= 1.625
2.已知用线性有序链表存储整数集合的元素。 阅读下面算法, 并回答下列问题:
1)写出执行 ABC (a, b)的返回值,其中 a 和 b 分别为指向存储集合 { 2, 4, 5, 7, 9, 12 } 和 { 2,4,5,7,9 } 的链表的头指针;
2)简述算法 ABC 的功能;
3)写出算法 ABC 的时间复杂度。
3
int ABC (LinkList ha,LinkList hb)
{ // LinkLi
您可能关注的文档
- 数据结构实施方案.doc
- 数据结构期中考试试题答案.doc
- 数据库试题答案1.doc
- 数据库迁移实施方案.doc
- 数据结构期末考试试卷含答案.doc
- 数据结构模拟题.doc
- 数据结构期末考试试卷答案.doc
- 数据结构期末考试试题及答案资料.doc
- 数据结构期末考试试题答案详解.doc
- 数据结构考试试题及答案3.doc
- 大学生职业规划大赛《新闻学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《应用统计学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《音乐学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《中医学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《信息管理与信息系统专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《汽车服务工程专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《水产养殖学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《市场营销专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《音乐表演专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《音乐学专业》生涯发展展示PPT.pptx
文档评论(0)