2023年研究生類研究生入學(xué)考試專業(yè)課計算機(jī)學(xué)科專業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解

2023年研究生類研究生入學(xué)考試專業(yè)課計算機(jī)學(xué)科專業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點(diǎn)試題黑鉆版(共50題)1.試設(shè)計一算法，使得在盡可能少的時間內(nèi)重排數(shù)組，將所有取負(fù)值的關(guān)鍵字放在所有取非負(fù)值的關(guān)鍵字之前，并分析算法的時間復(fù)雜度。2.無向圖G有23條邊，度為4的頂點(diǎn)有5個，度為3的頂點(diǎn)有4個，其余都是度為2的頂點(diǎn)，則圖G最多有______個頂點(diǎn)。A.11B.12C.15D.163.由權(quán)值為8，4，5，7的4個葉結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為______。A.24B.36C.48D.724.多路平衡歸并排序是外排序的主要方法，試問多路平衡歸并排序包括哪兩個相對獨(dú)立的階段?每個階段完成何種工作?5.設(shè)某二叉樹的前序遍歷序列為：ABCDEFGGI，中序遍歷序列為：BCAEDGHFI

(1)試畫出該二叉樹；

(2)寫出由給定的二叉樹的前序遍歷序列和中序遍歷序列構(gòu)造出該二叉樹的算法。

(3)設(shè)具有四個結(jié)點(diǎn)的二叉樹的前序遍歷序列為abcd；S為長度等于4的由a，b，c，d排列構(gòu)成的字符序列，若任取S作為上述算法的中序遍歷序列，試問是否一定能構(gòu)造出相應(yīng)的二叉樹?為什么?試列出具有4個結(jié)點(diǎn)二叉樹的全部形態(tài)及相應(yīng)的中序遍歷序列。6.設(shè)有一個n×n的上三角矩陣(aij)，將其上三角中的元素按先行后列的順序存于數(shù)組B[m]中，使得B[k]=aij且k=f1(i)+f2(j)+c，請推導(dǎo)出函數(shù)f1、f2和常數(shù)c，要求f1和f2中不含常數(shù)項。7.如下圖所示，在下面的5個序列中，符合深度優(yōu)先遍歷的序列有______個。

①aebfdc

②acfdeb

③aedfcb

④aefdbc

⑤aecfdb

A.3B.4C.3D.28.利用雙向鏈表做線性表的存儲結(jié)構(gòu)的優(yōu)點(diǎn)是______。A.便于進(jìn)行插入和刪除的操作B.提高按關(guān)系查找數(shù)據(jù)元素的速度C.節(jié)省空間D.便于銷毀結(jié)構(gòu)釋放空間9.設(shè)計一個算法，將一棵以鏈接方式存儲的二叉樹按順序方式存儲到數(shù)組A中。10.設(shè)T是哈夫曼二叉樹，具有5個葉結(jié)點(diǎn)，樹T的高度最高可以是______。A.3B.4C.5D.611.采用順序結(jié)構(gòu)存儲串，編寫一個函數(shù)index(s1，s2)，用于判定s2是否是s1的子串。若是子串，返回其在主串中的位置；否則返回-1。12.線性表是(

)。A.一個有限序列，可以為空B.一個有限序列，不可以為空C.一個無限序列，可以為空D.一個無限序列，不可以為空13.在一棵表示有序集S的二叉搜索樹(binarysearchtree)中，任意一條從根到葉結(jié)點(diǎn)的路徑將S分為3部分：在該路徑左邊結(jié)點(diǎn)中的元素組成的集合S1；在該路徑上的結(jié)點(diǎn)中的元素組成的集合S2；在該路徑右邊結(jié)點(diǎn)中的元素組成的集合S3。S=S1∪S2∪S3。若對于任意的a∈S1，b∈S2，c∈S3，是否總有a≤b≤c?為什么?14.已知A和B為兩個n×n階的對稱矩陣，輸入時，對稱矩陣只輸入下三角形元素，存入一維數(shù)組，如圖所示(對稱矩陣M存儲在一維數(shù)組A中)，設(shè)計一個算法求對稱矩陣A和B的乘積。

