數據結構查找練習題及答案

 

一 選擇題

1.若查找每個記錄的概率均等，則在具有n個記錄的連續順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為(C )。

A． (n-1)/2      B. n/2   C. (n+1)/2         D. n

2. 對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為( A )

A．（N+1）/2       B. N/2      C. N      D. [（1+N）*N ]/2  

3．順序查找法適用于查找順序存儲或鏈式存儲的線性表，平均比較次數為（D）,二分法查找只適用于查找順序存儲的有序表，平均比較次數為（C）。 在此假定N為線性表中結點數，且每次查找都是成功的。

A.N+1       B.2log2N     C.logN     D.N/2 E.Nlog2N F.N2

4. 下面關于二分查找的敘述正確的是 ( D )

A. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲

B. 表必須有序且表中數據必須是整型，實型或字符型

C. 表必須有序，而且只能從小到大排列

D. 表必須有序，且表只能以順序方式存儲 

5. 用二分（對半）查找表的元素的速度比用順序法( D )

A．   必然快    B. 必然慢   C. 相等     D. 不能確定

6. 具有12個關鍵字的有序表，二分查找的平均查找長度（ A ）

A. 3.1       B. 4     C. 2.5     D. 5     

7. 二分法查找的時間復雜性為（ D ）。

A. O（n2）    B. O（n）   C. O（nlogn）       D. O（logn）

8．當采用分快查找時，數據的組織方式為 ( B )

A．數據分成若干塊，每塊內數據有序

B．數據分成若干塊，每塊內數據不必有序，但塊間必須有序，每塊內最大（或最小）的數據組成索引塊

C. 數據分成若干塊，每塊內數據有序，每塊內最大（或最小）的數據組成索引塊

D. 數據分成若干塊，每塊（除最后一塊外）中數據個數需相同

9. 設有一組記錄的關鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構造散列表，散列函數為H（key）=key MOD 13,散列地址為1的鏈中有（ D ）個記錄。

A．1     B．2     C．3     D.4      

10. 下面關于哈希(Hash，雜湊)查找的說法正確的是( C )

A．哈希函數構造的越復雜越好，因為這樣隨機性好，沖突小

B．除留余數法是所有哈希函數中最好的 

C．不存在特別好與壞的哈希函數，要視情況而定

D．若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可 

11. 若采用鏈地址法構造散列表，散列函數為H（key）=key MOD 17，則需 (A) 個鏈表。這些鏈的鏈首指針構成一個指針數組，數組的下標范圍為 (C)

（1） A．17     B. 13     C. 16     D. 任意

（2） A．0至17     B. 1至17     C. 0至16     D. 1至16

 

二、判斷題

1．采用線性探測法處理散列時的沖突，當從哈希表刪除一個記錄時，不應將這個記錄的所在位置置空，因為這會影響以后的查找。（ √ ）

2．在散列(哈希)檢索中，“比較”操作一般也是不可避免的。（ √ ）

3．哈希函數越復雜越好，因為這樣隨機性好，沖突概率小. （ × ）

4．哈希函數的選取平方取中法最好。 （ × ）

5．Hash表的平均查找長度與處理沖突的方法無關。 （ × ）

6．負載因子 (裝填因子)是哈希表的一個重要參數，它反映哈希表的裝滿程度。（ √ ）

7. 哈希法的平均檢索長度不隨表中結點數目的增加而增加，而是隨負載因子的增大而增大。（ √ ）

8. 哈希表的結點中只包含數據元素自身的信息，不包含任何指針。 （ × ）

9．查找相同結點的效率二分查找總比順序查找高。 （ × ）

10．用數組和單鏈表表示的有序表均可使用二分查找方法來提高查找速度。 （ × ）

11. 在索引順序表中，實現分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數有關，而且與每塊中元素個數有關。（ √ ）

12. 順序查找法適用于存儲結構為順序或鏈接存儲的線性表。 （ √ ）

13. 二分查找法的查找速度一定比順序查找法快 。（ × ）

14. 就平均查找長度而言，分塊查找最小，二分查找次之，順序查找最大。（ × ）

15．對無序表用二分法查找比順序查找快。（× ）

 

三、填空 

1. 順序查找n個元素的順序表，若查找成功，則比較關鍵字的次數最多為n次；當使用監視哨時，若查找失敗，則比較關鍵字的次數為n+1。

2. 在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關鍵碼值20，需做的關鍵碼比較次數為4.

3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標依次為6,9,11,12。

4. 在有序表A[1..20]中，按二分查找方法進行查找，查找長度為5的元素個數是5

