二、应用题 1．

(1) 采用邻接矩阵表示得到的顶点序列如下表所示： 图 深度优先序列 广度优先序列 G4 0 1 2 8 3 4 5 6 7 9 0 1 4 2 7 3 8 6 5 9

G5 0 1 2 5 8 4 7 3 6 0 1 3 4 2 6 7 5 8

(2) 采用邻接表表示得到的顶点序列如下表所示： 图 深度优先序列 广度优先序列 G4 0 4 3 8 9 5 6 7 1 2 0 4 1 3 7 2 8 6 9 5

G5 0 4 7 5 8 3 6 1 2 0 4 3 1 7 5 6 2 8

2．唯一的一种拓扑序列为：1 4 0 2 3 5 7 6 8 9

第八章 查找

一、填空题

1、(n+1)/2、O(n)

2、见p264公式ASL=…、O(log2n) 3、37/12

4、顺序、有序 5、1、3

6、二叉搜索树、理想平衡树 7、6、31、19

8、索引、开始地址

9、(12,63,36)、(55,40,82)、(23,74) 10、3、3、2 a1211、散列 12、链接

a5a1813、2、7/5 14、5

a2a8a15a2115、开放定址、链接

16、3、2 a0a3a6a10a13a16a19a23

二、应用题 a1a4a7a9a11a14a17a20a22a24 1．(1) 顺序查找：

ASL = ( 1+2+3+…+25)/25 = 13 (2) 二分查找：

ASL = ( 1+2*2+4*3+8*4+10*5 )/25 = 99/25 = 3.96 ( 参见上图的二分查找树 )

２５

2．散列函数：H(K) = k % m 其中依题意得 m = 13 H( 32 ) = 32 % 13 = 6 H( 75 ) = 75 % 13 = 10 H( 29 ) = 29 % 13 = 3 H( 63 ) = 63 % 13 = 11 H( 48 ) = 48 % 13 = 9

H( 94 ) = 94 % 13 = 3 (冲突) 设 d0 = H(K) = H(94) = 3

d1 = ( d0+1 ) % m = (3+1) = 4

H( 25 ) = 25 % 13 = 12 H( 46 ) = 46 % 13 = 7 H( 18 ) = 18 % 13 = 5

H( 70 ) = 70 % 13 = 5 (冲突) 设 d0 = H(K) = H(70) = 5

d1 = ( d0+1 ) % m = (5+1) = 6 (冲突) d2 = ( d1+1 ) % m = (6+1) = 7 (冲突) d3 = ( d2+1 ) % m = (7+1) = 8

ASL = ( 8*1+1*2+1*4 )/10 = 1.4 29941832467048

0123456789

3．散列函数：H(K) = k % m 其中依题意得 m = 11

H( 32 ) = 32 % 11 = 10 H( 75 ) = 75 % 11 = 9 H( 29 ) = 29 % 11 = 7

H( 63 ) = 63 % 11 = 8 H( 48 ) = 48 % 11 = 4

H( 94 ) = 94 % 11 = 6 H( 25 ) = 25 % 11 = 3

H( 46 ) = 46 % 11 = 2 H( 18 ) = 18 % 11 = 7 H( 70 ) = 70 % 11 = 4

ASL = ( 8*1+2*2 )/10 = 1.2

012345678910

∧∧∧ 4625489429637532 ∧∧∧∧∧∧

7018

∧∧

751063112512

２６

三、算法设计 递归算法：

int Binsch( ElemType A[] , int low , int high , KeyType K ) { if ( low <= hight ){

int mid = (low+high)/2; if ( K == A[mid].key )

return mid; // 查找成功，返回元素的下标 else if ( K

return Binsch( A , low , mid-1 , K ); // 在左子表上继续查找 else

return Binsch( A , mid+1 , high , K ); // 在右子表上继续查找 } else

return -1; // 查找失败，返回-1 }

非递归算法：

int Binsch( ElemType A[] , int n , KeyType K ) { int low = 0 , high = n-1; while ( low <= hight ){

int mid = (low+high)/2; if ( K == A[mid].key )

return mid; // 查找成功，返回元素的下标 else if ( K

high = mid-1; // 在左子表上继续查找 else

low = mid+1; // 在右子表上继续查找 }

return -1; // 查找失败，返回-1 }

第九章 排序

一、填空题 1、插入、堆 2、快速、归并 3、O(n2)、O(n) 4、?n/2?-1、n-1

5、O(log2n)、O(nlog2n)

6、84 79 56 30 40 46 7、O(nlog2n)、O(n2) 8、O(log2n)、O(n) 9、两端、中间

10、38 40 46 56 79 80 11、4 4

12、 ?log2n? 或 ?log2n?+1

２７

13、O(n)、O(n log2n)、O(n) 14、6、4、8

15、 38 46 56 79 40 80 二、应用题

(1) ( 46 ) ( 74 16 53 14 26 40 38 86 65 27 34 ) ← 初态 ( 46 74 ) ( 16 53 14 26 40 38 86 65 27 34 ) ( 16 46 74 ) ( 53 14 26 40 38 86 65 27 34 ) ( 16 46 53 74 ) ( 14 26 40 38 86 65 27 34 ) ( 14 16 46 53 74 ) ( 26 40 38 86 65 27 34 ) ( 14 16 26 46 53 74 ) ( 40 38 86 65 27 34 ) ( 14 16 26 40 46 53 74 ) ( 38 86 65 27 34 ) ( 14 16 26 38 40 46 53 74 ) ( 86 65 27 34 ) ( 14 16 26 38 40 46 53 74 86 ) ( 65 27 34 ) ( 14 16 26 38 40 46 53 65 74 86 ) ( 27 34 ) ( 14 16 26 27 38 40 46 53 65 74 86 ) ( 34 ) ( 14 16 26 27 34 38 40 46 53 65 74 86 )

(2) ( 46 74 16 53 14 26 40 38 86 65 27 34 ) ← 初态 ( 14 )( 74 16 53 46 26 40 38 86 65 27 34 ) ( 14 16 )( 74 53 46 26 40 38 86 65 27 34 ) ( 14 16 26 )( 53 46 74 40 38 86 65 27 34 ) ( 14 16 26 27 )( 46 74 40 38 86 65 53 34 ) ( 14 16 26 27 34 )( 74 40 38 86 65 53 46 ) ( 14 16 26 27 34 38 )( 40 74 86 65 53 46 ) ( 14 16 26 27 34 38 40 )( 74 86 65 53 46 ) ( 14 16 26 27 34 38 40 46 )( 86 65 53 74 ) ( 14 16 26 27 34 38 40 46 53 )( 65 86 74 ) ( 14 16 26 27 34 38 40 46 53 65 )( 86 74 ) ( 14 16 26 27 34 38 40 46 53 65 74 86 )

(3) ( 46 74 16 53 14 26 40 38 86 65 27 34 ) ← 初态 构造初始堆过程：(构造大根堆)

( 46 74 16 53 14 34 40 38 86 65 27 26 ) ( 46 74 16 53 65 34 40 38 86 14 27 26 ) ( 46 74 16 86 65 34 40 38 53 14 27 26 ) ( 46 74 40 86 65 34 16 38 53 14 27 26 ) ( 46 86 40 74 65 34 16 38 53 14 27 26 ) ( 86 74 40 53 65 34 16 38 46 14 27 26 )

初始堆对应的完全二叉树： 86

7440

53653416

3846142726

２８