哈工大2009年春季试卷-数据结构与算法-带答案.pdf

《哈工大2009年春季试卷-数据结构与算法-带答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈工大2009年春季学期班号学号姓名数据结构与算法试卷题号一二三四总分分值2010103070得分一、填空题（每空2分，共20分）1.在情况下，等长编码是最优前缀码。22．设有两个算法在同一机器上运行，其执行时间分别为100n和n2，要使前者快于后者，n至少为。注意行为3．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的规范是_。遵守4．设二叉树结点的先根序列为ABDECFGH，中根序列为考场DEBAFCHG,则二叉树中叶结点是_________.纪律5.用下标从0开始的N个元素的数组实现循环队

2、列时,为实现下标变量m加1后在数组有效下标范围内循环,可采用的表达式是m=。6.由带权为3，9，4，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为。7.对n个记录的表进行选择排序，在最坏情况下所需要进行的关键字的比较次数为。8.任意一个有n个结点的二叉树，已知它有m个叶结点，则度数为2的结点有。9.n个顶点的连通图用邻接矩阵表示时，该矩阵至少有个非零元素主管10.举出两种磁带文件的分类方法：。领导审核签字二、选择题（每题1分，共10分）1．设一组初始记录关键字序列为(45，80，55，40，42，

3、85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，55，80，45，85(D)42，40，45，85，55，802．数据的最小单位是（）。(A)数据项(B)数据类型(C)数据元素(D)数据变量3．关键路径是AOE网中()。A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径D.从始点到终点的边数最少的路径4．下列说法正确的是（）。A．最小生成树也是哈夫曼树B

4、．最小生成树是唯一的Ｃ．对于n个顶点的连通无向图，Prim算法的时间复杂性为2O(n)D．Kruskal算法比Prim算法更适合边稠密的图5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。(A)6(B)4(C)3(D)26.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。(A)100(B)40(C)55(D)807.若数据元素序列11，12

5、，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序结果，则该排序算法只能是()。A.插入排序B.冒泡排序C.选择排序D.二路归并排序8.设哈希表长m＝14，哈希函数H（key）＝key％11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其余地址为空。如果用二次探测再散列处理冲突，关键字为49的结点的地址是（）A．8B.3C.5D.99.有组记录的输入顺序为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为(

6、)A.79，46，56，38，40，80B.38，40，56，79，46，84C.84，79，56，46，40，38D.84，56，79，40，46，3810.下列叙述中，不符合m阶B树定义要求的是（）A.根结点最多有m棵子树B.所有叶结点都在同一层上C．各结点内的关键字有序D.叶结点之间通过指针链接三、简答题（10分）.带权图（权值非负，表示边连接的两个顶点的距离）的最短路径问题是找出初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间的存在路径，现有一种解决该问题的方法：1）设最短路径初

7、始时仅包含初始顶点，令当前顶点u为初始顶点；2）选择离u最近的且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v;3)重复步骤2），直到u是目标顶点为止。请问上述方法能否求得最短路径？若可行请证明之；否则，请举例说明。四、算法设计：栈、队列的存储结构、基本操作可以直接引用（共30分）1.设二叉树采用左右链方式存储，设计一个判断二叉树是否是二叉排序树的算法。（10分）2.设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值

8、均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写出符合上述要求的LocateNode运算的算法。(10分)3.给定一个无向连通图，写一个算法找出半径最小的生成树（搜索起点作为生成树的根，树的半径定义为从根到叶子的最大距离）。（10分）参考答案：一、填空题1.等概率2.153.冒泡