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

定整个二叉树。

假设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

11

i-1

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，平均查找长度是多少?

12

15.解答：

(1)在给定n的前提下，理想的块长d为√n＝√2000≈45

(2)因查找方法为等分区间顺序查找，长度为n的表被分成b＝[n/d]块，d为块长，故有

b＝[n/d]＝[2000/45]＝45 (3)平均查找长度为

ASL＝b＋d/2＋1＝(45＋45)/2＋1＝46

(4)因每块的长度为20，所以表被分成b块，其平均查找ASL长度为 b＝[n/d]＝[2000/20]＝100

ASL＝(b＋d)/2＋1＝(100＋20)/2＋1＝61

16.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动， 从而认为该排序算法是不稳定的，这种说法对吗?为什么? 16. 解答:这种说法不对。因为排序的不稳定性是指排序前两个排序码相同的元素的相对次 序经过排序后发生了变化，而题中未涉及到元素的相对次序（特别是相同排序码的元素）的改变，只有移动方向，所以此种说法不对。

17.设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?

快速排序，堆排序，归并排序，基数排序的Shell排序。

17. 解答:上面所列的几种排序方法的速度都很块，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。而堆排序则每次输入一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。

**18.证明对一个长度为n的任意文件进行排序，至少需要作nlog2 n比较。

18.证明

在排序过程中，每次时行元素的比较产生两种 …… 此处隐藏：3742字，全部文档内容请下载后查看。喜欢就下载吧 ……