15.設(shè)循環(huán)隊列的存儲容量為maxSize，隊頭和隊尾指針分別為front和rear。若有一個循環(huán)隊列Q，則可應(yīng)用下列______算式計算隊列元素個數(shù)。A.Q.rear-Q.frontB.Q.rear-Q.front+1C.(Q.rear-Q.front)%maxSize+1D.(Q.rear-Q.front+maxSize)%maxSize16.對于有n個數(shù)據(jù)元素的順序存儲的表，一個遞增有序，另一個無序，查找一個元素時采用順序算法，對有序表從頭開始查找，發(fā)現(xiàn)當(dāng)前運(yùn)算已小于待查找元素時停止查找，確定查找不成功。已知查找任何一個元素的概率相同，則在兩種表中成功查找______。A.平均時間后者小B.無法確定C.平均時間前者小D.平均時間相同17.有5個元素，其入棧次序為A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧的次序不包括______。A.CDEBAB.CDBEAC.CDBAED.CDAEB18.假設(shè)以行序為主序存儲二維數(shù)組A—array[1..100，1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5，5]=

。A.808B.818C.1010D.102019.在二叉樹的二叉鏈表中，空指針數(shù)有______個，等于非空指針數(shù)加2。選項中n為二叉樹結(jié)點(diǎn)數(shù)，n1是單分支結(jié)點(diǎn)數(shù)，n2是雙分支結(jié)點(diǎn)數(shù)。A.n+1B.n1C.n2D.n1+120.計算出的地址分布最均勻的散列函數(shù)是______。A.數(shù)字分析法B.除留余數(shù)法C.平方取中法D.折疊法21.若一個圖的邊集為{(A，B)，

(A，C)，

(B，D)，

(C，F(xiàn))，

(D，E)，

(D，F(xiàn))}，則從頂點(diǎn)A開始對該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為

。A.A，B，C，D，E，F(xiàn)B.A，B，C，F(xiàn)，D，EC.A，B，D，C，E，F(xiàn)D.A，C，B，F(xiàn)，D，E22.由權(quán)值分別為3，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為

。A.24B.48C.72D.5323.如果一棵有n個結(jié)點(diǎn)的滿二叉樹的高度為h(根結(jié)點(diǎn)所在的層次為1)，則求解下列問題。

(1)用高度如何表示結(jié)點(diǎn)總數(shù)n?用結(jié)點(diǎn)總數(shù)n如何表示高度h?

(2)若對該樹的結(jié)點(diǎn)從0開始按中序遍歷次序進(jìn)行編號，則如何用高度h表示根結(jié)點(diǎn)的編號?如何用高度h表示根結(jié)點(diǎn)的左子女結(jié)點(diǎn)的編號和右子女結(jié)點(diǎn)的編號?24.下面給出的4種排序方法中，______排序法是不穩(wěn)定性排序法。A.插入B.冒泡C.二路歸并D.堆25.若在一棵完全二叉樹中對所有結(jié)點(diǎn)按層次自上向下，同一層次自左向右進(jìn)行編號，根結(jié)點(diǎn)的編號為0，現(xiàn)有兩個不同的結(jié)點(diǎn)，它們的編號是p和q，那么判斷它們在同一層的條件應(yīng)是______。

A．

B．

C．

D．p/2==q/226.以下排序方法中，穩(wěn)定的排序方法是______。A.直接插入排序B.直接選擇排序C.堆排序D.基數(shù)排序27.圖的D-搜索類似于BFS(廣度優(yōu)先搜索)，不同之處在于用棧代替BFS中的隊列，入、出隊列的操作改為入、出棧的操作，即當(dāng)一個頂點(diǎn)的所有鄰接點(diǎn)被搜索之后，下一個搜索出發(fā)點(diǎn)應(yīng)該是最近入棧(棧頂)的頂點(diǎn)。請用鄰接表作為存儲結(jié)構(gòu)，寫一個D-搜索算法。28.在對一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行希爾排序時，假定d0=9，d1=4，d2=2，d3=1，則第二趟排序結(jié)束后前4條記錄為______。A.(50，20，15，70)B.(60，45，80，50)C.(15，20，50，40)D.(15，20，80，70)29.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)?A.存儲密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示30.關(guān)于B-樹，下列說法中不正確的是______。A.B-樹是一種查找樹B.所有的葉結(jié)點(diǎn)具有相同的高度C.2-3樹中，所有非葉子結(jié)點(diǎn)有1或者3個孩子結(jié)點(diǎn)D.通常情況下，B-樹不是二叉樹31.對于無向圖的生成樹，下列說法錯誤的是______。A.生成樹是遍歷的產(chǎn)物B.從同一頂點(diǎn)出發(fā)所得的生成樹相同C.生成樹中不包括環(huán)D.不同遍歷方法所得的生成樹不同32.如果從無向圖的任意一個頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是______。A.強(qiáng)連通圖B.連通圖C.有回路D.一棵樹33.已知一棵二叉樹，共有n個結(jié)點(diǎn)，那么此二叉樹的高度為______。

