DOC《各章习题》

各章习题 各章习题

1 答案

1

第一章 绪论(7)

1

第二章 线性表(6)

1

第三章 栈和队列(5)

2

第四章 串(3)

2

第五章 数组(3)

2

第六章 二叉树(20)

2

第七章 图(5)

5

第九章 查找(5)

5

第十章 排序(8)

6 答案

第一章 绪论(7) 集合、线性结构、树形结构、网(图)状结构 C B A 7.

n

第二章 线性表(6) n/2 H->next=H A A B D (a) 5, 8,

9 (b) 4,2,14,5,8,9 (c) (4,2,14,1,8,9) (5,2,14,5,8,9) (d) (2,5,8,9) (2,4,3,9) (e) (10,5,8,9) (4,12,8,9) (2,4,12,8,9) (2,10,5,8,9)

第三章 栈和队列(5) 线性 任意 栈顶 队头 队尾 A B D A

第四章 串(3) 1.长度相同 对应位值的字符相同 2.C 3.B

第五章 数组(3)

1100 A i j v i j v

1 2

12 1

3 -3

1 3

9 1

6 15

3 1 -3

2 1

12 3

6 14

2 5

18 4

3 24

3 1

9 5

2 18

3 4

24 6

1 15

4 6 -7

6 4 -7

6 3

14 三元组 转置后三元组

第六章 二叉树(20) 1.2n-1 2.3 3.68 4.2 n-1

1 n

1 n-1 5.n+1 6.2k-1 B D A 10.A 11.D 12.C 13.

0 1

2 3

4 5

6 7

8 9 A B C D E F G I J K

0 1

2 3

4 5

6 7

8 9

10 A B C D E F I J 14. (1) 设结点所处的层数为L,则各层的结点数:kL-1 (i-1)/k 下取整 2*k+m i%k!=0 i+1 n0=kh-1 nk= kh-1-n0= (k-1)*n0-1 15.若一棵二叉树的前序序列为ADCBFKHIGJE,中序序列为BCDKFHAGIJE,请画出该二叉树. 16.一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来,试求出空格处的内容,并画出该二叉树. 先序序列:ABDFKICEHJG;

中序序列:DBKFIAHEJCG;

后序序列:DKIFBHJEGCA;

17 已知某系统在通信联络中只可能出现八种字符,其概率分别为0.07(A)、0.19(B)、0.02(C)、0.06(D)、0.32(E)、0.03(F)、0.21(G)、0.10(H),试设计哈夫曼编码. 哈夫曼编码为(假设为左0右1) A

0011 4 目录 B

10 C

00000 D

0001 E

01 F

00001 G

11 H

0010 带权路径长度为2.61 18. 19. 20.先序:-+a*b-cd/ef 中序:a+b*c-d-e/f 后序:abcd-*+ef/-

第七章 图(5) 1.n-1 2.D 略

第九章 查找(5) D D 3.ASL=2i =1/2+2/22+3/23+……n/2n =2 C 1/2n-1+n/2n 4.已知哈希表地址空间为0..14,哈希函数为H(k)=k mod 13,采用线性探测法处理冲突.将下面各数依次存入该散列表中,并求出在等概率下的平均查找长度和失败的查找长度. 240, 29, 345, 189, 100, 20, 21, 35, 3, 208, 78, 99, 45,

350 0

1 2

3 4

5 6

7 8

9 10

11 12

13 14

208 78

350 29

3 240

345 189

100 20

21 35

99 45

240 mod 13=6

29 mod

13 =3

345 mod

13 =6 (冲突,地址7)

189 mod

13 =7 (冲突,地址8)

100 mod

13 =9

20 mod

13 =

7 (冲突,地址10)

21 mod

13 =8 (冲突,地址11)

35 mod

13 =12

3 mod

13 =3 (冲突,地址4)

208 mod

13 =0

78 mod

13 =

0 (冲突,地址1)

99 mod

13 =

8 (冲突,地址13)

45 mod

13 =

6 (冲突,地址14)

350 mod

13 =12 (冲突,地址2) 查找成功的ASL = 1/14*(1*5+2*4+4*2+6*2+9) =

3 查找失败的ASL = 1/14*(6+5+4+3+2+1+15+14+13+12+11+10+9) =7.5 5.折半查找的算法 int BinarySearch ( int Element[CurrentSize], const int x ) { int high = CurrentSize-1, low = 0, mid;

while (low Element[mid]) _low=mid+1_;

//右缩搜索区间 else if (x< Element[mid] ) _high=mid-1_;

//左缩搜索区间 else _return mid__;

//搜索成功 } return -1;

搜索失败 }

第十章 排序(8)

11 A B A B B 7.已知关键字序列{12,77,21,65,38,7,45,53,38,59},按递增有序进行排序 (1)直接插入排序每一趟的排序结果 12,77,21,65,38,7,45,53,38,59 12,77,21,65,38,7,45,53,38,59 12,21,77,65,38,7,45,53,38,59 12,21,65,77,38,7,45,53,38,59 12,21,38,65,77,7,45,53,38,59 7,12,21,38,65,77,45,53,38,59 7,12,21,38,45,65,77,53,38,59 7,12,21,38,45,53,65,77,38,59 7,12,21,38,38,45,53,65,77,59 7,12,21,38,38,45,53,59,65,77 (2)希尔排序每一趟的排序结果,增量序列为{5,3,1} 12,77,21,65,38,7,45,53,38,59 7,45,21,38,38,12,77,53,65,59 7,38,12,38,45,21,59,53,65,77 7,12,21,38,38,45,53,59,65,77 (3)冒泡排序每一趟的排序结果 12,77,21,65,38,7,45,53,38,59 12,21,65,38,7,45,53,38,59,77 12,21,38,7,45,53,38,59,65,77 12,21,7,38,45,38,53,59,65,77 12,7,21,38,38,45,53,59,65,77 7,12,21,38,38,45,53,59,65,77 7,12,21,38,38,45,53,59,65,77 (4)2路-归并排序每一趟的排序结果 12,77, 21,65, 38,7, 45,53, 38,59 (12,77),(21,65),(7,38),(45,53),(38,59) (12,21,65,77), (7,38,45,53), (38,59) (7,12,21,38,45,53,65,77), (38,59) (7,12,21,38,38,45,53,59,65,77) 8. (a) 否,100