《数据结构试卷一参考答案3199Datastructuretestpaperarefertoanswer3199》由会员分享，可在线阅读，更多相关《数据结构试卷一参考答案3199Datastructuretestpaperarefertoanswer3199（34页珍藏版）》请在金锄头文库上搜索。
1、数据结构试卷(一)参考答案3199（Data structure test paper (a) refer to answer 3199）17, read a good book, like making a good friend - CangkejiaData structure test paper (a) reference answersFirst, the multiple-choice questions (2 points per game, 20 points)1.A, 2.D, 3.D, 4.C, 5.C, 6.D, 7.D, 8.C, 10.A, 9.DTwo, fill
2、 in the blanks (1 points per minute, 26 points)1. accuracy, readability, robustness, efficiency2. O (n)3.9334. -1 34 X * + 2 Y * 3 / -5. 2n n-1 n+16. e 2e7. directed acyclic8. n (n-1) /2 n (n-1)9. (12, 40) () (74) (23,55, 63)10. increase by 111. O (log2n) O (nlog2n)12. mergeThree, the calculation qu
3、estions (6 points per game, 24 points)1. linear tables are: (78, 50, 40, 60, 34, 90)2. adjacency matrix:The adjacency table is shown in figure 11:Figure 113. the minimum spanning tree obtained by the Kruskal algorithm is:(1,2) 3, (4,6) 4, (1,3) 5, (1,4) 8, (2,5) 10, (4,7) 20;4. see Figure 12Figure 1
4、2Four, read algorithm (7 points per game, a total of 14 points)1. (1) query the tail node of the list(2) link the first node to the tail of the list as the new tail node(3) the returned linear tables are (A2, A3,., an, A1)2. recursive traversal chain storage of two fork treeFive. Fill in the blanks
5、(2 cents per minute, 8 points each)True BST-left BST-rightSix, write algorithms (8 points)Int CountX (LNode*, HL, ElemType, x)int i=0; LNode* p=HL; /i is counterWhile (P, =NULL)if (P-data=x) i+;P=p-next;/while, when the loop is out, the value in I is the number of X nodesReturn i;/CountXData structu
6、re test paper (two) reference answerFirst, the multiple-choice question1.D, 2.B, 3.C, 4.A, 5.A, 6.C, 7.B, 8.CTwo. Fill in the blanks1. construct a good HASH function and determine the solution to the conflict2. stack.top+, stack.sstack.top=x3. order4. O (N2), O (nlog2n)5. N0-1, 2N0+N16. d/27. (31, 3
7、8, 54, 56, 75, 80, 55, 63)8. (1, 3, 4, 5, 2), (1, 3, 2, 4, 5)Three. Application questions1. (22, 40, 45, 48, 80, 78), (40, 45, 48, 80, 22, 78)2. q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q;3.2, ASL=91*1+2*2+3*4+4*2) =25/94. tree chain storage structure slightly, two fork tree slightly5. E
8、=(1, 3), (1, 2), (3, 5), (5, 6), (6, 4)6.Four, algorithm designThe 1. is provided with a set of initial record key sequence (K1, K2,., Kn), required to design an algorithm to O (n) time complexity in the linear table is divided into two parts, the left part of each keyword is less than Ki, the right
9、 part of each keyword were less than KiVoid QuickPass (int, r, int, s, int, t)Int, i=s, j=t, x=rs;While (ij) While (ix) j=j-1 if (ij); ri=rj; i=i+1;While (ij and rix) i=i+1 if (inext)for (q=hb; Q; =0; q=q-next) if (q-data=p-data) break;If (Q, =0) t= (lklist *) malloc (sizeof (lklist); t-data=p-data;
10、 t-next=hc; hc=t;Data structure test paper (three) reference answerFirst, the multiple-choice question1.B, 2.B, 3.A, 4.A, 5.A6.B, 7.D, 8.C, 9.B, 10.DAnalysis of third questions: first using the successor node pointer variable B Q to node A, then the node B value is copied to the A node, finally dele
11、te the node BNinth item analysis: 9 quick sort, merge sort and insertion sort must wait until the entire order after the end to be able to calculate the number of the smallest of the 10, but only in the initial heap sort based on the heap and then a 10 screening can, each screening, the time complex
12、ity is O (log2n)Two. Fill in the blanks1. sequential storage structure, chain storage structure2.95013.54. degrees of penetration56. e=d7. in Preface8.79. O (1)10. i/2, 2i+111. (5, 16, 71, 23, 72, 94, 73)12. (1, 4, 3, 2)13. j+1, hashtablej.key=k14. return (T), t=t-rchildEighth questions: two search
13、process analysis can be used to describe a two binary tree, the two fork tree called the two binary decision treeWhen performing two - point lookups on an ordered table, the lookup length is not more than two forks, and the height of the decision tree is 1+log2nThree. Calculation questionsOne2, H (36), =36, mod, 7=1, H1 (22) = (1+1), mod, 7=2,. ConflictH (15) =15, mod, 7=1,. Conflict H2 (22) = (2+1) mod 7=3;H1 (15) = (1+1) mod 7=2;H (40) =40 mod 7=5;H (63) =63 mod 7=0;H (22) =22, mod, 7=1,. Conflict(1) 0123456Sixty-th