A．nlog2n

B．log2n

C．

D．不確定34.已知單鏈表A的長度為m，單鏈表B的長度為n，若將B鏈接在A的末尾，在沒有鏈尾指針的情況下，算法的時間復(fù)雜度應(yīng)為______。A.O(1)B.O(m)C.O(n)D.O(m+n)35.設(shè)計在無頭結(jié)點(diǎn)的單鏈表中刪除第i個結(jié)點(diǎn)的算法。36.試問中序序列及后序序列是否能唯一地建立二叉樹?若不能，則說明理由；若能，則對中序序列[)BEAFGC和后序序列DEBGFCA構(gòu)造二叉樹。37.后序序列與層次序列相同的非空二叉樹是______。A.滿二叉樹B.完全二叉樹C.單支樹D.只有根結(jié)點(diǎn)的樹38.試編寫一個算法，檢查一個程序中的花括號、方括號和圓括號是否配對，若能夠全部配對則返回1，否則返回0。39.假設(shè)按低下標(biāo)優(yōu)先存儲整型數(shù)組A[-3:8，3:5，-4:0，0:7]時，第一個元素的字節(jié)存儲地址是100，每個整數(shù)占4個字節(jié)，則A[0，4，-2，5]的存儲地址是(

)。A.1783B.1784C.1985D.198440.設(shè)有15000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素。

在快速排序、堆排序、歸并排序、基數(shù)排序和希爾排序中，宜采用哪種方法并說明理由?41.已知連通圖如下：

(1)若從頂點(diǎn)B出發(fā)對該圖進(jìn)行遍歷，分別給出本圖的按深度優(yōu)先搜索和按廣度優(yōu)先搜索的頂點(diǎn)序列；

(2)寫出按深度優(yōu)先搜索的遞歸程序。42.假定數(shù)組A[0，…，n-1]中有多個零元素，試寫出一個函數(shù)，將A中所有的非零元素依次移到數(shù)組A的前端。43.有6個元素按6，5，4，3，2，1的順序依次進(jìn)棧，不合法的出棧序列是______。A.543612B.453126C.346521D.23415644.就平均性能而言，目前最好的排序算法是______。A.選擇排序B.快速排序C.冒泡排序D.插入排序45.中綴表達(dá)式D/C“A+B*E—D*F的前綴表達(dá)式為

。A.-+/D^CA*BE*DFB.DCA^/BE*+DF*-C.-C^A+/D*BE*DFD.-+/D^C*ABE*DF46.設(shè)計一個算法，判斷無向圖G是否連通。若連通，則返回1；否則返回0，假設(shè)圖中頂點(diǎn)標(biāo)號從0到g.vexnum-1。47.如果T2是由有序樹T轉(zhuǎn)換成的二叉樹，那么T中結(jié)點(diǎn)的后根遍歷序列對應(yīng)T2中結(jié)點(diǎn)的______遍歷序列。A.前序B.中序C.后序D.層次序48.下面關(guān)于m階B樹的說法中，正確的是______。

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

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

③所有葉子在同一層上。

④當(dāng)插入一個數(shù)據(jù)項引起B(yǎng)樹結(jié)點(diǎn)分裂后，樹長高一層。A.①②③B.②③C.②③④D.③49.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時，允許退棧操作，則下面得不到的序列為______。A.fedcbaB.bcafedC.dcefbaD.cabdef50.說明稀疏矩陣的三元組存儲結(jié)構(gòu)并實現(xiàn)稀疏矩陣的基本操作。第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：采用類似于快速排序中的劃分思想。算法如下：

voidpart(KeyTypeA[],intn){

inti-1;j=n;

KeyTypetemp;

while(i＜j){

while(i＜j&&A[j]＞=0)j--;

//從右向左找負(fù)數(shù)

while(i＜j&&A[i]＜0)i++;

//從左向右找非負(fù)數(shù)

if(i＜j){

//交換元素A[i]和A[j]

temp=A[i];A[i]=A[j];A[j]=temp;

i++;j--;

}

}

}

該算法的時間復(fù)雜度為O(n)。2.參考答案：D由于在具有n個頂點(diǎn)e條邊的無向圖中，有，故可求得度為2的頂點(diǎn)數(shù)為7個，從而最多有16個頂點(diǎn)。3.參考答案：C[解析]由權(quán)值為8，4，5，7的4個葉結(jié)點(diǎn)構(gòu)造出的一棵哈夫曼樹如下圖所示。它的帶權(quán)路徑長度WPL的計算有兩種方法：一是先求每一個葉結(jié)點(diǎn)的帶權(quán)路徑長度，加起來得到WPL=4×2+5×2+7×2+8×2=48；另一種方法是把所有非葉結(jié)點(diǎn)的權(quán)值加起得到WPL=24+9+15=48。

