單元練習9
一．判斷題（下列各題，正確的請在前面的括號內打√；錯誤的打╳ ）
（√）（1）二分查詢法要求待查表的關鍵字值必須有序。
（ㄨ）（2）對有序表而言採用二分查詢總比採用順序查詢法速度快。
（ㄨ）（3）在二叉排序樹中，根結點的值都小於孩子結點的值。
（√）（4）雜湊儲存法的基本思想是由關鍵字的值決定資料的儲存位址。
（√）（5）雜湊表是一種將關鍵字轉換為儲存位址的儲存方法。
（ㄨ）（6）選擇好的雜湊函式就可以避免衝突的發生。
（ㄨ）（7）在有序的順序表和有序的鍊錶上，均可以採用二分查詢來提高查詢速度。
（√）（8）採用分塊查詢，既能實現線性表所希望的查詢速度，又能適應動態變化的需要。
（√）（9）雜湊法的查詢效率主要取決於雜湊表構造時選取的雜湊函式和處理衝突的方法。
（ㄨ）（10）在二叉排序樹上刪除乙個結點時，不必移動其它結點，只要將該結點的父結點的相應的指標域置空即可。
二．填空題
（1） 順序查詢法，表中元素可以任意存放。
（2） 在分塊查詢方法中，首先查詢索引 ，然後再查詢相應的塊。
（3） 順序查詢、二分查詢、分塊查詢都屬於靜態查詢。
（4） 靜態查詢表所含元素個數在查詢階段是固定不變的。
（5） 對於長度為n的線性表，若進行順序查詢，則時間複雜度為 o（n） 。
（6） 對於長度為n的線性表，若採用二分查詢，則時間複雜度為： o（log2n） 。
（7） 理想情況下，在雜湊表中查詢乙個元素的時間複雜度為： o（1） 。
（8） 在關鍵字序列（7，10，12，18，28，36，45，92）中，用二分查詢法查詢關鍵字92，要比較 4 次才找到。
（9） 設有100個元素，用二分查詢時，最大的比較次數是 7 次。
（10） 對二叉排序樹進行查詢的方法是用待查的值與根結點的鍵值進行比較，若比根結點小，則繼續在左子樹中查詢。
（11） 二叉排序樹是一種動態查詢表。
（12） 雜湊表是按雜湊儲存方式構造的儲存結構
（13） 雜湊法既是一種儲存方法，又是一種查詢方法。
（14） 雜湊表的查詢效率主要取決於雜湊表造表時選取的雜湊函式和處理衝突的方法。
（15） 設雜湊函式h和鍵值k1，k2，若k1≠k2，且h（k1）=h（k2），則稱這種現象為衝突 。
（16） 處理衝突的兩類主要方法是開放定址法和拉鍊法（或鏈位址法） 。
（17） 雜湊表（或雜湊） 查詢法的平均查詢長度與元素個數n無關。
（18） 在雜湊函式h(key)=key % p中，p一般應取質數 。
（19） 在查詢過程中有插入元素或刪除元素操作的，稱為動態查詢。
（20） 各結點左右子樹深度之差的絕對值至多為 1 的二叉樹稱謂平衡二叉樹。
三．選擇題
（1）查詢表是以（ a ）為查詢結構。
a．集合b．圖c．樹d．檔案
（2）順序查詢法適合於儲存結構為（ b ）的線性表。
a．雜湊儲存b．順序儲存或鏈結儲存
c．壓縮儲存d．索引儲存
（3）在表長為ｎ的鍊錶中進行線性查詢，它的平均查詢長度為（ b ）。
ａ. aslasl＝(n+1)/２;
ｃ. aslasl≈log2ｎ
（4）對線性表進行二分查詢時，要求線性表必須 （ d ）。
a．以順序方式儲存b．以鏈結方式儲存，且結點按關鍵字有序排序
c．以鏈結方式儲存d．以順序方式儲存，且結點按關鍵字有序排序
（5）衡量查詢演算法效率的主要標準是（ b ）。
a．元素個數 b. 平均查詢長度 c．所需的儲存量 d．演算法難易程度
（6）如果要求乙個線性表既能較快地查詢，又能適應動態變化的要求，可以採用（ a ）查詢方法。
a．分塊b．順序c．二分d．雜湊
（7） 鍊錶適用於（ a ）查詢。
a．順序b．二分c．隨機d．順序或二分
（8）乙個有序表為，當二分查詢值為82的結點時，( c )次比較後查詢成功。
a．2b．3c．4d．5
（9）二分查詢有序表,若查詢表中元素58，則它將依次與表中（ b ）比較大小，查詢結果是失敗。
a．30，88，70，50 b． 20，70，30，50 c．20，50 d．30，88，50
（10）對有14個元素的有序表a[1..14]作二分查詢，查詢元素a[4]時的被比較元素依次為（ c ）。
a．a[1]，a[2]，a[3]，a[4b．a[1]，a[14]，a[7]，a[4]
c．a[7]，a[3]，a[5]，a[4d．a[7]，a[5]，a[3]，a[4]
（11）有乙個長度為12的有序表，按二分查詢法對其進行查詢，在表內各元素等概率情況下查詢成功所需的平均比較次數為（ b ）。
a．35／12b．37／12c．39／12d．43／12
（12）採用分塊查詢時，若線性表共有625個元素，查詢每個元素的概率相等，假設採用順序查詢來確定結點所在的塊時，每塊分（ c ）個結點最佳。
a．6b．10c．25d．625
（13）下列（ c ）不是利用查詢表中資料元素的關係進行查詢的方法。
a．平衡二叉樹b．有序表的查詢
c. 雜湊查詢d．二叉排序樹的查詢
（14）設雜湊表長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
（15）對包含n個元素的雜湊表進行查詢，平均查詢長度為（ d ）。
a．o(n2b．o(log2n) c. o(nd．不直接依賴於n
（16）衝突指的是（ c ）。
a．兩個元素具有相同序號b. 兩個元素的鍵值不同
c．不同鍵值對應相同的儲存位址d．兩個元素的鍵值相同
（17）在查詢過程中，不做增加、刪除或修改的查詢稱為（ a ）。
a．靜態查詢b. 內創造c．動態查詢 d．外查詢
（18）已知8個元素為，按照依次插入結點的方法生成一棵二叉樹，最後兩層上結點的總數為（ b ）。
a．1b．2c. 3d．4
（19）不可能生成下圖二叉排序樹的關鍵字的序列是（ a ）。
a． 4 5 3 1 2 b．4 2 5 3 1 c．4 5 2 1 3 d．4 2 3 1 5
（20）動態查詢包括（ b ）查詢。
a．順序表b. 二叉排序樹
c．有序表d．索引順序表
四．應用題
1． 對於給定結點的關鍵字集合k=，
（1）試構造一棵二叉排序樹；
（2）求等概率情況下的平均查詢長度asl。
解：（1）構造二叉排序樹2）asl=(1*1+2*2+3*4+4*3)/10=2.9
2． 對於給定結點的關鍵字集合k=，
（1）試構造一棵二叉排序樹；
（2）求等概率情況下的平均查詢長度asl。
解：（1）構造二叉排序樹 ：
（2）asl=(1*1+2*2+3*4+4*2+5*1)/10=3
3． 將資料序列：25，73，62，191，325，138，依次插入下圖所示的二叉排序樹，並畫出最後結果。
解：4． 對於給定結點的關鍵字集合k=，
（1）試構造一棵二叉排序樹；
（2）在二叉樹排序bt中刪除「12」後的樹結構：
或5． 對於給定結點的關鍵字集合k=，
（1）試構造一棵二叉排序樹；
（2）求等概率情況下的平均查詢長度asl。
解：（1）構造二叉排序樹
（2）asl=（1*1+2*2+3*3+4*2）/ 8 =2.75或=11/4）
6． 對於給定結點的關鍵字集合k=，
（1）試構造一棵二叉排序樹；
（2）求等概率情況下的平均查詢長度asl。
資料結構單元練習
單元練習8 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 圖可以沒有邊，但不能沒有頂點。2 在無向圖中，v1，v2 與 v2，v1 是兩條不同的邊。3 鄰接表只能用於有向圖的儲存。4 乙個圖的鄰接矩陣表示是唯一的。5 用鄰接矩陣法儲存乙個圖時，所占用的儲存空間大小與圖中頂點個數無關，...
資料結構單元4練習
單元測驗4 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 佇列是限制在兩端進行操作的線性表。2 判斷順序隊列為空的標準是頭指標和尾指標都指向同乙個結點。3 在鏈佇列上做出隊操作時，會改變front指標的 值 所指向的位置或儲存空間。4 在迴圈佇列中，若尾指標rear大於頭指標fron...
資料結構單元2練習
單元練習2 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 線性表的鏈式儲存結構優於順序儲存。2 鍊錶的每個結點都恰好包含乙個指標域。3 性表的鏈式儲存結構中，邏輯上相鄰的兩個元素在物理位置上並不一定緊鄰。4 順序儲存方式的優點是儲存密度大，插入 刪除效率高。5 線性鍊錶的刪除演算法簡...