[期末] 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 个元素的存储地址时 。 A.112 B.144 C.148 D.412 6．若频繁地对线性表进行插入和删除操作，该线性表应该采用 存储结构。 A.散列 B.顺序 C.链式 D.索引 7．若长度为n 的非空线性表采用顺序储存结构，删除表中第i 个数据元素，需要移动表中 个数据元素。 A.n+i B.n-i C.n-i+1 D.n-i-1 8．栈和队列的相同之处是 。 A.元素的进出满足先进后出 B.元素的进出满足后进先出 C.只允许在...
