发布时间 : 星期日 文章【精选资料】数据结构英文试卷A及答案 NEW更新完毕开始阅读
北京交通大学2009年《数据结构与算法设计》试卷
Final examination
2009 Fall
Data Structure and Algorithm Design
Class: Student Number: Name: Teacher
No. Mark 1 2 3 4 5 6 7 8 9 Total 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 \
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
第 1 页
北京交通大学2009年《数据结构与算法设计》试卷
(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, 1≤i ≤n, be the number assigned to an element of a complete binary tree. Which of
the following statements is NOT true?
(a) If i＞1, then the parent of this element has been assigned the number ?i/2? .
(b) If 2i>n, then this element has no left child. Otherwise its left child has been assigned the
number 2i.
(c) If 2i+1>n, 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(y>0)
if(x>200) {x=x-10;y--;} else x++;
What is its asymptotic time complexity?
(a) O(1) (b) O(n) (c) O(n2) (d) O(n3)
第 2 页
北京交通大学2009年《数据结构与算法设计》试卷
(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 A[m][n] is stored in an 1-D array with row-major mapping, then the address of element A[i][j] relative to A[0][0] is _ _
(5) When sorting a record sequence with 20 keys using merge sorting, how many passes. will it
execute? Answer:
1 71
2 6 3 401 4 i*n+j 5 5 第 3 页
北京交通大学2009年《数据结构与算法设计》试卷
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:
51 :
1525 36 152536a 88a a a 3042a 5296 a a a 5points 87 51a 88a 4252 87 96 a 30a a 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
48
44 9235a a a 771364F29a a a 3 points
第 4 页