2009数据结构英文试卷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

-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) log

2

n (b) n

2

(c) 2

n

(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

第 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.2

i-1

b. 2i c.2

i

d.2

i

-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 log

2

(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(n

2

) (d) O(n

3

)

第 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.n

2

(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

:

15

25 36

51

15

25

36

a

88

a

a

a

30

42

a

52

96

a

a

87

a

5points

a

88

a

42

52 87

96

a

30

a

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

92

35

a

a

a

77

13

64

F

29

a

a

a

3 points

第 4 页

北京交通大学2009年《数据结构与算法设计》试卷

35

44

77

92

a

a

a

48

13

64

F

29

a

a

a

4 points

92

44

29

13

a

a

a

48

64

35

F

77

a

a

a

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.

A

B

E

C D

Answer:

第 5 页

北京交通大学2009年《数据结构与算法设计》试卷

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

A

0

4 ∧

1

1

B

3 ∧

2

C

2

4 ∧

D

3

2 22 ∧

0

E

4

0 ∧

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

4

2

3

12

4

49

5

38

6

13

7

24

8

32

9

21

10

(6 points)

ASL

succ

= (5*1+3*2)/8=11/8 (2 points)

ASL

unsucc

= (1+2+1+8+7+6+5+4+3+2+1)/11=40/11 (2 points)

第 6 页

北京交通大学2009年《数据结构与算法设计》试卷

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; i>1 && change; --i)

{ change = FALSE;

for (j=0; j

if (a[j] > a[j+1])

{ b = a[j]; a[j]=a[j+1];

a[j+1] = b ; change = TRUE ;

}

}

} // bubble_sort

8. (10 points) Please read the following program, and write its function and the output.

#include

void unknown( int A[ ], int B[ ], int C[ ],int Aend,int Bend,int* Num)

{ int Apos, Bpos, Cpos;

Apos=0; Bpos=0; Cpos=0;

while( Apos

{if (A[ Apos ] < B[ Bpos ])

{ C[ Cpos++ ] = A[ Apos++ ]; (*Num)++; }

if (A[ Apos ] == B[ Bpos ])

{ C[ Cpos++ ] = A[ Apos++ ]; Bpos++; (*Num)++;}

if (A[ Apos ] > B[ Bpos ])

{ C[ Cpos++ ] = B[ Bpos++ ]; (*Num)++; } }

while( Apos < Aend )

{C[ Cpos++ ] = A[ Apos++ ]; (*Num)++; }

while( Bpos < Bend )

{C[ Cpos++ ] = B[ Bpos++ ]; (*Num)++; }

}

第 7 页

北京交通大学2009年《数据结构与算法设计》试卷

main()

{

int A[4] = {3,5,8,11};

int B[8]= {2,5,6,8,9,11,15,20};

int C[12];

int length=0;

int i;

unknown (A , B, C,4,8,&length);

for(i=0;i

return 0;

}

Answer: merge two ascending ordered lists La and Lb into a new ascending ordered list Lc.

There is no duplicate items in Lc. (5 points)

Lc contain 2,3,5,6,8,9,11,15,20 (5 points)

9．

(10 points)

Please describe the binary link of a binary tree in C Language. Write a function to

count the number of leaves in a binary tree.

Answer:

typedef struct BinNode

{ datatype data;

struct BinNode *lchild, *rchild;

} BinNode, * BinTree; (2 points)

int CountLeaf (BinTree T)

{int n1,n2;

if ( !T ) return 0; (2 points)

else { if ((!T->lchild)&& (!T->rchild)) (2 points)

return 1; // 对叶子结点计数

else {n1=CountLeaf( T->lchild); (1 points)

n2=CountLeaf( T->rchild); (1 points)

return (n1+n2);} (2 points)

} // if

} // CountLeaf

第 8 页