- 1、本文档共26页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
[期末]2005数据结构与算法试卷
试卷类型:期末
试卷年份:05
授课教师:廖明宏
有无答案:无答案
哈工大2005年春季学期
数据结构与算法试卷
)
一.填空题(每空1分,共10分)
1.假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K%7作为散列函
数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均
查找长度分别为_______和________。
2.假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排序的过程中,
第二趟归并后的结果为________________。
3.在堆排序的过程中,对任一分支结点进行调整运算的时间复杂度为________,
整个堆排序过程的时间复杂度为________。
4.有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的,某一列非
0元素的个数是该顶点的。
]
5.对于下面的带权图G3,若从顶点v0出发,则按照普里姆(Prim)算法生成
的最小生成树中,依次得到的各条边为______________。
6.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树,则带权路径长
度为
7.由三个结点构成的二叉树,共有种不同结构。
二.选择题(每题1分,共10分)
1.快速分类在的情况下不利于发挥其长处.
`
A.待分类的数据量太大B.待分类的数据相同值过多
C.待分类的数据已基本有序D.待分类的数据值差过大.
2.两路归并排序中,归并的趟数是。
A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)
注意行为规范
(
遵守考场纪律
第1页,共6页
3.对外部分类的K路平衡归并,采用败者树时,归并的效率与K。
A.有关B.无关C.不能确定D.都不对
4.对于一个索引顺序文件,索引表中的每个索引项对应主文件中的。
}
A.一条记录B.多条记录
C.所有记录D.三条以上记录
5..若线性表采用顺序存储结构,每个元素占用4个存储单元,第一个元素的存
储地址为100,则第12个元素的存储地址时。
`
6.若频繁地对线性表进行插入和删除操作,该线性表应该采用存储结构。
A.散列B.顺序C.链式D.索引
7.若长度为n的非空线性表采用顺序储存结构,删除表中第i个数据元素,需
要移动表中个数据元素。
+i+1
8.栈和队列的相同之处是。
【
A.元素的进出满足先进后出B.元素的进出满足后进先出
C.只允许在端点进行插入和删除操作D.无共同点
9.在一棵高度为k的二叉树中,最多含有()个结点。
A.2k-1B.2k-lC.2k-1D.k
10.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。
.
A.发生改变B.不发生改变C.不能确定D.以上都不对
三.判断题,正确的在括号内画∨,错误的在括号内画╳。
(每小题1分,共10分)
1.树的父链表示就是用数组表示树的存储结构。().
2.任何二元树都唯一对应一个森林,反之亦然。.()
:
3.有向图的邻接矩阵一定不是对称的。()
4.AOE网中,只有一个入度为0的顶点(起始点),只有一个出度为0的顶点
(结束点)。()
5.关键路径可能不只一条,但缩短某一关键路径一定能够缩短工期。()
6.顺序存储方式只能用于存储线性结构。()
7.用循环链表作为存储结构的队列就是循环队列。()
】
8.倒排文件的主要优点为便于节省空间()。
9.一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第
一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84()。
10.算法分析的目的是分析算法的易读性()。
四.简答题
1.简述如何用两个栈模拟一个队列的入队和出队操作.(6分)
《
2.对于图G5所示的树:(7分)
(1)写出先根遍历得到的结点序列;
(2)写出按层遍历得到的结点序列;
(3)画出转换后得到的二元树
图G5
五.算法设计
1.设二元树采用左右链存储,
您可能关注的文档
最近下载
- 数控加工工艺-全套PPT课件.pptx
- 幼儿园数学领域教育精要——关键经验与活动指导试题.doc
- 护理预见性护理课件.pptx
- 理光RICOH使用手册GRⅡ说明书.pdf
- 义务教育版(2024)信息科技六年级全一册 第4课 输入输出与计算 教案.docx VIP
- 深信服安全评估系统TSS用户手册_v1.7.3.pdf
- BOSE博士 SoundTouch 300 Soundbar 用户指南支持 简体中文.pdf
- 预应力锚杆与锚索支护技术.pptx VIP
- 灾难现场挤压伤挤压综合征救治技术规范.pdf VIP
- 统编版(五四制)道德与法治三年级上册12《家庭的记忆+传统节日中的“家”》(教学设计).docx
文档评论(0)