4.參考答案：多路平衡歸并排序由兩個相對獨(dú)立的階段組成：生成初始?xì)w并段和多趟歸并排序。生成初始?xì)w并段階段根據(jù)內(nèi)存工作區(qū)的大小，將有n個記錄的磁盤文件分批讀入內(nèi)存，采用有效的排序方法分別進(jìn)行排序，生成若干個有序的子文件，即初始?xì)w并段。多趟歸并排序階段采用多路歸并方法將這些歸并段逐趟歸并，最后歸并成為一個有序文件。5.參考答案：

(1)

(2)設(shè)二叉樹的前序遍歷序列為P1，P2，…，Pm，中序遍歷序列為S1，S2，…，Sm。因為前序遍歷是“根左右”，中序遍歷是“左右根”，則前序遍歷序列中第一個結(jié)點(diǎn)是根結(jié)點(diǎn)(P1)。到中序序列中查詢到Si=P1，根據(jù)中序遍歷時根結(jié)點(diǎn)將中序序列分成兩部分的原則，有：

若i=1，即S1=P1，則這時的二叉樹沒有左子樹；否則，S1，S2，…，Si-1是左子樹的中序遍歷序列，用該序列和前序序列P2，P3，…，Pi去構(gòu)造該二叉樹的左子樹。

若i=m，即Sm=P1，則這時的二叉樹沒有右子樹；否則，Si+1，Si+2，…，Sm是右子樹的中序遍歷序列，用該序列和前序序列中Pi+1。，Pi+2，…，Pm，去構(gòu)造該二叉樹的右子樹。算法描述請參見下面算法設(shè)計第56題。

(3)若前序序列是abcd，則并非由這4個字母的任意組合(4！=24)都能構(gòu)造出二叉樹。因為以abcd為輸入序列，通過棧只能得到1/(n+1)*2n!/(n!*n!)=14種，即以abcd為前序序列的二叉樹的數(shù)目是14。任取以abcd作為中序遍歷序列，并不全能與前序的abcd序列構(gòu)成二叉樹，例如中序序列dcab。6.參考答案：上三角矩陣第1行有n個元素，第i-1行有n-(i-1)+1個元素，第1行到第i-1行是等腰梯形，而第i行上第j個元素(即aij)是第i行上第j-i+1個元素，故元素aij在一維數(shù)組中的存儲位置(下標(biāo)k)為：

k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1

進(jìn)一步整理為：。則得。此問題考查的知識點(diǎn)是上三角矩陣的存儲方式。7.參考答案：D本題中，符合深度優(yōu)先遍歷順序的是1和5，其他三個序列均不符合。8.參考答案：B[解析]查找直接前驅(qū)和直接后繼的時間代價都是O(1)。9.參考答案：本題采用遞歸方法求A的元素值。實現(xiàn)本題功能的程序代碼如下：

voidctree(BTNode*t,charA[],inti)

{

if(t!=NULL)

{

A[i-1]=t→data;

ctree(t→left,A,2*i);

ctree(t→right,A,2*i+1);

}

}10.參考答案：C[解析]哈夫曼二叉樹是只有度為2和度為0的結(jié)點(diǎn)的二叉樹，有n個葉結(jié)點(diǎn)，就有n-1個非葉結(jié)點(diǎn)，其最大高度是n，即從第1層起到次底層止，每層有一個非葉結(jié)點(diǎn)，最底層有兩個葉結(jié)點(diǎn)。例如，下圖所示的哈夫曼樹，n=5，葉結(jié)點(diǎn)的權(quán)值為{12，22，32，42，52}，該哈夫曼樹的高度是5，所以具有5個葉結(jié)點(diǎn)的哈夫曼樹的高度最高可以是5。

11.參考答案：本題的算法思想是，設(shè)

s1="a1a2…am"

s2="b1b2…bn"

從s1中找與b1匹配的字符ai，若ai=b1，則判斷是否ai+1=b2，…，ai+1=bn，若都相等，則s2為s1子串；否則繼續(xù)比較ai之后的字符。

本題代碼如下：

intindex(Str*s1,Str*s2)

