新闻搜索：
北师大教育技术数据结构复习题
来源：Easy考研网
一. 选择题
(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%11将整数值映射为hash表的素引.将数据1,23,19,30,14,33,12,22,7插入hash表中.
a) 用开放探测寻址法建立hash表.
b) 用独立链表地址法建立hash表.
c) 分别计算等概率情况下两种方法查找成功的平均查找次数.
