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

2023年研究生類研究生入學(xué)考試專業(yè)課計算機學(xué)科專業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點試題黑鉆版(共50題)1.已知10個數(shù)據(jù)元素為(54，28，16，34，73，62，95，60，26，43)，對該序列按從小到大排序，經(jīng)過一趟冒泡排序后的序列為______。A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，952.一棵含有n個結(jié)點的k叉樹，可能達到的最大深度為______，最小深度為logk(n×(k-1)+1)。A.logk(n×(k-1)+1)B.logk(n×k-1)+1C.kD.n3.一個遞歸算法必須包括______。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分4.若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點后再刪除最后一個結(jié)點，則采用______存儲方式最節(jié)省運算時間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.帶頭結(jié)點的雙循環(huán)鏈表5.設(shè)A是n×n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B[1…n(n+1)/2]中，對上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為______。A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-16.欲用4種顏色對地圖上的國家涂色，有相鄰邊界的國家不能用同一種顏色(點相交不算相鄰)。

(1)試用一種數(shù)據(jù)結(jié)構(gòu)表示地圖上各國相鄰的關(guān)系；

(2)描述涂色過程的算法。(不要求證明)7.已知單鏈表A的長度為m，單鏈表B的長度為n，若將B鏈接在A的末尾，在沒有鏈尾指針的情況下，算法的時間復(fù)雜度應(yīng)為______。A.O(1)B.O(m)C.O(n)D.O(m+n)8.鄰接多重表的存儲結(jié)構(gòu)和十字鏈表類似，也是由頂點表和邊表組成，每一條邊用一個結(jié)點表示，其頂點表結(jié)點結(jié)構(gòu)和邊表結(jié)點結(jié)構(gòu)如下圖所示：

關(guān)于圖中各個域的說明，不正確的是______。A.vertex存儲的是結(jié)點的數(shù)值域的內(nèi)容B.firstedge域指示第一條依附于該頂點的邊C.mark指向下一條依附于結(jié)點的邊D.info為指向和邊相關(guān)的各種信息的指針域9.具有10個葉結(jié)點的二叉樹中有

