中国海洋大学2012-2013学年期末考试试题及参考答案
2012-2013学年第 2 学期 试题名称 ： 数据结构
专业年级： 计算机 学号 姓名 授课教师名 分数
一、解答下列各题（40 分，每小题 8 分）
1. 画出广义表L=(a,(( ),b),(((e)))) 的存储结构图，并利用取表头和取表尾的操作分离出原子e。
2．对下图所示有向图，利用Dijkstra算法求出从顶点A到其它各顶点的最短路径及距离。
B 10 E 2 30 15 A 4 D 10
15 4 C 10 F
3. 已知一棵3阶B-树如图一所示。
50 77 20 40 10 19 22 43 53 55 70 60 75 80 78 85
图一
①画出插入（18）后的3阶B-树；
②画出在插入（18）后的3阶B-树中删除（78）后的3阶B-树。
4. 给出一组关键字（12，2，16，30，8，28，4，10，20，6，18），按从小到大顺序，写出对其进行希尔排序（排序的间隔增量为5、2、1）的排序过程。
5. 从空树开始，按下列插入顺序：DEC、FEB、NOV、OCT、JUL、SEP、AUG、APR、MAR、MAY、JUN、JAN，给出最终所得到的二叉平衡树。
二、判断题：正确的打√，错误的打×（每题1分，共15分）
1．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（ ）
2．在单链表中，要访问某个节点，只要知道该结点的指针即可：因此，单链表是一种随机存取结构。（ ）
3．顺序存储结构属于静态结构，链式结构属于动态结构。（ ） 4．广义表是线性表的推广，是一类线性数据结构。（ ）
5．线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。（ ）
6．广义表中原子个数即为广义表的长度。（ ）
7．用树的前序遍历和中序遍历可以导出树的后序遍历。（ ）
8．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（ ） 9．二叉树中不存在度大于2的结点，当某个结点只有一棵子树时，无所谓左、右子树之分。（ ）
10．若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
11．邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。（ ） 12．若散列表的负载因子α<1，则可避免碰撞的产生。（ ）
13．AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于1。（ ） 14．内排序的快速排序方法，在任何情况下均可得到最快的排序效果。（ ） 15．归并排序要求的辅助空间最多。（ ）
三、（15分）已知一棵度为M的树中有n1个度为1的结点，n2个度为的2结点，…nm
m个度为m的结点，证明其叶结点个数为 1+?(i?1)ni 。
i?1
四、（15分）设有一大批需实时处理的数据元素集合S，实时处理开始后，每隔一
极短的时间间隔便收到一个新的数据元素加入S。要求在每次接收一个新元素之前，找出S中现有的最小元素并将其输出（从S中删除）。试选择或构造一种适当的数据结构并设计一个算法，尽可能高效的完成上述任务（要求用文字辅助说明算法的基本设计思想）。
五、（15分）已知二叉树存于二叉链表中，编写算法求树中任一给定结点P的双亲
结点。
中国海洋大学2012-2013学年期末考试试题及参考答案
