浙江工商大学数据结构期末复习题2

22.中序遍历二叉排序树的结点就可以得到排好序的结点序列（√ ）。

23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可（√ ）。

24.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素（√ ）。

25.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)（ √ ）。 26.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)（√ ）。 27.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值（ √）。 **28.磁盘上的顺序文件中插入新的记录时，必须复制整个文件（ × ）。 **29.在索引顺序文件中插入新的记录时，必须复制整个文件（× ）。

**30.索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上（× ）。 判断题参考答案

１.× ２.× ３.√ ４.√ ５.× ６.× ７.× ８.× ９.√ 10.√ 11.√ 12.× 13.× 14.√ 15.× 16.× 17.√ 18.× 19.√ 20.√ 21.√ 22.√ 23.√ 24.√ 25.√ 26.√ 27.√ 28.× 29.× 30.× 四、综合题

1. 线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?

(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?

(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么? 1. 解答:

(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。

(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。 (3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。

2. 用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?

2.解答: 不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。

3. 在单链表和双向表中，能否从当前结点出发访问到任一结点?

3. 解答: 在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4. 试述栈的基本性质?

4. 解答: 由栈的定义可知，这种结构的基本性质综述如下：

9

(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；

(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；

(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示； (4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即： Ｃn ＝Ｃn 2n /(n＋1)

其中，n为编号元素的个数，Cn 是可能的排列数目。

5. 何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。

5. 解答: 在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存储空间的大小）为m。当有元素要加入队列时，若rear＝m（初始时reat＝0），则发生队列的上溢现象，该元素不能加入队列。

这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能进队 列。造成这种现象的原因是由于队列的操作方式所致。 解决队列的上溢有以下几种方法：

(1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。 (2)当出现假溢出时，可采用以下几种方法：

①采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头 移动一个位置（当然要有空余的空间可移）；

②每当删去一个队头元素时，则依次序移队中的元素，始终使front指针指向队列 中的第一个位置；

③采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上 队尾在队首之前，但逻辑上队首依然在前，作插入和删除运算时仍按“先进先出”的原则。 6. 两个字符串相等的充要条件是什么?

6. 解答: 两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。

**7. 画出广义表(A(B(E，F(J))，C，D(G(K，L)，H，I)))对应的树型结构。

7. 解答: 根据广义表的结构可知，该树的根结点为A；而B、C、D为A的子树，B又有两棵子 树等等，该广义表对应的树型结构见下图。 A

B C D

E F G H I

J K L

**8. 对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。

8. 解答:其特点是只有最下面的二层结点可以小于２，其它结点的度数必须为２。 9. 试证明：已知一棵二叉树的前序序列和中序序列，则可唯一地确定一棵二叉树。 9. 证明

利用前序遍历的结果序列能够得到各子树的根，即从左到右检查前序遍历序列，当得 到根结点之后，利用根结点在中序遍历序列中的位置可以确定其左右子树，这样便可逐次确定整个二叉树。

10

假设BT为二叉树的根，P1 ，P2 ，?，Pn 为前序遍历序列，I1 ，I2 ，?，In 为中 序遍历序列。

由前序遍历序列可以得到BT＝P1 。

在中序遍历序列中查找等于P1 的结点，设该结点为Ii ，则有Ii ＝P1 。

根据二叉树中序遍历的原理，则该二叉树可被分成左右两棵子树：对于左子树，在中序遍历序列中有I1 ，I2 ，?，Ii－1 ，依此序列在前序遍历序列中可以得到其左子树为P2 ， P3 ，?，Pi ；

同理，对于右子树有 Ii＋1 ，Ii＋2 ，?，In Pi＋1 ，Pi＋2 ，?，Pn

对于这两棵子树而言，其左子树的根为P2 ，其右子树的根为Pi＋1 。 依此类推，用同样的方法就可以确定整个二叉树。 10.证明n个顶点的无向完全图的边数的n(n－1)/2。 10.证明 方法一： 用归纳法证明

当n＝1时，边数为0，结论成立。 当n＝2时，边数为1，结论成立。

当n＝1,2?,k时均成立，即当n＝k时，边数为k(k－1)/2。现证明当n＝k＋1时若仍然 成立，则结论正确。

由前面证得，对于有k个顶点时，其边数总和为 k(k－1)/2。 当再增加一个新顶点时，由于是无向完全图，故该顶点到原来各个顶点均有一条边， 这样就共有边数为

k(k－1)/2＋k＝k(k＋1)/2＝(k＋1)[(k＋1)－1]/2

可知当顶点数k＋1时，结论仍然成立，故具有n个顶点的无向完全图的这数为 n(n－1)/2 方法二：

在n个顶点的无向完全图中，每个顶点与其余各顶点均有一条边。第一个顶点到其余 各顶点的边数为n－1，第二个顶点到其余各顶点的边数为n－1，但它与第一个顶点之间的 边已在第一个顶点的边中，故第二个顶点到其它n－2个顶点的边为n－2,?，第n－1个到余下的第n个顶点为边数为1，所以总的边数为 (n－1)＋(n－2)＋(n－3)＋?＋2＋1＝n(n－1)/2 所以其结论成立。

11.证明一个有n个顶点，e条边的无向图G，必有 ∑dj ＝2e

其中dj 为顶点j的度。

11.证明

由度的定义可知，顶点j所联接的边数必为dj 条，另一方面，图G中的任一条边均关联 G中的两个顶点，即一条边均要分别计入两个不同的dj 和di 中，故∑dj 中的边数应为G中边数的两倍，即有

n ∑j ＝2e i-1

11

12.证明：若无向图G的顶点度数的最小值大于或等于2，则G有一条回路。 12.证明 方法一：

设G＝(V，E)，任取一顶点v1 ∈V，因V1 的度大于或等于2,在v1 的邻接顶点中任取一个不同于v1 的顶点作为v2 。因v2 的度大于或等于2,在v2 的邻接顶点中任取一个不同于v2 的顶 点作为v3 。若v1 、v2 、v3 不构成回路，则在再v3 的邻接顶点中任取一个不同于v3 的的顶点 作为v4 ，??。因为图中顶点的集合V是有限的，当取得某个顶点vi 后，vi＋1 一定为v1 ， v2 ，?，vi-1 之一，因而构成回路。命题得证。

方法二：

设图G有n个顶点，整个图G的度数之和为N，则有 N≥2n

我们知道，图中每条边涉及二个顶点，也就是每条边含有2个度，这样一来，该图G至少有n条边。由于一个n个顶点的树图只有n－1条边，多于n－1条边时则树图就不存在，图中会出现回路。由前面推得，该图至少有n条边，故会出现回路。

13.若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试问在下面三 种情况下，分别讨论两者在等概率时，平均查找长度是否相同?

(1)查找不成功，即表中没有关键字等于给定值k的记录； (2)查找成功，且表中只有一个关键字等于给定值k的记录；

(3)查找成功，且表中有若干个关键字等于给定值k的记录，一次查找要求找出所有记 录，此时的平均查找长度应考虑找到所有记录时所用的比较次数。

13.(1) 解答:不相同。对于有序的顺序表而言，当表中无此关键字时，只要在查找过程中发现顺序表中的某个关键字大于待查的关键字时，查找过程就可以结束（假定顺序表是由小到大排列的，对于由大到小排列的情况类似），没有必要查找到表中最后一个关键字才确定查找不成功。而对于非有序的顺序表，只有对表中的每一个关键字比较完之后，才能说明查找不成功。显然在等概率时两种顺序的平均查找长度是不相同的。有序顺序表的平均长度为(n＋1)/2，而无序顺序表的平均查找长度为n。但从数量级上两者是相同的,即O(n)。 (2) 解答:相同的。其分析类似于(1)。两者在等概率下的平均长度为(n＋1)/2，数量级上为 O(n)。

(3) 解答:不相同。其分析完全与(1)相同，其结论也完全相同。

14.假定有n个关键字，它们具有相同的Hash函数值，用线性探测方法把这n个关键字 存入到Hash地址空间中要做多少次探测?

14. 解答:由于线性探测的查找次数主要取决于装载因子α，即与Hash地址空间的占用情况 有关。假定初始时Hash地址空间为空，在此情况下连续装入n个具有相同的Hash函数值的 关键字所需的总探测次数为 1＋2＋?＋n＝n(n＋1)/2

15.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，问 (1)每块的理想长度是多少? (2)分成多少块最为理想? (3)平均查找长度是多少?

(4)若每块长度为20，平均查找长度是多少? 15.解答：

12