数据结构复习题习题全六章含答案

H( 18 ) = 18 % 11 = 7 H( 70 ) = 70 % 11 = 4 ASL = ( 8*1+2*2 )/10 = 1.2 三、算法设计 递归算法：

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 )

初始堆对应的完全二叉树： 堆排序过程：

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