數(shù)據(jù)結(jié)構習題三課件

數(shù)據(jù)結(jié)構習題三第五部分查找考點一查找的基本概念本部分考查查找的基本概念。

2第五部分查找考點一查找的基本概念1.要進行線性查找，則線性表(1)；要進行二分查找，則線性表(2)；要進行散列查找，則線性表(3)。某順序存儲的表格，其中有90000個元素，已按關鍵項的值的上升順序排列?，F(xiàn)假定對各個元素進行查找的概率是相同的，并且各個元素的關鍵項的值皆不相同。當用順序查找法查找時，平均比較次數(shù)約為(4)，最大比較次數(shù)為(5)。

(1)~(3):

A.必須以順序方式存儲

B.必須以鏈表方式存儲

C.必須以散列方式存儲

D.既可以以順序方式，也可以以鏈表方式存儲

E.必須以順序方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好

F.必須以鏈表方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好

(4)~(5)：

A.25000B.30000C.45000D.90000DECCD3【解析】

(1).順序存儲和鏈式存儲方式都支持線性查找。(2).二分查找時，數(shù)據(jù)必須以順序方式查找，而且必須有序。若是鏈式存儲，則只能

支持順序查找。若是數(shù)據(jù)無序，則不能二分查找。

(3).要進行散列查找，則元素必須以散列方式進行存儲。

(4).某順序存儲的表格，其中有90000個元素，已按關鍵項的值的上升順序排列?，F(xiàn)假定對各個元素進行查找的概率是相同的，并且各個元素的關鍵項的值皆不相同。當用順序查找法查找時，平均比較次數(shù)約為表長的一半，即45000。最壞的情況下，元素在表尾的位置，需要比較約90000次。

第五部分查找考點一查找的基本概念4第五部分查找考點二順序查找法順序查找法通常考查查找一個元素的平均查找長度。5第五部分查找考點二順序查找法1.對于靜態(tài)表的順序查找法，若在表頭設置崗哨，則正確的查找方式為（）A.從第0個元素往后查找該數(shù)據(jù)元素

B.從第1個元素往后查找該數(shù)據(jù)元素

C.從第n個元素往開始前查找該數(shù)據(jù)元素

D.與查找順序無關【解析】對靜態(tài)表的順序查找，通常在表頭或者表尾設置崗哨，道理其實都是一樣的。本題中，若在表頭設置崗哨，則應該從表尾開始向表頭方向查找，即從第n個元素開始向前查找數(shù)據(jù)元素，若查找成功，則返回該元素的位置。若返回的結(jié)果是0，則表示讀到了崗哨，查找失敗。

C6第五部分查找考點三折半查找法折半查找算法是本章的重點內(nèi)容，也是數(shù)據(jù)結(jié)構的重點考點，主要考查：1、折半查找的條件；2、折半查找條件下的關鍵字比較次數(shù)、平均時間復雜度；3、折半查找樹的建立。

7第五部分查找考點三折半查找法1.有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當折半查找值為82的結(jié)點時，（）次比較后查找成功。

A.11B.5C.4D.8C【解析】本考點大部分題目都考查在有序表上利用折半查找算法查找元素的方法以及平均查找長度，我們不再贅述。簡單地畫一個順序表A來幫助我們分析，如下表所示。對上表進行折半查找元素82，首先，?low+high)/2?=?(1+13)/2?=7，顯然A[7]=45<82，故而，在A[8]~A[13]中再進行折半查找。

此時，low=7+1=8，high=13，?(low

+high)/2?=?(8+13)/2?=10，顯然A[10]=77<82，繼續(xù)在A[11]~A[13]中查找。

此時，low=10+1=11，high=13，因為?(low+high)/2?=?(11+13)/2?=12，A[12]=95>82，

故而在A[11]查找。因為high=mid-1=12-1=11=low，A[low]=A[high]=82，查找成功。8第五部分查找考點三折半查找法2.在有11個關鍵字的有序表中進行折半查找，查找失敗時的最少比較次數(shù)和最多比較次數(shù)分別是（）

