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

2023年研究生類研究生入學(xué)考試專業(yè)課計(jì)算機(jī)學(xué)科專業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點(diǎn)試題黑鉆版(共50題)1.下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)?

A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作2.在n×n(n≥3)階的稀疏矩陣A中，只有下標(biāo)滿足1＜i＜n和n-i≤j≤n-i+2的元素A[i][j]不等于0，若這些非0元素按行優(yōu)先的順序存儲(chǔ)在一維數(shù)組B中，編寫一個(gè)算法通過B求A[i][j]之值。也就是說，在存在B的情況下已知i、j，求A[i][j]。3.______的遍歷仍需要棧的支持。A.前序線索樹B.中序線索樹C.后序線索樹D.中序線索樹和前序線索樹4.對(duì)于具有n(n＞1)個(gè)頂點(diǎn)的強(qiáng)連通圖，其有向邊的條數(shù)至少是______。A.n+1B.nC.n-1D.n-25.給定一個(gè)關(guān)鍵字集合{25，18，34，9，14，27，42，51，38}，假定查找各關(guān)鍵字的概率相同，請(qǐng)畫出其最佳二叉排序樹。6.一棵124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有______個(gè)結(jié)點(diǎn)。A.247B.248C.249D.250E.2517.對(duì)一個(gè)由n個(gè)關(guān)鍵字不同的記錄構(gòu)成的序列，能否用比2n-3少的次數(shù)選出該序列中關(guān)鍵字取最大值和關(guān)鍵字取最小值的記錄?請(qǐng)說明如何實(shí)現(xiàn)?在最壞的情況下至少要進(jìn)行多少次比較?8.多維數(shù)組實(shí)際上是由______實(shí)現(xiàn)的。A.一維數(shù)組B.多項(xiàng)式C.三元組表D.簡(jiǎn)單變量9.一組記錄的關(guān)鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為

。A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84)D.(40，38，46，84，56，79)10.編寫一個(gè)在順序表上執(zhí)行順序查找的遞歸算法，在算法的參數(shù)表中增加一個(gè)整數(shù)形參loe，指明查找的開始位置。函數(shù)的首部為：

intseqSearch1(seqList&L,DataTypex,intloc);其中，DataType是順序表中每個(gè)元素的數(shù)據(jù)類型，假設(shè)已經(jīng)定義可直接使用。11.證明：具有n個(gè)頂點(diǎn)和多于n-1條邊的無向連通圖G一定不是樹。12.在下列關(guān)于線性表的敘述中，正確的是______。A.線性表的邏輯順序與物理順序總是一致的B.線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示C.線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，所有存儲(chǔ)單元的地址可連續(xù)也可不連續(xù)D.每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和查找13.用S表示進(jìn)棧操作，用X表示出棧操作，若元素的進(jìn)棧順序是1，2，3，4，為了得到出棧順序1，3，4，2，相應(yīng)的S和X的操作序列為______。A.SXSXSSXXB.SSSXXSXXC.SXSSXXSXD.SXSSXSXX14.設(shè)計(jì)一個(gè)算法指出一個(gè)無序數(shù)序中的任意一個(gè)元素是第幾大元素(從小到大數(shù))，要求比較的次數(shù)最少。15.在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的Prim算法的時(shí)間復(fù)雜度為

。A.O(n)B.O(n+e)C.O(n2)D.O(n3)16.試設(shè)計(jì)一個(gè)實(shí)現(xiàn)下述要求的Locate運(yùn)算的函數(shù)。設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表L，每個(gè)結(jié)點(diǎn)有4個(gè)數(shù)據(jù)成員：指向前驅(qū)結(jié)點(diǎn)的指針lLink、指向后繼結(jié)點(diǎn)的指針rLink、存放數(shù)據(jù)的成員data和訪問頻度freq。所有結(jié)點(diǎn)的freq初始時(shí)都為0。每當(dāng)在鏈表上進(jìn)行一次Loeate(L，x)操作時(shí)，令元素值為x的結(jié)點(diǎn)的訪問頻度freq加1，并將該結(jié)點(diǎn)前移，鏈接到與它的訪問頻度相等的結(jié)點(diǎn)后面，使得鏈表中所有結(jié)點(diǎn)保存按訪問頻度遞減的順序排列，以使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。17.設(shè)圖有n個(gè)頂點(diǎn)和e條邊，在采用鄰接矩陣時(shí)，遍歷圖的頂點(diǎn)所需時(shí)間為______；在采用鄰接表時(shí)，遍歷圖的頂點(diǎn)所需時(shí)間為O(n+e)。A.O(n)B.O(n2)C.O(e)D.O(n×e)18.關(guān)于圖(Graph)的一些問題：

(1)有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊?最少有多少條邊?

