数据结构 2014 – 2015 期末试卷 （1.不保证题目完全没有问题 2.部分图片来自网络） 一、选择(2’×15=30’) ) ) B.O(1) C.O(n) D.O(n2) B.仅修改队尾指针 D.队头、队尾指针都可能要修改 1.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时 间复杂度为( A.O(0) 2.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾 结点，则在进行删除操作时( A.仅修改队头指针 C.队头、队尾指针都不修改 3.设栈 S 和队列 Q 的初始状态均为空，元素 a,b,c,d,e,f,g 依次进入栈 S，若每个元素出栈 后立即进入队列 Q，且 7 个元素出队的顺序是 b,d,c,f,e,a,g，则栈 S 的容量至少是( ) A.1 4.对 n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( A.该树一定是一棵完全二叉树 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 5.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是( A.CABDEFG D.ADCFEG 6.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是( D ) B.树中一定没有度为 1 的结点 B.ABCDEFG C.DACEFBG D.4 B.2 C.3 ) ) ) 7.下面关于二分查找的叙述正确的是( A.表必须有序，表可以顺序方式存储，也可以链表方式存储 B.表必须有序，且表中数据必须是整型，实型或字符型 C.表必须有序，而且只能从小到大排列 D.表必须有序，且表只能以顺序方式存储 8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受 数据初始特性影响的是( A.直接插入排序 C.直接选择排序 B.快速排序 D.堆排序 ) 

) 9.下列关于无向连通图特性的叙述中，正确的是( I.所有顶点的度之和为偶数 II.边数大于顶点个数减 1 III.至少有一个顶点的度为 1 A.只有 I 10.在下列所示的平衡二叉树中插入关键字 48 后，得到一棵新平衡二叉树，在新平衡二 叉树中，关键字 37 所在结点的左、右子结点保存的关键字分别是( A.13,48 B.只有 II D.I 和 III D.24,90 B.24,48 C.24,53 C.I 和 II ) ) )是稳定的 C.选择排序 B.插入排序 D.二路归并排序 B.快速排序，堆排序 D.归并排序，冒泡排序 11.若数据元素序列 11,12,13,7,8,9,23,4,5 是采用下列排序方法之一得到的第二趟排序后 的结果，则该排序算法只能是( A.冒泡排序 12.下列排序算法中，其中( A.堆排序，冒泡排序 C.直接选择排序，归并排序 13.下列叙述中，不符合 m 阶 B-树定义要求的是( A.根节点最多有 m 棵子树 C.各结点内关键字均升序或降序排列 14.已知关键序列 5,8,12,19,28,20,15,22 是小根堆（最小堆），插入关键字 3，调整后得到 的小根堆是( A.3,5,12,8,28,20,15,22,19 C.3,8,12,5,20,15,22,28,19 15.下列 AOE 网表示一项包含 8 个活动的工程，通过同时加快若干活动的进度可以缩短 整个工程的工期，下列选项中，加快其进度就可以缩短工程工期的是( A.c 和 e B.所有叶结点都在同一层上 D.叶结点之间通过指针链接 B.3,5,12,19,20,15,22,8,28 D.3,12,5,8,28,20,15,22,19 ) D.f 和 h B.d 和 e C.f 和 d ) ) 

二、简答(60’) 1.(10’)用序列(46,88,45,39,70,58,101,10,66,34)建立一棵二叉搜索树，画出该树，并求在 等概率情况下查找成功和查找不成功的平均查找长度，画出依次删除 46,58 后的二叉搜 索树 2.(8’)设字符 a,b,c,d,e,f 的使用频度分别为 25,20,6,14,28,7，求 a,b,c,d,e,f 的哈夫曼编码并 给出相应的哈夫曼树，计算带权路径长度 3.(10’)设 G=(V,E)的邻接表存储如下所示，试画出该图，给出深度优先和广度优先搜索序 列，并画出深度优先和广度优先生成树 4.(6’)已知一个森林的先序序列和后序序列如下，请构造出该森林 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK 5.(6’)图的邻接矩阵如下，试给出弗洛伊德算法求各点间最短距离的矩阵序列 A1,A2,A3,A4 A = 0 2 ∞ ∞ ∞ 0 1 6 5 ∞ 0 4 3 ∞ ∞ 0 6.(10’)一组记录的关键码为{45,81,67,36,40,85,52,43}，按照递增序进行排序 ⑴.分别给出冒泡排序、快速排序（以第一个元素为轴）、二路归并排序的第一趟排序结 果 ⑵.画出初始的最大堆（给出调整过程） 7.(10’)选择哈希函数 H(Key)=Key%13，用开放定址法处理冲突 ，探查的地址序列为 H(Key),H(Key)+1,H(Key)+3,H(Key)+5, … … 试 构 造 给 定 关 键 字 序 列 {22,31,40,03,47,69,14, 27,15,01,61,55,78}的哈希表；查找 27,15 各要比较多少呢？计算在等概率的条件下查找 成功时的平均查找长度 三、算法设计(10’) 简要描述 Dijkstra 算法的思想； 设带权有向图 G 的邻接矩阵为 A，给出利用 Dijkstra 算法，计算 G 中一点到其余各顶点 的最短路径及最短路径长度的程序代码