8.1選擇題
1、順序查詢法適合於儲存結構為( b )的線性表。
a、雜湊儲存b、順序儲存或鏈結儲存
c、壓縮儲存d、索引儲存
2、對線性表進行折半查詢時，要求線性表必須( c )。
a、以順序方式儲存b、以鏈結方式儲存
c、以順序方式儲存，且結點按關鍵字有序排序
d、以鏈結方式儲存，且結點按關鍵字有序排序
3、採用順序查詢方法查詢長度為n的線性表時，每個元素的平均查詢長度為( c )。
a、nb、n/2 c、(n+1)/2d、(n-1)/2
4、採用折半查詢方法查詢長度為n的線性表時，每個元素的平均查詢長度為( d )。
a、o(n2) b、o(nlog2n) c、o(nd、o(log2n)
5、有乙個有序表為（1，3，9，12，32，41，45，62，75，77，82，95，100），當折半查詢給定值為82的元素時，（ c ）次比較後查詢成功。
a、1b、2c、4d、8
6、設雜湊表長m=14，雜湊函式h（key）=key%11。表中已有4個結點：
addr(15)=4、addr(38)=5、addr(61)=6、addr(84)=7，其餘位址為空，如用二次探測再雜湊解決衝突，關鍵字為49的結點的雜湊位址是（ d ）。
a、8b、3c、5d、9
7、如圖所示的4棵二叉樹，（ b ）是平衡二叉樹。
abcd
8、具有五層結點的二叉平衡樹至少有個結點。
a、10b、12c、15d、17
9、從二叉排序樹中查詢乙個元素時，其時間複雜度大致為( b )。
a、o(n2b、o(log2n) c、o(nd、o(1)
10、在雜湊函式h(key)=key%p中，p應取( a )。
a、素數 b、整數c、任意數d、小數
8.2填空題
1、假定在有序表r[0…9]上進行二分查詢，則比較一次查詢成功的結點數為（1），比較兩次查詢成功的結點數為（2），比較三次查詢成功的結點數為（ 4），平均查詢長度為（log2n）。
2、在分塊查詢中，首先查詢（索引表），然後再查詢相應的（主表），整個分塊查詢的平均查詢長度等於查詢索引表的平均長度與查詢相應子表的平均查詢長度的（和）。
3、在雜湊儲存中，裝填因子的值越大，訪問元素時發生衝突的可能性就（越大），當裝填因子的值越小，訪問元素時發生衝突的可能性就（越小）。
4、用二分查詢方法進行查詢時，要求資料檔案應為（順序），且限於（有序），要進行順序查詢，則線性表的儲存方式為（順序或鏈式儲存）。
5、假定查詢共有12個元素的有序表的概率相等，則進行順序查詢的平均查詢長度為（13/2），進行二分查詢時的平均查詢長度為（37/12）。
8.3 應用題
1、假定查詢有序表a[25]中每個元素的概率相等，試分別求出順序、折半和分塊（假定被分為5塊，每塊5個元素）查詢每個元素時的平均查詢長度。
解： 順序查詢asl=（n+1）/2=13
折半查詢asl=（1*1+2*2+4*3+8*4+9*5+1*6）/25=100/25=4
分塊查詢asl=（（2+3+4+5+6）+（3+4+5+6+7）+（4+5+6+7+8）+（5+6+7+8+9+）+（6+7+8+9+10））/25=150/25=6
2、設有一組關鍵字（19，01，23，14，55，20，84，27，68，11，10，77），採用雜湊函式h(key)=key%13，採用開放定址法的二次探測再雜湊方法解決衝突，試在0到18的形式列位址空間中對該關鍵字序列構造雜湊表。
解：計算雜湊位址：
h(19)=19%13=6h(01)=01%13=1h(23)=23%13=10
h(14)=14%13=1(衝突) h1=(1+12)%19=2
h(55)=55%13=3h(20)=20%13=7
h(84)=84%13=6(衝突) h1=(6+12)%19=7（衝突） h2=(6-12)%19=5
h(27)=27%13=1（衝突） h1=(1+12)%19=2（衝突） h2=(1-12)%19=0
h(68)=68%13=3（衝突） h1=(3+12)%19=4
h(11)=11%13=11
h(10)=10%13=10（衝突） h1=(10+12)%19=11（衝突） h2=(10-12)%19=9
h(77)=77%13=12
雜湊表為：
asl=（7*1+2*2+3*3）/12=20/12=5/3
3、假定乙個待雜湊儲存的線性表為（32，75，29，63，48，94，25，36，18，70），雜湊位址空間為ht[13],若採用除留餘數法構造雜湊函式和線性探查法處理衝突，試求出每個元素的雜湊位址，畫出最後得到的雜湊表，並求出平均查詢長度。
解： 雜湊位址為：
h(32)=32%13=6h(75)=75%13=10h(29)=29%13=3
h(63)=63%13=11 h(48)=48%13=9
h(94)=94%13=3（衝突） h1=(3+1)%13=4
h(25)=25%13=12
h(36)=36%13=10（衝突） h1=(10+1)%13=11（衝突） h2=(10+2)%13=12（衝突）
h3=(10+3)%13=0
h(18)=18%13=5
h(70)=70%13=5（衝突） h1=(5+1)%13=6（衝突） h2=(5+2)%13=7
雜湊表為：
asl=（7*1+1*2+1*3+1*4）/10=16/10=1.6
4、假定乙個待雜湊儲存的線性表為（32，75，29，63，48，94，25，36，18，70），雜湊位址空間為ht[11],若採用除留餘數法構造雜湊函式和鏈位址法處理衝突，試求出每一元素的雜湊位址，畫出最後得到的雜湊表，求出平均查詢長度。
解： 雜湊位址為：
h(32)=32%13=6h(75)=75%13=10h(29)=29%13=3
h(63)=63%13=11 h(48)=48%13=9h(94)=94%13=3
h(25)=25%13=12 h(36)=36%13=10h(18)=18%13=5
h(70)=70%13=5
雜湊表為：
圖沒有畫
asl=（1*7+2*3）/10=1.3
8.4演算法題
1、 編寫折半查詢的非遞迴演算法。（作為上機實踐題目）
int binsearch(listsq l, int low, int high, keytype k)
return -1; //查詢失敗返回-1
}2、 假設查詢表以單鏈表的形式儲存，試寫出對此單鏈表進行順序查詢時的實現演算法。（作為上機實踐題目）
struct elemtype //資料元素的資料型別定義
；struct lnode
;int seqsearch (lnode *l ,keytype s )
if(p) return n;
else return –1;
}3、設計乙個演算法，利用分塊查詢演算法在乙個有序表中插入乙個元素x，並保持表的有序性。（作為上機實踐題目）(沒要求)
4、設計乙個演算法，求出指定結點在給定二叉排序樹中的層次。(沒要求)
資料結構1800第八章
青島大學 2000 十 10分 中國人民大學 2000 一 1 4分 7 組織成迴圈鍊錶的可利用空間表附加什麼條件時，首次適配策略就轉變為最佳適配策略？北方交通大學 1998 四 8分 8 已知乙個大小為512個字長的儲存，假設先後有6個使用者申請大小分別為23，45，52，100，11和19的儲存...
《資料結構》第八章習題
1 用鄰接矩陣法儲存乙個圖所需的儲存單元數目與圖的邊數有關。2 有e條邊的無向圖，在鄰接表中有e個結點。3 強連通圖的各頂點間均可達。4 無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。5 乙個網 帶權圖 都有唯一的最小生成樹。6 最小生成樹問題是構造連通網的最小代價生成樹。7 關...
資料結構第八章排序
第八章排序 1.當檔案區域性有序或檔案長度較小的情況下，最佳的排序方法是 a 直接插入排序 b 直接選擇排序 c 氣泡排序 d 歸併排序 2.當初始序列已按鍵值有序時，用直接插入演算法進行排序，需要比較的次數為 a n 1 b log2n 注 2是下標 c 2log2n 注 後乙個2是下標 d n2...