(CIP) /. :,2005. 7 ISBN 7 5612 1935 0.... T P311. 12 4 CIP (2005) 040538 : : 127 :710072 : 029-88493844 88491757 : www.nwpup.com : : 787 mm 1 092 mm 1/ 16 : 6.75 : 165 : 2005 9 1 : 9. 00
: : :
,,,,,,,, 2005 4
1 1 2 3 3 5 4 8 5 9 6 12 7 23 9 32 10 38 ( ) 46 ( ) 50 53
1 : 1. 2. x = 91; y = 100; while ( y > 0 ) { * if ( x > 100 ) {x - = 10 ; y - - else x + + ; * 1., 2. 1. ( ) A. B. C. D. 2. ( ) for (i = 0; i < n; i + + ) for (j = 1; j < m; j + + ) A [ 1] [j] = 0; A. O ( n ) B. O ( m + n + 1) C. O ( m + n ) D. O ( m * n) 3., ( ) A. B. C. D. 4. ( ) A. B.
2 C. D. 5., ( ) A. B. C. D.
2 : ; ; 1.,? 2. :,, ( ) 3. 1., ( ) A. B. C. D. 2., p q ( llink, data, rlink ) A. p - > llink = q; q - > rlink = p; p - > llink - > rlink = q; q - > llink = q; B. p - > llink = q; p - > llink - > rlink = q; q - > rlink = p; q - > llink = p - > llink; C. q - > rlink = p ; q - > llink = p - > llink; p - > llink - > rlink = q; p - > llink = q; D. q - > llink = p - > llink; q - > rlink = p ; p - > llink = q; p - > llink = q; 1.,,
4,, 2.,,,, ( ) 1. va, x 2., : pre, dat a link, pre 3. i 4. 5. x y,, x 1 y ( ) 6.,
3 : ; ; 1. 1, 2, 3,..., n, n, i 2., ( ) A., B., C. D. 3. (1 ) PO P ( PU SH ( S, A) ) ; (2 ) P US H ( S, POP ( S ) ) ; (3 ) P US H ( S, POP ( PUS H ( S, B) ) ) 4. 1, 2, 3, 4, 5, 6,, 3, 2, 5, 6, 4, 1 1, 5, 4, 6, 2, 3,?? 5., 1000 H ( ), 1, 2, 3, 4, 5, PU SH, PU SH, POP, P US H, POP, PU SH, P USH,, 6.,, ( ) 7., ( ) F = R = nil F = R F nil R = nil R - F = 1 8.???, 9. sequ [0.. m - 1 ], tag
6 ( rear) ( front)? 1. n, front rear 2. S1 S2,, V [ 1.. n ],,, 3.,,, 4. 5. sequ [0.. m - 1 ], rear quelen, 6.
3 7 7. ( ), 1, 2, 3, 4 : (1 ), ; (2 ), ; (3 ),
4 : 1.??? 2. S = syntax, ( ) A. 6 B. 21 C. 22 D. 7 3. s = aaab, t = abcabaa, u = abcaabbabcabaacbacba next
5 : ; 1. 10 a,,, a1 1, 1, 1, a85 ( ) A. 13 B. 33 C. 18 D. 40 2. n * n,, ( ) A. n * n B. n * ( n + 1) / 2 C. ( n + 1) * ( n + 1 ) / 2 D. ( n - 1) * n/ 2 3. a 6, i 0 8, j 1 10 a, a [ 8, 5 ] a ( ) ( ) A. a [8, 5] B. a [ 3, 10] C. a [5, 8] D. a [ 0, 9 ] 4. ls = ( a, ( b, c, d), e), head tail ls b ( ) A. head ( head (ls) ) B. t ail ( head (ls) ) C. head ( head ( tail (ls) ) ) D. head ( tail (ls) ) 5. a = ( ( a, b, c), ( d, e, f) ), a e ( ) A. tail ( head ( a) B. head ( tail (a) ) C. head (t ail ( tail ( head ( a) ) ) ) D. head ( tail ( tail (a) ) ) 6. tail [ ( (a, b), (c, d) ) ] ( ) A. c, d B. (c, d) C. (( c, d) ) D. d, c 1. b [ 1.. 10, - 2.. 6, 2.. 8], 100, 3b [ 5, 0, 7] 2. a [ 10, 20 ],, a [ 1, 1 ] 200, a [ 6, 12]?
10 3. ( ) n * n ( n > = 3 ) a, : 1 < i < n n - i < = j < = n - i + 2 a [i, j] first, a [i, j] 4. (a, ( a, b ), d, e, ( (i, j), k) ), 5. n * n ( a i, j) b (1 : 3 * n - 2), b [ k] = a i, j, : (1 ) i, j k (2 ) k i, j 6. : (1 ) ; (2 ) ; (3 ) n * n, p,, ( ) 4,, ( ) 7. n * n,,? 8. 0 1 0 0 0 2 0 0 0 3 m = 0 0 4 0 0 0 0 0 5 0
5 11 1. a [1.. n] n ( n > 1 ), a a a [ 1.. i] (1 < = i < = n) 2. ( ) a [ 1.. n], O ( n)
6 : ; ; 1. 5 ( ) A. 16 B. 30 C. 31 D. 32 2. ( ) A. B. C. D. 3. T2 T, T T2 ( ) A. B. C. D. 4.? ( ) A. B. C. D. 5. 65 ( ) ( 0) A. 8 B. 7 C. 6 D. 5 6. F, B F, F n, B ( ) A. n - 1 B. n C. n + l D. n + 2 7., x 5, x, ( ) A. 5 B. 4 C. 5 D. 4 8. : ( ) A. B. C. D. 9. ( ) A. B. C. D. 10. 2 15, 1 10 ( ) A. 25 B. 30 C. 31 D. 41 11. 2 15, 1 10, ( ) A. 25 B. 30 C. 31 D. 16
6 13 12. 6 6 3, ( ) A. 15 B. 16 C. 17 D. 34 13. h, ( ) A. 2 h B. 2 h - 1 C. 2 h - 1-1 D. 2 h - 1 + 1 14., ( ) A. B. C. D. 15.,, ( ) A. B. C. D. 16., ( ) A. B. C. 1 D. 1, 2 17. ABDECF, DBEAFC, ( ) A. DEBA FC B. DEFBCA C. DEBCF A D. DEBFCA 18. ( ) A. 2 B. C. 2 D., 19. ( ) A. 4 5 3 1 2 B. 4 2 5 3 1 C. 4 5 2 1 3 D. 4 2 3 1 5 20., ( ) A. B. C. D. 21., ( ) A. 0 B. 1 C. 2 D. 22., ( ) A. B. C. D. 23. 64 ( ) ( 1)
14 A. 8 B. 7 C. 6 D. 5 24. n, ( ) A. n - 1 B. 2 n - 1 C. n + 1 D. 2 n + 1 25. ( ) A. {1, 01, 000, 001 B. {1, 01, 011, 010 C. {0, 10, 110, 11 D. {0, 1, 00, 11 26. n, ( ) A. n - 1 B. 2n - 1 C. n + 1 D. 2n + 1 1. n 2. K,, n,, ( :,, K K - 1 1 )? 3. 1001? 2 0? 4. n, 5. 15, 6 6. n, 7. T, T, BT 8. P 9. 121, 10. 121, 3 0, 11. 3, 2 1, 0 6, 3 12. 3, 3 2, 2 1, 0 13. 2000, 14. n0 15. 30, 5,,, 16. m n, Y N U
6 15 n m? n m? n m? n m n m n m n m 1. ABCDEFG H IJKL 2. T ABCDE FG HJKIL, CBE FDJIKLH- GAT 3. ABCDEF G HIJK, CDBGF EA HJIK, 4.,, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 data pa rent A B C D E F G H I J K L M N O 0 1 1 1 2 2 3 3 4 4 5 6 6 7 8 5. ABDIC * EF * * m * * * H
16 6. ( 1) 2? (2 ) ( )? 7. N, M, : ( M - 1 ) 2, 1 8. : (1 ) ; (2 ) ; (3 ) ; 9. BDCEAF H G DECBH GF A, 10. n0,? 11. : (1 ) ; (2 )
6 17 12. {a, b, c, d, e, f, 34, 5, 12, 23, 8, 18, 6 ( ), 13. ( b ), p, (a), : (1 ) f ( p ) ; (2 ) f void f ( BinT hrt ree t) { while ( t) { printf ( t - > data) ; if (t - > lchild) t = t - > lchild; else t = t - > rchild;
18 14. {a, b, c, d, e, f, g, : 0110, 10, 110, 111, 00, 0111 010 (1 ), (2 ) 3, 35, 13, 15, 20, 5 9, 15. F, : void F (Bin Tree T) { Stack S; if ( T ) { InitStack ( &S) ; Push ( &S, N ULL) ; while ( T) { printf ( " % c", T - > data) ; if ( T - > rchild) Pus h ( &S, T - > rchild) ; if ( T - > lchild) T = T - > lchild; else T = Pop ( & S) ; (1 ), rt F ( rt) (2 ) F 16.
6 19 17., : typedef struct node { Da tet ype data ; Struct node * nex t ; List Node ; t ypedef ListN ode * LinkList ; Link List Leafhead = NULL ; Void Inorder ( BinTree T ) { Link List s ; If ( T) { Inorder ( T - > lchild) ; If ( (! T - > lchild) & & (! T - > rchild) ) { s = ( ListNode * ) malloc ( sizeof ( List Node) ) ; s - > data = T - > data ; s - > next = Leafhead; Leafhead = s; Inorder ( T - > rchild) ; : (1 ) (2 ) 18.,,,
20 19. ( text) CAS T, CATS, SA T, A T, A, TASA, D = {C, A, S, T D, 1. 2. x, x, x ( ) 3. bt (1 : n ), 4.,, 5., 6., 7., T :
6 21 8. BT 9. 10. T : typedef struct node { Da tatype data ; struct node * lchild, * rchild, * parent ; PBin Tree;, lchild rchild, parent ( ), parent 11., x,, : lchild key rchild, T, it em,,, void DELLEA F ( T ) { top 0 / / / / p T do { while ( p nil) { if then/ / ( ) / / { if then / / / / T nil
22 else / / / / if then lchild ( q) nil / / / / else rchild ( q) nil/ / / / call RET ( p ) / / / / return ; ; top top + 1 S TACK [ top] p / / p / / q p / / p / / p lchild ( p ) / / p / / / / while ( p nil) p STACK [ top ] / / () p / / top top - 1 q p / / p / / p rchild ( p) whilel / / p / /
7 : ; 1.,,, ( ) 2., ( ) 3. ( AOV - ) ( ) 4. ( ) 5., ( ) 6. A, Vi Vj, A i j 0 ( ) 7. AOE ( ) 8. ( ) 9. ( ) 10. ( A OV - ) ( ) 11. ( ) 12. ( ) 13. 0, ( ) 14. ( ) 15. ( ) 16. A OE ( ) 17. G = ( V, E ), < vi, vj > < vj, vi > ( ) 18., ( ) 19., i i ( ) 20. ( ) 21. G, n - 1 ( n G ) ( ) 1. G n, G ;
24 G, n, G ; n, ; n, 2. G n e,, G 2e > = n,, 3. n 4. (, ), (, ), n, (, ) 5. n e, prim ; Krus kal 6. n e,, 7. n e,,, 8. 9., 10. 11., 12., 13. G = < V, E >, V = {v1, v2, v3, v4, v5,, E = { ( v1,, v2) 7, ( v1, v4 ) 6, ( v1, v4 ), ( v2, v3 ) 8, ( v2, v4) 4, ( v2, v5) 4, ( v3, v4 ) 6, ( v4, v5 ) 2, ( : ), G 14. n, 15., Vp Vq Vp Vq,, 16. 17. V G : V = {0, 1, 2, 3, 4, 5, 6, 7; E = {( 0, 1 ) 3, ( 0, 3 ) 5, ( 0, 5 ) 18, (1, 3) 7, (1, 4) 6, (2, 4) 10, ( 2, 7 ) 20, (3, 5) 15, (3, 6) 12, ( 4, 6 ) 8, ( 4, 7 ) 12 2, :,,,,,, 18. n,, 19. n e,,
7 25 20., 21. n, 22. 23. 1. ( ) A. C. B. D. 2. n e, ( ) A. O (loge) B. O (en) C. O (elogn ) D. O ( n + e) 3. ( ) A. C. 4. ( ) A. B. D. B. C. D. 5. G = ( V, E) C = ( V, E ), C G, ( ) A. C C C. C C 6. ( ) A. B. C C D. C C V = V
26 B. C. D. 7. G = < V, E >, V = {v1, v2, v3, v4, v5, v6; E = { < v1,, v2 >, < v1, v4 >, < v2, v6 >, < v3, v1 >, < v3, v4 >, < v4, v5 >, < v5, v2 >, < v5, v6 >, G ( ) A. v3, v1, v4, v5, v2, v6 B. v3, v4, v1, v5, v2, v6 C. v1, v3, v4, v5, v2, v6 D. v1, v4, v3, v5, v2, v6 8. C1 C7, ( ) A. C1, C2, C6, C7, C5, C4, C3 B. C1, C2, C6, C3, C4, C5, C7 C. C1, C4, C2, C3, C5, C6, C7 D. C5, C7, C4, C1, C2, C6, C3 9. n e, ( ) A. e B. 2e C. n 2 - e D. n 2-2e 10. n e, vi ( ) A. O ( n ) B. O ( e) C. O ( n + e) D. O ( n * e) 11., a, DFS ( ) A. a d b e f c B. a d c e f b C. a d c b f e D. a d e f c b 12., ( ) A. B. C. D. 13. ( ) A. B. C. D. 14., a ( ) A. a c e f b d B. a c b d f e C. a c b d e f D. a c d b f e
7 27 15. Dijkstra ( ) A. O ( n) B. O ( n + e) C. O ( n 2 ) D. O ( n e) 16. DFS ( ) A. O ( n) B. O ( n 3 ) C. O ( n 2 ) D. O ( n + e) 17. DFS ( ) A. O ( n) B. O ( n 3 ) C. O ( n 2 ) D. O ( n + e) 1. n n ( n - 1) / 2 2. G n, G n - 1 3. n,, : (1 )? (2 ) i j? (3 )? 4. AOE,, A OE,? 5. ABCDE FG H,, 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0
28 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 A 6. AOE G = ( V, E ), V = { v1, v2, v3, v4, v5, v6, v7 ; E = {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10; a1: ( v1, v2 ) 3, a2: ( v1, v3 ) 2, a3: ( v2, v4) 1, a4: ( v2, v5 ) 8, a5 : ( v3, v4) 3 ; a6: ( v3, v6 ) 7, a7: ( v4, v5 ) 4, a8: ( v4, v6) 2, a9: ( v5, v7 ) 9, a10: ( v6, v7 ) 6; ( : ) e [i] l [i] a1, e [i] l [i] (1 i 10 ) 7.,, (5, 5, 16), 16, ( 1, 2, 7 ), (1, 3, 6 ), ( 1, 4, 9), (2, 1, 7 ), ( 2, 3, 8), (2, 4, 4), (2, 5, 4 ), ( 3, 1, 6 ), ( 3, 2, 8 ), ( 3, 4, 6), ( 4, 1, 9 ), (4, 2, 4 ), ( 4, 3, 6 ), (4, 5, 2), ( 5, 2, 4 ), ( 5, 4, 2) 8., a b c d e f,, acbefd, acbdfe 9.
7 29 10. : 11. V G : V = {0, 1, 2, 3, 4, 5, 6, 7, 8; E = { < 0, 1 >, < 0, 2 >, < 1, 3 >, < 1, 4 >, < 2, 4 >, < 2, 5 >, < 3, 6 >, < 3, 7 >, < 4, 7 >, < 4, 8 >, < 5, 7 >, < 6, 7 >, < 7, 8 >,,, ( :, ) { 12. : void AJ (adjlist GL, int i, int n) Queue Q ; InitQueue ( Q) ; cout < < i < < ; visited [i] = true ;
30 Qinsert (Q, i) while (! QueueEmpty ( Q) ) { int k = Qdelete ( Q) ; edgenode * p = GL [ k ] ; while ( p! = N ULL ) { int j = p - > adjvex; if (! Visit ed [j] ) { cout < < j < < ; visited [ j] = tr ue; Qinsert (Q, j) ; p = p - > next ; GL { (0, 1), ( 0, 2 ), (0, 5 ), ( 1, 3), ( 1, 4 ), ( 2, 4 ), (2, 5 ), (3, 6), (4, 6), i n 0 7, adjvex,? 13. {a, b, c, d, e, : a 0 1 0 0 1 b 1 0 0 1 0 c 0 0 0 1 1 d 0 1 1 0 1 e 1 0 1 1 0 (1 ) ; (2 ) a, 14., (1 ), ; (2 )
7 31 15. 16. V G : V = {0, 1, 2, 3, 4, 5, 6, 7; E = { (0, 1) 8, (0, 2) 5, (0, 3) 2, (1, 5) 6, (2, 3) 25, ( 2, 4 ) 13, (3, 5) 9, (3, 6) 10, (4, 6) 4, (5, 7) 20, 17. V G : V = {0, 1, 2, 3, 4, 5, 6, 7; E = { (0, 1) 8, (0, 2) 5, (0, 3) 2, (1, 5) 6, (2, 3) 25, ( 2, 4 ) 13, (3, 5) 9, (3, 6) 10, (4, 6) 4, (5, 7) 20 (1 ) Prim V0, ; (2 ) ; (3 )
9 : ; ; ; 1. ( ) 2. ( ) 3., ( ) 4., ( ) 5. ( ) 6. 1, ( ) 7.,,, ( ) 8. m B - m ( ) 9. m B - m/ 2 ( ) 10. m B - k k - 1 ( ) 11. m B - ( ) 12. ( ) 13. ( ) 14. ( ) 15., ( ) 16., ( ) 17.,,, ( ) 18.,, ( ) 19.,, ( ) 20. ( ) 21., ( )
9 33 22.,, ( ) 23. ( ) 24. ( ) 1. ( ) A. B. C. D. 2.,,, ( ) A. B. C. D. 3. 18, A [ 3 ] ( ) A. 1, 2, 3 B. 9, 5, 2, 3 C. 9, 5, 3 D. 9, 4, 2, 3 4., A, A - 1, 0, ( ) A. LL B. LR C. RL D. RR 5. ( ) A. B. C. D. 6. 14 R [ 14 ], R [ 3], ( ) A. R [0 ], R [ 1], R [2 ], R [ 3] B. R [ 0], R [13], R [2 ], R [ 3] C. R [6 ], R [ 2], R [4 ], R [ 3] D. R [ 6], R [4 ], R [ 2], R [3 ] 7. (18, 20, 25, 34, 48, 62, 74, 85) 85, ( ) A. 1 B. 2 C. 3 D. 4 8. ( ) A. B. C. D. 9. ( MON, T UE, WED, T H U, FRI, SAT, S UN), H ( k) = i MOD 7,, i k, [0 : 6], ( )
34 A. 0 1 2 3 4 5 6 T H U TUE W ED FRI S UN SAT MON B. 0 1 2 3 4 5 6 TUE T H U W ED FRI S UN SAT MON C. 0 1 2 3 4 5 6 TUE T H U W ED FRI SA T SU N MON D. 0 1 2 3 4 5 6 TUE T H U W ED SU N SAT FRI MON 10. H ( n ) = n MOD p, p ( ) A. B. C. D. 11. ( ) A. O ( n * n ) B. O ( n) C. O ( nlogn) D. O (logn ) 12., k, k, ( ) A. k B. k + 1 C. k ( k + 1 ) / 2 + 1 D. k ( k + 1) / 2 13. n,, ( A. n - 1 2 ) B. n 2 C. n + 1 2 D. n 14. H ( key) = key% 13, ( ) A. 35 41 B. 23 39 C. 15 44 D. 25 51 15. 123, 3,,, ( ) A. 21 B. 23 C. 41 D. 64 1. ( 34, 76, 45, 18, 26, 54, 92, 65, ),, 2. ( ),, 3.,, 4. (12, 24, 36, 48, 60, 72, 84) 72 5. 10000,, 6. 20 7. m, H ( key),,
9 35 8. ( 12, 18, 30, 43, 56, 78, 82, 95 ) 43 56, : 43 ( 18 ( 12, 30 ), 78 (56, 82 (, 95) ) ) 9. (38, 25, 74, 52, 48), H (K ) = K% 7,, 10.,, 11., 12. (2, 5, 8, 11, 15, 16, 22, 24, 27, 35, 40 ) ( ) 24, 13. h,, 1. B - B +,, B +,, B -,? 2.,, n? ( ) 3.,, 4. 10 ( ), 5. 150,, 2? (,
36 ASL = (1 + 1/ ( 1 - ) ) / 2) 6. 53, 78, 65, 17, 87, 09, 81, 45, 23, 7. (40, 36, 53, 38, 25, 16, 28, 64, 60, 42), 8. ( 17, 33, 31, 40, 48 ) 7, h ( key) = key%7, hi = ( h ( key) + i ( key%5 + 1) ) %7 0 i 6 (1 ) ; (2 ) 9. [ 0: 9 ], H ( key) = key MOD 9,, 8, 10, 14, 19, 21, 23, 28, 32 10. : 45, 24, 53, 12, 24, 90 11. 12 : ( Jan, Feb, Mar, Apr, May, J une, J uly, Aug, Sep, Oct, Nov, Dec) (1 ),, (2 ), (3 ) A VL,
9 37 13, H ( k) = K MOD 13, : 19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79,, 12. k1, k2, k3, k1 > k2 > k3, 13. H ( k ) = k MOD 7, 0 6, {32, 13, 49, 18, 22, 38, 21, ( )
10 : ; ; 1., ( ) 2.,,, ( ) 3. n, O ( nlogn) ( ) 4. n, O ( n) ( ) 5. n, O ( n * n ) ( ) 6. n, O ( nlogn) ( ) 7. n, O ( n) ( ) 8. n, O ( n * n ) ( ) 9. n, O ( nlogn) ( ) 10. n, O ( n) ( ) 11. ( ) 12. () ( ) 13. ( ) 1. ALV, ( ) A. B. 1 C. D. 2. n i ( 1 i n + 1 ), ( ) A. n - i + 1 B. n - i C. i D. i - 1 3., ( ) A. B. C. D. 4. n, ( )
10 39 A. O (1 ) B. O (logn) C. O ( n) D. O ( n logn) 5., O ( nlogn) ( ) A. B. C. D. 6. {25, 48, 36, 72, 79, 82, 23, 40, 16, 35, ( A. {25, 36, 48, 72, 23, 40, 79, 82, 16, 35 B. {25, 36, 48, 72, 16, 23, 40, 79, 82, 35 C. {25, 36, 48, 72, 16, 23, 35, 40, 79, 82 D. {16, 23, 25, 35, 36, 40, 48, 72, 79, 82 7. ( ) ) A. B. C. D. 8.,, ( ( ) A. B. C. D. n 9.,, O ( nlog2 ) A. B. C. D. ) 10., ( ) :, A. B. C. D. S HELL 11. ( ) A. O ( n) B. O ( nlog2 n) C. O ( n 2 ) D. O (log2 n) 12. A 10000, 10, ( ) A. B. C. D. 13.,,, ( ) A. B. C. D. 14. {46, 79, 56, 38, 40, 84, ( ) A. {38, 46, 79, 56, 40, 84 B. {38, 79, 56, 46, 40, 84 C. {40, 38, 46, 56, 79, 84 D. {38, 46, 56,? 9, 40, 84 15., ( ) A. B. C. D. 16., 1, ( A. 70, 75, 82, 90, 23, 16, 10, 68 B. 70, 75, 68, 23, 10, 16, 90, 82 )
40 C. 82, 75, 70, 16, 10, 90, 68, 23 D. 23, 10, 16, 70, 82, 75, 68, 90 17.,,,,, ( ) A. B. C. D. 18. (49, 72, 68, 13, 38, 50, 97, 27), : : 13, 72, 68, 49, 38, 50, 97, 27 : 13, 27, 68, 49, 38, 50, 97, 72 : 13, 27, 38, 49, 68, 50, 97, 72 ( ) A. B. C. D. 19., ( ) A. B. C. D. 1., 2. N, 3. ( 54, 38, 96, 23, 15, 72, 60, 45, 83 ), 7 60, 4. n, 5. n, 6. ( 37, 66, 48, 29, 31, 75 ) 7. ( 52, 80, 63, 44, 48, 91 ) 8.,,, 9. 8 4800 8,, 10.,,,, 11.,, 12. 13., 14.
10 41 15. (49, 38, 65, 97, 76, 13, 27, 50), 1.??,? 2.,,,?? 3. 5000, 10,,,, shell,?? 4. key = {51, 28, 38, 86, 70, 90, 7, 30, 40, 25, key 5. {17, 18, 60, 40, 7, 32, 73, 65, 85, 6. ( 54, 38, 96, 23, 15, 72, 60, 45, 83), 7. (72, 87, 61, 23, 94, 16, 05, 58 ), : 1 : 2 :
42 3 : 8. R [ 1.. 8] ( 12, 5, 9, 20, 6, 31, 24, 27 ), MergeSortDC R, 5 Merge ( R, low, mid, high) low, mid high void MergeSortDC (int R [ ], int low, int mid, int high ) { int mid; if (low < high ) { mid = ( low + high) / 2; MergeSortDC ( R, low, mid ) ; MergeSortDC ( R, mid + 1, high ) ; Merge ( R, low, mid, high ) ; / / MergeSortDC (1 ) ; (2 ) ; (3 ) ; (4 ) ; (5 ) 9. : (70, 12, 20, 31, 1, 5, 44, 66, 61, 200, 30, 80, 150, 4, 28 ) 10. ( 46, 79, 56, 38, 40, 80, 36, 40, 75, 66, 84, 24 ),, 11. ( 46, 79, 56, 38, 40, 80, 25, 34 ),
10 43 12. ( 38, 56, 30, 25, 35, 20, 18, 59 ), 13. ( 84, 79, 56, 42, 40, 46, 50, 38 ), 14. : 45, 24, 53, 12, 24, 90 15. ( k1, k2, kn ),?, 16. (76, 38, 65, 13, 97, 27, 50, 49) ( ), 1 2 3 4 5 6 7 8 17. : 72 73 71 23 94 16 05 68 1., :
44 (1 )? (2 ) R [ n + 1 ]? Typedef struct { KeyType key; infotype ot he rinfo; nodetype; typedef nodetype SqList [ MAXLEN ] ; void sort ( SqList R, int n ) { / / n MAXLEN - 1 int k; i; for ( k = n - 1; k > = 1; k - - ) if ( R [ k ]. key > R [ k + 1]. key) { R [ n + 1 ] = R [ k] ; for (i = k + 1 ; R [i]. key < R [ n + 1 ]. key; i + + ) R [i - 1 ] = R [i] ; R [i - 1] = R [ n + 1] ; da ta next L, L, void SelectSor t ( LinkedList L ) { LinkedList p, q, min; Da tatype rcd; p = ( 1) ; while ( p! = N ULL ) { min = p; q = p - > next ;
10 45 while ( q! = N ULL) { if ( (2 ) ) min = q; q = q - > next ; if ( (3 ) ) { rcd = p - > data ; p - > data = min - > data; min - > data = rcd; ( 4) ;
( ) ( 1, 20 ) 1. n e,,, 2. G n, G ; G, n, G ; n, ; n, 3. n 4. (, ), (, ), n, (, ) 5.,,,, 6. B [ 1.. 10, - 2.. 6, 2.. 8], 100, 3B [ 5, 0, 7] 7., 1000 H ( ), 1, 2, 3, 4, 5, PU SH, P US H, POP, P USH, POP, P USH, PUS H,, ( 10 ) 1. ( ) A. B. C. D. 2. key = {50, 26, 38, 80, 70, 90, 8, 30, 40, 20, : 50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 ( ) A. B. C. D. 3. ( 25, 48, 16, 35, 79, 82, 23, 40, 36, 72 ), 5 2, ( )
( ) 47 A. 16 25 35 48 23 40 79 82 36 72 B. 16 25 35 48 79 82 23 36 40 72 C. 16 25 48 35 79 82 23 36 40 72 D. 16 25 35 48 79 23 36 40 72 82 4. 5000, 10,, ( ) A. B. C. D. shell 5., ( ) A. B. C. D. 6. ( ) A. B. C. D. 7. n * n,, ( ) A. n * n B. n * ( n + 1) / 2 C. ( n + 1 ) * ( n + 1) / 2 D. ( n - 1) * n/ 2 8. 5 ( ) A. 16 B. 30 C. 31 D. 32 9. ( ) A. B. C. D. 10. 10 A,,, a11, 1, 1, a85 ( ) A. 13 B. 33 C. 18 D. 40 ( 10 ) 1. ( ) 2. ( AO V - ) ( ) 3., ( ) ( ) 4. () ( ) 5.,,, ( ) 6., i i ( ) 7. () ( ) 8. AOE ( ) 9. ( ) 10. ( )
48 ( 5, 30 ) 1. va, x : Status Insert _ SqList ( SqList & va, int x) / / x va { if ( va. length + 1 > va. listsize) return ERROR ; va. length + + ; for (i = va. length - 1 ; ; i ) va. elem [i + 1 ] = va. elem [i] ; va. elem [i + 1 ] = x; return O K; / / Insert _ SqList 2.. int leaf - number ( btree * t) { if ( t = = null) return ( 0) ; else if ( t - > lchild = null & & ( t - > rchild = null) return (1 ) ; else retrn (leaf - number ( ) + leaf - number ( ) ) ; 3., int height ( bitree * t) { in the, he1, he2; if ( t = = N ULL) return 0; else { he1 = height ( t - > left) ; he2 = height ( t - > right) ; if ( he1 > he2) the = ; else the = ; return the ;
( ) 49 4. : void Insert _ Sort1 ( SqList & L) { k = L. length; for (i = k - 1; i; - - i) if ( L. r [i]. key > L. r [i + 1]. key) { L. r [ k + 1]. key = ; for (j = i + 1; L. r [ j]. key > L. r [i]. key; + + j) L. r [j - 1]. key = L. r [j]. key; L. r [j - 1]. key = L. r [ k + 1 ]. key; / / Insert _ Sort1 ( 30 ) 1. (10 ) N, M, ( M - 1 ) 2, 1 2. (10 ) : (a) ; ( b ) ; (c) 3. (10 ) {a, b, c, d, e, a 0 1 0 0 1 b 1 0 0 1 0 c 0 0 0 1 1 d 0 1 1 0 1 e 1 0 1 1 0 (1 ) ; (2 ) a,
( ) ( 1, 10 ) 1., p q ( llink, dat a, rlink) p. llink: = q; q. rlink : = p; p. llink. rlink: = q; q. llink: = q; p. llink: = q; p. llink. rlink: = q; q. rlink: = p ; q. llink : = p. llink; q. rlink: = p; q. llink : = p. llink ; p. llink. rlink: = q; p. llink: = q; q. llink: = p. llink; q. rlink : = p ; p. llink : = q; p. llink: = q; 2. 1, 2, 3,, n, n, i 3., K m, d0,, d3 4. A [10, 20],, A [ 1, 1 ] 200, A [6, 12 ] 5. n 6. K,, n,, ( 7 ) 1. n * n,, ( ) A. n * n B. n * ( n + 1 ) / 2 C. ( n + 1 ) * ( n + 1) / 2 D. ( n - 1 ) * n/ 2 2. 10 A,,, a11, 1, 1, a85 ( ) A. 13 B. 33 C. 18 3. ( ) A. B. C. D. 4. 6 ( ) A. 16 B. 30 C. 63 D. 32
( ) 51 5. ( ) A. B. C. D. 6. T2 T, T T2 ( ) A. B. C. D. 7. : ABCDE FG HIJKL ( ) A. h i d j k e b l f g c a B. A B C D E F G H I J K L C. H D I B J E K A L F C G D. A B C D E G F H J I K L ( 8 ) 1.,,, ( ) 2. ( ) 3., ( ) ( ) 4. () ( ) ( 30 ) 1., int leaf - number ( btree * t) { if ( t = = nil) return (0 ) ; else if ( t - > lchild = nill & & ( t - > rchild = nill) retur n ( 1) ; else retrn ( + + ) ; 2., : int Search _ Sq ( SSTable S T, int key) / /, { ST. elem [ ST. length + 1]. key = key; for (i = 1; S T. elem [i]. key > key; i + + ) ; if ( S T. elem [i]. key < key) return ERROR; return i; / / Search _ Sq 3. :
52 Status Bracket _ Test (char * str ) / / { count = 0 ; for ( p = str; * p; p + + ) { if ( * p = = ( ) count + + ; else if ( * p = = ) ) count - - ; if ( count < 0 ) return ERROR ; if ( ) return ERROR ; return O K; / / Bracket _ Test ( 10, 30 ) 1. n0,? 2. 13, H ( k ) = K MOD 13, : 19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79 3. key = {51, 28, 38, 86, 70, 90, 7, 30, 40, 25, key, (15 ) n,, : (1 )? (2 ) I j? (3 )?
1 1. :,, 2. : y ( > 0 ) * 11, 100 * 11 1. 2. 1. A 2. D 3. B 4. D 9. D 2 1. :, ;,,, 2. : ; : ( ), ;,,, 3. :, ( ),, ;,,,,,, ;
54 1. B 2. C 1. 2. n 2, 1. : void insert _ sqlist ( sqlist & va, int x ) / / x va { if ( va. length + 1 > va. listsize) retur n error; va. length + + ; for (i = va. length - 1 ; va. elem [i] > x & &i > = 0; i - - ) va. elem [i + 1 ] = va. elem [i] ; va. elem [i + 1 ] = x; return ok ; / / insert _ sqlist 2. : s, p q ; s, ; pre, p q, p q : ( lnode ) void singlechanget odouble ( l node * s) { lnode * p, * q; p = s; do { q = p - > link; q - > pre = p; p = q; while ( p! = s ) ; p q 3. : i < = 0,, ; i = 1, i > n ( n ),, ; 1 < i < = n,, i, i.
55 : ( lnode ) void preinsert (lnode * q, elementype x, int i) { lnode * s, * p; int j; if ( i < = 0 ) printf ( " can not insert" ) ; else { s = ( lnode * ) malloc ( sizeof (lnode) ) ; s - > data = x; if ( i = = 1) { s - > link = q; q = s; else { j = 1; p = q; while ( (j < i - 1) & & ( p < > n uil) ) { p = p - > link; j = j + 1; if ( p = = nuil) printf ( " can not insert" ) ; else { s - > link = p - > link; p - > lin k = s ; 4. : p, t, t = nil, s t, t - > data = p - > data, t, s - > link = t - > link; p, : p = p - > link,, p = nil : void deleteequal ( lnode * q) {lnode * p, * t, * s; p = q - > link; t = p; while ( p < > nuil) / / { s = t ; t = t - > link; do { while ( t < > nuil) & & ( t - > data < > p - > data) { s = t; t = t - > link; if ( t < > nuil) { s - > link = t - > link; free ( t) ; t = s - > link ; ; while ( t! = nuil) ; p = p - > lin k; t = p ;
56 5. : x, y ; y x, x ; y x, : typedef struct record { data type char; struct r ecord * link; * ctr ; datatype stringloca tion (ctr x, ctr y) ; { ctr px, py ; while ( px < > nuil) { py = y; while ( ( py < > nuil) & & ( px - > dat a < > py - > data) ) py = py - > link; if ( py = = nuil ) return px - > char ; / / else { px = px - > link; ; return 0; / / 6. : : # include < stdio. h > # include " string. h" # include " malloc. h" # include " stdlib. h" # define st ringsize 12 typedef struct node / * * / { char data ; / * */ struct node * next ; / * */ listnode ; typedef listnode * linklist ; linklist set (int L ) { int t = 0 ; char ch = ; listnode * head; listnode * s, * r;
57 head = ( listnode * ) m alloc ( sizeof ( list node) ) ; if (! head ) {printf ( " ERROR" ) ; retur n N ULL ; head - > next = N ULL ; / *, * / while ( t < L & & ch! = \ n ) {scanf ( " % c", & ch ) ; t + + ; s = ( listnode * ) malloc ( sizeof (listnode) ) ; if (! s) {printf ( " ERROR" ) ; return N ULL ; s - > data = ch; if ( head - > next = = NULL) {head - > next = s; r = s ; / * */ else { r - > next = s; / * * r */ r = s; if ( r! = N ULL) r - > next = NULL ; / *, * / return head; linklist getnode ( linklist head, int i) { int j; listnode * p; p = head - > next ; if ( p = = N ULL p - > next = = NULL) printf ( " position error" ) ; if (i = = 1 ) {p = head; return p; j = 2; / * * / while ( p - > next! = N ULL& &j < i) { p = p - > next ; j + + ; if (i = = j) return p; else return N ULL ;
58 void insertlist (linklist head, char x, int i) { / * x head i */ listnode * p, * s; p = getnode ( head, i) ; if ( p = = N ULL p - > next = = NULL) printf ( " position error" ) ; if ( p = = N ULL) printf ( " error" ) ; s = (listnode * ) malloc ( sizeof (listnode) ) ; if (! s ) {printf ( " error" ) ; return ; s - > data = x; s - > next = p - > next; p - > next = s; void deletelist ( linklist head, int i) { / * head i */ listnode * p, * r; p = getnode ( head, i) ; if ( p = = N ULL p - > next = = NULL) printf ( " position error" ) ; r = p - > next ; p - > next = r - > next ; free ( r) ; void main ( ) { linklist headt, t = 0 ; int i, n, k = 0; char x, a [ stringsize] ; loop: printf ( " \ n" ) ; printf ( " * * * * * * * * * * * * * * * * * * * " ) ; printf ( " \ n \ n \ n" ) ; printf ( " 1 2 3 4 5 " ) ; printf ( " \ n \ n \ nn" ) ; printf ( " 0 \ n" ) ;
59 printf ( " * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * " ) ; printf ( " \ n \ n \ n" ) ; printf ( " : " ) ; scanf ( " % d", & n) ; printf ( " \ n" ) ; switch ( n ) { case 1: getchar ( ) ; printf ( " ( ) : " ) ; headt = set ( stringsize + 1) ; t = headt ; goto loop; case 2: printf ( " : " ) ; getchar ( ) ; scanf ( " % c% d", & x, &i) ; insertlist ( headt, x, i) ; goto loop; case 3: printf ( " : " ) ; scanf ( " % d", &i) ; deletelist ( headt, i) ; goto loop; case 4: t = headt ; t = t - > next ; k = 0; while (t! = N ULL ) { a [ k + + ] = t - > data ; t = t - > next ; for ( k = k - 1 ; k > = 0; k - - ) printf ( " % c", a [ k] ) ; goto loop; case 5: t = headt ; t = t - > next ; while (t! = N ULL ) { printf ( " % c", t - > data) ; t = t - > next ; ; goto loop; default : printf ( "!" ) ; break;
60 3 1. ( n - i + 1) 2. B 3. : (1 ) PUS H ( S, A), A S, ; A, 1 POP ( S ),, 1 (2 ) POP ( S ) A, ;, (3 ) ( 1) (2 ), S B 4. : 3, 2, 5, 6, 4, 1, 1, 5, 4, 6, 2, 3, 5 4, 2, 3, 5, 5, 4, 3, 2, ( ) 5, 4, 3, 2, 5, 4, 2, 3. 2, 2 3, 2 3, 1, 5, 4, 6, 2, 3 5. 2, 3, 1003 H 6. 7. 8. :, front, rear, ( ) m, rear = m ( rear = 0 ),,,, : (1 ), (2 ), :, ( ) ;,, front ;,,, 9. : tag 0, rear = front, tag 1 ;, rear = front, t ag 0, rear = front, tag, 1. : 1 ( n - 1 ) ;,
61 : int queuen umber ( in t i, linkqueue Q ) { if ( Q. rear = = Q. front ) return 0 ; if ( Q. rear > Q. front ) retur ( i = Q. rear - Q. front) else return ( ( Q. rear - q. front + n ) MOD n ) ; 2. :,,, i (i = 1, 2 ) (1 ) : void sharepush ( elementype ARRAY [1.. n], { int top1, top2, i ; scanf ( %d, &i) ; if ( (i < > 1) if (top1 + 1 < > top2) switch (i) { elementype x) & & (i < > 2) ) printf ( Input I error! ) ; case 1 : top1 = top1 + 1; V [top1 ] = x; break ; case 2: top2 = top2-1 ; V [ top2] = x; break ; else printf ( stack is full ) (2 ) : void sharepop ( elementype ARRAY [i.. n ] ) { int top1, top2, i ; elementype y ; scanf ( " %d", &i ) ; if ( (i < > 1 ) & & (i < > 2 ) ) printf ( " Input i error!" ) ; swicth ( i ) { case 1: if ( top1 < > 0) {y = V [top1] ; top1 = top1-1; break ; ; else printf ( " stack1 is empty" ) ; case 2: if ( top2 < > n + 1 ) { y = V [ top2 ] ; top2 = top2 + 1; else printf ( stack2 is empty ) ; 3. : (1 ),, :
62 void cycleset Queue ( lnode * r ea r) { rear = ( lnode * ) malloc ( sizeof (lnode) ) ; rear - > link = rear; ; (2 ), rear : void cycleinser tq ueue ( lnode * rear, elem en type x) { lnode p ; p = ( lnode * ) malloc ( sizeof ( lnode) ) ; p - > data: = x ; p - > link = rear - > link ; rear - > link = p; rear = p ; (3 ) ( ),, rear, : void cycledeleteq ueue ( l node * rear ) {lnode * p, * q; if ( rear - > link = = rear ) printf ( " T he queue is empty" ) ; else { p = rear - > lin k; q = p - > link; if ( q = = rear) rear = p; / /, p - > link = q - > link ; x = q - > data ; free ( q) ; 4. : Status Bracket _ Test (char * str ) / / { count = 0 ; for ( p = str ; * p ; p + + ) { if ( * p = = ( ) count + + ; else if ( * p = = ) ) count - - ; if ( count < 0 ) return ERROR ; if (count ) return ERROR ; / /
63 return O K; / / Bracket _ Test 5. : (1 ) : void queueinsert ( elementype ARRAY [0.. m - 1 ], elementype x ) {int rear, quelen ; if ( quelen = = m) printf ( OVERFLOW ) ; else { rear = ( rear + 1 ) MOD m; sequ [ rear ] = x; quelen = quelen + 1 ; (2 ) : void queuedelete ( elementype ARRAY [0.. m - 1] ) {int front, rear, quelen; if ( quelen = = 0 ) printf ( U NDERF LOW ) ; else { front = rear - quelen + 1; / / front ; 6. : if (front < 0 ) front = front + m; quelen = quelen - 1 ; R ETU RN ( sequ [front] ) ; # include" stdio. h" # include" stdlib. h" # define sqstack _ maxsize 6 / * 6 */ typedef struct sqst ack { char data [ sqstack _ maxsize] ; int top; sqstacktp; sqstacktp * set ( ) / * */ { sqstacktp * sp; sp = ( sqstacktp * ) malloc ( sizeof ( sqstacktp) ) ; if (! sp) printf ( " error " ) ; sp - > top = 0;
64 return sp; int pus h ( sqstacktp * sq, char x) { / * */ if ( sq - > top > sqst ack _ max size - 1) return (0 ) ; else { sq - > data [ sq - > top] = x; sq - > top + + ; return (1 ) ; int pop ( sqst acktp * sq, char * x ) { if ( sq - > top = = 0) return 0; else { sq - > top - - ; * x = sq - > data [ sq - > top] ; / / return ( 1) ; int emptystack ( sqstacktp * sq ) { if ( sq - > top = = 0) return ( 1) ; else return ( 0) ; / / void main ( ) { sqstacktp * sq; int i, n, p = 0 ;
65 char ch ; printf ( " \ n" ) ; loop: printf ( " \ n" ) ; printf ( " * * * * * * * * * * * * * * * * * * * * * " ) ; printf ( " \ n \ n \ n" ) ; printf ( " 1 2 3 4 5 " ) ; printf ( " \ n \ n \ n \ " ) ; printf ( " 0 \ n" ) ; printf ( " * * * * * * * * * * * * * * * * * * * * * * * * * * * * * " ) ; printf ( " \ n \ n \ n" ) ; printf ( " 1 - - 5: " ) ; printf ( " \ n" ) ; printf ( " \ n" ) ; scanf ( " % d", & n) ; getchar ( ) ; switch ( n ) { case 1: sq = set ( ) ; printf ( " \ n" ) ; printf ( "!" ) ; goto loop; case 2: printf ( " : " ) ; for (i = 0; i < sqstack _ maxsize; i + + ) { scanf ( " % c", & ch ) ; / * */ if ( push ( sq, ch) ) printf ( " % c! ", ch ) ; else {printf ( " error" ) ; goto loop ; printf ( " \ n" ) ; p = 1 ; goto loop; case 3: while (! emptystack ( sq) ) if (! pop ( sq, &ch ) ) printf ( " error" ) ; p = 0 ; printf ( " \ n" ) ; printf ( "!" ) ; goto loop; case 4: printf ( ", : " ) ; if (! p ) printf ( "!" ) ; while (! empty stack ( sq) )
66 { pop ( sq, &ch) ; printf ( " % c", ch) ; printf ( " \ n" ) ; goto loop; case 5: if ( p = = 1) { printf ( ", : " ) ; printf ( " \ n" ) ; for (i = 0; i < sqstack _ maxsize; i + + ) printf ( " % c ", sq - > data [i] ) ; printf ( " \ n" ) ; else { printf ( ", " ) ; goto loop; goto loop; default : printf ( "!" ) ; break; 7. :,,,, : 4, 2, 1, 3 4, 2, 3, 1 : 4, 1, 3, 2 4, 2, 3, 1 : ( 1) 4, 1, 3, 2 ( 2) 4, 2, 1, 3 ( 3) 4, 2, 3, 1
67 4 1. :, 0,,, 2. C 3. : J 1 2 3 4 s a a a b next [j] 0 1 2 3 J 1 2 3 4 5 6 7 next [j] 0 1 1 1 2 3 2 J 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 u a b c a a b b a b c a b a a c b a c b a Next [ j] 0 1 1 1 2 2 3 1 2 3 4 5 3 2 2 1 1 2 1 1 5 1. B. 2. B 3. B 4. C 5. D 6. C 1. : ( ) : loc (i, j, k ) = loc (c1, c2, c3 ) + [ (i - c1 ) ( d2 - c2 + 1 ) ( d3 - c3 + 1 ) ] + (j - c2) ( d3 - c3 + 1) + ( k - c3) ] * l =
68 100 + (4 * 9 * 7 + 2 * 7 + 5) * 3 = 913 2. : : loc [aj, j] = b + [ (j - 1 ) m + (i - 1) ] * l, b, m, l, b = loc [a1, 1 ] = 200, m = 10, l = 1 ; loc [a (6, 12 ) ] = 200 + [ ( 12-1) 10 + (6-1) ] 1 = 200 + 110 + 5 = 315 3. : n 2 < = i < = n - 1, ai, n - i, ai, n - i + 1, ai, n - i + 2,, : a2, n - 2 a2, n - 1 a2, n a3, n - 3 a3, n - 2 a3, n - 1... an - 1, 1 an - 1, 2 an - 1, 3 fir st, ( i - 1 ) 3 * (i - 2 ), ai, j, j - ( n - i), a2, n - 2 loc (a2, n - 2 ), ai, j : loc (ai, j ) = loc ( a2, n - 2 ) + 3 * (i - 2 ) + ( i + j - n) 2 < = i < = n - 1, n < = i + j < = n + 2 loc (ai, j ) = first + 3 * (i - 2) + (i + j - n) 4. 5, 3 5. : (1 ),, 3n - 2 ( ) : i = j + 1 k : k = (i - 1 ) * 3 i = j + 1 ; : i = j k : k = (i - 1 ) * 3 + 1 i = j : i = j - 1 k : k = (i - 1 ) * 3 + 2 i = j - 1, : k = 2 * (i - 1) + j (2 ) i, j k : i = [ k/ 3] + 1 j = [ k/ 3] + ( k mod 3) 6. : : 3 * n * 4 + P * 4 * : 4 * n * n : 3 * ( P + 1 ) * 4 7. : n ( n + 1) / 2
69 8. :, : (1 ) m * n m, n n * m ; (2 ) i j ; (3 ) : i j data 1 2 2 2 1 1 3 3 4 4 4 5 5 2 3 1. : : void mov ( real a [ n] ) ; { int i, j; i = 0; for (j = 1 ; j < = n; j + + ) {if ( a [j] < > 0) { i = i + 1; a [i] = a [j] ; if i < > j then a [j] = 0 2. : i j : (1 ) a [i], a [j], a [i] a [j], i = i + 1, j: = j - 1; (2 ) a [i], a [ j], i, j = j - 1; (3 ) a [i], a [j], j, i = i + 1; (4 ) a [i], a [ j], i = i + 1, j = j - 1; (5 ) j = j, a [i] a [j] : 1: void move (int a [ n] ) int c, i, j ; { i = 1; j = n; while ( i < j)
70 { while ( (a [i] mod 2) & & ( i < j) ) i = i + 1; while ( ( a [j] mod 2 = = 0) & & (i < j) ) j = j - 1; if (i < j) { c = a [i] ; a [i] = a [j] ; a [ j] = c; i = i + 1; j = j - 1 ; 2: void mov2 (int a [ 1.. n ] ) int i, j, c ; { i = 1; j = n; while ( i < j ) { if (a [ j] mod 2 = = 1 ) { c = a [j] ; a [ j] = a [i] ; a [i] = c; i = i + 1 else j = j - 1 ; 6 1. C 2. C 3. B 4. A 5. C 6. C 7. D 8. B 9. C 10. D 11. D 12. D 13. B 14. A 15. A 16. D 17. D 18. D 19. D 20. A 21. B 22. D 23. B 24. A 25. A 26. C
71 1. log2 n + 1 2. 2 k - 1, 2 k - 1, 2 log2 n 3. 501, 500, 0 4. n + 1 5. 13 6. 2N - 1 7. 8. p ltag = 0 9. 5 10. 81 11. 2 12. 6 13. 11 14. 2 * ( n0-1 ) 15. 10, 11, 2 16. n m? n m? n m? n m Y Y Y n m N N N n m y N N n m N U Y 1. : h, i, d, j, k, e, b, l, f, g, c, a 2. :
72 3. : 4. : 5. : : A B I F C M D E H : F I B C M A D E H 6. : : ; (1 ) 2, ;,, (2 ) : ( A),
73 ( B), ( C), 7. : N1 1, N2 2, N = N1 + N2 + M ( 1),,, B, N = B + 1 1 2, B = N1 + 2 * N2 : N = N1 + 2 * N2 + 1 ( 2) ( 1), (2 ) N1 + N2 + M = N1 + 2 * N2 + 1 N2 = M - 1 8. : (1 ),, ; ( 2 ), ( 3 ), (1 ). (2 ). (3 ). 9. : 10. : I ni, n, n = n0 + n1 + n2 ( ) n0 = n2 + 1 ( ) 1, n = n0 + 0 + n0-1 = 2n0-1 11. : (1 ) EBJKFG HICDA (2 )
74 12. : a : 11 b: 0110 c: 010 d: 10 f: 00 e: 0111 13. : (1 ) ABDFCEG H (2 ) 14. : 253 15. : ( 1) a b d e g c f h (2 ) 16. :
75 17. : (1 ) Leafhead F H G D (2 ), Leafhead ( ) 18. 19. : W = {2, 7, 4, 5, C: 110 A : 0 S: 111 T : 10 1. : int depth ( tree * T ) { if (! T ) retur n 0; else return 1 + max ( depth ( T Lchild), depth ( T Rchild) ) ; 2. :,,, 0, 1, S : void ancester s ( bt ree t, datat ype x) { top: = 0 ; W HILE ( t < > nil) A ND ( t - > da ta < > x ) OR ( top < > 0 ) { W HILE ( t < > nil) A ND ( t - > da ta < > x ) { top = top + 1; s [ top ]. p = t ; s [ top ]. tag = 0; { t = t - > lchild ; { IF ( t < > nil) AND ( t - > data = x) { FOR I: = 1 To top DO WRIT E ( s [ i]. p data ) ; / / x return; ELSE while ( (top > 0) AND ( S [ top]. tag = 1) ] top = top - 1; if ( top > 0 ) s [ top ]. tag = 1; {
76 t = s [ top]. p rchild [] 3. : void preorder (int a [ n] ) ; { Top: = 0; t : = 1; { W HILE ( ( t < = n) OR ( top > 0) ) { W HILE ( t < n ) { write ( a [ t] ) ; { top = top + 1; s [ top] : = t ; { t = 2 * t { I F ( top > 0 ) { t = s [ top] * 2 + 1; top: = top - 1 {, 4. : void inorder ( JD * bt) { int i = 0; JD * p, * s [ M] ; p = bt ; do { while ( p! = N ULL ) { s [ i + + ] = p; p = p - > lchild; if (i > 0) { p = s [ - - i] ; printf ( " % d \ t", p - > data) ; p = p - > rchild; while (i > 0 p! = N ULL) ; 5. : int leaf - number ( btree * t) { int num1, num2; if ( t = = nil) return (0 ) ; else if (t - > lchild = nil& & ( t - > rchild = nil) return (1 ) ; else retrn (leaf ( t - > child ) + leaf ( t - > lrchild) + 1 ) ;
77 6. : leaf ( t) t, : int leaf ( btree * t) { I F t = nil T HEN retur n (0 ) ; ELSE I F ( ( t - > lchild = nil) A ND ( t - > rchild = nil) ) return (1 ) ; ELSE retur n (leaf ( T - > lchild ) + leaf ( t - > rchild) ) ; 7. : void exchange ( bt ree t) ; { IF ( t < > nil ) { p = t - > rchild; t - > rchild = t - > lchild; t - > lchild = p; Exchange ( t - > lchild) ; Exchange ( t - > rchild ) 8. : void preorder ( btreeptr bt ) ; {Instack ( S ) ; Push ( S, bt ) ; WH ILE ( not empty ( S) ) { write ( gettop ( S) - > data) ; p = pop ( S ) ; I F ( p - > rchild < > nil ) push ( S, p - > rchild ) ; I F ( p - > lchild < > nil ) Pu sh ( S, p - > lchild) ; 9. : : boolen full ( btree t) { static int tag; I F ( ( t - > lchild = nil) A ND ( t - > rchild = nil) ) t ag = 1 ; ELSE IF ( ( t - > lchild = nil) OR ( t - > rhcild = nil) ) t ag = 0 ; ELSE tag = full (t - > lchild) A ND full ( t - > rhcild ) ; return t ag;
78 10. : void toparent ( pbitree * bt) { pbitree * p; if ( bt) { p = bt - > lchils ; if ( p) { p - > parent = bt ; toparent ( p ) ; p = bt - > rchild; if ( p) {p - > parent = bt ; toparent ( p ) ; 11. : void printdata ( bitree * bt, int x ) { if ( bt) { if ( bt - > key > = x) printf ( x) ; print ( bt - > lchild) ; print ( bt - > rlchils ) ; : p - > data = item p = t q - > lchild = p top < > 0 7 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.
79 1. 0; n ( n - 1) / 2; 0; n ( n - 1) ; n ( n - 1) / 2; n ( n - 1 ) 2. O ( n + e) ; O ( n + e) ; O ( e) ; O (e) 3. n - 1 4. ; ; n - 1; 5. O ( n * n) ; O ( eloge) 6. O ( n + e) 7. n, 2e 8. 9. 2 10. 11. 12. 0 1 13. 15 14. n - 1 15. 16. 17. ( 2, 4 ) 10, (4, 1) 6, (1, 0) 3, (0, 3) 5, (4, 6) 8, (4, 7) 12, ( 3, 5 ) 15 18. n - 1, n ( n - 1 ) / 2 19. e, 2e 20. abefcdg 21. O ( n * n) 22. 12 23. 1. C 2. O ( n + e) 3. A 4. C 5. A 6. D 7. A 8. 9. B 10. C 11. A 12. D 13. B 14. C 15. C 16. C 17. D 1. : : n = 1, 0, n = 2, 1, n = 1, 2,.., k, n = k, k ( k - 1 ) / 2, n = k + 1,, k, k ( k - 1 ) / 2,,,, k ( k - 1) / 2 + k = k ( k + 1 ) / 2 = ( k + 1) [ ( k + 1 ) - 1] / 2, k + 1,, n n ( n - 1 ) / 2 : n, n - 1, n - 1,, n - 2 n - 2,... n - 1 n 1, ( n - 1) + ( n - 2 ) + ( n - 3) + + 2 + 1 = n ( n - 1 ) / 2, 2. : n = 2, G, n = 3, 4,, k, n = k, G k - 1 G, G k + 1,
80 G k, k - 1 P k, P G P k, P G k + 1 k, n = k + 1 3. : (1 ) (2 ) i, j A [i, j] < > 0, A [j, i] < > 0 (3 ) i i 4. : AOE,, ; AOE,,. 5. : : A C D F B E H G 6. : e [i] 1 [ i] :
81 Ve v1 V1 0 0 V2 3 3 V3 2 4 V4 5 7 V5 11 11 V6 9 14 V7 20 20 Ei li a1 0 0 a2 0 2 a3 2 6 a4 3 3 a5 2 4 a6 2 7 a7 5 7 a8 5 12 a9 11 11 a10 9 14 7. : 8. :
82 9. : 10. : 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0 : 1 4 6 5 3 2 : 1 4 3 2 6 5
83 11. : 0, 2, 5, 1, 4, 3, 6, 7, 8 12. : 2, 0, 5, 2, 1, 4, 3, 6 13. : (2 ) abdce ; abedc 14. : (1 ) : : (2 ) :
84 15. : 7) 20 16. : ( 0, 3 ) 2, ( 4, 6 ) 4, ( 0, 2 ) 5, ( 1, 5 ) 6, ( 0, 1 ) 8, ( 3, 6 ) 10, ( 5, 17. : ( 1) (2 ) : (0, 3) 2 (0, 2) 5 (0, 1) 8 (1, 5) 6 (3, 6) 10 ( 6, 4 ) 4 ( 5, 7 ) 20 (3 ) : 0 1 2 3 4 5 6 0 0 0 1 3 6 7 3 2 1 5 6 4 7 2 5 8 6 10 4 20 (3 ) 55 9. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
85 21. 22. 23. 24. 1. D 2. A 4. B 5. D 8. C 9. B 10. C 12. D 13. C 14. D 15. D 1. 5 2. 3. 4. 2 5. ( 10000 + 1 ) / 2 6. 5 7. H ( key) + di ( di = 1, 2, 3,, m - 1 ) ; 8. 1, 3 9. 2 1. 4 10. 11. 12. 4 13. 2 h - 1, 2 h - 1 1. : B -, 2. :, ( ), ( ) : (1 ) ( n + 1 ) / 2 (2 ) ( n + 1) n log2 ( n + 1 ) - 1 (3 ), 1/ 2 ( n/ s + s ) + 1;, log2 ( n/ s + 1 ) 3. : (1 ) : int sequsearch (int a [ n] ; int k ) { A [ n ] = k ; i = 0 ; while (a [i] < k ) i = i + 1; return (i mod ( n + 1) ) ; (2 ) : ASL s ucc = 1/ n i = ( n + 1) / 2 : ASLun succ = ( n + 1) + s/ 2
86 4. : ASL = 1/ 10 ( 1 * 1 + 2 * 2 + 3 * 4 + 4 * 3 ) = 1/ 10 ( 1 + 4 + 12 + 12 ) = 29/ 10 = 2. 9 5. : = / = ( 1 + (1/ (1 - ) ) / 2, : 225 6. : : 7. : 8. : (1 ) : (2 ) : 8/ 5
87 9. : 8, 10, 14, 19, 21, 23, 28, 32 8 1 5 1 3 5 1 5 10. : : : : 12 24 45 53 90 11. : : :
88 : (1 + 2 * 2 + 4 * 3 + 5 * 4 ) / 12 : (1 + 2 * 2 + 3 * 3 + 4 * 4 + 2 * 5 ) / 12 A VL : ( 14 )
89
90
91 12. : 0 1 2 3 4 5 6 7 8 9 10 11 12 14 1 68 27 55 19 20 84 79 23 11 10 1 2 1 4 3 1 1 3 9 1 1 3 H (19) = 19 MOD 13 = 6 H (14) = 14 MOD 13 = 1 H ( 23 ) = 23 MOD 13 = 10 H ( 01 ) = 01 MOD 13 = 1 ( ) H ( 01 ) = ( 01 + 1) MOD 13 = 2 H ( 68 ) = 68 MOD 13 = 3 H (20) = 20 MOD 13 = 7 H (84) = 84 MOD 13 = 6 ( ) H (84) = (6 + 1) MOD 13 = 7 ( ) H (84) = (7 + 1) M OD 13 = 8 H (27) = 27 MOD 13 = 1 ( ) H (27) = (1 + 1) MOD 13 = 2 ( ) H (27) = (2 + 1) MOD 13 = 3 ( ) H (27) = (3 + 1) M OD 13 = 4 H (55) = 55 MOD 13 = 3 ( ) H (55) = (3 + 1) MOD 13 = 4 ( ) H (55) = (4 + 1) M OD 13 = 5 H (11) = 11 M OD 13 = 11 H (10) = 10 MOD 13 = 10 ( ) H (10) = (10 + 1 ) MOD 13 = 11 ( ) H (10) = (11 + 1 ) MOD 13 = 12 H (79) = 79 MOD 13 = 1 ( ) H (79) = (1 + 1) MOD 13 = 2 ( ) H (79) = (2 + 1) MOD 13 = 3 ( ) H (79) = (3 + 1) MOD 13 = 4 ( ) H (79) = (4 + 1) MOD 13 = 5 ( ) H (79) = (5 + 1) MOD 13 = 6 ( ) H (79) = (6 + 1) MOD 13 = 7 ( ) H (79) = (7 + 1) MOD 13 = 8 ( ) H (79) = (8 + 1) M OD 13 = 9 : ASLs uc = 1/ 2 (1 * 6 + 2 * 1 + 3 * 3 + 4 * 1 + 9 ) = 30/ 12 = 2. 5
92 : ASLun suc = 1/ 13 (1 + 2 + 3 + 4 + 5 + 13 ) = 7 : ASLs uc = 1/ 12 ( 1 * 6 + 2 * 4 + 1 * 3 + 1 * 4 ) = 21/ 12 = 1. 75 : ASLun suc = 1/ 13 (7 * 1 + 5 + 3 * 3 + 2 * 2 ) = 25/ 13 = 1. 9 13. :
93 : 32 13 49 18 22 38 21 1 1 1 2 1 1 2 : r [l : h], K,,, 0, : int bnsrch (int l, int h, datatpe k ) { if 1 > h then return ( 0) { else [ MID = ( l + h ) div 2 ; case { r [ mid]. key = k; return ( MID) ; { r [ mid ]. key < k ; return ( bn srch ( mid + 1 ), h, k ) ; r [ mid ]. key > k ; return ( bn srch (l, mid - 1, k) ) ; ] 10 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 1. B 2. A 3. C 4. B 5. B 6. A 7. C 8. A 9. A 10. C 11. B 12. A 13. B 14. C 15. A 16. A 17. C 18. B 19. B 1. 2. n ( n - 1) / 2-1 3. 3 4. n - 1 5. O ( nlog2 n )
94 6. 75, 66, 48, 29, 31, 27 7. 48, 44, 52, 63, 80, 91 8. 9. 10. n - 1 11. 12. 13. n ( n - 1 ) / 2 14. O (log2 n ) 15. 13, 27, 38, 97, 76, 65, 49, 50 1. :,,, Ki = Kj ( i, j = 1, 2 n, i j ), Ri Rj, ;,, Rj Ri, 2. :,, 3. :,,, shell,, 10 10, 4. : (3 )
95 5. : : [17, 18, 60, 40, 7, 32, 73, 65, 85 ] : [17, 18, 40, 7, 32, 60, 65, 73, 85 ] : [17, 18, 7, 32, 40, 60, 65, 73, 85 ] : [17, 7, 18, 32, 40, 60, 65, 73, 85 ] : [7, 17, 18, 32, 40, 60, 65, 73, 85 ] : [7, 17, 18, 32, 40, 60, 65, 73, 85 ], 6. : : 54, 38, 96, 23, 15, 72, 60, 45, 83 48 38 15 23 54 72 60 96 83 : 48 38 15 23 : 23 38 15 48 : 23 38 15 : 15 23 38 : 72 60 96 83 : 60 72 96 83 : 96 83 : 83 96 : 15 23 38 48 54 60 72 83 96 7. : : 5 16 23 94 61 72 58 1 : 16 58 23 94 61 72 5 2 : 23 58 72 94 61 16 5 3 : 58 61 72 96 23 16 5 8. : (1 ) : Merge ( r, 1, 1, 2 ) (2 ) ; Merge ( r, 3, 3, 4) (3 ) ; Merge ( r, 1, 2, 4) (4 ) ; Merge ( r, 5, 5, 6) (5 ) ; Merge ( r, 7, 7, 8) :
96 9. : 1, 12, 4, 31, 30, 5, 20, 66, 61, 200, 70, 80, 150, 44, 28 10. : [ 36 38 40 40 46 56 79 80 ] [ 25 66 75 84 ] 11. : [ 40 34 25 38 ] 46 [ 80 56 79 ] 12. : ( 59, 56, 30, 38, 35, 20, 18, 25 ) 13. : ( 50, 42, 46, 38, 40, 56, 79, 84 ) 14. : ;
97 15. :, 16. : 1 13 38 27 49 97 65 50 76 2 27 38 50 49 97 65 76 13 3 38 49 50 76 97 65 27 13 4 49 65 50 76 97 38 27 13 5 50 65 97 76 49 38 27 13 6 65 76 97 50 49 38 27 13 7 76 97 65 50 49 38 27 13 8 97 76 65 50 49 38 27 13 17. : : 65 5 71 23 16 72 94 73 : 16 5 23 65 71 72 73 94 : 5 16 23 65 71 72 73 94 : (1 ) (2 ) R [ n + 1 ] : (1 ) p = L - > next (2 ) q - > data < p - > data (3 ) min! = p (4 ) p = p - > next ( ) 1. n, 2 * e 2. 0; n ( n - 1) / 2; 0; n ( n - 1) ; n ( n - 1) / 2; n ( n - 1 ) 3. n - 1 4. ; ; n - 1; 5. ; ; ; 6. () LOC (i, j, k ) = LOC (c1, c2, c3) + [ (i - c1) ( d2 - c2 + 1 ) ( d3 - c3 + 1 ) ] + (j - c2) ( d3 - c3 + 1 ) + ( k - c3 ) * l = 100 + (4 * 9 * 7 + 2 * 7 + 5) * 3 = 913
98 7. 2, 3 ; 1003 H 1. A 2. C 3. A 4. B 5. C 6. A 7. B 8. C 9. C 10. B 1. 2. 3. 4. 1. va. elem [i] > x & &i > = 0 2. ( t - > Lchild) ( t - > rchild) 3. he1 + 1 he2 + 1 4. L. r [i]. key 1. : N1 1, N2 2, N = N1 + N2 + M ( 1),,, B, N = B + 1 1 2, B = N1 + 2 * N2 N = N1 + 2 * N2 + 1 ( 2) ( 1), (2 ) N1 + N2 + M = N1 + 2 * N2 + 1 N2 = M - 1 2. : ( a),, ; ( b ), ( c), (a) ( b ) (c) 3. : : abdce : abedc
99 ( ) 1. 3 2. ( n - i + 1 ) 3. d0 + 2 2 4. : LOC [aij] = b + [ (j - 1) m + ( I - 1 ) ] * L b, m, L, b = LOC [ a11] = 200, m = 10, L = 1, LOC [ A (6, 12 ) ] = 200 + [ ( 12-1) 10 + (6-1) ] * 1 = 200 + 110 + 5 = 315 5. log2 n + 1 6. 2 ( K - 1 ), 2 K - 1 1. B 2. B 3. C 4. C 5. A 6. B 7. A 1. 2. 3. 4. 1. leaf - number ( t - > Lchild) + leaf - number (t - > rchild) + 1 2. i > ST. length 3. count 1. : n = n0 + 0 + n0-1 = 2n0-1 2. : 0 0 ^ 1 1 14 1 27 79 ^ 2 2 ^ 3 3 68 55 ^ 4 4 ^ 5 5 ^ 6 6 19 84 ^ 7 7 20 ^ 8 8 ^
100 9 9 ^ 10 10 23 10 ^ 11 11 11 ^ 12 12 ^ 3. : : 51 28 38 86 70 90 7 30 40 25 d = 5 51 7 30 40 25 90 28 38 86 70 d = 3 28 7 30 40 25 86 51 38 90 70 d = 1 7 25 38 30 38 40 51 70 86 90 : (1 ) (2 ) I, j A [ I, j] < > 0, A [ j, i] < > 0 (3 ) I I