北师大教育技术系《数据结构》复习题

文章作者 100test 发表时间 2007:05:21 12:34:20
来源 100Test.Com百考试题网

一. 选择题
(1)采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为( ).
A. n B. (n 1)/2 C. n/2 D. (n-1)/2
(2)采用折半法查找长度为10的有序线性表时,在表内各元素等概率的情况,下,查找成功所需的平均比较次数为( ).
– 37/10 B. 31/10 C. 29/10 D. 27/10
(3)采用分块查找时,若线性表中共有361个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块分( )结点最好
A. 10 B. 14 C. 17 D. 19
(4)在哈希函数H(key)=key % m 中, m应取大小恰当的( )
A. 素数 B. 奇数 C. 偶数 D. 任意数

二、为数列 25,45,90,65,55,10,75,40,30 分别建立二叉排序树 和平衡二叉树.

三、
A.给定数组int A[10]={25,15,80,20,70,45,10,60}.给出它的极小堆.
B.给出从上堆中删除堆顶元素后所得堆对应的数列.
C.给定字符串 char * A=“previous”. 给出它的极大堆.
D.给出从上堆中添加一个元素t后所得的堆.

四.用快速排序算法对如下数组排序,
60 55 65 90 20 5 80 100
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
1. 第一轮支点(pivot) 选20,列出第一轮排序后的元素次序.
2. 列出第一轮排序后的高端子列,对这个子列再用快速排序算法排一论.
3. 快速排序的计算复杂性:
A.平均情况____ B.最坏情况________ C.最好情况________
(a) O(nlogn) (b) O(n2) (c) O(n) (d) O(1)

五.用hash函数hashf(x)=x将整数值映射为hash表的素引.将数据1,23,19,30,14,33,12,22,7插入hash表中.
a) 用开放探测寻址法建立hash表.
b) 用独立链表地址法建立hash表.
c) 分别计算等概率情况下两种方法查找成功的平均查找次数.

六.下面一段程序输出什么?
void main(void)
{ Stack S. Queue Q. Pqueue PQ. char ch.
char sentence[]=”StackQueue”.
for(int i=0.i PQ.PQInsert(sentence[i]).
while(!PQ.PQEmpty())
{ ch = PQ.PQDelete().
while(!S.StackEmpty())
{ ch = S.pop(). cout< cout< while(!Q.Qempty())
{ ch = Q.Q0delete().cout< cout< if ( isupper(ch) S.Push(ch).
else Q.Qinsert(ch). }

七.(1)用preorder遍历一棵Binary Search Tree得到序列 20 15 10 17 16 18 25 22 21 24 35给出这棵树,并给出postorder遍历.
(2) 说明函数F的作用
void InorderAssign(TreeNode*t,Array