(2)表示有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素?是否為稀疏矩陣?19.折半查找的時(shí)間復(fù)雜性為______。A.O(n2)B.O(n)C.O(nlog2n)D.O(log2n)20.設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)。B的根為p，p的右子樹中結(jié)點(diǎn)個(gè)數(shù)為n，則森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是______。A.m-nB.m-n-1C.n+1D.無法確定21.表達(dá)式3*2^(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為，其中^為乘冪(

)。A.3，2，4，1，1；*^(+*-B.3．2，8；*^-C.3，2，4，2，2；*^(-D.3，2，8；*^(-22.將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，除了單向遞歸和尾遞歸的情況外，通常用來保存中間結(jié)果的是______。A.鏈表B.棧C.隊(duì)列D.順序表23.在下列指定的排序算法中，______使用的附加空間與輸入序列的長(zhǎng)度及初始排列無關(guān)。A.錦標(biāo)賽排序B.快速排序C.基數(shù)排序D.歸并排序24.線性表的每一個(gè)表元素是否必須類型相同?為什么?25.樹是結(jié)點(diǎn)的有限集合，一棵樹中有______根結(jié)點(diǎn)。A.有0個(gè)或1個(gè)B.有0個(gè)或多個(gè)C.有且只有一個(gè)D.有1個(gè)或1個(gè)以上26.設(shè)如圖所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有

個(gè)。

aebdfcacfdebaedfcbaefdcbaefdbc

A．5

B．4

C．3

D．2

27.假定從空樹開始建立一棵有n個(gè)關(guān)鍵字的m階B樹，最終得到有p(p＞2)個(gè)非失敗結(jié)點(diǎn)的B樹，那么這p個(gè)結(jié)點(diǎn)最多經(jīng)過______次分裂得來。A.pB.p-1C.p-2D.p-328.假設(shè)在二叉樹中值為x的結(jié)點(diǎn)不多于一個(gè)，試編寫算法輸出值為x的結(jié)點(diǎn)的所有祖先。29.在開地址法中散列到同一個(gè)地址而引起的“堆積”問題是由于______引起的。A.同義詞直接發(fā)生沖突B.非同義詞直接發(fā)生沖突C.同義詞之間或非同義詞之間發(fā)生沖突D.散列表“溢出”30.解決散列法中出現(xiàn)的沖突問題常采用的方法是______。A.數(shù)字分析法、除留余數(shù)法、平方取中法B.數(shù)字分析法、除留余數(shù)法、線性探測(cè)法C.數(shù)字分析法、線性探測(cè)法、雙散列法D.線性探測(cè)法、雙散列法、鏈地址法31.在有n個(gè)結(jié)點(diǎn)且為完全二叉樹的二叉排序樹中查找一個(gè)鍵值，其平均比較次數(shù)的數(shù)量級(jí)為______。A.O(n)B.O(log2/n)C.O(nlog2n)D.O(n2)32.用S表示進(jìn)棧操作，用X表示出棧操作，若元素的進(jìn)棧順序是1234，為了得到1342的出棧順序，相應(yīng)的S和X的操作序列為______。A.SXSXSSXXB.SSSXXSXXC.SXSSXXSXD.SXSSXSXX33.設(shè)排序二叉樹中結(jié)點(diǎn)的結(jié)構(gòu)由三個(gè)域構(gòu)成：數(shù)據(jù)域data，指向左兒子結(jié)點(diǎn)的指針域left，指向右兒子結(jié)點(diǎn)的指針域right。

設(shè)data域?yàn)檎麛?shù)，該二叉樹樹根結(jié)點(diǎn)地址為T?，F(xiàn)給出一個(gè)正整數(shù)x。請(qǐng)編寫非遞歸程序，實(shí)現(xiàn)將data域的值小于等于x的結(jié)點(diǎn)全部刪除。34.具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有______條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.835.分別以下列序列構(gòu)造二叉排序樹，與用其他三個(gè)序列所構(gòu)造的結(jié)果不同的是

。A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)36.自由樹(即無環(huán)連通圖)T=(V，E)的直徑是樹中所有點(diǎn)對(duì)點(diǎn)之間最短路徑長(zhǎng)度的最大值，即T的直徑定義為d(u，v)的最大值(其中u，v∈V)。這里d(u，v)表示頂點(diǎn)u到頂點(diǎn)v的最短路徑長(zhǎng)度(路徑長(zhǎng)度為路徑中包含的邊數(shù))。如圖所示為一棵自由樹，其直徑為18。試寫算法求T的直徑，并分析算法的時(shí)間復(fù)雜度。

37.設(shè)計(jì)快速排序的遞歸和非遞歸算法。38.編寫一個(gè)算法，將一個(gè)非負(fù)的十進(jìn)制整數(shù)N轉(zhuǎn)換為一個(gè)二進(jìn)制數(shù)。39.當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為______。A.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊(除最后一塊外)中數(shù)據(jù)個(gè)數(shù)需相同40.設(shè)一個(gè)循環(huán)隊(duì)列Q[maxSize]的隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為maxSize。除此之外，該隊(duì)列再?zèng)]有其他數(shù)據(jù)成員，則該隊(duì)列的隊(duì)滿條件是______。A.Q.front==Q.rearB.front+Q.rear＞=maxSizeC.Q.fron==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%maxSize41.一個(gè)二部圖的鄰接矩陣A是一個(gè)______類型的矩陣。A.n×n矩陣B.分塊對(duì)稱矩陣C.上三角矩陣D.下三角矩陣42.敗者樹中的“敗者”指的是什么?若利用敗者樹求m個(gè)排序碼中的最大者，在某次比較中得到a＞b，那么誰是敗者?43.假設(shè)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個(gè)簡(jiǎn)單有向回路，若存在，則以頂點(diǎn)序列的方式輸出該回路(找到一條即可)。(注意：圖中不存在頂點(diǎn)到自己的弧)44.給出折半查找的遞歸算法，并給出算法時(shí)間復(fù)雜度分析。45.以下有關(guān)排序的說法中，正確的是______。A.使用鏈表可以實(shí)現(xiàn)簡(jiǎn)單選擇排序，但很難實(shí)現(xiàn)堆排序B.當(dāng)待排序元素序列的初始排列完全有序時(shí)，快速排序的排序速度顯著提高C.簡(jiǎn)單選擇排序是一個(gè)穩(wěn)定的排序方法D.在最壞情況下，快速排序的時(shí)間性能也好于堆排序的時(shí)間性能46.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為______。A.1和5B.2和4C.4和2D.5和147.圖的D-搜索類似于BFS(廣度優(yōu)先搜索)，不同之處在于用棧代替BFS中的隊(duì)列，入、出隊(duì)列的操作改為入、出棧的操作，即當(dāng)一個(gè)頂點(diǎn)的所有鄰接點(diǎn)被搜索之后，下一個(gè)搜索出發(fā)點(diǎn)應(yīng)該是最近入棧(棧頂)的頂點(diǎn)。請(qǐng)用鄰接表作為存儲(chǔ)結(jié)構(gòu)，寫一個(gè)D-搜索算法。48.假設(shè)有n(n＞1)個(gè)線性表順序地存放在順序表S[1，…，m]中，令F[i]和R[i]指示第i個(gè)(1≤i≤n)表的第1個(gè)元素和最后1個(gè)元素在S中的位置，并設(shè)定R[i]＜F[i+1]，F(xiàn)[n+1]=m+1，如圖所示。試寫出實(shí)現(xiàn)下列要求的算法。

