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

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

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

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

個(gè)度為2的結(jié)點(diǎn)。A.8B.9C.10D.1110.現(xiàn)有兩棧，其共享空間為V[1..m]，top[i]代表第i個(gè)棧(i=1，2)棧頂，棧1的底在V[1]，棧2的底在V[m]，若兩棧均采用順序存儲(chǔ)方式存儲(chǔ)，則棧滿(mǎn)的條件是______。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.當(dāng)所有n個(gè)待排序記錄的排序碼都相等時(shí)，直接插入排序、堆排序、起泡排序、簡(jiǎn)單選擇排序的排序碼比較次數(shù)和元素移動(dòng)次數(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.無(wú)向圖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)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是

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

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

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

(1)插入90

(2)插入25

(3)插入45

(4)刪除60

(5)刪除80

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

如果按行序?yàn)橹餍驅(qū)⑾氯窃豠ij存儲(chǔ)在一個(gè)一維數(shù)組B[1..n(n+1)/2]中，則對(duì)任一個(gè)三角矩陣元素aij，它在一維數(shù)組B中的下標(biāo)為

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

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

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

(3)若找不到將其插入表中并使表中元素仍遞增有序。48.設(shè)森林中有三棵樹(shù)，第一、第二和第三棵樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3。那么在由該森林轉(zhuǎn)化成的二叉樹(shù)中根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是______。A.m1+m2B.m2+m3C.m3+m1D.m1+m2+m349.假設(shè)有n(n＞1)個(gè)線(xiàn)性表順序地存放在順序表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，如圖所示。試寫(xiě)出實(shí)現(xiàn)下列要求的算法。

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

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

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

typedefstruct

{

intdata[maxSize];

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

inttop;

//棧頂指針

}SqStack;

//順序棧類(lèi)型定義

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

intPush(SqStack&st,intx}

{

if(st.top==maxSize-1)

//棧滿(mǎn)不能進(jìn)棧

return0;

++(st.top);

//先移動(dòng)指針，再進(jìn)棧

st.data[st.top]=x;

return1;

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

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

{

ints[]；

∥棧的下標(biāo)是國(guó)家編號(hào)，內(nèi)容是色數(shù)

s[1]=1；

∥編號(hào)01的國(guó)家涂1色

i=2；j=1；∥i為國(guó)家號(hào)，j為涂色號(hào)

while(i＜=n)

{

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

{

k=1；

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

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é)果進(jìn)棧，繼續(xù)對(duì)下一區(qū)涂色進(jìn)行試探

}

}

if(j＞4)

{

1——：

j=s[i]+1；

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

}

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

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

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

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

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

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

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

//p無(wú)左子女

else{

//用p左子樹(shù)中的最大值代替p結(jié)點(diǎn)的值

q=p-＞lchild;s=q;

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

//查P左子樹(shù)中序序列最右結(jié)點(diǎn)

if(s==p-＞lchild)

//p左子樹(shù)的根結(jié)點(diǎn)無(wú)右子女

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

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

}

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

Typedefunion{

//聯(lián)合

intintegerInfo;

//整型

charcharInfo;

//字符型

floatfloatInfo;

//浮點(diǎn)型

}info;

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

程序代碼如下：

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;

//相當(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處

}

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);

//元素在右邊，對(duì)右邊進(jìn)行劃分

else

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

//元素在左邊，對(duì)左邊進(jìn)行劃分

returnA[j];

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

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

BTNode*first(BTNode*root)

//返回root為根的中序線(xiàn)索樹(shù)中的第一個(gè)結(jié)點(diǎn)

{

while(root→ltag==0)

root=root→left;

returnroot;

}

BTNode*last(BTNode*root)

//返回root為根的中序線(xiàn)索樹(shù)中的最后一個(gè)結(jié)點(diǎn)

{

BTNode*p=root→right;

returnpi

}

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

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

{

BTNode*p=q→right,*n;

if(q→rtag==0)

//有右孩子時(shí)

while(p→ltag==0)

p=p→left;

n=p;

if(n==root)

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

returnNULL;

else

returnn;

}

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

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

{

BTNode*p=q→left,*n;

if(q→ltag==0)

while(p→rtag==0)

p=p→right;

n=p;

if(n==root)

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

returnNULL;

else

returnn;

}

voidforward(BTNode*root)

//中序正向遍歷二叉樹(shù)

{

BTNode*p;

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

visit(p);

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

}

