数据结构期末考试真题
需积分: 0 98 浏览量
2010-06-04
11:06:21
上传
评论
收藏 112KB DOC 举报
--------------------------------------------------- 密 ---------------------------- 封 --------------------------- 线 -------------------------------------------------
（ 答 题 不 能 超 出 密 封 线 ）
2007～2008 学年 第二学期 《DATA STRUCTURE》科目 考试 试题 A 卷
Ⅰ、Computation ( 63 scores )
1、Is A=<4,16,10,14,7,9,3,2,8,1> a max-heap? Why? And illustrate it. ( 8 scores )
2、 illustrate the result of each operation in the sequence PUSH(S,5), POP(S),
PUSH(S,4), PUSH(S, 6), PUSH(S, 8), POP(S), and POP(S) on an initially empty
stack S stored in array S[1 ‥ 6].( 7 scores )
3、Illustrate the operation of PARTITION on the array A =<13, 9, 5, 21, 8, 4, 11,
2, 6, 12>(9 scores)
4、Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table
of length m = 13 using open addressing with the primary hash function h'(k) = k
mod m. Illustrate the result of inserting these keys
(1) using linear probing
(2) using quadratic probing with c1 = 1 and c2 = 3.( 10 scores)
5、The postorder of a binary search tree is dabec，and it’s inorder is
debac，what is the preorder of the tree? (9 scores)
6、Working modulo q = 11, how many spurious hits does the Rabin-Karp matcher
encounter in the text T = 2341265677590 when looking for the pattern P = 12?
( 10 scores )
第 1 页 （共 3 页）
评论0