2014数据结构A卷

1

---○---○---

---○---○

………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 中南大学考试试卷 2014~2014学年 二 学期 数据结构 课程 时间100分钟

一、 单选题：（每小题2分，共4分） 1、二分查找的存储结构必须是( )。 A

．顺序存储 B ．链式存储 C.散列存储 D ．A,B 都可以 2、20个结点的连通图至少有 边。 A ．20 B ．19 C ．190 D ．380 二、填空题（每空2分，共 6分） 1. 在二叉树中，指针P 所指结点为叶子结点的条件为 。 2. 二叉树的中序序列和后序序列相同的条件为 。 3.等概率的二分查找的平均查找长度为 三、应用题（共65分） 1. 将整数序列{30,29,40,35,37,34,45}中的数依次插入到一棵空的平衡二叉树 中，试构造相应的平衡二叉树，请写出构造的过程。并对最后的平衡二叉树进行先序序线索化（用虚线表示线索）

2

---○---○---

---○---○

………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 2. 一个有四个顶点1,2,3,4的有向图的邻接矩阵用二维数组表示，a[0][0]=a[1][1]=a[2][2]=a[3][3]=0,a[0][2]=a[1][0]=a[3][0]=a[3][1]=MAX ,a[0][1]=7,a[0][3]=9,a[1][2]=6;a[1][3]=a[2][3]=4,a[2][0]=a[2][1]=5,a[3][2]=3.请用弗洛伊德算法求每对顶点之间的最短路径长度和最短路径顶点序列。要求把存放最短路径长度的矩阵和最短路径顶点序列的矩阵的变化过程列出。

3

---○---○---

---○---○

………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 3、给定一组数据{8,6,2,5,4,1,7,10,2}，以它们为权值构造一棵哈夫曼树，并求出树带权路径值。要求图示哈夫曼树的构造过程。 4、有向图的二元组为d={1,2,3,4,5,6}，s={（1,2），（1,3），（2,4），（2,5），（3,4），（3,5），（6,3），（6,4）}，请写出拓扑排序的序列的其中四种

4

---○---○---

---○---○---

………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 5. 请对下图以A 为起点，写出四种深度优先遍历的序列和四种广度优先遍历序列。 6、对给定文件（409,308,205,500,600,202,304,90,10,80,400，50,60,407）1）希尔排序的增量序列为（5,3,1）请写出排序的过程。请问希尔排序是稳定的吗？ 2）以第一个数409为基准，写出快速排序第一次划分的过程。 C B D E F A

5

---○---○---

---○---○---

………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 五、算法设计题：（共25分） 1、 用单链表LA 表示一个数列A （a1,a2,a3

…an ）， 设计一算法将单链表中每个元素的值都加其后继结点的值，最后一个结点的值不变。

2、假设二叉树采用二叉链表存储结构，结点的数据域为整数，试设计一算法，将二叉树的所有结点的数据域乘以2倍。

6