5. 高度為4的3階b-樹中，最多有26（第4層是葉子結點，每個結點兩個關鍵字）個關鍵字。

6. 在有序表A[1…20]中，按二分查找方法進行查找，查找長度為4的元素的下標從小到大依次是1,3,6,8,11,13,16,19

7. 給定一組數據{6，2，7，10，3，12}以它構造一棵哈夫曼樹，則樹高為5 ，帶權路徑長度WPL的值為96。

8. 己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當用二分法查找90時，需2次查找成功，47時4成功，查100時，需3次才能確定不成功。

9．哈希表是通過將查找碼按選定的哈希函數和解決沖突的方法，把結點按查找碼轉換為地址進行存儲的線性表。哈希方法的關鍵是選擇好的哈希函數和處理沖突的方法。一個好的哈希函數其轉換地址應盡可能均勻，而且函數運算應盡可能簡單。

 

四、應用題

1．名詞解釋：

哈希表：

同義詞：

答：概念是基本知識的主要部分，要牢固掌握。這里只列出一部分，目的是引起重視，解答略。 

 

2. 回答問題并填空

（1）哈希表存儲的基本思想是什么？

答：散列表存儲的基本思想是用關鍵字的值決定數據元素的存儲地址 

 

（2）哈希表存儲中解決沖突的基本方法有哪些？其基本思想是什么？

答：散列表存儲中解決碰撞的基本方法：

    ① 開放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表長，di是增量。根據di取法不同，又分為三種：

       a．di =1，2，…，m-1 稱為線性探測再散列，其特點是逐個探測表空間，只要散列表中有空閑空間，就可解決碰撞，缺點是容易造成“聚集”，即不是同義詞的關鍵字爭奪同一散列地址。

       b．di =12，-12，22，-22，… ，k2（k≤m/2） 稱為二次探測再散列，它減少了聚集，但不容易探測到全部表空間，只有當表長為形如4j+3（j為整數）的素數時才有可能。

       c．di =偽隨機數序列，稱為隨機探測再散列。

   ② 再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函數，即在同義詞產生碰撞時，用另一散列函數計算散列地址，直到解決碰撞。該方法不易產生“聚集”，但增加了計算時間。

    ③ 鏈地址法 將關鍵字為同義詞的記錄存儲在同一鏈表中，散列表地址區間用H[0..m-1]表示，分量初始值為空指針。凡散列地址為i（0≤i≤m-1）的記錄均插在以H[i]為頭指針的鏈表中。這種解決方法中數據元素個數不受表長限制，插入和刪除操作方便，但增加了指針的空間開銷。這種散列表常稱為開散列表，而①中的散列表稱閉散列表，含義是元素個數受表長限制。

    ④ 建立公共溢出區 設H[0..m-1]為基本表，凡關鍵字為同義詞的記錄，都填入溢出區 O[0..m-1]。 

 

3. 如何衡量hash函數的優劣？簡要敘述hash表技術中的沖突概念，并指出三種解決沖突的方法。

答：評價哈希函數優劣的因素有：能否將關鍵字均勻影射到哈希空間上，有無好的解決沖突的方法，計算哈希函數是否簡單高效。由于哈希函數是壓縮映像，沖突難以避免。解決沖突的方法見上面2題。 

 

4．HASH方法的平均查找路長決定于什么？ 是否與結點個數N有關？ 處理沖突的方法主要有哪些？

答：哈希方法的平均查找路長主要取決于負載因子（表中實有元素數與表長之比），它反映了哈希表的裝滿程度，該值一般取0.65~0.9。解決沖突方法見上面2題。 

 

5．在采用線性探測法處理沖突的哈希表中，所有同義詞在表中是否一定相鄰？

答：不一定相鄰。哈希地址為i（0≤i≤m-1）的關鍵字，和為解決沖突形成的探測序列i的同義詞，都爭奪哈希地址i。 

五、算法設計題

1．在用除余法作為散列函數、線性探測解決沖突的散列表中，寫一刪除關鍵字的算法，要求將所有可以前移的元素前移去填充被刪除的空位，以保證探測序列不致于斷裂。