(1)在第i個(gè)表中的第j項(xiàng)后面插入1個(gè)元素，僅當(dāng)整個(gè)順序表空間填滿時(shí)，不允許進(jìn)行插入操作。

(2)刪除第i個(gè)表中的第j個(gè)元素，要求在刪除第j個(gè)元素后，該表仍為順序存儲(chǔ)的線性表。49.在一個(gè)無向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的______倍。A.1/2B.1C.2D.450.有一個(gè)n×n的對(duì)稱矩陣A，將其上三角部分按列壓縮存放于一個(gè)一維數(shù)組B中，A[0][0]存放于B[0]中。

B=[A00，A01，A11，A02，A12，A22，…，A0(n-1)，A1(n-1)，A2(n-1)，…，A(n-1)(n-1)]

同時(shí)有兩個(gè)函數(shù)：max(i,j)和min(i,j)，分別計(jì)算下標(biāo)i和j中的大者與小者。試?yán)盟鼈兘o出求任意一個(gè)A[i][j]在B中存放位置的公式。第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：B線性表采用順序存儲(chǔ)，并不便于進(jìn)行插入和刪除操作。2.參考答案：依題意，稀疏矩陣A按行優(yōu)先順序存放這些非0元素，可得到如下序列：

a2,n-2a2,n-1a2,na3,n-3a3,n-2a3,n-1...an-1,1an-1,2an-1,3

把它們順序存放在一維數(shù)組B中，前j-1行共有非0元素3x(i-2)個(gè)，在非0的ai,j前，本行還有非0元素的個(gè)數(shù)為j-(n-i)個(gè)，則ai,j在B中的位置為1+3×(i-2)+(i+j-n)，也就是說，A[i][j]存放在B[1+3×(i-2)+(i+j-n)]元素中。

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

intvalue(inta[],inti,intj)

//已知i,j返回A[i][j]之值

{

intadd;

if(i＞1&&i＜n&&j＞=n-i&&j＜=n-i+2)

//非0元素的條件

{

add=1+3*(i-2)+(i+j-n);

//在B中的下標(biāo)

returna[add];

}

elsereturn0;

}

voiddisp(inta[])

{

inti,j;

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

{

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

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

cout＜＜endl;

}

}3.參考答案：C由于后序遍歷先訪問子樹后訪問根結(jié)點(diǎn)，從本質(zhì)上要求運(yùn)行棧中存放祖先的信息，即使對(duì)二叉樹進(jìn)行后序線索化，仍然不能脫離棧的支持對(duì)此二叉樹進(jìn)行遍歷。4.參考答案：B[解析]對(duì)于有向強(qiáng)連通圖，當(dāng)n等于1時(shí)，邊為0，否則至少需要n條邊才能形成強(qiáng)連通圖。此時(shí)所有n個(gè)頂點(diǎn)都在某一個(gè)有向環(huán)上，如下圖所示。在此情況下，當(dāng)有向邊的條數(shù)少于n時(shí)，不能構(gòu)成環(huán)，不再是強(qiáng)連通圖。

5.參考答案：當(dāng)各關(guān)鍵字的查找概率相等時(shí)，最佳二叉排序樹應(yīng)是高度最小的二叉排序樹。構(gòu)造過程分兩步走：首先對(duì)各關(guān)鍵字值從小到大排序，然后仿照折半查找的判定樹的構(gòu)造方法構(gòu)造二叉排序樹。這樣得到的就是最佳二叉排序樹，如下圖所示。

6.參考答案：B[解析]2的6次方是64，2的7次方是128，因此得到：此完全二叉樹不是滿二叉樹，此完全二叉樹有8層，除去最底層，此二叉樹有127個(gè)結(jié)點(diǎn)。

設(shè)n為最底層結(jié)點(diǎn)的個(gè)數(shù)。則：

1)當(dāng)n為偶數(shù)時(shí)，n+64-n/2=124，解得n=120，則此樹共有127+120=247個(gè)結(jié)點(diǎn)。

2)當(dāng)n為奇數(shù)時(shí)，n+64-(n+1)/2=124，解得n=121，則此樹共有127+121=248個(gè)結(jié)點(diǎn)。綜上本題選B。7.參考答案：將n個(gè)元素對(duì)稱比較，即第一個(gè)元素與最后一個(gè)元素比較，第二個(gè)元素與倒數(shù)第二個(gè)元素比較……比較中的小者放前半部，大者放后半部，用了n/2次比較。再在前后兩部分中分別簡(jiǎn)單選擇最小和最大元素，各用(n/2)-1次比較?？偣灿昧?3n/2)-2次比較。顯然，當(dāng)n≥3時(shí)，(2n-3)＞(3n/2)-2。

用分治法求解再給出另一參考答案。

對(duì)于兩個(gè)數(shù)x和y，經(jīng)一次比較可得到最大值和最小值；對(duì)于三個(gè)數(shù)x，y，z，最多經(jīng)3次比較可得最大值和最小值；對(duì)于n個(gè)數(shù)(n＞3)，將分成長(zhǎng)為，n-2和2的前后兩部分A和B，分別找出最大者和最小者：MaxA，MinA，MaxB，MinB，最后Max={MaxA，MaxB}和Min={MinA，MinB}。對(duì)A使用同樣的方法求出最大值和最小值，直到元素個(gè)數(shù)不超過3。

設(shè)C(n)是所需的最多比較次數(shù)，根據(jù)上述原則，當(dāng)n＞3時(shí)有如下關(guān)系式：

通過逐步遞推，可以得到：C(n)=(3n/2)-2。顯然，當(dāng)n＞3時(shí)，2n-3＞(3n/2)-2。事實(shí)上(3n/2)-2是解決這一問題的比較次數(shù)的下限。8.參考答案：A[解析]多維數(shù)組本質(zhì)上是一維數(shù)組，是由一維數(shù)組實(shí)現(xiàn)的，是數(shù)組元素為一維數(shù)組的一維數(shù)組。9.參考答案：C快速排序是對(duì)冒泡排序的一種改進(jìn)，其基本思想是：通過一趟排序?qū)⒋判虻挠涗浄殖瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字比另一部分的關(guān)鍵字小。然后對(duì)這兩部分再繼續(xù)排序，一直達(dá)到整個(gè)序列有序。