{

inti=0,j,k;

while(i＜s1-＞length)

{

j=0;

if(s1-＞ch[i]==s2-＞ch[j])

{

k=i+1;++j;

while(k＜s1-＞length&&j＜s2-＞length&&s1-＞ch[k]==s2-＞ch[j])

{

++k;++j;

}

if(j==s2-＞length)

//s2終止時找到了子串

break;

else++i;

}

else++i;

}

if(i＞=s1-＞length)

return-1;

else

returni+1;

}12.參考答案：A線性表是由相同類型的結(jié)點(diǎn)組成的有限序列。如：由n個結(jié)點(diǎn)組成的線性表

(a1，a2，…，an)

a1是最前結(jié)點(diǎn)，an是最后結(jié)點(diǎn)。結(jié)點(diǎn)也稱為數(shù)據(jù)元素或者記錄。

線性表中結(jié)點(diǎn)的個數(shù)稱為其長度。長度為O的線性表稱為空表。

所以答案為A。13.參考答案：不是。如下圖所示的二叉搜索樹：

取從4到12的路徑，則S1={1，2，3，7}，S2={4，8，10，12}，S3為空集，取S1中的元素7和S2中的元素4，令a=7，b=4，有a＞b。則上述命題不成立。14.參考答案：對稱矩陣第i行和第j列元素的數(shù)據(jù)在一維數(shù)組中的位置是：

i×(i-i)/2+j

(當(dāng)i≥j時)

j×(j-1)/2+i

(當(dāng)i＜j時)

本題實現(xiàn)代碼如下：

intvalue(inta[],inti,intj)

{

if(i＞=j)

returna[(i*(i-1))/2+j];

else

returna[(j*(j-1))/2+i];

}

voidmult(inta[],intb[],intc[n][n])

{

inti,j,k,s;

for(i=0;i＜n;++i)

for(j=0;j＜n;++j)

{

s=0;

for(k=0;k＜n;++k)

s=s+value(a,i,k)*value(b,k,j)；

c[i][j]=s;

}

}

voiddisp(inta[])

{

inti,j;

for(i=0;i＜n;++i)

{

for(j=0;j＜n;++j)

cout＜＜setw(3)＜＜value(a,i,j);

cout＜＜endl;

}

}15.參考答案：D[解析]隨著隊列中元素的進(jìn)隊出隊的交替進(jìn)行，對于rear與front兩指針，其相對位置不定。當(dāng)rear＜front時，Q.reai-Q.front+maxSize正好是隊列元素個數(shù)；當(dāng)rear＞front時，可以用(Q.rear-Q.front+maxSize)%maxSize得到隊列元素個數(shù)。16.參考答案：D[解析]順序查找算法的性能與查找表是否有序無關(guān)，注意題目中所問是成功查找的效率。17.參考答案：D以元素C，D最先出棧的次序有三個：CDEBA、CDBEA、CDBAE。18.參考答案：B公式：Loc(Aij)=10(基地址)+[(5-1)*100+(5-1)]*2=818。19.參考答案：A[解析]對于有n個結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲，其二叉鏈表中有2n個指針，其中有n-1個指針指向二叉樹結(jié)點(diǎn)，剩下n+1個指針為空，所以空指針數(shù)等于非空指針數(shù)加2。20.參考答案：B[解析]用除留余數(shù)法轉(zhuǎn)換后的散列表在表的裝填因子不斷趨向1的過程中，查找性能退化速度最慢，說明它產(chǎn)生的沖突最少，散列地址均勻分布在地址空間各處。21.參考答案：D對圖的廣度優(yōu)先遍歷方法描述為：從圖中某個頂點(diǎn)v出發(fā)，在訪問該頂點(diǎn)v之后，依次訪問v的所有未被訪問過的鄰接點(diǎn)，然后再訪問每個鄰接點(diǎn)的鄰接點(diǎn)，且訪問順序應(yīng)保持先被訪問的頂點(diǎn)其鄰接點(diǎn)也優(yōu)先被訪問，直到圖中的所有頂點(diǎn)都被訪問為止。22.參考答案：D

生成的哈夫曼樹如上圖所示，路徑長度為：3*(2+3)+2*(8+5+6)=53。23.參考答案：按照題意，該滿二叉樹的高度為h，結(jié)點(diǎn)總數(shù)為n，則：

(1)按照滿二叉樹的性質(zhì)，n=2h-1；反之，h=log2(n+1)。

(2)用高度h確定根結(jié)點(diǎn)編號的依據(jù)有以下3種。

1)從滿二叉樹推知，結(jié)點(diǎn)數(shù)有n=2h-1個，編號從0到n-1，即0～(2h-2)。

2)由于是按中序遍歷次序所作的編號，根結(jié)點(diǎn)的左、右子樹的結(jié)點(diǎn)數(shù)相等，根結(jié)點(diǎn)的編號應(yīng)位于正中。