A.1和4B.3和4C.1和3D.4和5

【解析】折半查找的過程為：給定值首先和處于待查區(qū)間“中間位置”的關鍵字進行比較，若相等，則查找成功，否則將查找區(qū)間縮小到“前半個區(qū)間”或“后半個區(qū)間”之后繼續(xù)進行查找。對11個關鍵字的有序表，構建其二分查找樹如下圖所示。從上圖可以看出，查找失敗的最少比較次數(shù)為3，最多比較次數(shù)為4次，故而選擇B答案。要特別注意，有的書把失敗的比較也算作一次比較，這里我們不算一次比較。B9第五部分查找考點四二叉排序樹本考點主要考查：二叉排序樹的概念和構造方法

10第五部分查找考點四二叉排序樹1.若構造一棵具有n個結(jié)點的二叉排序樹，最壞的情況下其深度不超過()

A.n/2B.nC.(n+1)/2D.n+1B【解析】

最壞的情況下，二叉排序樹為單支樹，比如構造一棵{1,2,3,4,5,…,n}的二叉樹，則得到的二叉排序樹如下圖所示。

由上圖可以看出，最壞的情況下，每插入一個結(jié)點，都在該二叉排序樹的尾部插入，該二叉排序樹插入結(jié)點的復雜度類似于在鏈表的表尾增加一個結(jié)點，該二叉排序樹的深度為n。

11第五部分查找考點五平衡二叉樹本考點主要考查：平衡二叉樹的概念和構造方法

12第五部分查找考點五平衡二叉樹1.由元素序列（27，16，75，38，51）構造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點最近且平衡因子的絕對值為2的結(jié)點）為()

A.27B.38C.51D.75

D【解析】由元素序列（27，16，75，38，51）構造平衡二叉樹，首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點最近且平衡因子的絕對值為2的結(jié)點）為第一次需要旋轉(zhuǎn)的部分，我們來看看構造平衡二叉樹的過程（如下圖）：

如上圖所示，當插入結(jié)點51之后，有27和75兩個結(jié)點失去平衡，但是首次出現(xiàn)的最小不平衡子樹應該是離插入結(jié)點51最近的且平衡因子的絕對值為2的結(jié)點75，而不是27。

13第五部分查找考點六B樹及其基本操作、B+樹的基本概念這部分主要考查：1、考查方式是B-樹的基本概念；2、B-樹的建立；

3、結(jié)點插入和刪除時，B-樹的調(diào)整；4、B+樹。本考點對考生提出的不是編程方面的要求，

而是對B-樹的建立、插入和刪除結(jié)點時對B-樹進行調(diào)整的手工操作。

141.設輸入序列為20,45,30,89,70,38,62，19依次插入到一棵2-3樹中(初始狀態(tài)為空)，該B-樹為（）。再刪除38，該B-樹為（）。

第五部分查找考點六B樹及其基本操作、B+樹的基本概念BF15第五部分查找考點六B樹及其基本操作、B+樹的基本概念【解析】構建B-樹的過程如圖所示。16第五部分查找考點六B樹及其基本操作、B+樹的基本概念B-樹的刪除操作不同于插入操作，其步驟如下：

①首先查找待刪除關鍵字所在結(jié)點，并且要求刪除之后，結(jié)點中的關鍵字個數(shù)不小于?m/2??1;

②否則，要從其左（或右）兄弟結(jié)點“借”關鍵字；

③若其左右兄弟都沒有關鍵字可以借（結(jié)點中只有最少量的關鍵字），則必須進行結(jié)點的合并。

下面我們再來看看刪除結(jié)點38之后，B-樹的變化情況。如圖6.5所示。待刪除關鍵字38所在結(jié)點向其左兄弟接一個關鍵字，于是把父結(jié)點的30“拉下來”，把兄弟結(jié)點里面最靠近自己的那個關鍵字往父結(jié)點“拉上去”，最后得到下圖(2)所示的B-樹17第五部分查找考點六B樹及其基本操作、B+樹的基本概念2.下面關于m階B樹說法正確的是（）

①每個結(jié)點至少有兩棵非空子樹；