設(shè)待排序序列為{L.r[1]，L.r[2]，…，L.r[n])，首先任意選取一個(gè)記錄(通常選擇第一個(gè)記錄L.r[1])作為支點(diǎn)(pivot)，然后按照下述原則排列其余記錄：將所有關(guān)鍵字比L.r[1]．key小的記錄都安排在它的位置之前，將所有關(guān)鍵字比L.r[1].key大的記錄都安排在它的位置之后?？梢园l(fā)現(xiàn)，在安置的過程中，L.r[1]的確切位置將被最終確定。設(shè)該支點(diǎn)(pivot)最后確定的位置為i，則將序列分割為左右兩部分。這個(gè)過程稱為一趟快速排序。

設(shè)待排序序列用數(shù)組e[low..high]保存。設(shè)置兩個(gè)指針low和high，分別指向數(shù)組的開始位置和終止位置。設(shè)支點(diǎn)記錄為e[low]，并將之暫存于t。

首先，從high的位置向前搜索，找到第一個(gè)小于t的記錄，將這個(gè)記錄和e[low]的值交換；然后，從low所指向的位置向后搜索，找到第一個(gè)值大于t的記錄，將這個(gè)記錄和e[high]的值交換。重復(fù)以上步驟，直到low=high。完成一趟排序，low(或者h(yuǎn)igh)指向的位置就是第一個(gè)元素的確切位置(從兩邊向中間“夾擠”)。

第一趟完成后，確定了第一個(gè)元素的確切位置，同時(shí)生成了兩個(gè)子序列，然后再對(duì)這兩個(gè)序列使用同樣的辦法，最終實(shí)現(xiàn)整個(gè)序列的有序。

舉例：利用快速排序法對(duì)以下序列進(jìn)行排序：

(49，38，65，97，76，13，27，49)

過程如下：

初始狀態(tài)：

high向左移動(dòng)(high——)，直到找到小于t(49)的關(guān)鍵字27，將27的值賦給e[low]，如下：

接著low開始向右移動(dòng)(low++)，直到找到大于t(49)的關(guān)鍵字65，將65的值賦給e[high]，如下：

high繼續(xù)左移(high——)，直到找到一個(gè)小于t的數(shù)13，將之賦給e[low]，如下：

low繼續(xù)右移(low++)，直到找到大于t(49)的關(guān)鍵字97，將之賦給e[high]，如下：

high繼續(xù)左移(high——)，沒有找到比t(49)還小的數(shù)，但是由于出現(xiàn)了high==low的情況，結(jié)束左移。如下：

此時(shí)low(或者h(yuǎn)igh)指向的位置就是第一個(gè)元素的確定位置：e[low]=t；

經(jīng)過以上一趟快速排序，可將原序列分為兩個(gè)序列，同時(shí)確定關(guān)鍵字49的確切位置，如下：

{27，38，13}

49

{76，97，65，[49]}

下面再分別對(duì)兩個(gè)子類進(jìn)行快速排序，得最終結(jié)果：

{13)27{38}

49

{49，

65}

76

{97}

49

{65}

則最終得到有序序列：(13，27，38，49，49，6576，97)

說明：在一趟排序中，支點(diǎn)最后才確定位置，故只需最后一步賦值即可，中間不必交換。即，雖然快速排序是交換排序的一種，但是可以不用交換操作即可實(shí)現(xiàn)。該算法由于有不相鄰元素交換，故是不穩(wěn)定排序，其時(shí)間復(fù)雜度為O(nlogn2)，是內(nèi)排序中最好的方法之一。10.參考答案：使用遞歸算法實(shí)現(xiàn)順序查找的基本思想是：先判斷是否檢測(cè)到表尾，是則返回L.n，表示查找失敗，次數(shù)loc(0≤loc≤L.n-1)停留在L.n位置，函數(shù)返回-1。不是則再判斷位于loc位置的元素的關(guān)鍵字是否等于x，是則查找成功，返回元素的位置。否則算法遞歸檢測(cè)下一個(gè)位置loc+1。該遞歸算法的調(diào)用語句形式為：

intPos=seqSearch1(L,x,0);

intseqSearchl(seqList&L,DataTypex,intloc){

if(loc＞=L.n)return-1;

//查找不成功

elseif(L.data[loc]==x)returnloc;

//查找成功

elsereturnseqSearchl(L,x,loc+1);

//繼續(xù)遞歸查找

}

每次遞歸，查找區(qū)間的左端點(diǎn)向待查找元素所在位置逼近一個(gè)位置，直到遞歸到達(dá)待查找元素所在位置，查找成功。如果遞歸下去，直到查找區(qū)間為空(loc==L.n)，查找失敗。函數(shù)返回找到的位置。算法的遞歸深度與待查找元素在表中的位置有關(guān)，最好情形是一開始就找到待查找元素，遞歸深度為l；最壞情形是遞歸深度等于表的長(zhǎng)度O(n)。11.參考答案：此題考查的知識(shí)點(diǎn)是圖的定義。具有n個(gè)頂點(diǎn)n-1條邊的無向連通圖是自由樹，即沒有確定根結(jié)點(diǎn)的樹，每個(gè)結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于n-1條，因一條邊要連接兩個(gè)結(jié)點(diǎn)，則必因加上這一條邊而使兩個(gè)結(jié)點(diǎn)多了一條通路，即形成回路。形成回路的連通圖不再是樹(在圖論中樹定義為無回路的連通圖)。12.參考答案：D[解析]本題主要考查線性結(jié)構(gòu)的特點(diǎn)和線性表的定義。線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)在不同的情況下各有利弊，無優(yōu)劣之分。

