B F
C D G
E H I
J
8、设a是含有n个元素的整数数组,写出一个求n个元素的平均值的递归定义。 解答：#include
double aver(float *a,int n,int t) {
if (t!=n) return (a[t]/n+aver(a,n,t+1)); else return 0; }
int main(void) {
float a[]={1,5,9,13,17}; printf(\ return 0; }
9、设a是含有n个元素的整数数组:
(1) 写出求该数组中最大元素的递归定义。 (2) 写出求该数组中最小元素的递归定义。 答：(1)int A :: Max (int n) //递归求最大值 {
if (n==1) return E[0]; int t=Max ( n-1 );
if (E[n-1]>t) return E[n-1]; else return t; }
(2) int A :: Min (int n) //递归求最小值 {
if (n==1) return E[0]; int t=Min ( n-1 );
if (E[n-1]>t) return E[n-1]; else return t; }
10、设a是含有n个元素的整数数组:
- 6 -
(1) 写出求n个整数之和的递归定义。 (2) 写出求n个整数之积的递归定义。 解答：（1）int A :: Sum (int n) //递归求数组之和 {
if (n==1) return E[0];
else return E[n-1]+Sum (n-1); }
（2） int A :: Multi (int n) //递归求整数之积 {
if (n==1) return E[0];
else return E[n-1]*Multi (n-1); }
11、二维数组A[4][4](即A[0..3][0..3])的元素起始地址是loc(A[0][0])=1000,元素的长度为2,则LOC(A[2][2])的地址为多少?
答：LOC(A[2][2])= loc(A[0][0])+（2*4+2)*2=1000+20=1020
数据结构复习题：图
问答题
1、无向图G如下图： B E / \\ / \\ A D G \\ / \\ / C F 试给出
(1)该图的邻接矩阵。 (2)该图的邻接表。
(3)从A出发的“深度优先”遍历序列。 (4)从A出发的“广度优先”遍历序列。 解答：(1) 图G的邻接矩阵 ┏０ １ １ ０ ０ ０ ０┓ ┃１ ０ ０ １ ０ ０ ０┃ ┃１ ０ ０ １ ０ ０ ０┃ A＝┃０ １ １ ０ １ １ ０┃ ┃０ ０ ０ １ ０ ０ １┃ ┃０ ０ ０ １ ０ ０ １┃ ┗０ ０ ０ ０ １ １ ０┛ (2)邻接表如见：
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ １│Ａ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ２│Ｂ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│
- 7 -
├─┼─┤ ├─┼─┤ ├─┼─┤ ３│Ｃ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│
├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ ┌─┬─┐ ４│Ｄ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│ ┼→┤Ｅ│＾├→─┤Ｆ│＾│
(3)从顶点A出发按深度优先遍历序列(不是唯一的)为A、B、D、C、E、G、F (4)从顶点A出发按广度优先遍历序列(不是唯一的)为A、B、C、D、E、F、G
2、用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否有关?
答：设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。 3、对于稠密图和稀疏图,就存储空间而言,采用邻接矩阵和邻接表哪个更好些? 答：稠密图采用邻接矩阵好，稀疏图采用邻接表好 4、请回答下列关于图的一些问题:
(1) 有n个顶点的有向强连通图最多有多少条边?这样的图应该是什么形状? (2) 有n个顶点的有向强连通图最少有多少条边?这样的图应该是什么形状?
(3) 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵? 答：（1）最多有n(n-1)条边 （2）最少有 n条边
（3）106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律） 5、对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何判别下列有关问题? (1) 图中有多少条边?
(2) 任意两个顶点i和j是否有边相连? (3) 任意一个顶点的度是多少? 答：无向图采用邻接表时，⑴ 边表中的结点个数之和除以2。⑵ 第i个边表中是否含有结点j。⑶ 该顶点所对应的边表中所含结点个数。
6、己知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树. 答：二叉树及线索二叉树（略）。 先序序列为：abcdefghij
7、下列整数序列由选序遍历一棵二叉排序树得到:50,40,30,45,65,55,70,80.试构造一棵这样的二叉排序树.
答：
数据结构复习题：内部排序
- 8 -
问答题
1、设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?
快速排序，堆排序，归并排序，基数排序的Shell排序。
1、上面所列的几种排序方法的速度都很块，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。而堆排序则每次输入一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的
2、判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。 (1) (100，85，98，77，80，60，82，40，20，10，66)。 (2) (100，98，85，82，80，77，66，60，40，20，10)。 (3) (100，85，40，77，80，60，66，98，82，10，20)。 (4) (10，20，40，60，66，77，80，82，85，98，100)。 解答：根据堆的定义可知堆中元素满足下面中的某一个式子的关系， ┌≤k2i ┌≥k2i ① ki 或 ② ki └≤k2i＋1 └≥k2i＋1 因此(1)、(2)和(4)序列是堆。(3)不是堆。
(3) 调整为100,98,66,85,80,60,40,77,82,10,20后成为堆。
3、什么是内部排序？什么是排序方法的稳定性和不稳定性？
解答：假设给定含有n个记录(R1 ，R2 ，…，Rn ）的文件，其相应的关键字为(K1 ，K2 ，…， Kn )，则排序是确定一个排列P(1)，P(2)，…，P(n)，使得KP(1) ≤KP(2) ，…，KP(n) ，
从而得到有序文件(RP(1) ，RP(2) ，…，RP(n) )。整个排序过程都在内存进行的排序称为 内部排序。 假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排 序法排序后，若这些相同关键字的记录的相对次序仍然保持不变，则这种排序方法是稳定 的，否则称这种排序方法是不稳定的。 4、输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38},建立一棵二叉排序树,然后删除结点72,分别画出该二叉树及删除结点72后的二叉树。
5、设数据集合d={1,12,5,8,3,10,7,13,9},试完成下列各题: (1) 依次取d中各数据,构造一棵二叉排序树bt; (2) 如何依据此二叉树bt得到d的一个有序序列; (3) 画出在二叉树bt中删除\后的树结构。 解答：（1）（3）图略。
（2）根据二叉排序树中左子树，根结点，右子树的排列顺序，有序序列：1，3，5，7，8，9，10，12，13 6、对给定的数列R={7,16,4,8,20,9,6,18,5},构告一棵二叉排序树,并且 (1) 给出按中序遍历得到的数列R1 (2) 给出按后序遍历得到的数列R2
解答：图略。中序遍历序列R1：5,6,4,7,8,9,16,18,20 后序遍历序列R2：5,6,4,9,8,18,20,16,7
7、设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数:H(key)=key
采用开放地址法的线性探测再散列方法解决冲突,试在0～18的散列地址空间中对该关键字序列构造散列表。 解答： H(19)=19 MOD 13=6 H(01)=01 MOD 13=1 H(23)=23 MOD 13=10
- 9 -
H(14)=14 MOD 13=1(冲突) H(14)=(1+1) MOD 19=2 H(55)=55 MOD 13=3 H(20)=20 MOD 13=7
H(84)=84 MOD 13=6 (冲突)
H(84)=(6+1) MOD 19=7 (仍冲突) H(84)=(6+2) MOD 19=8 H(27)=27 MOD 13=1 (冲突) H(27)=(1+1) MOD 19=2 (冲突) H(27)=(1+2) MOD 19=3 (仍冲突) H(27)=(1+3) MOD 19=4 H(68)=68 MOD 13=3 (冲突)
H(68)=(3+1) MOD 19=4 (仍冲突) H(68)=(3+2) MOD 19=5 H(11)=11 MOD 13=11
H(10)=10 MOD 13=10 (冲突)
H(10)=(10+1) MOD 19=11 (仍冲突) H(10)=(10+2) MOD 19=12 H(77)=77 MOD 13=12 (冲突) H(77)=(12+1) MOD 19=13
因此，各关键字相应的地址分配如下： address(01)=1 address(14)=2 address(55)=3 addre
8、线性表的关键字集合{87,25,310,08,27,132,68,95,187,123,70,63,47},共有13个元素,己知散列函数为:H(key)=k
采用拉链法处理冲突。设计出这种链表结构,并计算该表的成功查找的平均查找长度。
9、己知序列{17,18,60,40,7,32,73,65,85},请给出采用冒泡排序法对该序列作为升序排序时的每一趟的结果。 解答：初始：17，18，60，40，7，32，73，65，85 第1趟：17，18，40，7，32，60，65，73，85 第2趟：17，18，7，32，40，60，65，73，85 第3趟：17，7，18，32，40，60，65，73，85 第4趟：7，17，18，32，40，60，65，73，85 第5趟：7，17，18，32，40，60，65，73，85 第5趟无元素交换，则排序结束。
10、己知序列 {503，87，512，61，908，170，897，275，653，462}，请给出采用快速排序法对该序列作升序排序时的每一趟结果。
解答：原始序列：503，87，512，61，908，170，897，275，653，462 第1趟： [462，87，275，61，170]503[897，908，653，512] 第2趟： [170，87，275，61] 462，503[897，908，653，512] 第3趟： [87，61]170[275] 462，503[897，908，653，512] 第4趟： 61 [87]170[275] 462，503[897，908，653，512]
第5趟： 61 ，87，170，[275] 462，503[897，908，653，512]
- 10 -