voidback(BTNode*root)

//中序反向遍歷二叉樹(shù)

{

BTNode*p;

p=last(root);

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

visit(p);

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

}20.參考答案：本題屬于條件深度(廣度)優(yōu)先搜索問(wèn)題，即在通常的搜索算法中加入一定的條件，過(guò)濾掉不滿(mǎn)足條件的搜索結(jié)果。cond函數(shù)即為判斷題目給出的條件是否滿(mǎn)足的函數(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)

//判斷路徑中是否有“財(cái)寶”

if(A[i]==v6)

{

flag2=1;

break;

}

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

//判斷路徑中是否沒(méi)有“強(qiáng)盜”

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)過(guò)的頂點(diǎn)數(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的第一個(gè)鄰接頂點(diǎn)

while(p!=NULL)

{

v=p→adjvex;

//v為vi的鄰接頂點(diǎn)

if(visited[v]==0)

//若該頂點(diǎn)未標(biāo)記訪(fǎng)問(wèn)，則遞歸訪(fǎng)問(wèn)

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

p=p→nextarc;

//找vi的下一個(gè)鄰接頂點(diǎn)

}

visited[v!]=0;

//取消訪(fǎng)問(wèn)標(biāo)記，以使該頂點(diǎn)可重新使用

--d;

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

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

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

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

n=n0+n1+n2

—————(1)

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

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

—————(2)

而分支是由度為1的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)貢獻(xiàn)的：每個(gè)度為1的結(jié)點(diǎn)貢獻(xiàn)1個(gè)分支，每個(gè)度為2的結(jié)點(diǎn)貢獻(xiàn)2個(gè)分支。則有：

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

—————(3)

由(2)、(3)得

n=n1+2n2+1

—————(4)

由(1)、(4)得

n0=n2+1

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

27.參考答案：C[解析]用Dijkstra算法求從帶權(quán)有向圖的某個(gè)源頂點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑，執(zhí)行n-1次或n-2次選擇，每次選擇一個(gè)頂點(diǎn)后還要計(jì)算繞過(guò)這個(gè)新選出的頂點(diǎn)是否能夠縮短從源頂點(diǎn)到其他未選擇最短路徑的頂點(diǎn)的路徑長(zhǎng)度，有兩層嵌套for循環(huán)，所以算法的時(shí)間復(fù)雜度為O(n2)。28.參考答案：A[解析]根據(jù)圖的廣度優(yōu)先遍歷算法可知，遍歷過(guò)程中每個(gè)頂點(diǎn)最多進(jìn)隊(duì)1次。29.參考答案：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)連通圖。

30.參考答案：B[解析]為了解釋這個(gè)問(wèn)題，這里規(guī)定對(duì)于任意一棵二叉樹(shù)，標(biāo)記訪(fǎng)問(wèn)根結(jié)點(diǎn)為V，標(biāo)記遍歷根的左子樹(shù)為L(zhǎng)，標(biāo)記遍歷根的右子樹(shù)為R，由此可得前序遍歷順序?yàn)閂LR，中序遍歷順序?yàn)長(zhǎng)VR，后序遍歷順序?yàn)長(zhǎng)RV，可以看出，對(duì)于3種遍歷方式，遍歷指針在二叉樹(shù)中走過(guò)的左、右子樹(shù)的次序都相同，都是先左后右，由此可知所有葉結(jié)點(diǎn)在遍歷時(shí)訪(fǎng)問(wèn)的先后次序都相同。就是說(shuō)，它們?cè)诟鞣N遍歷算法結(jié)果序列中的相對(duì)次序都相同。31.參考答案：能存儲(chǔ)多少索引項(xiàng)，主要看葉結(jié)點(diǎn)。非葉結(jié)點(diǎn)是對(duì)下層最多關(guān)鍵字的復(fù)寫(xiě)。

對(duì)于高度為1的B+樹(shù)：根據(jù)B+樹(shù)定義，根結(jié)點(diǎn)又是葉結(jié)點(diǎn)，最多可存儲(chǔ)m=100個(gè)索引項(xiàng)，最少可存放1個(gè)索引項(xiàng)。

對(duì)于高度為2的B+樹(shù)：最多可存儲(chǔ)m×m=1002個(gè)索引項(xiàng)，最少可存儲(chǔ)101個(gè)索引項(xiàng)。因?yàn)楫?dāng)根結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)n達(dá)到101，發(fā)生結(jié)點(diǎn)分裂，其高度才會(huì)變?yōu)?。

