1. 若查詢每個元素的概率相等，則在長度為n的順序表上查詢任一元素的平均查詢長度為( )。
a. nb. n+1c. (n-1)/2 d. (n+1)/2
2. 對於長度為9的順序儲存的有序表，若採用折半查詢，在等概率情況下的平均查詢長度為( )的9分之一。
a. 20b. 18c. 25d. 22
3. 對於長度為18的順序儲存的有序表，若採用折半查詢，則查詢第15個元素的比較次數為( )。
a. 3b. 4c. 5d. 6
4. 對於順序儲存的有序表(5,12,20,26,37,42,46,50,64)，若採用折半查詢，則查詢元素26的比較次數為( )。
a. 2b. 3c. 4d. 5
5. 對具有n個元素的有序表採用折半查詢，則演算法的時間複雜度為( )。
a. o(nb. o(n2c. o(1d. o(log2n)
6. 在索引查詢中，若用於儲存資料元素的主表的長度為n，它被均分為k個子表，每個子表的長度均為n/k，則索引查詢的平均查詢長度為( )。
a. n+kb. k+n/k c. (k+n/k)/2 d. (k+n/k)/2+1
7. 在索引查詢中，若用於儲存資料元素的主表的長度為144，它被均分為12子表，每個子表的長度均為12，則索引查詢的平均查詢長度為( )。
a. 13b. 24c. 12d. 79
8. 從具有n個結點的二叉排序樹中查詢乙個元素時，在平均情況下的時間複雜度大致為( )。
a. o(nb. o(1c. o(log2n) d. o(n2)
9. 從具有n個結點的二叉排序樹中查詢乙個元素時，在最壞情況下的時間複雜度為( )。
a. o(nb. o(1c. o(log2n) d. o(n2)
10. 在一棵平衡二叉排序樹中，每個結點的平衡因子的取值範圍是( )。
a. -11b. -22c. 12d. 01
11. 若根據查詢表(23,44,36,48,52,73,64,58)建立雜湊表，採用h(k)=k%13計算雜湊位址，則元素64的雜湊位址為( )。
a. 4b. 8c. 12d. 13
12. 若根據查詢表(23,44,36,48,52,73,64,58)建立雜湊表，採用h(k)=k%7計算雜湊位址，則雜湊位址等於3的元素個數( )。
a. 1b. 2c. 3d. 4
13. 若根據查詢表建立長度為m的雜湊表，採用線性探測法處理衝突，假定對乙個元素第一次計算的雜湊位址為d，則下一次的雜湊位址為( )。
a. db. d+1c. (d+1)/m d. (d+1)%m
14. 假定對元素序列（7, 3, 5, 9, 1, 12）進行堆排序，並且採用小根堆，則由初始資料構成的初始堆為（ ）。
a. 1, 3, 5, 7, 9, 12b. 1, 3, 5, 9, 7, 12
c. 1, 5, 3, 7, 9, 12d. 1, 5, 3, 9, 12, 7
15. 在平均情況下速度最快的排序方法為（ ）。
a. 簡單選擇排序 b. 歸併排序 c. 堆排序 d. 快速排序
1. 以順序查詢方法從長度為n的順序表或單鏈表中查詢乙個元素時，平均查詢長度為________，時間複雜度為________。
2. 對長度為n的查詢表進行查詢時，假定查詢第i個元素的概率為pi,查詢長度（即在查詢過程中依次同有關元素比較的總次數）為ci，則在查詢成功情況下的平均查詢長度的計算公式為________。
3. 假定乙個順序表的長度為40，並假定查詢每個元素的概率都相同，則在查詢成功情況下的平均查詢長度________，在查詢不成功情況下的平均查詢長度________。
4. 以折半查詢方法從長度為n的有序表中查詢乙個元素時，平均查詢長度約等於________的向上取整減1，時間複雜度為________。
5. 以折半查詢方法在乙個查詢表上進行查詢時，該查詢表必須組織成________儲存的________表。
6. 從有序表(12,18,30,43,56,78,82,95)中分別折半查詢43和56元素時，其比較次數分別為________和________。
7. 假定對長度n=50的有序表進行折半查詢，則對應的判定樹高度為________，最後一層的結點數為________。
8. 假定在索引查詢中，查詢表長度為n，每個子表的長度相等，設為s，則進行成功查詢的平均查詢長度為
9. 在索引查詢中，假定查詢表（即主表）的長度為96，被等分為8個子表，則進行索引查詢的平均查詢長度為________。
10. 在一棵二叉排序樹中，每個分支結點的左子樹上所有結點的值一定________該結點的值，右子樹上所有結點的值一定________該結點的值。
11. 對一棵二叉排序樹進行中序遍歷時，得到的結點序列是乙個________。
12. 從一棵二叉排序樹中查詢乙個元素時，若元素的值等於根結點的值，則表明_______，若元素的值小於根結點的值，則繼續向________查詢，若元素的值大於根結點的值，則繼續向________查詢。
13. 向一棵二叉排序樹中插入乙個元素時，若元素的值小於根結點的值，則接著向根結點的________插入，若元素的值大於根結點的值，則接著向根結點的________插入。
14. 根據n個元素建立一棵二叉排序樹的時間複雜度大致為________。
15. 假定對線性表(38,25,74,52,48)進行雜湊儲存，採用h(k)=k % 7作為雜湊函式，採用線性探測法處理衝突，則在建立雜湊表的過程中，將會碰到________次儲存衝突。
1. 已知乙個順序儲存的有序表為(15,26,34,39,45,56,58,63,74,76)，試畫出對應的折半查詢判定樹，求出其平均查詢長度。
2. 假定乙個線性表為(38,52,25,74,68,16,30,54,90,72)，畫出按線性表中元素的次序生成的一棵二叉排序樹，求出其平均查詢長度。
3. 假定乙個待雜湊儲存的線性表為(32,75,29,63,48,94,25,46,18,70)，雜湊位址空間為ht[13]，若採用除留餘數法構造雜湊函式和線性探測法處理衝突，試求出每一元素在雜湊表中的初始雜湊位址和最終雜湊位址，畫出最後得到的雜湊表，求出平均查詢長度。
元素 32 75 29 63 48 94 25 46 18 70
初始雜湊位址
最終雜湊位址
0 1 2 3 4 5 6 7 8 9 10 11 12
雜湊表4. 假定乙個待雜湊儲存的線性表為(32,75,29,63,48,94,25,36,18,70,49,80)，雜湊位址空間為ht[12]，若採用除留餘數法構造雜湊函式和拉鍊法處理衝突，試畫出最後得到的雜湊表，並求出平均查詢長度。
1. 試寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設此二叉樹以二叉鍊錶作為儲存結構，且樹中結點的關鍵字均不同。
2. 試將折半查詢的演算法改寫成遞迴演算法。
資料結構答案
1 有乙個帶頭指標的單鏈表，寫出在值為x的結點之後插入m個結點的演算法 int insertm linklist l,int x,int m p next q連線斷點 3 假設乙個長度大於1的單迴圈鍊錶既無頭結點也無頭指標，s為指向鍊錶中某個結點的指標，試設計刪除結點s的直接前驅結點的演算法 voi...
資料結構複習答案
8.設指標變數p指向單鏈表結點a，則刪除結點a的後繼結點b需要的操作為 a p next p next nextb p p next c p p next nextd p next p 9.又稱為fifo表 又稱為filo表。a 佇列 b 雜湊表c 棧 d 雜湊表 10.對於棧運算元據的原則是 a ...
資料結構作業答案
第一章單選題1 下列關於演算法的基本特徵，說法不正確的是 能行性是演算法中的每乙個步驟必須能夠實現且能達到預期的目的。演算法的確定性是指演算法中的每乙個步驟必須是有明確的定義，不允許模稜兩可。演算法的有窮性是指演算法必須能在有限的時間內做完。演算法與提供情報無關。d 教師批改 d 2 演算法的時間複...