05年春数据结构与算法 试卷+答案.doc

文档介绍：哈工大2005年春季学期
数据结构与算法试卷答案
(每空1分,共10分)
(38,25,74,52,48)进行散列存储,采用H(K)=K %7作为散列函数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为_______和________。
(46,79,56,38,40,80),对其进行归并排序的过程中,第二趟归并后的结果为________________。
,对任一分支结点进行调整运算的时间复杂度为________,整个堆排序过程的时间复杂度为________。
,某一列非0元素的个数是该顶点的。
,若从顶点v0出发,则按照普里姆(Prim)算法生成的最小生成树中,依次得到的各条边为______________。
,9,6,2,5的5个叶子结点构成一棵哈夫曼树,则带权路径长度为
,共有种不同结构。
(每题1分,共10分)
.
A. 待分类的数据量太大 B. 待分类的数据相同值过多
C. 待分类的数据已基本有序 D. 待分类的数据值差过大.
,归并的趟数是。
A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2)
注意行为规范
遵守考场纪律
第1页,共6页
,采用败者树时,归并的效率与K 。
A. 有关 D. 都不对
,索引表中的每个索引项对应主文件中的。
A. 一条记录
C. 所有记录
5..若线性表采用顺序存储结构,每个元素占用4个存储单元,第一个元素的存储地址为100,则第12个元素的存储地址时。

,该线性表应该采用存储结构。

,删除表中第i个数据元素,需要移动表中个数据元素。
+i -i -i+1 -i-1
。


,最多含有( )个结点。
-1 -l -1
、中序和后序遍历序列中的相对次序( )。

,正确的在括号内画∨,错误的在括号内画╳。
(每小题1分,共10分)
。( ).
,反之亦然。.( )
。( )
,只有一个入度为0的顶点(起始点),只有一个出度为0的顶点(结束点)。( )
,但缩