2009数据结构英文试卷a及答案----new

Final examination 2009 Fall Data Structure and Algorithm Design Class: Student Number: Name: Teacher No. 1 2 3 4 5 6 7 8 9 Total Mark 1.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 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) 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，84 18，23，24，28，35，30，47，71，84 18，23，24，28，30，35，47，71，84 The 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 using 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 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 algorithm. 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) order. 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 tree. 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 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? 北京交通大学 2009 年数据结构与算法设计试卷 第 3 页 (a) O(1) (b) O(n) (c) O(n2) (d) O(n3) (17) In a Binary Tree with n 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 EGBFADHC, 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 linked answer: 1 2 3 4 5 6 7 8 9 10 c c a a d b a c a b 11 12 13 14 15 16 17 18 19 20 c d c b d a a b a a 2、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 matrix 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: 1 2 3 4 5 71 6 401 i*n+j 5 3. (10 points) Show the result of inserting 51, 25, 36, 88, 42, 52, 15, 96, 87, 30 into (a) an initially empty AVL tree; (b) an initially empty B-tree of order 3 answer: 5points : 5points 4. (10 points) Show the result of inserting 48,35,64,92,77,13, 29,44 into an initially empty complete Binary Tree , if sorting the list in ascending order, then please justify the complete Binary Tree into a heap, and draw the heap after finishing heapsort process. answer 3 points 51 a 36 a 42 a 25 a 30 a 88 a 15 a 52 a 87 96 35 a 77 a 92 a 64 F a 29 a 13 a 44 48 a 51 a 25 36 42 a30a 88 a 15 a 52 87 96 北京交通大学 2009 年数据结构与算法设计试卷 第 5 页 4 points 3 points 5. (10 points) Please draw the adjacency matrix and 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. Answer: A E DC B 77 a 48 a 44 a 64 F a 29 a 13 a 35 92 a 29 a 48 a 44 a 35 F a 77 a 64 a 92 13 a 1 2 3 4 5 1 0 1 0 0 1 2 0 0 1 1 0 3 0 0 0 0 1 4 1 0 1 0 1 5 1 0 0 0 0 3 points 0 1 2 3 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. b. Calculate the average search length for successful and unsuccessful search under the equal probability. 0 1 2 3 4 5 6 7 8 9 10 4 12 49 38 13 24 32 21 (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) 1 4 0 A B C D E 3 2 22 0 2 4 北京交通大学 2009 年数据结构与算法设计试卷 第 7 页 7. (10 points) Please fill i