②樹中每個結(jié)點至多有m?1個關鍵字；

③所有葉子在同一層上；

④當插入一個數(shù)據(jù)項引起B(yǎng)樹結(jié)點分裂后，樹長高一層。BA.①②③B.②③C.②③④D.③【解析】對于m階B樹，除了根結(jié)點至少要有兩棵子樹之外，其他非葉子結(jié)點至少有?m/2?棵子樹，故而①錯誤。樹中，每個結(jié)點至多有m-1個關鍵字，而且所有葉子都在同一層上，故而②③顯然正確。但是，插入一個關鍵字使得B樹結(jié)點分裂，并不一定會引起樹長高一層，如第2題中插入結(jié)點70，B-樹的前后高度都是2，故而④錯誤。18第五部分查找考點七哈希表本考點主要命題有以下幾種形式：1、什么是哈希表的特點？影響哈希表查

找效率的因素有哪些？有哪些解決沖突的方法？2、怎么構建哈希表、怎么樣利用沖突解決

方案（如鏈地址法、二次探測再散列等）來解決沖突。這部分需要考生手工畫圖；3、計算哈希表的在查找成功和查找失敗的情況下平均查找長度（或查找某一個元素的比較次數(shù)）。19第五部分查找考點七哈希表1.以下說法錯誤的是（）

A.散列法存儲的思想是由關鍵字值決定數(shù)據(jù)的存儲地址

B.散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。

C.負載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。

D.散列表的查找效率主要取決于散列表構造時選取的散列函數(shù)和處理沖突的方法。B【解析】散列表解決沖突的辦法有多種，比如線性探測法、平方探測法、再散列法等開放定址法（即：可存放新表項的空閑地址既向其同義詞表項開放，也向其非同義詞表項開放）。當然，還有拉鏈法，拉鏈法的散列表中的結(jié)點除了包含元素自身信息，還會有其同義詞的指針，而散列地址為i的同義詞鏈表的頭指針存放在散列表的第i個單元中。20第五部分查找考點七哈希表2.設哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個結(jié)點：

addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探測再散列處理沖突，關鍵字為49的結(jié)點的地址是（）

A.8B.3C.5D.9

D【解析】二次探測再散列法，簡單地理解，就是先探測H(key)=keymod11，若成功，則得到key的地址，否則依次探測H（key）=(key±i*i)mod14，直到探測到key的地址為止。【注意，處理沖突為(mod表長)】

因為H（49）=49mod11=5，與38的地址發(fā)生沖突。再計算

H1=(5+12)mod14=6

可知依然發(fā)生了沖突。再接著計算

H1=(5?12)mod14=4

可知依然發(fā)生了沖突。再接著計算

H2=(5+22)mod14=9

因為沒有關鍵字存放在下標為9的位置，所以49可以放在下標為9的位置。21第六部分排序考點一排序的基本概念本考點考查排序的基本概念。

22第六部分排序考點一排序的基本概念1.一個排序算法時間復雜度大?。ǎ┯嘘P。

A.不與所需移動記錄的數(shù)目B.與該算法的穩(wěn)定性

C.與所需比較關鍵字的次數(shù)D.與所需輔助存儲空間的大小

【解析】本題考查影響排序算法時間復雜度的因素。內(nèi)部排序算法種類繁多，但就其排序所遵循的原則而言，大致可分為五大類：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。算法性能主要從時間復雜度、空間復雜度和穩(wěn)定性三個方面來比較。一個算法的時間復雜度，與所需要比較的關鍵字次數(shù)、需要移動的記錄數(shù)量都有關，但是與算法是否穩(wěn)定沒有關系，與所需要的輔助空間也沒有關系。

C23第六部分排序考點二插入排序本考點主要考查折半插入排序和直接插入排序。請同學們注意插入排序的復雜度、平均移動元素次數(shù)，并圍繞這兩個點展開復習。

24第六部分排序考點二插入排序1.n個關鍵碼排序，如果選用直接插入排序方法，則元素的移動次數(shù)在最壞情況下可以達到（）

