资源描述：
《哈工大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分)..