3)按照求中點(diǎn)的公式，中點(diǎn)的編號應(yīng)為mid=(low+high)/2=(0+2h-2)/2=2h-1-1，此即滿二叉樹根結(jié)點(diǎn)的編號。依次類推，根結(jié)點(diǎn)左子樹有2h-1-1個結(jié)點(diǎn)，其結(jié)點(diǎn)編號從0到2h-1-2，左子樹根結(jié)點(diǎn)(即根結(jié)點(diǎn)左子女結(jié)點(diǎn))的編號為2h-2-1；而右子女結(jié)點(diǎn)的編號為2h-1+(2h-2-1)=3×2h-2-1。24.參考答案：D此題考查的知識點(diǎn)是排序算法的穩(wěn)定性問題。如果待排序的文件中，存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，則稱這種排序是穩(wěn)定的排序；反之，若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則稱這種排序是不穩(wěn)定的排序。是否穩(wěn)定與算法有關(guān)，相鄰數(shù)據(jù)比較的算法是穩(wěn)定的，不相鄰數(shù)據(jù)比較會出現(xiàn)不穩(wěn)定。選項A、B、C都是相鄰元素比較，是穩(wěn)定的。所以選D。25.參考答案：A[解析]由結(jié)點(diǎn)層號計算公式可得編號為i(假設(shè)結(jié)點(diǎn)編號從0開始)的結(jié)點(diǎn)所在層號為+1。當(dāng)兩個結(jié)點(diǎn)位于同一層時，有，即。注意，如果結(jié)點(diǎn)編號從1開始，則。26.參考答案：A下表為各種排序方法的性能比較。由表可知，本題答案為A。27.參考答案：本題直接將BFS算法中的隊列改為棧即可，程序代碼如下：

voidbfs1(graphg,intV)

{

intstack[Vnum],top=-1;

intvisited[Vnum],i;

arcnode*p;

for(i=0;i＜Vnum;++i)

//賦初值

visited[i]=0;

visit(v);

//假設(shè)此函數(shù)已經(jīng)定義，表示對v結(jié)點(diǎn)的訪問操作

visited[v]=1;

++top;

stack[top]=v;

while(top＞=0)

{

v=stack[top];

--top;

p=g.adjlist[v].firstarc;

while(p!=NULL)

{

if(!visited[p→adjvex])

{

visit(p→adjvex);//訪問p

visited[p→adjvex]=1;

++top;

stack[top]=p→adjvex;

}

p=p→nextarc;

}

}

}28.參考答案：Ct=3，d0=9，d1=4，d2=2，d3=1，第1趟(d1=4)后的結(jié)果為(15，40，60，20，50，70，95，45，80)，第2趟(d2=2)后的結(jié)果為(15，20，50，40，60，45，80，70，95)，本題答案為(15，20，50，40)。29.參考答案：A[解析]本題主要考查的知識點(diǎn)是順序存儲結(jié)構(gòu)的特點(diǎn)。順序存儲的主要優(yōu)點(diǎn)：可以順序存取表中任意元素；主要缺點(diǎn)：在插入、刪除某一元素時，需要移動大量元素。30.參考答案：CB-樹定義如下：

一棵m階B-樹，或者是空樹，或者是滿足以下性質(zhì)的m叉樹：

(1)根結(jié)點(diǎn)或者是葉子，或者至少有兩棵子樹，至多有m棵子樹。

(2)除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有棵子樹，至多有m棵子樹。

(3)所有葉子結(jié)點(diǎn)都在樹的同一層上。

(4)每個結(jié)點(diǎn)應(yīng)包含如下信息：(n，A0，K1，A1，K2，A2，…，Kn，An)。

其中：

·Ki(1≤i≤n)是關(guān)鍵字，且K＜Ki+1(1≤i≤n-1)；

·Ai(i=0，1，…，n)為指向孩子結(jié)點(diǎn)的指針，且Ai-1所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都小于Ki，Ai所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都大于Ki。

