哈工大2009年春季试卷a

《哈工大2009年春季试卷a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、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，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。(A)40，42，45，55，80，83(B)42，40，45，80，

3、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．最小生成树是唯一的Ｃ．对于n个顶点的连通无向图，Prim算法的时间复杂性为O(n2)D．Kruskal算法比Prim算法更适合边稠密的图5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6

4、依次通过栈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，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， a

5、ddr(61)=6， addr(84)=7 其余地址为空。 如果用二次探测再散列处理冲突，关键字为49的结点的地址是（）A．8B.3C.5D.99. 有组记录的输入顺序为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为()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分）.带权图（权值非

6、负，表示边连接的两个顶点的距离）的最短路径问题是找出初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间的存在路径，现有一种解决该问题的方法：1）设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；2）选择离u最近的且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v;3)重复步骤2），直到u是目标顶点为止。请问上述方法能否求得最短路径？若可行请证明之；否则，请举例说明。四、算法设计：栈、队列的存储结构、基本操作可以直接引用（共30分）1.设二叉树采用左右链方式存储，设计一个判断二叉树是否是二叉排序树的算法。（10分）2.设有一个双链表，每

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