鏈?zhǔn)酱鎯?chǔ)表示要求結(jié)點(diǎn)內(nèi)的存儲(chǔ)單元一定連續(xù)。13.參考答案：D[解析]此題可以用排除法來解決。由選項(xiàng)A、B、C所得出的棧序列分別為(1，2，4，3)、(3，2，4，1)、(1，3，2，4)，可以看出都是錯(cuò)誤的。選項(xiàng)D得到的出棧序列為1，3，4，2。14.參考答案：對(duì)于給定的數(shù)k，將所有小于它的元素排到其前面，所有大于它的元素排到其后面，該數(shù)的位置即為有序中的序號(hào)(從0開始數(shù))，這樣最大的比較次數(shù)為n-1次。

實(shí)現(xiàn)本題功能的程序如下：

intdatai(intr[],intn,intk)

{

inti=0,j=n-1;

inttemp;

while(i＜=j)

{

while(i＜n&&r[i]＜=k)

++i;

while(j＞=0&&r[j]＞k)

--j;

if(i＜j)

{

temp=r[i];r[i]=r[j];r[j]=temp;

++i;

--j;

}

}

returnj;

}15.參考答案：B設(shè)N一{V，{E}}是連通網(wǎng)，TE是最小生成樹中邊的集合，初始為空。

定義一個(gè)僅含一個(gè)頂點(diǎn)的集合U={u0)，u0∈V(u0可從頂點(diǎn)集合V中任意選取)，

則將N中的所有頂點(diǎn)分成了兩個(gè)集合：U，V—U。

重復(fù)執(zhí)行以下操作：在所有的u∈U，v∈V決定的邊(u，v)∈{E)中尋找一條代價(jià)最小的邊(u0，v0)，將該邊并入TE集合，同時(shí)v0并入U(xiǎn)，直到U=V為止。

以上操作，通俗地講，實(shí)際上是從兩大陣營(兩個(gè)圖的頂點(diǎn)的集合)中尋找一條最短的路。Prim算法中，最小代價(jià)生成樹的頂點(diǎn)和邊都是逐步生成的，開始的時(shí)候頂點(diǎn)集合中有一個(gè)頂點(diǎn)，邊的集合為空。16.參考答案：

