一. 選擇題
(1)采用順序查找方法查找長度為n的線性表時,每個元素的平均查找長度為( ).
A. n B. (n+1)/2 C. n/2 D. (n-1)/2
(2)采用折半法查找長度為10的有序線性表時,在表內各元素等概率的情況,下,查找成功所需的平均比較次數(shù)為( ).
– 37/10 B. 31/10 C. 29/10 D. 27/10
(3)采用分塊查找時,若線性表中共有361個元素,查找每個元素的概率相同,假設采用順序查找來確定結點所在的塊時,每塊分( )結點最好
A. 10 B. 14 C. 17 D. 19
(4)在哈希函數(shù)H(key)=key % m 中, m應取大小恰當?shù)? )
A. 素數(shù) B. 奇數(shù) C. 偶數(shù) D. 任意數(shù)
二、為數(shù)列 25,45,90,65,55,10,75,40,30 分別建立二叉排序樹 和平衡二叉樹.
三、
A.給定數(shù)組int A[10]={25,15,80,20,70,45,10,60};給出它的極小堆.
B.給出從上堆中刪除堆頂元素后所得堆對應的數(shù)列.
C.給定字符串 char * A=“previous”; 給出它的極大堆.
D.給出從上堆中添加一個元素t后所得的堆.
四.用快速排序算法對如下數(shù)組排序, 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函數(shù)hashf(x)=x%11將整數(shù)值映射為hash表的素引.將數(shù)據(jù)1,23,19,30,14,33,12,22,7插入hash表中.
a) 用開放探測尋址法建立hash表.
b) 用獨立鏈表地址法建立hash表.
c) 分別計算等概率情況下兩種方法查找成功的平均查找次數(shù).
