1、北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第1頁Final examination2009 FallData Structure and Algorithm DesignClass: _ Stude nt Number: _ Name: _Teacher_No.123456789TotalMark1.Si ngle-Choice(20 poi nts)Con sider the follow ing defi niti on of a recursive fun cti on ff. int ff( int n ) if( n = 0 ) return 1;return 2 * ff(

2、n - 1 );If n 0, what is returned by ff( n )?_2n(a) log2n (b) n (c) 2(d) 2 * n(2) An input into a stack is like 1,2,3,4,5,6. Which output is impossible? _ .a. 2,4,3,5,1,6b.3,2,5,6,4,1c.1,5,4,6,2,3d.4,5,3,6,2,1(3) Which of the following data structures uses a Last-in, First-out policy for element inse

3、rtionand removal? _(a) Stack (b) Tree(c) Hash table (d) Queue(4) If deleting the ith key from a contiguous list with n keys, _keys need to be shifted leftone positi on.a. n-ib. n-i+1c. i d. n-i-1(5) Sorting a key sequence(28,84,24,47,18,30,71,35, 23), its status is changed as follows.23,18,24,28,47,

4、30,71,35,8418,23,24,28,35,30,47,71,8418,23,24,28,30,35,47,71,84The sorting method is called_(a),select sorting(b).Shell sorting(c).merge sorting(d).quick sorting(6) The nu mber of keyword in every node except root in a B- tree of order 5 is _ _ _ at leasta. 1b. 2c. 3d. 4北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第2頁(7

5、) When sorting a record sequenee with multiple keys using Least Significant Digit method, thesort ing algorithm used for every digit except the least sig ni fica nt digit _ .a. must be stable b. must be un stablec. can be either stable or un stable(8) In the followi ng four Binary Trees, _ is not a

6、complete Bi nary Tree.(9) The maximum nu mber of no des on level i of a binary tree is _ .i-1iia.2b. 2ic.2d.2-1(10) If the Bi nary Tree T2 is tran sformed from the Tree T1, the n the postorder traversal seque neeof T1 is the _traversal seque nee of T2.a. preorderb. ino rderc. postorderd. level order

7、(11) In the following sorting algorithm, _ is an unstable algorithm.a. the in serti on sort b. the bubble sort c. quicksort d. mergesort(12) In order to find a specific key in an ordered list with 100 keys using binary search algorithm,the maximum times of comparis ons is _ .a. 25b.10c. 1d.7(13) The

8、 result of travers ing ino rderly a Binary Search Tree is a(a n) _ order.a. desce nding or asce ndingb. desce ndingc. asce nding d. disorder(14) To sort a key seque nee in asce nding order by Heap sort ing n eeds to con struct a _ heap.(a) min (b) max (c) either min or max (d)complete binary tree(15

9、) . Let i, 1i1, then the parent of this element has been assigned the number _i/2.(b) If 2in, then this element has no left child. Otherwise its left child has been assigned thenu mber 2 i.(c) If 2i+1n, then this elementhas no right child. Otherwise its right child has beenassig ned the nu mber 2i+1

10、.(d) The height of the binary tree is Iljog2(n + 1)(16) . Con sider the followi ng C+ code fragme nt.x=191;y=200;while(y0)if(x200)x=x-10;y-;else x+;What is its asymptotic time complexity? _23(a) O(1)(b) O( n)(c) O( n) (d) O( n)北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第3頁(17) In a Bi nary Tree with n no des, there ar

11、e _ non-empty poi nters.a. n-1b. n+1c. 2n-1d.2 n+1(18) In an undirected graph with n vertices, the maximum number of edges is _.2a. n(n+1)/2b. n(n-1)/2c. n(n-1)d.n(19) Assume the preorder traversal sequenee of a binary tree T is ABEGFCDH, the inordertraversal sequenee of T is EGBFADHC, then the post

12、order traversal sequenee of T will be.a. GEFBHDCA b. EGFBDHCA c. GEFBDHCA d. GEBFDHCA(20) The binary search is suitable for a(an) _ list.a. ordered and con tiguousb. disordered and con tiguousc. disordered and lin kedd. ordered and lin kedan swer:12345678910ccaadbacab11121314151617181920cdcbdaabaa2、

13、Fill in blank (10 points)(1)A Huffman tree is made of weight 11,8,6,2,5 respectively, its WPL is_。(2)The most depth of an AVL tree with 20 nodes is _ .(3)A tree of degree 3 has 100 no des with degree 3 and 200 no des with degree 2. The nu mber ofleaf no des is _(4) If a 2-dimensions matrix Amn is st

14、ored in an 1-D array with row-major mapping, then the address ofeleme nt Aij relative to A00 is _ _(5) When sorting a record seque nee with 20 keys using merge sorting, how many passes. will itexecute? _An swer:12345716401i*n+j5北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第4頁3. (10 points) Show the result of inserting 5

15、1,25, 36, 88, 42, 52, 15, 96, 87, 30 into(a) an in itially empty AVL tree;(b) an in itially empty B-tree of order 3an swer:4. (10 poi nts)Show the resultofinserting48,35,64,92,77,13, 29,44 in to an in itially empty complete Binary Tree , if sorting the list in ascending order,then please justify the

16、 complete Binary Tree into a heap, and draw the heap after finishing heapsort process.an swer5points北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第5頁5. (10 poin ts) Please draw the adjace ncy matrix and adjace ncy list of the follow ing directed graph, and thenfrom the starting point A, traverse the graph using depth-fir

17、st search and breadth-first search accord ing toyour adjace ncy list and give the two corresp onding traversal seque nces.Answer:北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第6頁3po intsDFS: A B CBFS: A B E6. (10 points) Given Hash function H(k)=3K mod 11 and the key sequenee 32,13,49,24,38,21,4,12. The size of hash tabl

18、e is 11.a. Con struct the hash table with lin ear prob ing method.b. Calculate the average search len gth for successful and un successful search un der theequal probability.01234567891012345101001200110300001410101510000r3points0A1B2C3D4E1_24A00A222A(2poi nts)(2poi nts)43北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第7頁

19、412493813243221(6 points)ASLsucc= (5*1+3*2)/8=11/8(2 poi nts)ASLunsucc= (1+2+1+8+7+6+5+4+3+2+1)/11=40/11(2 points)北京交通大學(xué) 2009 年數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)試卷第8頁7. (10 poin ts) Please fill in the bla nks in the program which sorts aasce nding order with bubble sort ing. (2po in ts/bla nk)Keysequenee invoid bubble_sort(i nt& a, int n) int b; cha nge=TRUE;for (i=n-1;i1 & cha nge; cha nge = FALSE;for (j=0; j aj+1) b = aj】;ai+1 = b :-i)aj=aj+1;cha nge = TRUE : / bubble_sort8. (10 poin ts) Please read the follow ing program, and write its function and