答：[題目分析]首先計算關鍵字的散列地址，若該地址為空，則空操作；若該地址有關鍵字，但與給定值不等，則用解決沖突的方法去查找給定值；若該地址有關鍵字且與給定值相等，則實行刪除。題目要求將所有可以前移的元素前移去填充被刪除的空位，以保證探測序列不斷裂。由于用線性探測解決沖突，設被刪除元素的散列地址為i，則其余m-1（m為表長）個位置均可能是同義詞。查找同義詞的操作直到碰到空地址或循環一圈回到i才能結束。為了提高算法效率，減少數據移動，應將最后一個同義詞前移填充被刪除關鍵字。

     void HsDelete（rectype HS[]，K）

     //在以除余法為散列函數、線性探測解決沖突的散列表HS中，刪除關鍵字K

     {i=K % P； // 以造表所用的除余法計算關鍵字K的散列地址

     if（HS[i]==null）{printf（“散列表中無被刪關鍵字”）；exit（0）；}

     // 此處null代表散列表初始化時的空值

     switch

     {case HS[i]==K：del(HS，i，i，K)；break；

     case HS[i]!=K：di=1；j=(i+ di)%m； // m為 表長

             while（HS[j]!=null && HS[j]!=K && j!=i）// 查找關鍵字K

             {di=di+1；

             j=(i+di)%m； }// m為 表長

    if（HS[j]==K）del(HS，i，j，K)；

    else {printf（“散列表中無被刪關鍵字”）；exit（0）;}

         }// switch

         }算法結束

    void del（rectype HS[]，in i，int j，rectype K）

    //在散列表HS中，刪除關鍵字K，K的散列地址是i，因解決沖突而將其物理地置于表中j。算法查找關鍵字K的同義詞，將其最后一個同義詞移到位置j，并將其同義詞的位置置空。

     {di=1；last=j；x=(j+di)% m；// 探測地址序列，last記K的最后一個同義詞的位置

     while（x!=i） //可能要探測一圈

         {if（HS[x]==null）break； // 探測到空位置，結束探測

         else if（HS[x]%P==i）last=x；// 關鍵字K的同義詞

         di=di+1；x=(j+di) % m； // 取下一地址探測

         }

     HS[j]=HS[last]; HS[last]=null; //將哈希地址last的關鍵字移到哈希地址j

    }

    [算法討論] 由于用線性探測解決沖突，可能發生“二次聚集”（兩個第一哈希地址不同的記錄爭奪同一后繼哈希地址）。象上面這樣處理后，對于哈希地址為i的記錄沒有問題了，但由于將地址j置空，有可能截斷了其它記錄的探測通路。最明顯的是哈希地址為j的記錄就查不到了。解決的辦法是繼續調整，直到當前哈希表中的每個記錄的查找都是正確的為止。這里不再深入討論。 

 

2．設排序二叉樹中結點的結構為下述三個域構成: 

    data: 給出結點數據的值；left: 給出本結點的左兒子結點的地址；right: 給出本結點的右兒子結點的地址

    設data 域為正整數，該二叉樹樹根結點地址為T。 現給出一個正整數x。請編寫非遞歸程序，實現將data域的值小于等于x的結點全部刪除掉。

答：[題目分析]利用二叉排序樹的性質，從根結點開始查找，若根結點的值小于等于x，則根結點及其左子樹均應刪除，然后以右子樹的根結點為樹根，重新開始查找。若根結點的值大于x，則順左子樹向下查找，直到某結點的值小于等于x，則該結點及其左子樹均應刪除。下面設計一查找算法，確定被刪除子樹的根結點，再設計一刪除算法，刪除以被刪結點為根的子樹。

     typedef struct node

    {int data； struct node *left，*right;

    }BiTNode，*BSTree；

    void DelTree(BSTree r）

         //非遞歸刪除以r為根的二叉排序樹

     {BSTree S[]；// 棧，容量足夠大，棧中元素是二叉排序樹結點的指針

    top=0；

    while （r!=null || top>0）

         {while（r!=null） // 沿左分枝向下

             {S[++top]=r；r=r->left ；}

         if（top>0） // 退棧，沿棧頂結點的右子樹向下刪除，釋放被刪除結點空間

             {p=S[top--]；r=p->right；free（p）；}

     }

    }// DelTree

     void DeleteAllx(BSTree Ｔ，int　x）

        　 //在二叉排序樹Ｔ中，刪除所有小于等于x的結點

     {BSTree p=T，q；

    while（T && T->data≤x） //根結點的值小于等于x

         {p=T；T=T->right；p->right=null；

    DelTree（p）；} //刪除二叉樹p,刪除持續到“根”結點值大于x或T為空樹為止

     if (T)

         {q=T；p=T->left；

         while（p && p->data>x） //沿根結點左分枝向下，查小于等于x的結點

         {while（p && p->data>x） { q=p；p=p->left；} // q記p的雙親

             if（p） //p結點的值小于等于x

             {q->left=p->right；p->right=null；DelTree（p）； }

             p=q->left；// 再查原p的右子樹中小于等于x的結點

             }}

    }// DeleteAllx