對(duì)于高度為3的B+樹(shù)：最多可存儲(chǔ)m×m×m=1003個(gè)索引項(xiàng)，最少可存儲(chǔ)2×101=202個(gè)索引項(xiàng)。因?yàn)楫?dāng)?shù)?層的關(guān)鍵字個(gè)數(shù)達(dá)到101做結(jié)點(diǎn)分裂，葉結(jié)點(diǎn)才會(huì)落到第2層，第2層2個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)達(dá)到101引發(fā)結(jié)點(diǎn)分裂，葉結(jié)點(diǎn)落到第3層。此時(shí)，葉結(jié)點(diǎn)有51+50+51+50=202個(gè)索引項(xiàng)。

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

36.參考答案：二叉樹(shù)是遞歸定義的，以遞歸方式建立最簡(jiǎn)單。二叉樹(shù)建立過(guò)程如下：

BiTreeCreat(){

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

ElemTypex;

BiTreebt;

scanf("%d",&x);

//本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎?/p>

if(x==0)bt=null;

elseif(x＞0){

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

bt-＞data=x;

bt-＞lchild=Creat();

bt-＞rchild=Creat();

}

elseerror("輸入錯(cuò)誤");

return(bt);

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

將所有頂點(diǎn)置為“未訪(fǎng)問(wèn)”標(biāo)志；

輸出起始頂點(diǎn)v0；

置v0為“已訪(fǎng)問(wèn)”標(biāo)志；

將v0入棧；

while(棧不空時(shí))

{

取棧頂v；

if(v存在未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)，則選擇一個(gè)頂點(diǎn)v1)

{

輸出v1；

置v1為“已訪(fǎng)問(wèn)”標(biāo)志；

將v1入棧；

}

else當(dāng)前頂點(diǎn)退棧；

}

c語(yǔ)言代碼如下：

voiddfs1(graphg,intv)

{

inti;

arcnode*p;

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

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

visited[i]=0;

//結(jié)點(diǎn)訪(fǎng)問(wèn)標(biāo)志均置為0

visit(v);

//訪(fǎng)問(wèn)頂點(diǎn)v

top++;

//v入棧

stack[top]=v;

visited[v]=1;

while(top＞=0)

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

{

v=stack[top];--top;

//取棧頂頂點(diǎn)

p=g.adjlist[v].firstarc;

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

p=p→nextarc;

if(p==NULL)

//若沒(méi)有，退到前一個(gè)

--top;

else

//若有，選擇一個(gè)

{

v=p→adjvex;

visit(v);

//訪(fǎng)問(wèn)頂點(diǎn)

visited[v]=1;

top++;

//入棧

stack[top]=v;

}

}

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

intEXYX(charE[]，intn)

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

{charsE30]；

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

inttop=0；

∥top用作棧頂指針

SEtop]=‘#’；

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

inti=0；

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

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

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

switch(E[i])

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

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

else{printf(“括號(hào)不配對(duì)”)；exit(0)；}

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

else{printf(“括號(hào)不配對(duì)\n”)；return(0)；)∥括號(hào)不配對(duì)

default：i++；

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

}

}

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

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

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

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

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

=i(i-1)/2+j

則A[i，j]存放在B中的元素下標(biāo)k—i(i一1)/2+j(因?yàn)锽的數(shù)據(jù)元素從1開(kāi)始)。

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

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

1)存儲(chǔ)分配的方式：

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

鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。

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

順序表的存儲(chǔ)密度=1。

鏈表的存儲(chǔ)密度＜1(因?yàn)榻Y(jié)點(diǎn)中有指針域)。

(2)基于時(shí)間的比較。

1)存取方式：

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

鏈表是順序存取的。

2)插入/刪除時(shí)移動(dòng)元素的個(gè)數(shù)：

順序表平均需要移動(dòng)近一半元素。

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

voidSearchExchangelnsert(ElemTypea[];ElemTypex)

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

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

{

low=0;

high=n-1;

//low和high指向線(xiàn)性表下界和上界的下標(biāo)

while(low＜=high)

{

mid=(low+high)/2;

//找中間位置

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

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

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

//到中點(diǎn)mid的右半去查

elsehigh=mid-1;

//到中點(diǎn)mid的左半去查

}

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

//若最后一個(gè)元素與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--)