2009数据结构英文试卷A及答案-NEW8页

1、Final examination2009 FallData Structure and Algorithm DesignClass: Student Number: Name: Teacher No.123456789TotalMark1.Single-Choice(20 points)(1) Consider the following definition of a recursive function ff. int ff( int n ) if( n = 0 ) return 1; return 2 * ff( n - 1 ); If n 0, what is returned by

2、 ff( n )? (a) log2 n (b) n2 (c) 2n (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,6 b.3,2,5,6,4,1 c.1,5,4,6,2,3 d.4,5,3,6,2,1(3) Which of the following data structures uses a Last-in, First-out policy for element insertion and removal? (a) Stack (b)

3、 Tree (c) Hash table (d) Queue(4) If deleting the ith key from a contiguous list with n keys, keys need to be shifted left one position.a. n-i b. n-i+1 c. 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，30，71，35，8418，23，24，28，35，30，4

4、7，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 number of keyword in every node except root in a B- tree of order 5 is _ _ at least a. 1 b. 2 c. 3 d. 4 (7) When sorting a record sequence with multiple keys usin

5、g Least Significant Digit method, the sorting algorithm used for every digit except the least significant digit .a. must be stable b. must be unstable c. can be either stable or unstable (8) In the following four Binary Trees, is not a complete Binary Tree. a b c d(9) The maximum number of nodes on

6、level i of a binary tree is .a.2i-1 b. 2i c.2i d.2i-1(10) If the Binary Tree T2 is transformed from the Tree T1, then the postorder traversal sequence of T1 is the traversal sequence of T2. a. preorder b. inorder c. postorder d. level order(11) In the following sorting algorithm, is an unstable algo

7、rithm.a. the insertion 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 comparisons is .a. 25 b.10 c. 1 d.7(13) The result of traversing inorderly a Binary Search Tree is a(an) o

8、rder.a. descending or ascending b. descending c. ascending d. disorder(14) To sort a key sequence in ascending order by Heap sorting needs to construct a heap.(a) min (b) max (c) either min or max (d)complete binary tree(15). Let i, 1i n, be the number assigned to an element of a complete binary tre

9、e. Which of the following statements is NOT true? (a) If i1, 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 the number 2i. (c) If 2i+1n, then this element has no right child. Otherwise its

10、right child has been assigned the number 2i+1. (d) The height of the binary tree is log2 (n +1)(16).Consider the following C+ code fragment.x=191; y=200; while(y0) if(x200) x=x-10;y-; else x+; What is its asymptotic time complexity? (a) O(1) (b) O(n) (c) O(n2) (d) O(n3) (17) In a Binary Tree with n

11、nodes, there are non-empty pointers.a. n-1 b. n+1 c. 2n-1 d.2n+1(18) In an undirected graph with n vertices, the maximum number of edges is .a. n(n+1)/2 b. n(n-1)/2 c. n(n-1) d.n2(19) Assume the preorder traversal sequence of a binary tree T is ABEGFCDH, the inorder traversal sequence of T is EGBFAD

12、HC, then the postorder traversal sequence 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 contiguous b. disordered and contiguous c. disordered and linked d. ordered and linkedanswer:12345678910ccaa dbacab11121314151617181

13、920cdcbdaabaa2、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 nodes with degree 3 and 200 nodes with degree 2. The number of leaf nodes is .(4) If a 2-dimensions mat

14、rix Amn is stored in an 1-D array with row-major mapping, then the address of element Aij relative to A00 is _ _ (5) When sorting a record sequence with 20 keys using merge sorting, how many passes. will it execute? Answer:12345716401i*n+j5 3. (10 points) Show the result of inserting 51, 25, 36, 88,

15、 42, 52, 15, 96, 87, 30 into (a) an initially empty AVL tree;(b) an initially empty B-tree of order 351aanswer:88a36a52a9625a42a8730a15a 5points51a:25 3688a52 879630a15a42a 5points4. (10 points) Show the result of inserting 48,35,64,92,77,13, 29,44 into an initially empty complete Binary Tree , if s

16、orting the list in ascending order, then please justify the complete Binary Tree into a heap, and draw the heap after finishing heapsort process. answer48a64Fa35a13a77a92a29a44 3 points92a64Fa77a13a48a44a29a35 4 points13a35Fa29a64a48a44a77a92 3 points5. (10 points) Please draw the adjacency matrix a

17、nd adjacency list of the following directed graph, and then from the starting point A, traverse the graph using depth-first search and breadth-first search according to your adjacency list and give the two corresponding traversal sequences. ABECDAnswer: 1 2 3 4 5 1 0 1 0 0 1 2 0 0 1 1 0 3 0 0 0 0 1

18、4 1 0 1 0 1 5 1 0 0 0 0 3 pointsABCDE 4 1 0 3 2 14 222 2 030 4 3points DFS: A B C E D (2points) BFS: A B E C D (2points)6. (10 points) Given Hash function H(k)=3K mod 11 and the key sequence 32，13，49，24，38，21，4，12. The size of hash table is 11.a. Construct the hash table with linear probing method.

19、b. Calculate the average search length for successful and unsuccessful search under the equal probability. 012345678910412493813243221 (6 points)ASLsucc = (5*1+3*2)/8=11/8 (2 points)ASLunsucc = (1+2+1+8+7+6+5+4+3+2+1)/11=40/11 (2 points)7. (10 points) Please fill in the blanks in the program which sorts a Key sequence in ascending order with bubble sorting. (2points/blank)void bubble_sort(int& a, int n) int b; change=TRUE;for (i=n-1; i1 & change; -i) change = FALSE; for (j=0; j aj+1) b = aj; aj=aj+1;aj+1 = b ; change = TRUE ; / bubble_sort8. (10 points