Question

数据结构题目

1．线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？

2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

3．在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?
单链表不能访问到它的前趋节点，双向链表可以访问到任何节点
4．如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2 和1 3 5 4 2 6;请说明为什么不能或如何才能得到。

5．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

6. 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。

7．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）

8. 一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。

9. 已知一个无向图如下图所示，用普里姆算法生成最小树（假设以①为起点，试画出构造过程）

10．写出用二分排序法将序列：34，3，12，20，11，6，19从小到大排列的过程。

Answer 1

1（1）：链表，理由是链表能够高效的执行插入删除操作，适用于元素变化较多的情形

1（2）：顺序表，不方便插入删除，但能高效的读取线性表中的元素

2： 链表可以克服弱点一，只需要改相邻指针，不需要移动元素；可以克服弱点二，控件动态分配；可以克服弱点三，链表方便扩充

3： 答过了

4： 4 3 5 6 1 2 不行，1234入栈43出栈5入栈5出栈6入栈6出栈12反序    

    1 3 5 4 2 6 可以，1入栈1出栈23入栈3出栈45入栈54出栈2出栈6入栈6出栈

5： 答过了

6： 见图

7： 见图

8： 这棵树除叶以外的所有节点都只有右节点，像一捺的感觉，退化成线性表

9： 没图

10：就是插入排序，只是插入的过程在查找插入位置的时候用二分法。