個度為2的結(jié)點。A.8B.9C.10D.1110.現(xiàn)有兩棧，其共享空間為V[1..m]，top[i]代表第i個棧(i=1，2)棧頂，棧1的底在V[1]，棧2的底在V[m]，若兩棧均采用順序存儲方式存儲，則棧滿的條件是______。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]11.設(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，XB.P，A，C，S，Q，D，F(xiàn)，X，R，H，M，YC.A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，XD.H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y12.當所有n個待排序記錄的排序碼都相等時，直接插入排序、堆排序、起泡排序、簡單選擇排序的排序碼比較次數(shù)和元素移動次數(shù)分別為(①)、O(n)和O(n)、n-1和0、n(n-1)/2和0。A.n-1和0B.n(n-1)/2和nC.n(n-1)/2和0D.O(n)和O(n)13.無向圖G=(V，E)，其中：V={a，b，c．d，e，f}，E={(a，b)，

(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e．d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是

。A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b14.設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點。B的根為p，p的右子樹中結(jié)點個數(shù)為n，則森林F中第一棵樹的結(jié)點個數(shù)是______。A.m-nB.m-n-1C.n+1D.無法確定15.在一棵m階B樹的結(jié)點中插入新關(guān)鍵字時，若插入前結(jié)點的關(guān)鍵字數(shù)為______，則插入新關(guān)鍵字后該結(jié)點必須分裂為兩個結(jié)點。A.mB.m-1C.m+1D.m-216.寫出在二叉排序樹中刪除一個結(jié)點的算法，使刪除后仍為二叉排序樹。設(shè)刪除結(jié)點由指針p所指，其雙親結(jié)點由指針f所指，并假設(shè)被刪除結(jié)點是其雙親結(jié)點的右孩子。描述上述算法。17.線性表的每一個表元素是否必須類型相同?為什么?18.對給定關(guān)鍵字的序號j(0≤j＜n)，要求在無序記錄A[0，…，n-1]中找按關(guān)鍵字從小到大排在第i位上的記錄，利用快速排序的劃分思想設(shè)計上述算法。19.編寫一個算法，在一棵中序線索二叉樹中以非遞歸的方式中序正向和中序反向遍歷該二叉樹。20.有一幅如圖所示的藏寶圖，設(shè)計一個算法要求從入口到出口，必須經(jīng)過“食品”和“財寶”的地方，不得經(jīng)過“強盜”的地方。

21.如果將所有中國人按照生日(不考慮年份，只考慮月、日)來排序，那么使用下列排序算法中最快的是______。A.歸并排序B.希爾排序C.快速排序D.基數(shù)排序22.一棵哈夫曼樹共有99個結(jié)點，對其進行哈夫曼編碼，共能得到______種不同的編碼。A.48B.50C.99D.10023.一棵二叉樹如下圖所示，其中序遍歷序列為______。

A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh24.設(shè)A是一個線性表(a1，a2，…，an)，采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均插入一個元素需要移動的元素個數(shù)是多少?若元素插入在ai與ai+1之間(1≤i≤n-1)的概率為，則平均每插入一個元素所要移動的元素個數(shù)是多少?25.對任何一棵二叉樹，如果終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則一定有n0=n2+1。26.對下面的3階B樹，依次執(zhí)行下列操作，畫出各步操作的結(jié)果。

(1)插入90

(2)插入25

(3)插入45

(4)刪除60

(5)刪除80

27.求最短路徑的Dijkstra算法的時間復(fù)雜度為______。A.O(n)B.O(n+e)C.O(n2)D.O(n×e)28.圖的廣度優(yōu)先遍歷算法中使用隊列作為其輔助數(shù)據(jù)結(jié)構(gòu)，那么在算法執(zhí)行過程中每個頂點最多進隊______次。A.1B.2C.3D.429.對于具有n(n＞1)個頂點的強連通圖，其有向邊的條數(shù)至少是______。A.n+1B.nC.n-1D.n-230.二又樹的葉結(jié)點在前序、中序和后序遍歷過程中的相對順序______。A.發(fā)生改變B.不發(fā)生改變C.無法確定D.以上均不正確31.設(shè)有一棵B+樹，其結(jié)點最多可存放100個索引項。對于高度為1、2、3、4的B+樹，最多能存儲多少索引項?最少能存儲多少索引項?32.對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的______個元素。A.n/2B.(n+1)/2C.(n-1)/2D.n33.在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行______操作。A.s→next=p→next;p→next=s;B.p→next=s→next;s→next=p;C.q→next=s;s→next=p;D.p→next=s;s→next=q;34.雙向鏈表中有兩個指針域，即prior和next，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個結(jié)點，q指向一個待插入結(jié)點，現(xiàn)要求在p前插入q，則正確的插入為______。A.p-＞prior=q;q-＞next=p;p-＞prior-＞next=q;q-＞prior=p-＞prior;B.q-＞prior=p-＞prior;p-＞prior-＞next=q;q-＞next=p;p-＞prior=q;C.q-＞next=p;p-＞next=q;p-＞prior-＞next=q;q-＞next=p;D.p-＞prior-＞next=q;q-＞next=p;q-＞prior=p-＞prior;p-＞prior=q;35.設(shè)有一個n階的三對角線矩陣A的對角元素A[i][j]可存放于一個一維數(shù)組B中，要求行下標必須滿足0≤i≤n-1，而列下標必須滿足______。A.0≤j≤n-1B.i-1≤j≤i+1C.0≤j≤iD.i≤j≤n36.6知一個二叉樹，用二叉鏈表形式存儲，給出此二叉樹建立過程算法(可不描述結(jié)構(gòu)體)。37.以下有關(guān)圖的最短路徑的說法中正確的是______。A.帶權(quán)有向圖的最短路徑一定是簡單路徑B.在有向圖中，從一個頂點到另一個頂點的最短路徑是唯一的C.求單源最短路徑的Dijkstra算法不適用于有回路的帶權(quán)有向圖D.在用Floyd算法求解各頂點之間的最短路徑時，每個表示兩個頂點之間路徑的path(k-1)[i][j]一定是path(k)[i][j]的子集38.隨著散列表的裝填因子a的增大，查找表中指定表項的平均查找長度也要增大，但如果采用______法解決沖突，可平穩(wěn)控制平均查找長度的增大幅度達到最小。A.線性探測B.二次探測C.雙散列D.鏈地址39.編寫一個實現(xiàn)連通圖G的深度優(yōu)先遍歷(從頂點v出發(fā))的非遞歸函數(shù)，可以用偽代碼描述。40.設(shè)表達式以字符形式已存入數(shù)組E[n]中，‘#’為表達式的結(jié)束符，試寫出判斷表達式中括號(‘(’和‘)’)是否配對的C語言描述算法：EXYX(E)；(注：算法中可調(diào)用棧操作的基本算法。)41.對于由n個頂點組成的有向完全圖來說，圖中共包含______條邊，對于由n個頂點組成的無向完全圖來說，圖中共包含______條邊。A.n，n(n-1)B.n，n(n-1)/2C.2n，n(n-1)D.n(n-1)，n(n-1)/242.設(shè)下三角矩陣A為：

如果按行序為主序?qū)⑾氯窃豠ij存儲在一個一維數(shù)組B[1..n(n+1)/2]中，則對任一個三角矩陣元素aij，它在一維數(shù)組B中的下標為

。A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-143.隊尾已到達一維數(shù)組的最高下標，不能再插入元素，然而隊中元素個數(shù)小于隊列的長度，這種現(xiàn)象稱作______。A.上溢B.下溢C.假溢出D.隊列滿44.假設(shè)一個循環(huán)隊列Q[maxSize]的隊頭指針為front，隊尾指針為rear，隊列的最大容量為maxSize，除此之外，該隊列再沒有其他數(shù)據(jù)成員，則該隊列的隊滿條件是______。A.Q.front==Q.rearB.Q.front+Q.rear＞=maxSizeC.Q.front==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%mexSize45.設(shè)G是一個非連通無向圖，有15條邊，則該圖至少有______個頂點。A.5B.6C.7D.846.請簡要比較順序表和鏈表各自的特點。47.線性表(a1，a2，a3，…，an)中元素遞增有序且按順序存儲于計算機內(nèi)。要求設(shè)計算法完成以下內(nèi)容：

(1)用最少的時間在表中查找數(shù)值為x的元素。

(2)若找到將其與后繼元素位置相交換。

(3)若找不到將其插入表中并使表中元素仍遞增有序。48.設(shè)森林中有三棵樹，第一、第二和第三棵樹中的結(jié)點個數(shù)分別為m1、m2和m3。那么在由該森林轉(zhuǎn)化成的二叉樹中根結(jié)點的右子樹上的結(jié)點個數(shù)是______。A.m1+m2B.m2+m3C.m3+m1D.m1+m2+m349.假設(shè)有n(n＞1)個線性表順序地存放在順序表S[1，…，m]中，令F[i]和R[i]指示第i個(1≤i≤n)表的第1個元素和最后1個元素在S中的位置，并設(shè)定R[i]＜F[i+1]，F(xiàn)[n+1]=m+1，如圖所示。試寫出實現(xiàn)下列要求的算法。

(1)在第i個表中的第j項后面插入1個元素，僅當整個順序表空間填滿時，不允許進行插入操作。

(2)刪除第i個表中的第j個元素，要求在刪除第j個元素后，該表仍為順序存儲的線性表。50.改寫順序棧的結(jié)構(gòu)和進棧函數(shù)Push(x)，要求當棧滿時執(zhí)行一個stackFull()操作進行溢出處理。其功能是：動態(tài)創(chuàng)建一個比原來的棧數(shù)組大一倍的新數(shù)組，代替原來的棧數(shù)組，原來棧數(shù)組中的元素占據(jù)新數(shù)組的前maxSize個位置。

原順序棧的程序代碼如下：

typedefstruct

{

intdata[maxSize];

//存放棧中元素，maxSize是已定義的常量

inttop;

//棧頂指針

}SqStack;

//順序棧類型定義

原進棧函數(shù)程序代碼如下：

intPush(SqStack&st,intx}

{

if(st.top==maxSize-1)

//棧滿不能進棧

return0;

++(st.top);

//先移動指針，再進棧

st.data[st.top]=x;

return1;

}第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：B冒泡排序每趟經(jīng)過比較、交換，從無序區(qū)中產(chǎn)生一個最大的元素，所以選B。2.參考答案：D[解析]讓k又樹的每層結(jié)點個數(shù)最少，深度可達最大，這就是單支樹的情形，所以該樹的深度最大為n；讓k叉樹的每層結(jié)點個數(shù)最多，深度可達最小，這相當于平衡樹，若設(shè)該樹的深度為d，上層的d-1層都是滿的，而第d層的結(jié)點散布在該層的各處，此時有n≤k0+k1+…+kd-1=(kd-1)/(k-1)，d≥logk(n×(k-1)+1)。3.參考答案：B此題考查的知識點是遞歸算法的組成部分。一個遞歸算法主要包括終止條件和遞歸部分，所以選B。A不全面，C、D不是遞歸算法。4.參考答案：D[解析]本題考查的是各種鏈表的主要特點，順序表的主要特點是查找方便，而鏈表的主要特點是插入和刪除元素方便。引入雙向循環(huán)鏈表更是為了滿足查找、插入、刪除多方面的性能。5.參考答案：B[解析]在堆成矩陣中，通常存儲其對角線及對角線下方的元素，此時，aij在壓縮后的數(shù)組中的位置為i(i-1)/2+j。但在本題中，B中存儲的是A的對角線及對角線上方的元素，且以列為主存儲次序，因此，aij在壓縮后的數(shù)組中的位置為j(j-1)/2+i。6.參考答案：地圖涂色問題可以用“四染色”定理。將地圖上的國家編號(1到n)，從編號1開始逐一涂色，對每個區(qū)域用1色，2色，3色，4色(下稱“色數(shù)”)依次試探，若當前所取顏色與周圍已涂色區(qū)域不重色，則將該區(qū)域顏色進棧；否則，用下一顏色。若1至4色均與相鄰某區(qū)域重色，則需退?；厮?，修改棧頂區(qū)域的顏色。用鄰接矩陣數(shù)據(jù)結(jié)構(gòu)C[n][n]描敘地圖上國家間的關(guān)系。n個國家用n階方陣表示，若第i個國家與第j個國家相鄰，則Cij=1，否則Cij=0。用棧s記錄染色結(jié)果，棧的下標值為區(qū)域號，元素值是色數(shù)。

voidMapColor(AdjMatrixC)∥以鄰接矩陣C表示的n個國家的地區(qū)涂色

{

ints[]；

∥棧的下標是國家編號，內(nèi)容是色數(shù)

s[1]=1；

∥編號01的國家涂1色

i=2；j=1；∥i為國家號，j為涂色號

while(i＜=n)

{

while(j＜=4&&i＜=n)

{

k=1；

∥k指已涂色區(qū)域號

while(k＜i&&s[k]*C[i][k]!=j)

k++；

∥判斷相鄰區(qū)是否已涂色

if(k＜i)

j=j+1；∥用j+1色繼續(xù)試探

else

{

s[i]=j；

l++：

j=1；

}

∥與相鄰區(qū)不重色，涂色結(jié)果進棧，繼續(xù)對下一區(qū)涂色進行試探

}

}

if(j＞4)

{

1——：

j=s[i]+1；

}//變更棧頂區(qū)域的顏色

}

}7.參考答案：B[解析]需要搜索并找到A的鏈尾，遍歷表A的m個結(jié)點。8.參考答案：C頂點表由兩個域組成，vertex域存儲和該頂點相關(guān)的信息，firstedge域指示第一條依附于該頂點的邊。邊表結(jié)點由六個域組成：mark為標記域，用以標記該條邊是否被搜索過；ivex和jvex為該邊依附的兩個頂點在圖中的位置；ilink指向下一條依附于頂點ivex的邊；jlink指向下一條依附于頂點jvex的邊；info為指向和邊相關(guān)的各種信息的指針域。9.參考答案：B對任何一棵二叉樹，如果終端結(jié)點數(shù)為n。，度為2的結(jié)點數(shù)為n：，則一定有n0=n2+1。所以n2=n0-1=9。10.參考答案：B此題考查的知識點是入棧的具體操作。判斷棧是否滿要看兩個棧頂是否相鄰，當top[1]+1=top[2]或top[2]-1=top[1]時都表示棧滿，所以選B，而A，C沒有任何意義。D表示已經(jīng)出現(xiàn)覆蓋了，也是錯的。11.參考答案：D解析見6。12.參考答案：A[解析]所有待排序的數(shù)據(jù)記錄的排序碼都相等，可按照數(shù)據(jù)初始排列已經(jīng)有序的情況來分析。按照本教材所給算法：

直接插入排序的排序碼比較次數(shù)和元素移動次數(shù)受數(shù)據(jù)的初始排列影響，每趟只比較1次，做n-1趟，排序碼比較次數(shù)總共為n-l，元素移動次數(shù)為0。

起泡排序的排序碼比較次數(shù)和元素移動次數(shù)也受數(shù)據(jù)的初始排列影響，只比較一趟，排序碼比較次數(shù)為n-1，元素移動次數(shù)為0。

簡單選擇排序的排序碼比較次數(shù)不受數(shù)據(jù)的初始排列影響，比較n-1趟，排序碼比較次數(shù)為n(n-1)/2；但元素移動次數(shù)受數(shù)據(jù)的初始排列影響，當待排序記錄排序碼都相等時，元素移動次數(shù)為0。

對于堆排序，在形成初始堆時，總共有次排序碼比較，次數(shù)據(jù)移動；在堆排序時，做n-1次對調(diào)和重新形成堆，每次對調(diào)做3次數(shù)據(jù)移動，最多做(n-1)×2次排序碼比較，(n-1)×(3+2)次數(shù)據(jù)移動。綜上所述，堆排序的排序碼比較次數(shù)最多為，元素移動次數(shù)最多是。13.參考答案：D深度優(yōu)先遍歷的思想類似于樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發(fā)，訪問該頂點，然后依次從v的未被訪問的鄰接點出發(fā)繼續(xù)深度優(yōu)先遍歷圖中的其余頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。14.參考答案：A[解析]將森林F轉(zhuǎn)化為二叉樹表示B，則B的根是第一棵樹的根，根的左子樹是第一棵樹的根的子樹森林，根的右子樹是森林中除去第一棵樹外其他樹構(gòu)成的森林。根據(jù)題意，B的根是p，p的右子樹中的結(jié)點個數(shù)為n，則森林F的第一棵樹中結(jié)點個數(shù)為m-n。15.參考答案：B[解析]根據(jù)m階B樹的定義，樹中每個結(jié)點最多有m棵子樹，有m-1個關(guān)鍵字，若插入新關(guān)鍵字后該結(jié)點的關(guān)鍵字數(shù)超過了m-1，則需要進行分裂。16.參考答案：voidDelete(BSTreet,p){

//在二叉排序樹t中，刪除f所指結(jié)點的右孩子(由p所指向)

if(p-＞lchild==null){f-＞rchild=p-＞rchild;free(p);}

//p無左子女

else{

//用p左子樹中的最大值代替p結(jié)點的值

q=p-＞lchild;s=q;

while(q-＞rchild){s=q;q=q-＞rchild;}

//查P左子樹中序序列最右結(jié)點

if(s==p-＞lchild)

//p左子樹的根結(jié)點無右子女

{p-＞data=s-＞data;p-＞lchild=s-＞lchild;free(s);}

else{p-＞data=q-＞data;s-＞rchild=q-＞lchild;free(q);}

}

}17.參考答案：線性表每一個表元素的數(shù)據(jù)空間要求相同，但如果對每一個元素的數(shù)據(jù)類型要求不同時可以用等價類型(union)變量來定義可能的數(shù)據(jù)元素的類型。如

Typedefunion{

//聯(lián)合

intintegerInfo;

//整型

charcharInfo;

//字符型

floatfloatInfo;

//浮點型

}info;

利用等價類型，可以在同一空間(空間大小相同)indo中存放不同數(shù)據(jù)類型的元素。但要求用什么數(shù)據(jù)類型的變量存，就必須以同樣的數(shù)據(jù)類型來取。18.參考答案：本算法不需要將整個記錄排序，只進行查找第j個記錄(從小到大排序)。

程序代碼如下：

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

{

intj;

elemtypex;

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;

//相當于交換A[i]與A[j]

}

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

//從左向右遍歷

++i;

if(i＜j)

{

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

//相當于交換A[i]與A[j]

}

}

