山东省 专升本 数据结构 计算机
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 的中序遍历。