资源描述:
《哈工大2005年《数据结构与算法》期末试题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、[期末]数据结构与算法试卷试卷类型:期末试卷年份:05授课教师:廖明宏有无答案:无答案哈工大2005年春季学期数据结构与算法试卷一.填空题(每空1分,共10分)1.假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K%7作为散列函数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为_______和________。2.假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排序的过程中,第二趟归并后的结果为________________。3.在堆排序的
2、过程中,对任一分支结点进行调整运算的时间复杂度为________,整个堆排序过程的时间复杂度为________。4.有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的,某一列非0元素的个数是该顶点的。5.对于下面的带权图G3,若从顶点v0出发,则按照普里姆(Prim)算法生成的最小生成树中,依次得到的各条边为______________。6.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树,则带权路径长度为7.由三个结点构成的二叉树,共有种不同结构。二.选择题(每题1分,共10分)1.快速分类在的情况下不利于发
3、挥其长处.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个存储单元,第一个元素
4、的存储地址为100,则第12个元素的存储地址时。A.112B.144C.148D.4126.若频繁地对线性表进行插入和删除操作,该线性表应该采用存储结构。A.散列B.顺序C.链式D.索引7.若长度为n的非空线性表采用顺序储存结构,删除表中第i个数据元素,需要移动表中个数据元素。A.n+iB.n-iC.n-i+1D.n-i-18.栈和队列的相同之处是。A.元素的进出满足先进后出B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作D.无共同点9.在一棵高度为k的二叉树中,最多含有()个结点。A.2k-1B.2k-lC.2
5、k-1D.k10.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。A.发生改变B.不发生改变C.不能确定D.以上都不对三.判断题,正确的在括号内画∨,错误的在括号内画╳。(每小题1分,共10分)1.树的父链表示就是用数组表示树的存储结构。().2.任何二元树都唯一对应一个森林,反之亦然。.()3.有向图的邻接矩阵一定不是对称的。()4.AOE网中,只有一个入度为0的顶点(起始点),只有一个出度为0的顶点(结束点)。()5.关键路径可能不只一条,但缩短某一关键路径一定能够缩短工期。()6.顺序存储方式只能用于
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五.算法
7、设计1.设二元树采用左右链存储,写出后序遍历该二元树的非递归算法。(12分)2.设图中各边上的权值均相等,试以邻接表为存储结构,写出求源点Vi到Vj的最短路径算法。(15分)..