A[i]=x;

//x定位在位置i處

}

sort(intA[],intj,intn)

{

ints=0,t=n-1,k;

split(A,s,t,k);

while(k!=j)

if(k＜j)

split(A,k+1,t,k);

//元素在右邊，對右邊進行劃分

else

split(A,s,k-1,k);

//元素在左邊，對左邊進行劃分

returnA[j];

}19.參考答案：根據(jù)中序線索二叉樹的定義得到求第一個結(jié)點(first())、下一個結(jié)點(next())、最后一個結(jié)點(last())和前一個結(jié)點(prior())的函數(shù)，再設(shè)計中序正向遍歷二叉樹(forward())和中序反向遍歷二叉樹(back())的函數(shù)。

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

BTNode*first(BTNode*root)

//返回root為根的中序線索樹中的第一個結(jié)點

{

while(root→ltag==0)

root=root→left;

returnroot;

}

BTNode*last(BTNode*root)

//返回root為根的中序線索樹中的最后一個結(jié)點

{

BTNode*p=root→right;

returnpi

}

BTNode*next(BTNode*root,BTNode*q)

//返回q結(jié)點的后繼結(jié)點

{

BTNode*p=q→right,*n;

if(q→rtag==0)

//有右孩子時

while(p→ltag==0)

p=p→left;

n=p;

if(n==root)

//若q為最后一個結(jié)點，則返回NULL，否則返回n

returnNULL;

else

returnn;

}

