《数据结构试卷(一)参考答案3199（Data structure test paper (a) refer to answer 3199）.doc》由会员分享，可在线阅读，更多相关《数据结构试卷(一)参考答案3199（Data structure test paper (a) refer to answer 3199）.doc（35页珍藏版）》请在三一文库上搜索。
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 (3
14、6), =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-threeThirty-sixFifteenTwenty-twoForty(2) ASL=3, (8,9,4,3,6,1), 10, (12,18,18)(1
15、,6,4,3) 8, (9), 10,12, (18,18);1, (3,4,6), 8,9,10,12,18, (18)1,3, (4,6), 8,9,10,12,18,181,3, 4,6,8,9,10,12,18,18Four, algorithm design1. design in the single list to delete the same value of redundant nodes algorithmTypedef int datatype;Typedef, struct, node, datatype, data; struct, node, *next;lkli
16、st;Void delredundant (lklist *&head)Lklist, *p, *q, *s;For (p=head; p; =0; p=p-next)For (q=p-next, s=q, Q, =0;)If (q-data=p-data) s-next=q-next; free (q); q=s-next;Else, s=q, q=q-next;2. design a node X in the two fork tree in the parent node algorithmTypedef, struct, node, datatype, data; struct, n
17、ode, *lchild, *rchild; bitree;BiTree *q20; int, r=0, f=0, flag=0;Void preorder (BiTree, *bt, char, x)If (BT =0 & & flag=0!)If (bt-data=x) flag=1; return;Else r= (r+1)% 20; qr=bt; preorder (bt-lchild, x); preorder (bt-rchild, x)Void parent (BiTree, *bt, char, x)Int i;Preorder (BT, X);For (i=f+1; ilch
18、ild-data=x | qi-rchild-data) break;If (flag=0) printf (not found xn);Else if (idata); else printf (not parent);Data structure test paper (four) reference answerFirst, the multiple-choice question1.C, 2.D, 3.D, 4.B, 5.C6.A, 7.B, 8.A, 9.C, 10.ATwo. Fill in the blanks1. O (N2), O (nlog2n)2. pllink-rlin
19、k=p-rlink; p-rlink-llink=p-rlink3.34. 2k-15. n/26.50, 517. M-1, (R-F+M)%M8. n+1-i, n-i9. (19, 18, 16, 20, 30, 22)10. (16, 18, 19, 20, 32, 22)11. Aij=112. equals13. BDCA14. hashtablei=0, hashtablek=sThree. Calculation questionsOneTwo(1) ABCDEF; BDEFCA; (2) ABCDEFGHIJK; BDEFCAIJKHG forest is converted
20、 to a corresponding two fork tree;3.H (4) =H (5) =0, H (3) =H (6) =H (9) =2, H (8) =3, H (2) =H (7) =6Four, algorithm design1. in a single list of data elements only three characters (letters, numbers and other characters), using the original node space in a single list designed three single table a
21、lgorithm, so that each single list contains only the similar characterTypedef char datatype;Typedef, struct, node, datatype, data; struct, node, *next;lklist;void split (lklist * good, lklist * & * & lklist ha, hb, lklist * & hc)lklist * p = 0; ha, hb, hc = 0 = 0,;for (p = good; p! = 0; p = good)goo
22、d = p - next; p - next = 0;if (p - data = a & & p - data next = ha ha = p;else if (p - data = 0 & & p - data next = hb; hb = p; else p - next = hc, hc = p;2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法typedef struct node int data, lchild struct node *, * rchild bitree;void swapbitree (bitree * bt)bitree * p;if (bt
23、= = 0) return;swapbitree (bt - lchild); swapbitree (bt - rchild);p = bt - bt - lchild; lchild = bt - bt - rchild; rchild = p;3. 在链式存储结构上建立一棵二叉排序树# define n 10typedef struct node int key; struct node * * rchild lchild, bitree;void bstinsert (bitree * & bt, int key)if (bt = = 0) bt = (bitree *) malloc
24、 (sizeof (bitree); bt - key = key; lchild = bt bt - - rchild = 0;else if (bt - key key) bstinsert (bt - lchild, key); else bstinsert (bt - rchild, key);void createbsttree (bitree * & bt)int i;for (i = 1, i = n; i + +) bstinsert (bt, random (100);参考答案 数据结构试卷 (五)一、选择题2 (b), 3 (1a, 4a, 5. d7 (b 8.b 9.c
25、 10.c 6. b二、填空题1. top1 + 1 = top22. 可以随机访问到任一个顶点的简单链表3. i (i + 1) / 2 + (j - 14. filo, fifo5. abdecf, dbeafc, debfca6. 8,647. 出度, 入度8. k2i & & ki ki = c三、应用题1. debca2. e = (1,5), (5.2), (5.3), (3,4), w = 103. asl = (1 * 1 + 2 + 3 * 4 * 2 = 17 / 7 / 7)4. asl1 = 7 / 6, asl2 = 4 / 3四、算法设计题1. 设计判断两个二叉树是
26、否相同的算法typedef struct node datatype data; struct node * * rchild lchild, bitree;int judgebitree (bitree bitree * * bt1, bt2)if (bt1 = = 0 & & bt2 = = 0) return (1);else if (bt1 = = 0 = = 0 | | | bt2 | bt1 - data! = bt2 - data) return (0);else return (judgebitree (bt1 and bt2 - lchild, lchild judgebit
27、ree (bt1) * - rchild, bt2 - rchild);2. 设计两个有序单链表的合并排序算法void mergelklist (lklist * ha * * & lklist lklist hb, hc)lklist * s = hc = 0;while (! ha ha ha! = 0 & & hb. = 0)if (ha, hb - data data) if (s = = 0) hc = s = ha; else s - next = ha, s = = ha ha ha; - next;else if (s = = 0) = s = hb, hc; else s -
28、 next = s = hb; hb; hb = hb; - next;if (ha = = 0) - next = hb; else s - next = ha;参考答案 数据结构试卷 (六)一、选择题2 (a) 1.d 5. d 4a, 3a9.c 10.b 6.d 7 (b 811.c 14.d 15.b 13.b 12a二、判断题1.错 2.对 3.对 4.对 5.错6.错 7.对 8.错 9.对 10.对三、填空题1. o (n)2. s - next = p - next; p - next = s3. (1,3,2,4,5)4. n - 15. 1296. f = = r7. p
29、 - lchild = = 0 & & p - rchild = = 08. o (n2)9. o (nlog2n), o (n)10. 开放定址法, 链地址法四、算法设计题1. 设计在顺序有序表中实现二分查找的算法key struct record int; int others;int bisearch (struct record r , int k)int = 0，中间，高= n-1；同时（低 K）高=中叶1；其他低=中+ 1；返回（0）；2。设计判断二叉树是否为二叉排序树的算法国际minnum = 32768，= 1旗； int关键结点；结点左右* rchild；二叉树；中序遍历（b
30、itree * BT）如果（bt）！= 0）序（BT -左右）；如果（minnum BT -键）旗= 0；minnum = BT -关键；为了（BT - rchild）；三.在链式存储结构上设计直接插入排序算法无效straightinsertsort（lklist *和头）lklist *，*，*问；int t；如果（头= = 0 | |头-下= = 0）返回；其他为（q =头，P =头-下）；P！= 0；P = q -下一步）为（s =头）！= Q 下；S = S -下）如果（S数据磷数据）打破；如果（s = q -下一）；否则，下一行；下一行；下一行；下一行；下一行；数据结构试卷（七）一、
31、选择题1 B 2 B 3 C 4 B 5 B。6，7，C，8，C，9，B，10，D。二、判断题1。对2。对3。对4。对对5。6。对7。对8。错9。错错10。三、填空题1。s =左，右，右2。n（n-1），n（n-1）2三.n / 24。开放定址法，链地址法5。十四6。2h-1,2h-17。（12,24,35,27,18,26）8。（12,18,24,27,35,26）9。五10。我 J & R 我，我 下= = 0）返回；对于（q =头；Q）！= 0；q = q -下一步）min = q =数据；对于（pq）下一个；p！= 0；P = P - 下）如果（minP数据） min = P -数据；
32、S = P；如果（S！= q）2。设计在顺序存储结构上实现求子串算法空字符串（char的 ，开始，长数、字符T ）我，J，长度= strlen（s）；如果（启动长度）printf（“副本的位置是错误的”）；如果（开始+ count-1 长度）printf（“字符被复制”）；对于其他（i = 1，j = 0；i 关键= = x）返回；否则如果（BT -键 X）水平（BT -左右，x）；其他层次（BT - rchild，x）；数据结构试卷（八）参考答案一、选择题1 C 2 C 3 C 4 B 5 B。6 C 7 B 8 C 9 A A 10。二、判断题1。对2。错3。对4。错错5。6。对7。对8。
33、对9。对对10。三、填空题1。（49,13,27,50,76,38,65,97）2。T =（bitree *）malloc（sizeof（二叉树），bstinsert（t rchild，K）三.p =下一个4。头- rlink，P左链域5。计算机辅助建筑设计6。167。零8。（13,27,38,50,76,49,65,97）9。N-110。五十四、算法设计题1。设计一个在链式存储结构上统计二叉树中结点个数的算法无效countnode（bitree * BT，int和计数）如果（bt）！= 0）计数+ +；countnode (bt - lchild, count); countnode (bt
34、 - rchild, count);2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法typedef struct int vertex m; int edge m m; gadjmatrix;typedef struct node1 int info; int adjvertex; struct node1 * nextarc glinklistnode;typedef struct node2 int vertexinfo; glinklistnode * firstarc glinkheadnode;void adjmatrixtoadjlist (gadjmatrix g1 g2
35、 glinkheadnode , )int i, j; glinklistnode * p;for (i = 0; i = n - 1; i + +) g2 .firstarc = 0;for (i = 0; i = n - 1; i + +) for (j = 0 and j adjvertex = j;p - nextarc = g i.firstarc; g i.firstarc = p;p = (glinklistnode *) malloc (sizeof (glinklistnode); p - adjvertex = i;p - nextarc = g j.firstarc; g
36、 j.firstarc = p;数据结构试卷 (九) 参考答案一、选择题a 3 4.c 5.d mobility6.d 7.c 8.b 9.c 10.a11.c 12.c 13.d 14.a 15.a二、填空题1. p - next, d - date2. 503. m - 14. 6.85. 快速, 堆6. 19 / 77. cbda8. 69. (24,65,33,80,70,56,48)10. 8三、判断题1.错 2.对 3.对 4.对 5.错6.错 7.对 8.对 9.错 10.对四、算法设计题1. 设计计算二叉树中所有结点值之和的算法void sum (bitree * bt, in
37、t & d)if (bt! = 0) s = s + bt - date; sum (bt - lchild, d) sum (bt - rchild, d);2. 设计将所有奇数移到所有偶数之前的算法void quickpass (int r , int s, int t)int i = s j = t, x = r d.while (i j)while (i j & r j% 2 = = 0) j = j - 1; if (i j) r i = r j; i = i + 1while (i j & r i% 2 = = 1) = i + 1; if (i next = = 0) retur
38、n (1); for (q = head, p = head - next; p! = 0; q = p, p = p - next) if (q - date p - date) return (0);return (1);数据结构试卷 (十) 参考答案一、选择题mobility 2.d 3.b 4.b 5 6.d7.a 8.d 9.d 10.c 11.b 12.d二、填空题1. 4.102. or (nlog2n), o (n2)3. n4. 1.25. n (m-1) + 16. q - next7. 线性结构, 树型结构, 图型结构8. o (n2) or (n + e)9. 8 / 3)10. (38,13,27,10,65,76,97)11. (10,13,27,76,65,97,38)12. 12465313. struct node * rchild, bt = 0, createbitree (bt - lchild)14. lklist, q = p三、算法设计题1. 设计在链式存储结构上合并排序的算法void mergelklist (lklist * *, lklist hb, lklist * & hc)lklist * s = hc =