下载文档原格式
中国海洋大学2012-2013学年期末考试试题及参考答案
2012-2013学年第 2 学期试题名称：数据结构
专业年级：计算机学号姓名授课教师名分数
一、解答下列各题（40 分，每小题 8 分）
1.画出广义表L=(a,(( ),b),(((e)))) 的存储结构图，并利用取表头和取表尾的操作分离出原子e。
2．对下图所示有向图，利用Dijkstra算法求出从顶点A到其它各顶点的最短路径及距离。
B 10 E
23015
A 4 D 10
154
C 10 F
3. 已知一棵3阶B-树如图一所示。
图一
①画出插入（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．若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）