BTNode*prior(BTNode*root,BTNode*q)

//返回q的前驅(qū)結(jié)點

{

BTNode*p=q→left,*n;

if(q→ltag==0)

while(p→rtag==0)

p=p→right;

n=p;

if(n==root)

//若q為第一個結(jié)點，則返回NULL，否則返回n

returnNULL;

else

returnn;

}

voidforward(BTNode*root)

//中序正向遍歷二叉樹

{

BTNode*p;

for(p=first(root);p!=NULL;p=next(root,p))

visit(p);

//訪問p,visit是已經(jīng)定義的訪問函數(shù)

}

voidback(BTNode*root)

//中序反向遍歷二叉樹

{

BTNode*p;

p=last(root);

for(p=last(root);p!=NULL;p=prior(root,p))

visit(p);

//訪問p,visit是已經(jīng)定義的訪問函數(shù)

}20.參考答案：本題屬于條件深度(廣度)優(yōu)先搜索問題，即在通常的搜索算法中加入一定的條件，過濾掉不滿足條件的搜索結(jié)果。cond函數(shù)即為判斷題目給出的條件是否滿足的函數(shù)。程序代碼如下：

intvisited[Vnum],A[Vnum];

intcond(intA[],intd,intv1,intv6,intv4)

//判斷條件

