北京交通大学软件学院
2012—2013学年第一学期期末考试试题
Data Structure and Algorithm Design(A)
Class: ____ Student Number: _________ Name: ________ Teacher ________
No、 I II III IV V VI Total Mark I 、 Single-Choice(20 points) 1、 The height of a bi nary tree that contains 1023 eleme nts is at most (1
) and at least ( 2
)、
D.9
E.10
F.11
A. 1022 B.1023 C. 1024
2、 If the seque nee of push ing eleme nts into a stack is a,b,c, which output seque nee
is impossible?( ). A.abc B.bca C.cba D.cab 3、How many minimum-cost spanning trees are there for an undirected connected graph with n vertices and e edges?( A、 must be only one B、 n-1 sure
4、 When using the adjace ncy matrix A to represe nt a un directed graph with n no des
and e edges, the degree of the node vi can be computed by formula (
n
)
C、 n-e
D、 not
)、
ti
^AUJJ +》A[iJ]
D、 B、丿 i /2 C、 e /2
5、 In the worst case, time complexity of quicksort will be degraded to (
)、
A.O( n) B.O( n2) C.O( nlog n)
6、 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、
25
B、 10
C、 1
)、
D、 7
7、 Con sider the follow ing pseudo-code, which in dicates part of a sta ndard binary tree
algorithm、 print( node ) { print data;
if( there is a left child ) print( left child ); if( there is a right child ) print( right child ); }
Which of the follow ing is the sta ndard n ame for this algorithm?( A、 Ino rder traversal
B、 Preorder traversal
C、 Postorder traversal D、 Bi nary search 8、 Which is not the property of a B-tree of order m? (
A、 The root node has m subtree at most B、 All leaf no des are at the same level、 C、 The keys in every node are ordered、 D、 All leaf no des are conn ected by links、
9、 Suppose that we have 1000 distinet integers, which are in the range from 0 to 50、 If using Radix Sort accord ing to the Least Signi fica nt Digit first, ( are n eeded to con structed、
A、 10
An swer table for Questi on I 1(1) 1(2) 2
)
)
) buckets
B、 50 C、 51 D、 1000
(write your an swers of Questi on I here) 3 4 5 7 6 8 D A B D B D 9 A B E D II、 Fill in the blank (2points * 5)
An swer table for II (Please write your an swers of II here) 1 2 2 3 4 5,4,3,2,1 2,3,⑤,5 preorder 11 i* n+j 1、 The strategy of depth-first searching algorithm for a graph is similar to
that of __ ______________ traversal algorithm for a normal tree、
2、 Here is a hash table, whose size is 18, hash ing function is H1(key)=key (% here is
the modulus operator), and which uses
Lin ear Prob ing strategy to cope with the collisi ons and in serts 26, 25, 72, 38, 8, 18, 59 into the hash table in turn、 The address of 59 is _______________ _
、
3、 Given a key sequenee {2,5,⑤,3}, please write its ascending ordered
sequenee after being sorted using heap sort、 (Note 5=⑤,just 5 is before ⑤ in original sequenee) ____________________________ 、 Please distinguish 5 and ⑤、
4、 If a 2-dimensions matrix A[m][n] is stored in an 1-D array with
row-major mapp ing, the n the address of eleme nt A[i][j] relative to A[0][0] is 5、 If the in-order and pre-order series of the no des in a binary tree are 1,2,3,4,5 ” and
1,2'：3,4,5” respectively, the postorder seque nee should be _________ 、
III、 (40 points)
1、 (8 poin ts) Suppose there is a stri ng abcadececdcdeeededthat comprises the
characters a, b, c, d and e、 We may encode the symbols using variable-length codes in order to make the length of string the shortest 、 Please draw the Huffma n tree used to en code the characters, calculate the weighted path length for the Huffman tree and write the code for each character (1) Draw the Huffman tree (3 poi nts)
(2) Calculate the weighted path len gth for the Huffma n tree (2 points)
WPL(T)= 6 2+5 2+2 3+1 3+4 2 =39
(3) write the code for each character、 (3 points)错一个扣一分,扣光为止
a b c d e 1 2、(8 points) Please respectively give two unsorted lists whose length are 4 to illustrate
that quick sort and selection sort are unstable、
(1) An example list for quick sort and the sorting procedure using quick sort、 (4 poi
nts)
(4, 2,②,3) --------------------------- (2 poin ts) sorting procedure The first pass: 3,2, ②,4
----------------------- (1point)
The seco nd pass: ②,2,3,4 ------------------------------ (1po int)
(2) An example list for select ion sort and the sorting procedure using
select ion sort、 (4 poin ts)
(2,②,3,1) -------------------------- (1 poi nts) sorting procedure The first pass:
1,②,3,2
------------------------- (1point)
-------------------- (1po int) --------------------- (1point)
The seco nd pass: 1,②,3,2 The third pass: 1,②,2, 3
3、 (8 points) Given the key sequence (331, 166, 367, 236, 268, 137, 337,
138), Please give the procedure (distribut ing and collect ing) of sorting using radix sort method、 not necessary to write queue front and rear pointer if queue is null、 (1) The first pass (3 poi nts)
p-331-13犷—236- 268 一 13^-33 7—13 S
1st pa? of distributing accordi to the Lea$t digit
fll]—331^i[l]
f[6]~* 16 6_*236^- if 6] f[7]—1 笫-337^ r[7] fl?]^268^138 —i[8]
lTtpasi of collecting
p—331^166—236-*367->137-^ 337^268—138
(2) The sec ond pass (3 poin ts)
p—331-*166->256->367-* 137^357^65^158
2ad pass of distributing according to the middle digit
f[3]T33iT236—137T337T138—T[3]
恥]—\—367T268I】[6]
2皿 pass of collecting
p ->331-*236 ->137->337->138 —\—367—2 闘
(3) The third pass (2 points)
p- 331- 236 f 137- 337 -*138 —1 - 36^- 268
3^ pasi of distributing according tc tbe moit signifkut digi
f[l]―137-*138—166^—r[l]
(I2H236->268 *-T[2]
t[3] -33 L ->337 ->367 — r[3J 3rd pas& of collecting
pT 137—13$T“J236T25gf 33—337—367
It is in ascending order*
4、(6 poin ts)There are n 1 no des of degree 1,n2 no des of degree 2,…,nm
2012数据结构英文试卷A及答案