n是結(jié)點(diǎn)中關(guān)鍵字的個數(shù)，且-1≤n≤m-1，n+1為子樹的棵數(shù)。31.參考答案：B[解析]生成樹不允許有環(huán)是顯而易見的。生成樹是通過遍歷圖中的頂點(diǎn)得到的；遍歷方法不同，所得生成樹也不同。從同一頂點(diǎn)開始遍歷，如果某一個頂點(diǎn)的鄰接頂點(diǎn)有多個可選時，選擇不同的鄰接頂點(diǎn)，可構(gòu)成不同的生成樹，所以選項B不正確。32.參考答案：B[解析]對無向圖作一次深度優(yōu)先搜索，可遍歷連通圖的所有頂點(diǎn)。當(dāng)然，通過深度優(yōu)先搜索也可以遍歷一棵樹，不過遍歷樹通常被稱為中序、前序、后序遍歷；強(qiáng)連通圖是有向圖，與題意矛盾；有回路的無向圖不一定是連通圖，因為回路不一定包含圖的所有結(jié)點(diǎn)。33.參考答案：D已知一棵二叉樹共有n個結(jié)點(diǎn)，但二叉樹的形式?jīng)]有給出，因此，二叉樹的高度不能確定。34.參考答案：B[解析]需要搜索并找到A的鏈尾，遍歷表A的m個結(jié)點(diǎn)。35.參考答案：算法思想為：

(1)應(yīng)判斷刪除位置的合法性，當(dāng)i＜0或i＞n-1時，不允許進(jìn)行刪除操作；

(2)當(dāng)i=0時，刪除第一個結(jié)點(diǎn)；

(3)當(dāng)0＜i＜n時，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：

delete(LinkList*q，inti)