{

intflag1=0,flag2=0,flag3=1,i;

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

//判斷路徑中是否有“食品”

if(A[i]==v1)

{

flag1=1;

break;

}

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

//判斷路徑中是否有“財寶”

if(A[i]==v6)

{

flag2=1;

break;

}

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

//判斷路徑中是否沒有“強盜”

if(A[i]==v4)

{

flag3=0;

break;

}

returnflag1&&flag2&&flag3;

//返回正確條件

}

voiddfs1(graph*g,intvi,intvj,intv1,intv6,intv4,intd)

{

intv,i;

arcnode*p;

visited[vi]=1;

++d;

//d指明DFS所經(jīng)過的頂點數(shù)目

A[d]=vi;

if(vi==vj&&cond(A,d,v1,v6,v4)==1)

{

//按照條件輸出路徑

cout＜＜"一條路徑:";

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

cout＜＜A[i]＜＜"";

}

p=g→adjlist[vi].firstarc;

//找vi的第一個鄰接頂點

while(p!=NULL)

{

v=p→adjvex;

//v為vi的鄰接頂點

if(visited[v]==0)

//若該頂點未標記訪問，則遞歸訪問

dfs1(g,v,vj,v1,v6,v4,d);

p=p→nextarc;

//找vi的下一個鄰接頂點

}

visited[v!]=0;

//取消訪問標記，以使該頂點可重新使用

--d;

}21.參考答案：D[解析]按照所有中國人的生日(月、日)排序，一方面是n很大，另一方面d不大(d=2，兩個排序碼)且一個排序碼的基數(shù)為12(月)，另一排序碼的基數(shù)為31(日)，都不大，可采用多排序碼，即基數(shù)排序。其時間復(fù)雜度可達O(n)。22.參考答案：B本題考查哈夫曼樹的性質(zhì)。哈夫曼樹中只有度為2和度為0的結(jié)點，哈夫曼編碼是對哈夫曼樹中的葉子結(jié)點編碼。根據(jù)樹的性質(zhì)N0=N2+1，故N0=(N2+N0+1)/2=(99+1)/2=50，哈夫曼樹共有50個葉子結(jié)點，所以共能得到50個不同的碼字。23.參考答案：B由中序遍歷過程可知本題答案應(yīng)為B。24.參考答案：A=(a1，a2，…，an)，有n+1個位置可插入元素，即a1之前，a1與a2之間，…，an-1與an之間和an之后，分別需要移動的元素個數(shù)為n，n-1，…，1，0，則平均插入一個元素需要移動的元素個數(shù)為

