数据结构C语言版清华大学出版社8-9章课后部分答案.doc

1. C2.A3.B4.C5.D6.B7.B8.A9.D10.D 11.C 12.C1. nn+12. 43. 8.25( )4. 5. 266. (n+1)/2O(log2n)7. m-1m/2-18. 1. log2n+1.log2n+1-1.nnnn1+4log2n3.KiKjHash(Ki) = Hash(Kj)KiK,j1 2 3 4.1210 12 15 20 24 28 30 35 46 50 55 684 ASLsucc = 1x1+2x2+3x3+4x3+5x3/12 = 41/128.H(35) = 35%11 = 2H(67) = 67%11 = 1H(42) = 42%11 = 9H(21) = 21%11 = 10H(29) = 29%11 = 7H(86) = 86%11 = 9H(95) = 95%11 = 7H(47) = 47%11 = 3H(50) = 50%11 = 6H(36) = 36%11 = 3H(91) = 91%11 = 31. D 2.C 3.B 4.D 5.C 6.B 7.A 8.A 9.D 10.D1. 2. 3. 4. 5. O(n)O(log2n)6. 7. Log2nn8. n/29. 1510. 12 38 25 35 50 74 63 9011.1Shell(5 3 1)100 87 52 61 27 170 37 45 61 118 14 88 32514 37 32 61 27 100 87 45 61 118 170 88 52314 27 32 52 37 61 61 45 88 87 170 100 118114 27 32 37 45 52 61 61 87 88 100 11814 27 32 37 45 52 61 61 87 88 100 118 1702100 87 52 61 27 170 37 45 61 118 14 88 3232 87 52 61 27 88 37 45 61 14100118 17014 273261 52 88 37 45 61 87100 11817014273245 52 376188 61 87100 1181701427323745526187 6188 100 1181701427323745526187 6188 100 118170142732374552616187 88 100 11817031008752612717037456111814883287 10052 6127 17037 4561 11814 883252 61 87 10027 37 45 17014 61 88 1183227 37 45 52 61 87 100 17014 32 61 88 11814 27 32 37 45 52 61 61 87 88 100 118 17014 27 32 37 45 52 61 61 87 88 100 118 17012. 1.#define MAXSIZE 100 /* 100 */typedef int KeyType; /* */typedef struct KeyType key;/* */OtherType other;/* */DataType;/* */typedef struct DataType RMAXSIZE+1;/* R0 */int length;/* */sqList;/* */nR1.nn-2n-21 Rn = Rn-1large = Rnsmall = Rn-1large = Rn-1small = Rn2 large i = n C 2 large RiRii-13 large Ri+2 = large4 small ismall length;if( s-Rn.key = s-Rn-1.key )large = s-Rn;small = s-Rn-1;elselarge = s-Rn-1;small = s-Rn;i = n-2;s-R0 = large;while( large.key Ri.key )s-Ri+2 = s-Ri;i = i-1;s-Ri+2 = large;s-R0 = small;while( small.key Ri.key )s-Ri+1 = s-Ri;i = i-1;s-Ri+1 = small;n3n/2n+24n/2 2.R0Rn-1nRivoid Shuttlesort( DataType R, int n )int i=1,j,exchange = 1;while( exchange = 1 )exchange = 0;for( j=i-1;j Rj+1.key