數(shù)據(jù)結(jié)構(gòu)習(xí)題三

數(shù)據(jù)結(jié)構(gòu)習(xí)題三第五局部查找考點(diǎn)一查找的根本概念本局部考查查找的根本概念。

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

(1)~(3):

A.必須以順序方式存儲(chǔ)

B.必須以鏈表方式存儲(chǔ)

C.必須以散列方式存儲(chǔ)

D.既可以以順序方式，也可以以鏈表方式存儲(chǔ)

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

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

(4)~(5)：

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

(1).順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)方式都支持線性查找。(2).二分查找時(shí)，數(shù)據(jù)必須以順序方式查找，而且必須有序。假設(shè)是鏈?zhǔn)酱鎯?chǔ)，那么只能

支持順序查找。假設(shè)是數(shù)據(jù)無(wú)序，那么不能二分查找。

(3).要進(jìn)行散列查找，那么元素必須以散列方式進(jìn)行存儲(chǔ)。

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

第五局部查找考點(diǎn)一查找的根本概念4.第五局部查找考點(diǎn)二順序查找法順序查找法通常考查查找一個(gè)元素的平均查找長(zhǎng)度。5.第五局部查找考點(diǎn)二順序查找法1.對(duì)于靜態(tài)表的順序查找法，假設(shè)在表頭設(shè)置崗哨，那么正確的查找方式為〔〕A.從第0個(gè)元素往后查找該數(shù)據(jù)元素

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

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

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

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

7.第五局部查找考點(diǎn)三折半查找法1.有一個(gè)有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，〔〕次比較后查找成功。

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

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

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

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

故而在A[11]查找。因?yàn)閔igh=mid-1=12-1=11=low，A[low]=A[high]=82，查找成功。8.第五局部查找考點(diǎn)三折半查找法2.在有11個(gè)關(guān)鍵字的有序表中進(jìn)行折半查找，查找失敗時(shí)的最少比較次數(shù)和最多比較次數(shù)分別是〔〕

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

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

10.第五局部查找考點(diǎn)四二叉排序樹1.假設(shè)構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不超過(guò)()

A.n/2B.nC.(n+1)/2D.n+1B【解析】最壞的情況下，二叉排序樹為單支樹，比方構(gòu)造一棵{1,2,3,4,5,…,n}的二叉樹，那么得到的二叉排序樹如以下圖所示。由上圖可以看出，最壞的情況下，每插入一個(gè)結(jié)點(diǎn)，都在該二叉排序樹的尾部插入，該二叉排序樹插入結(jié)點(diǎn)的復(fù)雜度類似于在鏈表的表尾增加一個(gè)結(jié)點(diǎn)，該二叉排序樹的深度為n。

11.第五局部查找考點(diǎn)五平衡二叉樹本考點(diǎn)主要考查：平衡二叉樹的概念和構(gòu)造方法

12.第五局部查找考點(diǎn)五平衡二叉樹1.由元素序列〔27，16，75，38，51〕構(gòu)造平衡二叉樹，那么首次出現(xiàn)的最小不平衡子樹的根〔即離插入結(jié)點(diǎn)最近且平衡因子的絕對(duì)值為2的結(jié)點(diǎn)〕為()

A.27B.38C.51D.75D【解析】由元素序列〔27，16，75，38，51〕構(gòu)造平衡二叉樹，首次出現(xiàn)的最小不平衡子樹的根〔即離插入結(jié)點(diǎn)最近且平衡因子的絕對(duì)值為2的結(jié)點(diǎn)〕為第一次需要旋轉(zhuǎn)的局部，我們來(lái)看看構(gòu)造平衡二叉樹的過(guò)程〔如以下圖〕：如上圖所示，當(dāng)插入結(jié)點(diǎn)51之后，有27和75兩個(gè)結(jié)點(diǎn)失去平衡，但是首次出現(xiàn)的最小不平衡子樹應(yīng)該是離插入結(jié)點(diǎn)51最近的且平衡因子的絕對(duì)值為2的結(jié)點(diǎn)75，而不是27。

13.第五局部查找考點(diǎn)六B樹及其根本操作、B+樹的根本概念這局部主要考查：1、考查方式是B-樹的根本概念；2、B-樹的建立；

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

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

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

第五局部查找考點(diǎn)六B樹及其根本操作、B+樹的根本概念BF15.第五局部查找考點(diǎn)六B樹及其根本操作、B+樹的根本概念【解析】構(gòu)建B-樹的過(guò)程如下圖。16.第五局部查找考點(diǎn)六B樹及其根本操作、B+樹的根本概念B-樹的刪除操作不同于插入操作，其步驟如下：

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

②否那么，要從其左〔或右〕兄弟結(jié)點(diǎn)“借〞關(guān)鍵字；

③假設(shè)其左右兄弟都沒(méi)有關(guān)鍵字可以借〔結(jié)點(diǎn)中只有最少量的關(guān)鍵字〕，那么必須進(jìn)行結(jié)點(diǎn)的合并。