若元素插入在ai與ai+1之間(1≤i≤n-1)的概率為，其中移動的元素個數(shù)為

則平均每插入一個元素所要移動的元素個數(shù)為

25.參考答案：[證明]假設(shè)二叉樹中度為1的結(jié)點個數(shù)為n。，結(jié)點總數(shù)為n。因為二叉樹中任何結(jié)點的度最大不超過2，因此有：

n=n0+n1+n2

—————(1)

從另一個角度看，我們來研究二叉樹的分支數(shù)。對所有結(jié)點來說，除了根結(jié)點，任何其余結(jié)點都有一個分支進入(指向)。不妨設(shè)B(Branch)為二叉樹的分支數(shù)，則有：

B=n-1(分支數(shù)比結(jié)點數(shù)少1)

—————(2)

而分支是由度為1的結(jié)點和度為2的結(jié)點貢獻的：每個度為1的結(jié)點貢獻1個分支，每個度為2的結(jié)點貢獻2個分支。則有：

B=n1×1+n2×2=n1+2n2。

—————(3)

由(2)、(3)得

n=n1+2n2+1

—————(4)

由(1)、(4)得

n0=n2+1

由此得出結(jié)論：二叉樹葉子結(jié)點個數(shù)總是比度為2的結(jié)點個數(shù)多1。26.參考答案：

27.參考答案：C[解析]用Dijkstra算法求從帶權(quán)有向圖的某個源頂點到其他各個頂點的最短路徑，執(zhí)行n-1次或n-2次選擇，每次選擇一個頂點后還要計算繞過這個新選出的頂點是否能夠縮短從源頂點到其他未選擇最短路徑的頂點的路徑長度，有兩層嵌套for循環(huán)，所以算法的時間復(fù)雜度為O(n2)。28.參考答案：A[解析]根據(jù)圖的廣度優(yōu)先遍歷算法可知，遍歷過程中每個頂點最多進隊1次。29.參考答案：B[解析]對于有向強連通圖，當n等于1時，邊為0，否則至少需要n條邊才能形成強連通圖。此時所有n個頂點都在某一個有向環(huán)上，如下圖所示。在此情況下，當有向邊的條數(shù)少于n時，不能構(gòu)成環(huán)，不再是強連通圖。

30.參考答案：B[解析]為了解釋這個問題，這里規(guī)定對于任意一棵二叉樹，標記訪問根結(jié)點為V，標記遍歷根的左子樹為L，標記遍歷根的右子樹為R，由此可得前序遍歷順序為VLR，中序遍歷順序為LVR，后序遍歷順序為LRV，可以看出，對于3種遍歷方式，遍歷指針在二叉樹中走過的左、右子樹的次序都相同，都是先左后右，由此可知所有葉結(jié)點在遍歷時訪問的先后次序都相同。就是說，它們在各種遍歷算法結(jié)果序列中的相對次序都相同。31.參考答案：能存儲多少索引項，主要看葉結(jié)點。非葉結(jié)點是對下層最多關(guān)鍵字的復(fù)寫。

對于高度為1的B+樹：根據(jù)B+樹定義，根結(jié)點又是葉結(jié)點，最多可存儲m=100個索引項，最少可存放1個索引項。

對于高度為2的B+樹：最多可存儲m×m=1002個索引項，最少可存儲101個索引項。因為當根結(jié)點關(guān)鍵字個數(shù)n達到101，發(fā)生結(jié)點分裂，其高度才會變?yōu)?。

對于高度為3的B+樹：最多可存儲m×m×m=1003個索引項，最少可存儲2×101=202個索引項。因為當?shù)?層的關(guān)鍵字個數(shù)達到101做結(jié)點分裂，葉結(jié)點才會落到第2層，第2層2個結(jié)點，每個結(jié)點的關(guān)鍵字個數(shù)達到101引發(fā)結(jié)點分裂，葉結(jié)點落到第3層。此時，葉結(jié)點有51+50+51+50=202個索引項。