{

∥在無頭結(jié)點(diǎn)的單鏈表中刪除第i個結(jié)點(diǎn)

LinkList

*P，*S；

intj；

if(i＜0)

printf(“Can'tdelete”)；

elseif(i==0)

{

s=q；

q=q—＞next；

free(s)；

}

else

{j=0；s=q；

while((j＜i)&&(s!=NULL))

{

p=s；

s=s=＞next；

j++：

}

if(s==NULL)

printf(“Cant'tdelete”)；

else

{

p—＞next=s—＞next；

free(s)；

}

}

}36.參考答案：[證明]

當(dāng)n=1時，只有一個根結(jié)點(diǎn)，由中序序列和后序序列可以確定這棵二叉樹。

設(shè)當(dāng)n=m-1時結(jié)論成立，現(xiàn)證明當(dāng)n=m時結(jié)論成立。

設(shè)中序序列為S1，S2，…，Sm，后序序列是P1，P2，…，Pm。因后序序列最后一個元素Pm是根，則在中序序列中可找到與Pm相等的結(jié)點(diǎn)(設(shè)二叉樹中各結(jié)點(diǎn)互不相同)Si(1≤i≤m)，因中序序列是由中序遍歷而得，所以Si是根結(jié)點(diǎn)，S1，S2，…，Si-1是左子樹的中序序列，而Si+1，Si+2，…，Sm是右子樹的中序序列。

若i=1，則S1是根，這時二叉樹的左子樹為空，右子樹的結(jié)點(diǎn)數(shù)是m-1，則{S2，S3，…，Sm}和{P1，P2，…．Pm-1}可以唯一確定右子樹，從而也確定了二叉樹。

若i=m，則Sm是根，這時二叉樹的右子樹為空，左子樹的結(jié)點(diǎn)數(shù)是m-1，則{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一確定左子樹，從而也確定了二叉樹。

最后，當(dāng)1＜i＜m時，s，把中序序列分成{S1，S2，…，Si-1}和{Si+1，Si+2，…，Sm}。由于后序遍歷是“左子樹—右子樹—根結(jié)點(diǎn)”，所以{P1，P2，…，Pi-1)和{Pi，Pi+1，…Pm-1}是二叉樹的左子樹和右子樹的后序遍歷序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一確定二叉樹的左子樹，由{Si+1，Si+2，…，Sm}和{Pi，Pi+1，…，Pm-1}可唯一確定二叉樹的右子樹。

由中序序列DBEAFGC和后序序列DEBGFCA構(gòu)造的二叉樹如下圖：

37.參考答案：D[解析]對二叉樹進(jìn)行后序遍歷的規(guī)則是LRV(左、右、根)，在多數(shù)情況下遍歷結(jié)果顯然與層次遍歷的結(jié)果不同，只有當(dāng)樹中僅含有一個結(jié)點(diǎn)的情形下，兩者才有相同的遍歷結(jié)果。38.參考答案：在算法中，掃描程序中的每一個字符，當(dāng)掃描到花、中、圓左括號時，令其進(jìn)棧，當(dāng)掃描到花、中、圓右括號時，則檢查棧頂是否為相應(yīng)的左括號，若是則作退棧處理，若不是則表明出現(xiàn)了語法錯誤，應(yīng)返回0。當(dāng)掃描到程序文件結(jié)尾后，若棧為空則表明沒有發(fā)現(xiàn)括號配對錯誤，應(yīng)返回1，否則表明棧中還有未配對的括號，應(yīng)返回0。另外，對于一對單引號或雙引號內(nèi)的字符不進(jìn)行括號配對檢查。

根據(jù)分析，編寫出算法如下：

intBracketsCheck(char*f){

//對由f所指字符串中的文本進(jìn)行括號配對檢查

stackS;charch;

//定義一個棧

char*p=f;

while(*p!='\0'){

//順序掃描字符串中的每一個字符

if(*p==39){

//單引號內(nèi)的字符不參與配對比較

while(*p!='\0'&&'P!=39)

//39為單引號的ASCII值、p++;

}

elseif(*p!='\0'&&*p==34){

//雙引號內(nèi)的字符不參與配對比較

while(*p!='\0'&&*p!=34)

//34為雙引號的ASCII值p++;

}

if(*p!='\0'){

switch(*p){

case'{':case'[':case'(':push(S,*p);break;

//左括號進(jìn)棧

case'}':getTop(S,ch);

if(ch=='{')pop(S,ch);

//棧頂?shù)淖蠡ɡㄌ柍鰲?/p>

elsereturn(0);break;

case']':getTop(S,ch);

if(ch=='[')pop(S,ch);

//棧頂?shù)淖笾欣ㄌ柍鰲?/p>

elsereturn(0);break;

case')':getTop(S,ch);

if(ch=='(')pop(S,ch);

//棧頂?shù)淖髨A括號出棧

elsereturn(0);

}

p++;

}

if(isEmpty(S))return(1);

elsereturn(0);

}

}39.參考答案：B40.參考答案：上面所說的幾種排序方法中，排序速度都很快，但快速排序、歸并排序、基數(shù)排序和希爾排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部序列，而排序過程中無法知道部分連續(xù)位置上的最終元素。而堆排序則是每次輸出一個堆頂元素(即最大或最小值的元素)，然后對堆進(jìn)行再調(diào)整，保證堆頂元素總是當(dāng)前剩下元素的最大或最小的，從而可知，如果在一個大量數(shù)據(jù)的文件中，如含有15000個元素的記錄文件中選取前10個最大的元素，宜采用堆排序。41.參考答案：

(1)在鄰接點(diǎn)按升序排列的前提下，其深度優(yōu)先搜索和廣度優(yōu)選搜索序列分別為BADCEF和BACEDF。

(2)

voiddfs(v)

{

i=GraphLocateVertex(g，v)；

∥定位頂點(diǎn)

visited[i]=1；

printf(v)；

∥輸出頂點(diǎn)信息

p=g[i]．firstarc；

while(p)

{

if(visited[p—＞adjvex]==0)dfs(g[p—＞adjvex]．vertex)；

p=p—＞next；

}

}

voidtraver()

∥深度優(yōu)先搜索的遞歸程序；以鄰接表表示的圖g是全局變量。

{

for(i=1；i＜=n；i++)

visited[i]=0；∥訪問數(shù)組是全局變量初始化。

for(vi=v1；vi＜=vn；vi++)

if(visited[GraphLocateVertex(g，vi)]==0)

dis(vi)；

}42.參考答案：因為數(shù)組是一種直接存取的數(shù)據(jù)結(jié)構(gòu)，在一維數(shù)組中元素不是像順序表那樣集中存放于表的前端，而是根據(jù)元素下標(biāo)直接存放于數(shù)組某個位置，所以將非零元素前移時必須檢測整個數(shù)組空間，并將后面變成零元素的空間清零。函數(shù)中設(shè)置一個輔助指針free，指示當(dāng)前可存放的位置，初值為0。算法的程序代碼如下：

voidcompact(intA[],intn)

{

intfree=0;

for(inti=0;i＜n;++i)

//檢測整個數(shù)組

if(A[i]!=0)

//發(fā)現(xiàn)非零元素

{

if(i!=free)

//前移非零元素

{

A[free]=A[i];

A[i]=0;

}

++free;

}

}43.參考答案：C此題考查的知識點(diǎn)是棧的后進(jìn)先出特點(diǎn)。考查出棧序列，要保證先入棧的一定不能在后入棧的前面出棧，C選項中的6在5前入棧，5沒有出棧，6卻出棧了，所以不合法。其他都符合規(guī)律。所以選C。44.參考答案：B[解析]目前，平均性能最好的排序是快速排序。45.參考答案：A第一步：加括號

D/(C^A)+B*E-D*F

(D/(C^A))+B*E-D*F

(D/(C^A))+(B*E)-D*F

(D/(C^A))+(B*E)-(D*F)

((D/(C^A))+(B*E))-(D*F)

(((D/(C-A))+(B*E))-(D*F))