下面我們?cè)賮?lái)看看刪除結(jié)點(diǎn)38之后，B-樹的變化情況。如圖6.5所示。待刪除關(guān)鍵字38所在結(jié)點(diǎn)向其左兄弟接一個(gè)關(guān)鍵字，于是把父結(jié)點(diǎn)的30“拉下來(lái)〞，把兄弟結(jié)點(diǎn)里面最靠近自己的那個(gè)關(guān)鍵字往父結(jié)點(diǎn)“拉上去〞，最后得到以下圖(2)所示的B-樹17.第五局部查找考點(diǎn)六B樹及其根本操作、B+樹的根本概念2.下面關(guān)于m階B樹說(shuō)法正確的選項(xiàng)是〔〕

①每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹；

②樹中每個(gè)結(jié)點(diǎn)至多有m?1個(gè)關(guān)鍵字；

③所有葉子在同一層上；

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

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

方案〔如鏈地址法、二次探測(cè)再散列等〕來(lái)解決沖突。這局部需要考生手工畫圖；3、計(jì)算哈希表的在查找成功和查找失敗的情況下平均查找長(zhǎng)度〔或查找某一個(gè)元素的比較次數(shù)〕。19.第五局部查找考點(diǎn)七哈希表1.以下說(shuō)法錯(cuò)誤的選項(xiàng)是〔〕

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

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

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

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

addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是〔〕

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

D【解析】二次探測(cè)再散列法，簡(jiǎn)單地理解，就是先探測(cè)H(key)=keymod11，假設(shè)成功，那么得到key的地址，否那么依次探測(cè)H〔key〕=(key±i*i)mod14，直到探測(cè)到key的地址為止。【注意，處理沖突為(mod表長(zhǎng))】

因?yàn)镠〔49〕=49mod11=5，與38的地址發(fā)生沖突。再計(jì)算

H1=(5+12)mod14=6

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

H1=(5?12)mod14=4

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

H2=(5+22)mod14=9

因?yàn)闆](méi)有關(guān)鍵字存放在下標(biāo)為9的位置，所以49可以放在下標(biāo)為9的位置。21.第六局部排序考點(diǎn)一排序的根本概念本考點(diǎn)考查排序的根本概念。

22.第六局部排序考點(diǎn)一排序的根本概念1.一個(gè)排序算法時(shí)間復(fù)雜度大小〔〕有關(guān)。

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

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

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

C23.第六局部排序考點(diǎn)二插入排序本考點(diǎn)主要考查折半插入排序和直接插入排序。請(qǐng)同學(xué)們注意插入排序的復(fù)雜度、平均移動(dòng)元素次數(shù)，并圍繞這兩個(gè)點(diǎn)展開復(fù)習(xí)。

24.第六局部排序考點(diǎn)二插入排序1.n個(gè)關(guān)鍵碼排序，如果選用直接插入排序方法，那么元素的移動(dòng)次數(shù)在最壞情況下可以到達(dá)〔〕

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

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

故而，選擇B答案。

25.第六局部排序考點(diǎn)二插入排序1.以下為直接插入排序的算法。請(qǐng)分析算法，并在橫線上填充適當(dāng)?shù)恼Z(yǔ)句。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.第六局部排序考點(diǎn)三冒泡排序冒泡排序的命題方式有兩種：1、圍繞記錄交換次數(shù)展開；2、可以簡(jiǎn)單地寫一個(gè)冒泡排序程序

27.1.設(shè)一組初始記錄關(guān)鍵字序列為(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

第六局部排序考點(diǎn)三冒泡排序D【解析】熟悉冒泡排序過(guò)程28.第六局部排序考點(diǎn)四簡(jiǎn)單項(xiàng)選擇擇排序本考點(diǎn)主要考查簡(jiǎn)單項(xiàng)選擇擇排序下的比較次數(shù)和移動(dòng)次數(shù)、排序的時(shí)間復(fù)雜度和穩(wěn)定性，也可能考查簡(jiǎn)單項(xiàng)選擇擇排序算法的編寫，請(qǐng)同學(xué)們多注意這些常見的考查點(diǎn)。

29.第六局部排序考點(diǎn)四簡(jiǎn)單項(xiàng)選擇擇排序2.采用簡(jiǎn)單項(xiàng)選擇擇排序，比較次數(shù)與移動(dòng)次數(shù)分別為〔〕

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

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

【解析】簡(jiǎn)單項(xiàng)選擇擇排序的比較次數(shù)KCN與對(duì)象的初始排列無(wú)關(guān)。設(shè)整個(gè)待排序?qū)ο?/p>

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

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

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

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

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

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

C30.第六局部排序考點(diǎn)五希爾排序本考點(diǎn)考查希爾排序算法。希爾排序算法和基數(shù)排序算法的解題思路都挺單一，請(qǐng)同學(xué)們掌握解題思路，舉一反三。

31.第六局部排序考點(diǎn)五希爾排序1.對(duì)序列{15，9，7，8，20，-1，4，}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15，-l，4，8，20，9，7}，那么該次采用的增量是〔〕

A.lB.4C.3D.2

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

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

33.第六局部排序考點(diǎn)六快速排序1.設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為〔〕

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

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

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

34.第六局部排序考點(diǎn)七堆排序堆排序主要命題有兩種方式：1、堆排序的