boolLocate(DblList&L,Typex){

//在雙向鏈表中查找值為x的結(jié)點(diǎn),找到后該結(jié)點(diǎn)被搬到適當(dāng)位置,函數(shù)返回true,

//否則函數(shù)返回false。

DblNode*p=L-＞rLink,*q;

while(p!=NULL&&p-＞data!=x)p=p-＞rLink;

if(p!=NULL){

//鏈表中存在x

p-＞freq++;q=p;

//該結(jié)點(diǎn)的訪問頻度加1

q-＞iLink-＞rLink=q-＞rLink;

//從鏈表中摘下這個(gè)結(jié)點(diǎn)

q-＞rLink-＞ILink=q-＞iLink;

p=q-＞lLink;

//尋找重新插入的位置

while(p!=L&&q-＞freq＞p-＞freq)p=p-＞lLink;

q-＞rLink=p-＞rlink;q-＞llink=p;

//插入在p之后

p-＞rLink-＞lLink=q;p-＞rLink=q;

returntrue;

}

elsereturnfalse;

//沒找到17.參考答案：B[解析]存儲(chǔ)結(jié)構(gòu)為鄰接矩陣的圖的遍歷算法要對(duì)所有頂點(diǎn)都訪問一次，每次訪問時(shí)為確定下一次要訪問哪個(gè)頂點(diǎn)，需遍歷該頂點(diǎn)的行向量，尋找該頂點(diǎn)的所有鄰接頂點(diǎn)，所以遍歷的時(shí)間復(fù)雜度為O(n2)。而對(duì)于存儲(chǔ)結(jié)構(gòu)為鄰接表的圖的遍歷算法也要對(duì)所有頂點(diǎn)訪問一次，每次訪問時(shí)為確定下一次要訪問哪個(gè)頂點(diǎn)，需遍歷該頂點(diǎn)的邊鏈表，所以時(shí)間復(fù)雜度為O(n+e)。18.參考答案：(1)n(n-1)，n

(2)106，不一定是稀疏矩陣此題考查的知識(shí)點(diǎn)是圖的相關(guān)術(shù)語。

(1)在有向圖G中，如果對(duì)于每一對(duì)vi，vj屬于V，vi不等于vj，從vi到vj和從vj到vi都存在路徑，則稱G是強(qiáng)連通圖。最多邊是所有的頂點(diǎn)每對(duì)之間都有邊，邊數(shù)為n(n-1)；最少只有一個(gè)方向有邊，為n。

(2)元素個(gè)數(shù)為矩陣的大小，即106，稀疏矩陣的定義是非零個(gè)數(shù)遠(yuǎn)小于該矩陣元素個(gè)數(shù)，且分布無規(guī)律，不一定稀疏。19.參考答案：D此題考查的知識(shí)點(diǎn)是折半查找的效率。其查找效率與比較次數(shù)有關(guān)，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過[log2n]+1，所以其效率為O(log2n)，應(yīng)選D。20.參考答案：A[解析]將森林F轉(zhuǎn)化為二叉樹表示B，則B的根是第一棵樹的根，根的左子樹是第一棵樹的根的子樹森林，根的右子樹是森林中除去第一棵樹外其他樹構(gòu)成的森林。根據(jù)題意，B的根是p，p的右子樹中的結(jié)點(diǎn)個(gè)數(shù)為n，則森林F的第一棵樹中結(jié)點(diǎn)個(gè)數(shù)為m-n。21.參考答案：D經(jīng)過入棧后：

開始出棧，遇到6之前：

22.參考答案：B[解析]棧的一個(gè)典型應(yīng)用就是在實(shí)現(xiàn)遞歸程序時(shí)作遞歸工作棧，用于開辟每一層遞歸程序調(diào)用時(shí)需要的局部變量空間、實(shí)際參數(shù)的副本空間和記錄返回上一層調(diào)用的返回地址等。23.參考答案：C[解析]基數(shù)排序是一種分配排序，或稱為桶排序。它根據(jù)排序碼每一位的取值范圍(基數(shù))，設(shè)置若干個(gè)桶，通過“分配”和“收集”完成排序。它的附加存儲(chǔ)與基數(shù)有關(guān)。如果不考慮可能需要的鏈接指針，它需要的附加存儲(chǔ)與待排序的元素個(gè)數(shù)和初始排列無關(guān)。當(dāng)待排序元素個(gè)數(shù)為n時(shí)，錦標(biāo)賽排序需要n-1個(gè)附加結(jié)點(diǎn)以構(gòu)成勝者樹；快速排序平均需要log2n個(gè)遞歸工作棧結(jié)點(diǎn)空間；歸并排序需要n個(gè)元素空間。24.參考答案：線性表每一個(gè)表元素的數(shù)據(jù)空間要求相同，但如果對(duì)每一個(gè)元素的數(shù)據(jù)類型要求不同時(shí)可以用等價(jià)類型(union)變量來定義可能的數(shù)據(jù)元素的類型。如

Typedefunion{

//聯(lián)合

intintegerInfo;

//整型

charcharInfo;

//字符型

floatfloatInfo;

//浮點(diǎn)型

}info;

利用等價(jià)類型，可以在同一空間(空間大小相同)indo中存放不同數(shù)據(jù)類型的元素。但要求用什么數(shù)據(jù)類型的變量存，就必須以同樣的數(shù)據(jù)類型來取。25.參考答案：C根據(jù)樹的基本定義可知，每個(gè)樹只能有且只有一個(gè)根結(jié)點(diǎn)。26.參考答案：D解析見7?？芍猘ebdfc，aefdbc符合深度優(yōu)先搜索條件。27.參考答案：B[解析]從空樹開始，最初建立的是根結(jié)點(diǎn)，又是葉結(jié)點(diǎn)。以后分裂成p個(gè)結(jié)點(diǎn)，經(jīng)過了p-1次分裂。28.參考答案：后序遍歷最后訪問根結(jié)點(diǎn)，當(dāng)訪問到值為X的結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先，所以此題采用后序遍歷進(jìn)行訪問。

typedefstruct

{

BiTteet：

inttag；

}stack；∥tag=0表示左子女被訪問，tag=1表示右子女被訪問voidSearch(BiTreebt，ElemTypex)

∥在二叉樹bt中，查找值為X的結(jié)點(diǎn)，并打印其所有祖先

{

stacks[]；

∥棧容量足夠大

top=0；

while(bt!=null‖top＞0)

{

while(bt!=null&&bt—＞data!=x)

∥結(jié)點(diǎn)入棧

{

s[++top]0t=bt；

S[top]．tag=0；

bt=bt—＞lchild：

}

∥沿左分枝向下

if(bt—＞data==x)

{

printf(“所查結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的值為：\n”)；

∥找到x

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

printf(s[i]．t—＞data)；

return；

}

/輸出祖先值后結(jié)束

while(top!=0&&s[top].tag==1)

top——；∥退棧(空遍歷)

if(top!=0)

{

s[top].tag=1；

bt=s[top]．t—＞rchild：

}

∥沿右分枝向下遍歷

}

}29.參考答案：C[解析]在開地址法中散列到同一個(gè)地址而引起的“堆積”問題是由于解決同義詞沖突的探測(cè)序列和非同義詞之間不同的探測(cè)序列交織在一起，導(dǎo)致關(guān)鍵字就位需要經(jīng)過較長(zhǎng)的探測(cè)距離，降低了散列的效率。所以必須選擇好的解決沖突的方法以避免“堆積”。30.參考答案：D[解析]常用的解決沖突的方法有兩大類：開地址法和鏈地址法。開地址法中尋找下一個(gè)可存放元素的空位不超出表的范圍，它又有線性探測(cè)、二次探測(cè)或雙散列之分。鏈地址法采用鏈表方式，在表的范圍之外分配空間存放發(fā)生沖突的元素。31.參考答案：B有n個(gè)結(jié)點(diǎn)且為完全二叉樹的二叉排序樹的高度為log2n。32.參考答案：D[解析]用排除法選擇答案。選項(xiàng)A、B、C得到的出棧序列分別為1243、3241、1324，都不是正確答案。選項(xiàng)D得到的出棧序列為1342。33.參考答案：利用二叉排序樹的性質(zhì)，從根結(jié)點(diǎn)開始查找，若根結(jié)點(diǎn)的值小于等于x，則根結(jié)點(diǎn)及其左子樹均應(yīng)刪除，然后以右子樹的根結(jié)點(diǎn)為樹根，重新開始查找。若根結(jié)點(diǎn)的值大于x，則順左子樹向下查找，直到某結(jié)點(diǎn)的值小于等于x，則該結(jié)點(diǎn)及其左子樹均應(yīng)刪除。下面設(shè)計(jì)一查找算法，確定被刪除子樹的根結(jié)點(diǎn)，再設(shè)計(jì)一刪除算法，刪除以被刪結(jié)點(diǎn)為根的子樹。

typedefstructnode{

intdata;

structnode*left,*right;

}BiTNode,*BSTree;

voidDelTree(BSTreer){

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

BSTreeS[];

//棧，容量足夠大，棧中元素是二叉排序樹結(jié)點(diǎn)的指針

BSTreep;

inttop=0;

while(r!=null||top＞0){

while(r!=null){S[++top]=r;r=r-＞left;}

//沿左分支向下

if(top＞0)

//退棧，沿棧頂結(jié)點(diǎn)的右子樹向下刪除，釋放被刪除結(jié)點(diǎn)空間

{p=S[top--];r=p-＞fight;free(p);}

}

}//DelTree

voidDeleteAllx(BSTreeT,intx){

//在二叉排序樹T中，刪除所有小于等于x的結(jié)點(diǎn)

BSTreep=T,q;

while(T&&T-＞data＜=x){

//根結(jié)點(diǎn)的值小于等于x

p=T;T=T-＞fight;p-＞fight=null;

DelTree(p);}

//刪除二叉樹P，刪除持續(xù)到“根”結(jié)點(diǎn)值大于x或T為空樹為止

if(T){

q=T;p=T-＞left;

while(p&&p-＞data＞x){

//沿根結(jié)點(diǎn)左分支向下，查小于等于x的結(jié)點(diǎn)

while(p&&p-＞data＞x){q=p;p=p-＞left;}

//q記p的雙親

if(p)

//p結(jié)點(diǎn)的值小于等于x

{q-＞left=p-＞fight;p-＞fight=null;DelTree(p);}

p=q-＞left;

//再查原p的右子樹中小于等于x的結(jié)點(diǎn)

}

}34.參考答案：A[解析]有n個(gè)頂點(diǎn)的連通圖，至少需要n-1條邊才能保持圖的連通。多一條邊將形成回路，少一條邊將變成非連通圖。當(dāng)n=6時(shí)，n-1=5。35.參考答案：C1．二叉排序樹定義：二叉排序樹是一棵二叉樹，它或者為空，或者具有如下性質(zhì)：1＞任一非終端結(jié)點(diǎn)若有左孩子，則該結(jié)點(diǎn)的關(guān)鍵字值大于其左孩子結(jié)點(diǎn)的關(guān)鍵字值；2＞任一非終端結(jié)點(diǎn)若有右孩子，則該結(jié)點(diǎn)的關(guān)鍵字值小于其右孩子結(jié)點(diǎn)的關(guān)鍵字值。是一種常用的動(dòng)態(tài)查找表，上面首先給出了它的非遞歸形式。

二叉排序樹也可以用遞歸的形式定義，即二叉排序樹是一棵樹，它或者為空，或者具有如下性質(zhì)：1＞若它的左子樹非空，則其左子樹所有結(jié)點(diǎn)的關(guān)鍵字值均小于其根結(jié)點(diǎn)的關(guān)鍵字值；2＞若它的右子樹非空，則其右子樹所有結(jié)點(diǎn)的關(guān)鍵字值均大于其根結(jié)點(diǎn)的關(guān)鍵字值；3＞它的左右子樹都是二叉排序樹。

2．構(gòu)造二叉排序樹：一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹，然后再對(duì)這棵二叉樹進(jìn)行中序遍歷，即可以變成有序序列。構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。例如：

設(shè)查找的關(guān)鍵字的序列為{45，24，53，45，12，90}，則生成二叉排序樹的過程為：

特別說明：結(jié)點(diǎn)個(gè)數(shù)和取值都相同的表構(gòu)成的二叉排序樹樹形可能不相同。其樹形由結(jié)點(diǎn)的輸入順序決定。36.參考答案：利用深度優(yōu)先遍歷求出一個(gè)根結(jié)點(diǎn)v到每個(gè)葉子結(jié)點(diǎn)的距離，這是由diameter(v)函數(shù)實(shí)現(xiàn)的。該函數(shù)的時(shí)間復(fù)雜度為O(n+e)，n為頂點(diǎn)個(gè)數(shù)，e為邊數(shù)。然后，以每個(gè)頂點(diǎn)作為根結(jié)點(diǎn)調(diào)用diameter()函數(shù)，其中最大值即為T的直徑，本算法的時(shí)間復(fù)雜度為O(n(n+e))。

實(shí)現(xiàn)本題功能的程序代碼如下：

voiddfs(intparent,intchild,int&len)

//函數(shù)執(zhí)行結(jié)束后，len中存放從根結(jié)點(diǎn)到child結(jié)點(diǎn)所在子樹的葉子結(jié)點(diǎn)的最大距離

//cost是帶權(quán)鄰接矩陣，visited是已經(jīng)初始化的訪問標(biāo)記數(shù)組

//N是已定義的常量，即頂點(diǎn)個(gè)數(shù)

{

intclen,v=0,maxlen;

clen=len;

maxlen=len;

while(v＜N&&cost[child][v]==0)

//找與child相鄰的第一個(gè)頂點(diǎn)v

v++;

while(v＜N)

//存在鄰接頂點(diǎn)時(shí)循環(huán)

{

if(v!=parent)

{

len=len+cost[child][v];

dfs(child,v,len);

if(len＞maxlen)

maxlen=len;

}

v++;

while(v＜N&&cost[child][v]==0)

//找與child相鄰的下一個(gè)頂點(diǎn)v

v++;

len=clen;

}

len=maxlen;

}

intdiameter(intv)

{

intmaxlen1=0;

//存放到目前為止所找到的根v到葉子結(jié)點(diǎn)的最大值

intmaxlen2=0;

//存放到目前為止所找到的根v到葉子結(jié)點(diǎn)的次大值

intlen=0;

//記錄深度優(yōu)先遍歷中到某個(gè)葉子結(jié)點(diǎn)的距離

intw=0;

//存放v的鄰接頂點(diǎn)

while(w＜N&&cost[v][w]==0)

//找與v相鄰的第一個(gè)頂點(diǎn)w

w++;

while(w＜N)

//存在鄰接頂點(diǎn)時(shí)循環(huán)

{

len=cost[v][w];

dfs(v,w,len);

if(len＞maxlen1)

{

maxlen2=maxlen1;

maxlen1=len;

}

elseif(len＞maxlen2)

maxlen2=len;

w++;

while(w＜N&&cost[v][w]==0)

//找與v相鄰的第一個(gè)頂點(diǎn)w

w++;

}

returnmaxlen1+maxlen2;

}

for(i=1;i＜N;i++)

//找出從所有頂點(diǎn)出發(fā)直徑的最大值

{

d=diameter(i);

if(diam＜d)

diam=d;

}[說明]本題提到最短路徑，拿到題目后，考生容易將其歸類為最短路徑問題，而去想相應(yīng)的算法。但由于本題限定圖為自由樹，所以只需用深度優(yōu)先搜索的方法即可得到每?jī)牲c(diǎn)的最短路徑。這種在題目中設(shè)置干擾因素的情況在正式考題中是常見的，因此考生必須注意區(qū)分，以提高做題效率。37.參考答案：本題非遞歸算法容易實(shí)現(xiàn)，在《數(shù)據(jù)結(jié)構(gòu)高分筆記》一書中已經(jīng)講過，核心算法即為序列的劃分，然后遞歸處理劃分好的子序列。非遞歸算法需要自己申請(qǐng)棧空間以代替系統(tǒng)棧。

劃分函數(shù)代碼如下：

voidsplit(intA[],intlow,inthigh,int&i)

{

intj;

intx;

i=low;j=high;x=A[i];

//初始化

while(i＜j)

{

while(A[j]＞=x&&i＜j)

//從右向左遍歷

--j;

if(i＜j)

{

A[i]=A[j];++i;

//相當(dāng)于交換A[i]與A[j]

}

while(A[i]＜=x&&i＜j)

//從左向右遍歷

++i;

if(i＜j)

{

A[j]=A[i];--j;

//相當(dāng)于交換A[i]與A[j]

}

}

A[i]=x;

//x定位在位置i處

}

遞歸算法代碼如下：

voidquicksort(intA[],ints,intt)

{

inti;

if(s＜t)

{

split(A,s,t,i);

quicksort(A,s,i-1);

quicksort(A,i+1,t);

}

}

非遞歸算法代碼如下：

voidquicksort2(intA[],intn)

{

inti,l,h;

intstack[maxSize][2],top=-1;

//maxSize是已定義的常量

i=0;h=n-1;

++top;

//入棧

stack[top][0]=1;stack[top][1]=h;

while(top＞=0)

{

l=stack[top][0];h=stack[top][1];

//出棧

--top;

split(A,l,h,i);

if(l＜h)

{

++top;

//入棧

stack[top][0]=1;stack[top][1]=i-1;

++top;

//入棧

stack[top][0]=i+1;stack[top][1]=h;

}

}

}38.參考答案：可以利用棧解決數(shù)制轉(zhuǎn)換問題。例如，4910=1·25+1·24+1·20=1100012，其轉(zhuǎn)換規(guī)則是：

式中，bi表示二進(jìn)制數(shù)的第i位上的數(shù)字。這樣，十進(jìn)制數(shù)N可以用長(zhǎng)度為位的二

進(jìn)制數(shù)表示為。若令，則有

N=bj2j+bj-12j-1+…+b121+b020

=(bj2j-1+bj-12j-2+…+b1)×2+b0

=(N/2)×2+N%2('/'表示整除運(yùn)算)

因此，可以先通過N%2求出b0，然后令N=N/2，再對(duì)新的N做除2求模運(yùn)算可求出b1……如此重復(fù)直到某個(gè)N等于零結(jié)束。這個(gè)計(jì)算過程是從低位到高位逐個(gè)進(jìn)行的，但輸出過程是從高位到低位逐個(gè)打印的，為此需要利用棧來實(shí)現(xiàn)。代碼如下：

intBaseTrans(intN)

{

inti,result=0;

intstack[maxSize],top=-1;

//定義并初始化棧，其中maxSize是已定義的常量，其大小足夠處理本題中數(shù)據(jù)

while(N!=0)

{

i=N%2;

N=N/2;

stack[++top]=i;

}

while(top!=-1)

{

i=stack[top];

--top;

result=result*10+i;

}

returnresult;

}39.參考答案：B[解析]本題主要考查分塊查找的相關(guān)概念。40.參考答案：C[解析]在不能附加其他任何數(shù)據(jù)成員的前提下，只能用犧牲一個(gè)隊(duì)列元素的整除取余的方式來區(qū)分隊(duì)空和隊(duì)滿的條件。因此，選項(xiàng)C正確。選項(xiàng)A是判斷隊(duì)列是否為空的條件，選項(xiàng)B和D則是干擾項(xiàng)。41.參考答案：B此題考查的知識(shí)點(diǎn)是二部圖的定義與存儲(chǔ)。二部圖定義為：若能將無向圖G=＜V，E＞的頂點(diǎn)集V劃分成兩個(gè)子集V1和V2(V1∩V2)=使得G中任何一條邊的兩個(gè)端點(diǎn)一個(gè)屬于V1，另一個(gè)屬于V2，則稱G為二部圖。由于其特點(diǎn)，其存儲(chǔ)矩陣必為分塊對(duì)稱的，所以選B。42.參考答案：如果最終勝者是指具有最小排序碼的記錄，那么“敗者”指的是兩個(gè)歸并段當(dāng)前參加歸并的記錄中排序碼較大的記錄；反之，如果最終勝者是指具有最大排序碼的記錄，那么“敗者”指的是兩個(gè)歸并段當(dāng)前參加歸并的記錄中排序碼較小的記錄。

若利用敗者樹求m個(gè)排序碼中的最大者，在某次比較中得到a＞b，那么敗者是b。43.參考答案：用鄰接矩陣存儲(chǔ)時(shí)，可用以下方法實(shí)現(xiàn)：

voidPrint(intv,intstart){//輸出從頂點(diǎn)start開始的回路

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

if(g[v][i]!=0&&visited[i]==1){

//若存在邊(v,i)，且頂點(diǎn)i的狀態(tài)為1

printf("%d",v);

if(i==start)printf("\n");

elsePrint(i,start);

break;

}//if

}//Print

voiddfs(intv){

visited[v]=1;

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

if(g[v][j]!=0)

//存在邊(v,j)

if(visited[j]!=1){if(!visited[j])das(j);}//if

else{cycle=1;Print(j,j);}

visited[vj=2;

}

voidfind_cycle(){

//判斷是否有回路，有則輸出鄰接矩陣。visited數(shù)組為全局變量

for(i=1;i＜=n;i++)visited[i]=0;

for(i=1;i＜=n;i++)if(!visited[i])dfs(i);

}此題考查的知識(shí)點(diǎn)是圖的遍歷。有向圖判斷回路要比無向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂點(diǎn)分成三類：未訪問，已訪問但其鄰接點(diǎn)未訪問完，已訪問且其鄰接點(diǎn)已訪問完。下面用0、1、2表示這三種狀態(tài)。前面已提到，若dfs(v)結(jié)束前出現(xiàn)頂點(diǎn)u到v的回邊，則圖中必有包含頂點(diǎn)v和u的回路。對(duì)應(yīng)程序中v的狀態(tài)為1，而u是正訪問的頂點(diǎn)，若找出u的下一鄰接點(diǎn)的狀態(tài)為1，就可以輸出回路了。44.參考