對于高度為4的B+樹：第4層是葉結(jié)點。最多可存儲m4=1004個索引項，最少可存儲4×101=404個索引項。葉結(jié)點有51+50+51+50+51+50+51+50=404個索引項。32.參考答案：A[解析]本題可以根據(jù)插入元素的位置列出一個移動元素個數(shù)序列，在末尾插入時，移動元素為0；在第n位插入時，移動元素為n-1；…；在起始位置插入時，移動元素為n。由于等概率插入，在每個位置上插入新元素的概率均為1/(n+1)。因此，平均移動元素為(0+1+2+…+n)/(n+1)=n/2。33.參考答案：C34.參考答案：A此題考查的知識點是雙向鏈表的插入操作。在p前插入，要修改p的prior指針、p的prior所指結(jié)點的next指針，所以選A。B、C、D都將使地址丟失，連接失敗。35.參考答案：B[解析]三對角線矩陣屬于帶狀矩陣，如圖所示。帶狀矩陣下標范圍可以表示為i-1≤j≤i+1，因此本題選B。

36.參考答案：二叉樹是遞歸定義的，以遞歸方式建立最簡單。二叉樹建立過程如下：

BiTreeCreat(){

//建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu)

ElemTypex;

BiTreebt;

scanf("%d",&x);

//本題假定結(jié)點數(shù)據(jù)域為整型

if(x==0)bt=null;

elseif(x＞0){

bt=(BiNode*)malloc(sizeof(BiNode));

bt-＞data=x;

bt-＞lchild=Creat();

bt-＞rchild=Creat();

}

elseerror("輸入錯誤");

return(bt);

}//結(jié)束BiTree37.參考答案：A[解析]簡單路徑是沒有重復(fù)頂點的路徑。圖的最短路徑采用貪心法求解，在求從vi到vj的最短路徑時，可以繞過那些已經(jīng)求得最短路徑的頂點，縮短從vi到vj的最短路徑。有可能最短路徑經(jīng)過許多頂點，但絕不會繞過，所以圖的最短路徑應(yīng)是簡單路徑。其他選項都是錯誤的。在有向圖中從一個頂點到另一個頂點的最短路徑不是唯一的，但最短路徑長度應(yīng)是唯一的。Dijkstra算法僅要求邊上的權(quán)值不能為負值，并未排除有回路的帶權(quán)有向圖，不過它的結(jié)果應(yīng)是簡單路徑。另外，path(k-1)[i][j]是從頂點vi繞過頂點v0，v1，…，vk-1到達vj的最短路徑，path(k)[i][j]是從頂點vi繞過頂點v0，v1，…，vk到達vj的最短路徑，路徑可能會改變，不是子集。38.參考答案：D[解析]線性探測、二次探測和雙散列都屬于解決沖突的開地址法，尋找下一個空位的操作僅限于散列表本身的基本存儲空間，隨著表的裝滿程度的增加，沖突越來越多，查找某一表項的平均查找次數(shù)也越來越多，以線性探測最甚。而鏈地址法設(shè)置溢出存儲空間，裝填因子a的增大，僅表明基本存儲空間裝得越來越滿，但大多數(shù)發(fā)生沖突的表項都存放到溢出空間去了，在基本存儲空間的沖突沒有大幅增加，平均查找次數(shù)也不會大幅增長。39.參考答案：本題的算法如下：

將所有頂點置為“未訪問”標志；

輸出起始頂點v0；

置v0為“已訪問”標志；

將v0入棧；

while(棧不空時)

{

取棧頂v；

if(v存在未被訪問的鄰接頂點，則選擇一個頂點v1)

{

輸出v1；

置v1為“已訪問”標志；

將v1入棧；

}

else當前頂點退棧；

}

c語言代碼如下：

voiddfs1(graphg,intv)

{

inti;

arcnode*p;

intvisited[Vnum],top=-1,stack[Vnum];

for(i=0;i＜g.vexnum;i++)

visited[i]=0;

//結(jié)點訪問標志均置為0

visit(v);

//訪問頂點v

top++;

//v入棧

stack[top]=v;

visited[v]=1;

while(top＞=0)

//棧不空時循環(huán)

{

v=stack[top];--top;

//取棧頂頂點

p=g.adjlist[v].firstarc;

while(p!=NULL&&visited[p→adjvex]==1)

p=p→nextarc;

if(p==NULL)

//若沒有，退到前一個

--top;

else

//若有，選擇一個

{

v=p→adjvex;

visit(v);

//訪問頂點

visited[v]=1;

top++;

//入棧

stack[top]=v;

}

}

}40.參考答案：判斷表達式中括號是否匹配，可通過棧，簡單說是左括號時進棧．右括號時退棧。退棧時，若棧頂元素是左括號，則新讀入的右括號與棧頂左括號就可消去。如此下去，輸入表達式結(jié)束時，棧為空則正確，否則括號不匹配

intEXYX(charE[]，intn)

//E[]是有n字符的字符數(shù)組，存放字符串表達式，以‘#’結(jié)束。本算法判斷表達式中圓括號是否匹配

{charsE30]；

∥s是一維數(shù)組，容量足夠大，用作存放括號的棧

inttop=0；

∥top用作棧頂指針

SEtop]=‘#’；

∥‘#’先入棧，用于和表達式結(jié)束符號‘#’匹配

inti=0；

∥字符數(shù)組E的工作指針