A.n2/2B.n(n-1)/2C.n/2D.(n-1)/2B【解析】我們舉一個例子，比如說，要對元素5、4、3、2、1這五個元素用直接插入的方法非遞減排序。那么，4插在5前面，需要移動一次元素。3插在4、5前面，需要移動兩次元素。2要在3、4、5前面，需要將3、4、5這三個元素后移，才能給2騰出位置來。1再插入到已有序的2、3、4、5序列中，需要把這4個元素都后移，才能騰出位置來放1。故而，總共移動了4+3+2+1=10次。當有n個元素時，最壞的情況下元素的移動次數(shù)為

N=1+2+?+(n-2)+(n-1)=n(n-1)/2

故而，選擇B答案。

25第六部分排序考點二插入排序1.以下為直接插入排序的算法。請分析算法，并在橫線上填充適當?shù)恼Z句。voidstraightsort(seqlistr,intn)

{for(i=2;i<=n;i++)

{

r[0]=r[i];

j=i-1;

while(r[0].key<r[j].key)

{

r[j+1]=r[j];

j--;

}

r[j+1]=r[0];

}

}

26第六部分排序考點三冒泡排序冒泡排序的命題方式有兩種：1、圍繞記錄交換次數(shù)展開；2、可以簡單地寫一個冒泡排序程序

271.設一組初始記錄關鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）

A.F，H，C，D，P，A，M，Q，R，S，Y，X

B.P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y

C.A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X

D.H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y

第六部分排序考點三冒泡排序D【解析】熟悉冒泡排序過程28第六部分排序考點四簡單選擇排序本考點主要考查簡單選擇排序下的比較次數(shù)和移動次數(shù)、排序的時間復雜度和穩(wěn)定性，也可能考查簡單選擇排序算法的編寫，請同學們多注意這些常見的考查點。

29第六部分排序考點四簡單選擇排序2.采用簡單選擇排序，比較次數(shù)與移動次數(shù)分別為（）

A.O(n),O(logn)B.O(logn),O(n*n)

C.O(n*n),O(n)D.0(nlogn),O(n)

【解析】簡單選擇排序的比較次數(shù)KCN與對象的初始排列無關。設整個待排序?qū)ο?/p>

序列有n個對象，則第i趟選擇具有最小排序碼對象所需的比較次數(shù)總是n-i-1次?？偟?/p>

排序碼比較次數(shù)為：

KCN=(n-1)+(n-2)+……+2+1=n(n-1)/2

當這組對象的初始狀態(tài)是按其關鍵字從小到大有序的時候,對象的移動次數(shù)達到最少，

此時RMN=0。最壞情況是每一趟都要進行交換，總的對象移動次數(shù)為RMN=3(n-1)。

故而比較次數(shù)時O(

n）

C30第六部分排序考點五希爾排序本考點考查希爾排序算法。希爾排序算法和基數(shù)排序算法的解題思路都挺單一，請同學們掌握解題思路，舉一反三。

31第六部分排序考點五希爾排序1.對序列{15，9，7，8，20，-1，4，}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15，-l，4，8，20，9，7}，則該次采用的增量是（）

A.lB.4C.3D.2

B【解析】對序列{15，9，7，8，20，-1，4，}用希爾排序方法排序，經(jīng)一趟排序后序列變?yōu)閧15，-l，4，8，20，9，7}?？梢缘弥?1和9交換了位置，增量是4或者2或者1。假設增量為1，則-1應該排在最前面的位置。再假設增量為2，則15、4、20、7一組，其他記錄是另一組，排序的結(jié)果應該是4、-1、7、8、15、9、20，顯然與題中的結(jié)果不符。故而增量d=432第六部分排序考點六快速排序快速排序主要考查兩點：1、快速排序算法的特點；2、快速排序算法實現(xiàn)；

3、快速排序的過程或者一趟排序的結(jié)果。

33第六部分排序考點六快速排序1.設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結(jié)果為（）

A.2，3，5，8，6B.3，2，5，8，6

C.3，2，5，6，8D.2，3，6，5，8

C【解析】快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行