一、填空题：（每小题2分，共10分）

1. 设有数据结构（D，R），其中 D 是数据元素的有限集，R 是          的有限集。

2. 深度为 k 的二叉树其结点数至多有        个。

3. 栈是一种特殊的线性表，它允许在表的一端进行                      操作。

4. 通常象交通、道路问题的数学模型是一种称为             的数据结构。

5. 哈希表是一种查找表，可以根据哈希函数直接获得                      。

二、单项选择题：（每小题2分，共10分）

对于下列各题，在备选答案中选出一个正确的，并将其编号填在“      ”位置上。

1.   若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用      存储方式最节省运算时间。

A. 单链表     B. 双链表     C. 单循环链表     D. 顺序表

2.   下列排序算法中，      算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

A. 直选择排序     B. 冒泡排序     C. 归并排序    D. 堆排序

3.   队列的操作原则是      。

A. 先进后出     B. 先进先出     C. 只能进行插入    D. 只能进行删除

4.   在具有 n 个结点的二叉链表中，非空的链域个数为      。

A. n-1    B. n     C. n+1     D. 不确定

5.   对具有 n 个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为      。

A. O(log2n)     B. O(n)     C. O(nlog2n)    D. O(n2)

三、判断题：（每小题2分，共10分）

判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。

1. 在栈为空的情况下不能作出栈处理，否则，将产生下溢出。（   ）

2. 如果有向图 G=(V, E) 的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。（   ）

3. 在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。（   ）

4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（   ）

5. 在索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。（   ）

四、解答下列各题：（每题10分，共40分）

1. 已知线性表 L 采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。

2. 已知一棵二叉树的先序、中序和后序序列如下所示，请填写各序列中空格处的结点，并画出该二叉树的二叉链表存储结构示意图。

先序序列是：_ B _ F _ I C E H _ G； 中序序列是：D _ K F I A _ E J C _ ；

后序序列是：_ K _ F B H J _ G _ A

3. 已知数据表为（48，70，33，65，24，56，12，92，86，22），a) 写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果；b) 写出按基数排序思想对最低位进行一次分配和收集的结果。

4. 

对图1所示的带权无向图，写出它的邻接矩阵和深度优先搜索序列，并按克鲁斯卡算法求其最小生成树（写出求解的详细过程示意图）。

图1    带权无向图

五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）

1. 已知队列 Q 以循环队列存储。写出 Q 的存储结构类型描述，并试编写算法实现将元素 x 插入队列 Q 的入队操作 EnQueue(Q,x)和从队列 Q 中获取队首元素的函数 GetTop(Q)。

2. 假设线性表 L=(a1,a2,……,an) 用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,……, a2,a1)。

3. 设非空二叉树 T 采用中序线索二叉链表表示，写出 T 的存储结构类型描述。试编写算法 InOrderTraverse(T) 实现对二叉树 T 的中序遍历。下载本文