while(E[l]!=‘#’)

∥逐字符處理字符表達式的數(shù)組

switch(E[i])

{caSe‘(’：s[++top]=‘(’；i++；break；

case‘)’：if(s[top]==‘(’{top——；i++；break；)

else{printf(“括號不配對”)；exit(0)；}

case‘#’：if(sEtop]==‘#’){printf(“括號配對＼n”)；return(1)；}

else{printf(“括號不配對\n”)；return(0)；)∥括號不配對

default：i++；

∥讀入其他字符，不作處理

}

}

本題是用棧判斷括號匹配的特例：只檢查圓括號的配對。一般情況下是檢查花括號(‘{’，‘}’)、方括號(‘[’，‘]’)和圓括號(‘(’，‘)’)的配對問題。編寫算法中如遇左括號(‘{’，‘[’，或‘(’)就壓入棧中，如遇右括號(‘)’，‘]’，或‘)’)，則與棧頂元素比較，如是與其配對的括號(左花括號、左方括號或左圓括號)，則彈出棧頂元素；否則，就結(jié)論括號不配對。在讀入表達式結(jié)束符‘#’時，棧中若只?！?’，表示括號全部配對成功；否則表示括號不匹配。

另外，由于本題只是檢查括號是否匹配，故對從表達式中讀入的不是括號的那些字符，一律未作處理。再有，假設(shè)棧容量足夠大，因此入棧時未判斷溢出。41.參考答案：D由完全圖的定義可知本題答案為D。42.參考答案：A如何將aij保存在數(shù)組B中，保存在哪個位置?也就是說，設(shè)k為aij保存在B中時的下標，那么k和i、j有什么關(guān)系?

A[i，j]在B中的位置=(A中前i-1行非0元素的個數(shù))

+(A中第i行、第j列之前非0元素的個數(shù)，包括第j列)

=(1+2+3+…+(i-1))+j

=i(i-1)/2+j

則A[i，j]存放在B中的元素下標k—i(i一1)/2+j(因為B的數(shù)據(jù)元素從1開始)。

例如：A[3，3]保存在B中的位置為

k=3×(3=1)/2+3=6，即A[3，3]保存在數(shù)據(jù)元素B[6]中。43.參考答案：C用常規(guī)意義下順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)(隊尾插入和隊頭刪除)，容易造成“假溢出”現(xiàn)象，即隊尾已到達一維數(shù)組的高下標，不能再插入，然而隊中元素個數(shù)卻小于隊列的長度(容量)。44.參考答案：C[解析]既然不能附加任何其他數(shù)據(jù)成員，只能采用犧牲一個隊列元素的整除區(qū)域的方式來區(qū)分隊空和隊滿的條件。因此，選項C是合適的。選項A是判斷隊列是否空的條件，選項B和選項D都是干擾項。45.參考答案：C[解析]本題根據(jù)連通圖的性質(zhì)以及頂點與邊數(shù)的關(guān)系即可求解：設(shè)無向圖有n個頂點，它的邊數(shù)e≤n(n-1)/2。若e=15，有15≤n(n-1)/2，解得n>≥6。在連通圖情形下至少需有6個頂點，在非連通圖情形下則至少需有7個頂點。46.參考答案：(1)基于空間的比較。

1)存儲分配的方式：

順序表的存儲空間是靜態(tài)分配的。

鏈表的存儲空間是動態(tài)分配的。

2)存儲密度(存儲密度=結(jié)點值域所占的存儲量/結(jié)點結(jié)構(gòu)所占的存儲總量)：

順序表的存儲密度=1。

鏈表的存儲密度＜1(因為結(jié)點中有指針域)。

(2)基于時間的比較。

1)存取方式：

順序表可以隨機存取，也可以順序存取(對于順序表一般只答隨機存取即可)

鏈表是順序存取的。

2)插入/刪除時移動元素的個數(shù)：

順序表平均需要移動近一半元素。

鏈表不需要移動元素，只需要修改指針。47.參考答案：(1)順序存儲的線性表遞增有序，可以順序查找，也可折半查找。題目要求“用最少的時間在表中查找數(shù)值為x的元素”，這里應(yīng)使用折半查找方法。

voidSearchExchangelnsert(ElemTypea[];ElemTypex)

//a是具有n個元素的遞增有序線性表，順序存儲。本算法在表中查找數(shù)值為x的

//元素，如查到則與其后繼交換位置；如查不到，則插入表中，且使表仍遞增有序

{

low=0;

high=n-1;

//low和high指向線性表下界和上界的下標

while(low＜=high)

{

mid=(low+high)/2;

//找中間位置

if(a[mid]==x)break;

//找到x，退出while循環(huán)

elseif(a[mid]＜x)low=mid+1;

//到中點mid的右半去查

elsehigh=mid-1;

//到中點mid的左半去查

}

if(a[mid]==x&&mid!=n)

//若最后一個元素與x相等，則不存在與其后繼交換的操作

{

t=a[mid];

a[mid]=a[mid+1];

a[mid+1]=t;

}

//數(shù)值x與其后繼元素位置交換

if(low＞high)

//查找失敗，插入數(shù)據(jù)元素x

{

for(i=n-1;i＞high;i--)