2023年研究生類(lèi)研究生入學(xué)考試專(zhuān)業(yè)課計(jì)算機(jī)學(xué)科專(zhuān)業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)2010-2022歷年真題選編帶答案難題含解析

2023年研究生類(lèi)研究生入學(xué)考試專(zhuān)業(yè)課計(jì)算機(jī)學(xué)科專(zhuān)業(yè)綜合基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)2010-2022歷年真題選編帶答案難題含解析（圖片大小可自由調(diào)整）第1卷一.歷年考點(diǎn)試題黑鉆版(共75題)1.在對(duì)一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較______次。A.1B.2C.3D.42.從鍵盤(pán)上輸入一個(gè)逆波蘭表達(dá)式，用偽碼寫(xiě)出其求值程序。規(guī)定：逆波蘭表達(dá)式的長(zhǎng)度不超過(guò)一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔，操作符只可能有+、-、*、/四種運(yùn)算，例如：234-34+2*$。3.在采用鏈地址法解決沖突時(shí)，每一個(gè)散列地址所鏈接的同義詞子表中各個(gè)表項(xiàng)的______相同。A.關(guān)鍵字值B.元素值C.散列地址D.含義4.有一組數(shù)據(jù)(15，9，7，8，20，-1，7，4)，用堆排序的篩選方法建立的初始堆為_(kāi)_____。A.-1，4，8，9，20，7，15，7B.-1，7，15，7，4，8，20，9C.-1，4，7，8，20，15，7，9D.A、B、C均不對(duì)5.為了增加內(nèi)存空間的利用率和減少溢出的可能性，兩個(gè)?？梢怨蚕硪黄B續(xù)的內(nèi)存空間，此時(shí)應(yīng)將兩棧的棧底分別設(shè)在______。A.內(nèi)存空間的首地址B.內(nèi)存空間的尾地址C.內(nèi)存空間的兩端D.內(nèi)存空間的中間6.若循環(huán)隊(duì)列以數(shù)組Q[0，…，m-1]作為其存儲(chǔ)結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中的隊(duì)尾元素的實(shí)際位置，其移動(dòng)按rear=(rear+1)MODm進(jìn)行，變量length表示當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是______。A.rear-lengthB.(rear-length+m)MODmC.(rear-length+l+m)MODmD.m-length7.設(shè)A和B是兩個(gè)順序表，其元素按從小到大的順序排列。編寫(xiě)一個(gè)將A和B中相同元素組成一個(gè)新的從大到小的有序順序表C的算法，并分析算法的時(shí)間復(fù)雜度。8.設(shè)計(jì)快速排序的遞歸和非遞歸算法。9.構(gòu)建一個(gè)哈夫曼樹(shù)，如果給定權(quán)值的個(gè)數(shù)為n，那么哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為_(kāi)_____．A.不確定B.2nC.2n+1D.2n-110.下列______是一個(gè)堆。A.19，75，34，26，97，56B.97，26，34，75，19，56C.19，56，26，97，34，75D.19，34，26，97，56，7511.一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足

。A.所有的結(jié)點(diǎn)均無(wú)左孩子B.所有的結(jié)點(diǎn)均無(wú)右孩子C.只有一個(gè)葉子結(jié)點(diǎn)D.是任意一棵二叉樹(shù)12.改寫(xiě)順序棧的結(jié)構(gòu)和進(jìn)棧函數(shù)Push(x)，要求當(dāng)棧滿時(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)

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

return0;

++(st.top);

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

st.data[st.top]=x;

return1;

}13.試問(wèn)中序序列及后序序列是否能唯一地建立二叉樹(shù)?若不能，則說(shuō)明理由；若能，則對(duì)中序序列[)BEAFGC和后序序列DEBGFCA構(gòu)造二叉樹(shù)。14.下列4組含C1～C7的結(jié)點(diǎn)序列中，______是下圖所示的有向圖的拓?fù)湫蛄小?/p>

A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C3，C615.若在一棵完全二叉樹(shù)中對(duì)所有結(jié)點(diǎn)按層次自上向下，同一層次自左向右進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為0，現(xiàn)有兩個(gè)不同的結(jié)點(diǎn)，它們的編號(hào)是p和q，那么判斷它們?cè)谕粚拥臈l件應(yīng)是______。

A．

B．

C．

D．p/2==q/216.已知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，9517.對(duì)AOE網(wǎng)絡(luò)中有關(guān)關(guān)鍵路徑的敘述中，正確的是______。A.從開(kāi)始頂點(diǎn)到完成頂點(diǎn)的具有最大長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最短時(shí)間B.從開(kāi)始頂點(diǎn)到完成頂點(diǎn)的具有最小長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最短時(shí)間C.從開(kāi)始頂點(diǎn)到完成頂點(diǎn)的具有最大長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最長(zhǎng)時(shí)間D.從開(kāi)始頂點(diǎn)到完成頂點(diǎn)的具有最小長(zhǎng)度的路徑，關(guān)鍵路徑長(zhǎng)度是完成整個(gè)工程所需的最長(zhǎng)時(shí)間18.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是

。A.9B.11C.15D.不確定19.若想在單鏈表中刪除某結(jié)點(diǎn)p(p既不是第一個(gè)，也不是最后一個(gè)結(jié)點(diǎn))的直接后繼，則應(yīng)執(zhí)行______操作。A.p→next=p→next→nextB.p=p→next;p→next=p→next→nextC.p→next=p→nextD.p=p→next→next20.無(wú)向圖的鄰接矩陣是一個(gè)______。A.對(duì)稱(chēng)矩陣B.零矩陣C.上三角矩陣D.對(duì)角矩陣21.設(shè)G是一個(gè)非連通無(wú)向圖，有15條邊，則該圖至少有______個(gè)頂點(diǎn)。A.5B.6C.7D.822.在n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中，線索的數(shù)目是______。A.n-1B.n+1C.2nD.2n-123.若某線性表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則下面最節(jié)省運(yùn)算時(shí)間的存儲(chǔ)方式是______。A.單鏈表B.帶有頭指針的單循環(huán)鏈表C.雙鏈表D.帶有尾指針的單循環(huán)鏈表24.下列二叉樹(shù)中，不平衡的二叉樹(shù)是

。

25.一組記錄的序列F={46，79，56，38，40，84}，則利用快速排序算法，以第一個(gè)記錄為基準(zhǔn)，得到的一次劃分結(jié)果為_(kāi)_____。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}26.一組記錄的關(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)27.用下列元素序列(22，8，62，35，48)構(gòu)造平衡二叉樹(shù)，當(dāng)插入______時(shí)，會(huì)出現(xiàn)不平衡的現(xiàn)象。A.22B.35C.48D.6228.已知深度為h的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)已存放于數(shù)組BT[1:2h一1]中，請(qǐng)寫(xiě)一非遞歸算法，產(chǎn)生該二叉樹(shù)的二叉鏈表結(jié)構(gòu)。設(shè)二叉鏈表中鏈結(jié)點(diǎn)的構(gòu)造為(lchild，data，rchild)，根結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的指針由T給出。29.若一個(gè)棧的輸入序列為1，2，3，…，n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是

。A.i-j-1B.i-jC.j-i+1D.不確定的30.試分別用順序表和單鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)將線性表(a0，a1，a2，……，an-1)就地逆置的操作，所謂“就地”，是指輔助空間應(yīng)為O(1)。31.用單鏈表存儲(chǔ)多項(xiàng)式的結(jié)構(gòu)定義如下：

TypedefstructTerm{

//多項(xiàng)式的項(xiàng)

floatcoef;

//系數(shù)

intexp;

//指數(shù)

structTerm*link;//鏈指針

}*Polynomial;

試編寫(xiě)一個(gè)算法，輸入一組多項(xiàng)式的系數(shù)和指數(shù)，按指數(shù)降冪的方式建立多項(xiàng)式鏈表，要求該鏈表具有表頭結(jié)點(diǎn)。如果輸入的指數(shù)與鏈表中已有的某一個(gè)項(xiàng)的指數(shù)相等，則新的項(xiàng)不加入，并報(bào)告作廢信息。整個(gè)輸入序列以輸入系數(shù)為0標(biāo)志結(jié)束。算法的首部為PolynomialcreatePoly()；32.設(shè)一棵二叉樹(shù)的前序序列為abdecf，后序序列為debfca，則該二叉樹(shù)中序遍歷的順序是______。A.adbecfB.dfecabC.dbeacfD.abcdef33.設(shè)T是哈夫曼二叉樹(shù)，具有5個(gè)葉結(jié)點(diǎn)，樹(shù)T的高度最高可以是______。A.3B.4C.5D.634.設(shè)一棵二叉樹(shù)的先序、中序遍歷序列分別為ABDFCEGH、BFDAGEHC

(1)畫(huà)出這棵二叉樹(shù)。

(2)畫(huà)出這棵二叉樹(shù)的后序線索樹(shù)。

(3)將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)(或森林)。35.對(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)/236.一個(gè)n×n的對(duì)稱(chēng)矩陣，如果以行或列為主序存入內(nèi)存，則其容量為多少?37.對(duì)于一個(gè)使用鄰接表存儲(chǔ)的有向圖G，可以利用深度優(yōu)先遍歷方法，對(duì)該圖中結(jié)點(diǎn)進(jìn)行拓?fù)渑判?。其基本思想是：在遍歷過(guò)程中，每訪問(wèn)一個(gè)頂點(diǎn)，就將其鄰接到的頂點(diǎn)的入度減1，并對(duì)其未訪問(wèn)的、入度為0的鄰接到的頂點(diǎn)進(jìn)行遞歸。

(1)給出完成上述功能的圖的鄰接表定義。

(2)定義在算法中使用的全局輔助數(shù)組。

(3)寫(xiě)出在遍歷圖的同時(shí)進(jìn)行拓?fù)渑判虻乃惴ā?8.若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為_(kāi)_____。A.(n-1)/2B.n/2C.(n+1)/2D.n39.已知二叉樹(shù)排序樹(shù)中某結(jié)點(diǎn)指針p，其雙親結(jié)點(diǎn)指針為fp，p為fp的左孩子。試編寫(xiě)算法，刪除p所指結(jié)點(diǎn)。40.已知一棵二叉樹(shù)的中序序列和后序序列如下：

中序：GLDHBEIACJFK

后序：LGHDIEBJKFCA

(1)給出這棵二叉樹(shù)；

(2)轉(zhuǎn)換為對(duì)應(yīng)的森林；

(3)畫(huà)出該森林的帶右鏈的先根次序表示法：

(4)畫(huà)出該森林帶度數(shù)的后根次序表示法；

(5)在帶度數(shù)的后根次序表示法中，不包含指針，但仍能完全反映樹(shù)的結(jié)構(gòu)。寫(xiě)出以結(jié)點(diǎn)x為根的子樹(shù)在后根次序序列中的前驅(qū)的求法。(用語(yǔ)言敘述，不用寫(xiě)算法)41.有5個(gè)元素，其入棧次序?yàn)锳，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧的次序不包括______。A.CDEBAB.CDBEAC.CDBAED.CDAEB42.已知一算術(shù)表達(dá)式的中綴形式為A+B+C-D/E，后綴形式為ABC*+DE/-，其前綴形式為_(kāi)_____。A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE43.不帶表頭結(jié)點(diǎn)的單鏈表first為空的判定條件是

，帶表頭結(jié)點(diǎn)的單鏈表first為空的判定條件是first→next==NULL;。A.first==NULL;B.first→next==NULL;C.first→next==first;D.first!=NULL;44.散列表的平均查找長(zhǎng)度______。A.與處理沖突的方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B.與處理沖突的方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突的方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突的方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)45.如果線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表46.為了增加內(nèi)存空間的利用率和減少溢出的可能性，通常采用兩個(gè)棧利用同一塊存儲(chǔ)空間的方法。通常兩個(gè)棧的棧底設(shè)在內(nèi)存空間的兩端，而棧頂相向，迎面增長(zhǎng)。已知有兩個(gè)棧s1、s2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[0～maxsize-1]。

設(shè)計(jì)共享存儲(chǔ)空間的兩個(gè)棧s1、s2的入棧和出棧算法。要求：

(1)給出算法的基本設(shè)計(jì)思想。

(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋?zhuān)?7.已知輸入序列為abed，經(jīng)過(guò)輸出受限的雙端隊(duì)列后，能得到的輸出序列是______。A.daebB.eadbC.dbeaD.以上答案都不對(duì)48.包含有4個(gè)結(jié)點(diǎn)的元素值互不相同的二叉排序樹(shù)有______種。A.4B.6C.10D.1449.有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存放在一維數(shù)組A[1..n]中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹(shù)，根由tree指向。(可不定義結(jié)構(gòu)體)50.以下是一個(gè)5×5階螺旋方陣。設(shè)計(jì)一個(gè)算法輸出該形式的n×n(n＜10)階方陣(順時(shí)針?lè)较蛐M(jìn))。

1

2

3

4

5

16

17

18

19

6

15

24

25

20

7

14

23

22

21

8

13

12

11

10

951.歸并排序中，歸并的趟數(shù)是______。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)52.判斷一個(gè)有向圖是否存在回路除了可利用拓?fù)渑判蚍椒ㄍ?，還可用利______。A.求關(guān)鍵路徑的方法B.求最短路徑的Dijkstra方法C.廣度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法53.在一個(gè)非空二叉樹(shù)的中序序列中，根結(jié)點(diǎn)的右邊______。A.只有右子樹(shù)上的所有結(jié)點(diǎn)B.只有右子樹(shù)上的部分結(jié)點(diǎn)C.只有左子樹(shù)上的部分結(jié)點(diǎn)D.只有左子樹(shù)上的所有結(jié)點(diǎn)54.已知一組遞增有序的關(guān)鍵字值存放在k[1，…，n]中，k[1]≤k[2]≤…≤k[n]，在相等搜索概率的情況下，若要生成一棵二叉排序樹(shù)，以哪個(gè)關(guān)鍵字值為根結(jié)點(diǎn)，按什么方式生成二叉排序樹(shù)平衡性最好且方法又簡(jiǎn)單?闡明算法思路，寫(xiě)出相應(yīng)的算法。如果數(shù)組k中元素為{7，12，13，15，21，33，38，41，49，55，58}，并畫(huà)出這棵二叉排序樹(shù)。55.已知下列各種初始狀態(tài)(長(zhǎng)度為n)元素，試問(wèn)當(dāng)利用直接插入法進(jìn)行排序時(shí)，至少需要進(jìn)行多少次比較(要求排序后的文件按關(guān)鍵字從大到小順序排列)?

(1)關(guān)鍵字自小到大有序(key1＜key2＜…＜keyn)；

(2)關(guān)鍵字自大到小逆序(key1＞key2＞…＞keyn)；

(3)奇數(shù)關(guān)鍵字順序有序，偶數(shù)關(guān)鍵字順序有序(key1＜key3)＜…，key2＜key4＜…)；

(4)前半部分元素按關(guān)鍵字順序有序，后半部分元素按關(guān)鍵字順序逆序(key1＜key2＜…＜keym，keym+1＞keym+2＞…＞keyn，m為中間位置)。56.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是______。A.10B.11C.16D.不確定57.試設(shè)計(jì)判斷兩棵二叉樹(shù)是否相似的算法。所謂二叉樹(shù)t1和t2相似是指t1和t2都是空的二叉樹(shù)；或者t1和t2的根結(jié)點(diǎn)是相似的，t1的左子樹(shù)和t2的左子樹(shù)是相似的且t1的右子樹(shù)與t2的右子樹(shù)是相似的。58.分析以下程序段的時(shí)間復(fù)雜度。

...

i=1;

while(i＜=n)

i=i*2;

...59.下面的敘述中正確的是______。

Ⅰ．線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比

Ⅱ．線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)

Ⅲ．線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比A.僅ⅠB.僅ⅡC.僅ⅢD.Ⅰ、Ⅱ、Ⅲ60.編寫(xiě)算法實(shí)現(xiàn)以被分類(lèi)序列中所有元素的平均值為界值的快速分類(lèi)方法。61.在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0＜i＜n+1)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)(

)個(gè)元素。A.n-iB.n-i+1C.n-i-1D.i62.一個(gè)二部圖的鄰接矩陣A是一個(gè)______類(lèi)型的矩陣。A.n×n矩陣B.分塊對(duì)稱(chēng)矩陣C.上三角矩陣D.下三角矩陣63.在有n個(gè)結(jié)點(diǎn)且為完全二叉樹(shù)的二叉排序樹(shù)中查找一個(gè)鍵值，其平均比較次數(shù)的數(shù)量級(jí)為_(kāi)_____。A.O(n)B.O(log2/n)C.O(nlog2n)D.O(n2)64.一棵高度為h的AVL樹(shù)，若其每個(gè)非葉結(jié)點(diǎn)的平衡因子都是0，則該樹(shù)共有______個(gè)結(jié)點(diǎn)。A.2h-1-1B.2h-1C.2h-1+1D.2h-165.某個(gè)待排序的序列是一個(gè)可變長(zhǎng)度的字符串序列，這些字符串一個(gè)接一個(gè)地存儲(chǔ)于唯一的字符數(shù)組中。請(qǐng)改寫(xiě)快速排序算法，對(duì)這個(gè)字符串序列進(jìn)行排序。66.下列4個(gè)序列中，哪一個(gè)是堆

。A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15，25，20，10D.75，45，65，10，25，30，20，1567.有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，已知葉結(jié)點(diǎn)個(gè)數(shù)為n0。

(1)寫(xiě)出求度為1的結(jié)點(diǎn)的個(gè)數(shù)的n1的計(jì)算公式。

(2)若此樹(shù)是深度為k的完全二叉樹(shù)，寫(xiě)出n為最小的公式。

(3)若二叉樹(shù)中僅有度為0和度為2的結(jié)點(diǎn)，寫(xiě)出求該二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)n的公式。68.依次讀入數(shù)據(jù)元素序列{a，b，C，d，e，f，g)進(jìn)棧，每進(jìn)一個(gè)元素，機(jī)器可要求下一個(gè)元素進(jìn)?；驈棗＃绱诉M(jìn)行，則棧空時(shí)彈出的元素構(gòu)成的序列是以下哪些序列?

A．{d，e，c，f，b，g，a}

B．{f，e，g，d，a，C，b}

C．{e，f，d，g，b，C，a}D．{c，d，e，b，f，a，g}69.假設(shè)圖采用鄰接表存儲(chǔ)，編寫(xiě)一個(gè)函數(shù)，利用深度優(yōu)先搜索算法，求出無(wú)向圖中通過(guò)給定點(diǎn)v的所有簡(jiǎn)單回路。70.由權(quán)值分別為3，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為

。A.24B.48C.72D.5371.假設(shè)稀疏矩陣只存放其非0元素的行號(hào)、列號(hào)和數(shù)值，以一維數(shù)組順次存放，行號(hào)-1作結(jié)束標(biāo)志。例如，如下所示的稀疏矩陣M，存放在一維數(shù)組D中，D的元素如下：D[0]=0，D[1]=0，D[2]=1，D[3]=0，D[4]=4，D[5]=10，D[6]=2，D[7]=8，D[8]=5，D[9]=-1。

現(xiàn)有兩個(gè)如上方法存儲(chǔ)的稀疏矩陣A和B，它們均為m行n列，分別存放在數(shù)組A和B中，編寫(xiě)求矩陣加法C=A+B的算法，C亦放在數(shù)組C中。72.在下列關(guān)于外排序過(guò)程輸入/輸出緩沖區(qū)作用的敘述中不正確的是______。A.暫存輸入/輸出的記錄B.內(nèi)部歸并的工作區(qū)C.產(chǎn)生初始?xì)w并段的工作區(qū)D.傳送用戶界面的消息73.給定整型數(shù)組B[0，…，M][0，…，N]。已知B中數(shù)據(jù)在每一維方向上都按從小到大的次序排列，且整型變量x在B中存在。設(shè)計(jì)一個(gè)程序段，找出一對(duì)滿足B[i][j]=x的i，j值，找到后輸出i和j的值，要求比較次數(shù)不超過(guò)M+N。74.有n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹(shù)的高度為_(kāi)_____。A.2n+1B.2n-1C.log22n+1D.log22n-175.用鄰接矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)vi和vj之間是否有長(zhǎng)度為m的路徑相連，則只要檢查_(kāi)_____的第i行第j列的元素是否為零即可。A.mAB.AC.AmD.Am-1第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：C第6趟的結(jié)果為(15，20，40，50，70，95，60，45，80)，此時(shí)插入60，要與95、70和50進(jìn)行比較，共比較3次，本題答案為C。2.參考答案：逆波蘭表達(dá)式(即后綴表達(dá)式)求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND，對(duì)表達(dá)式從左到右掃描(讀入)，當(dāng)表達(dá)式中掃描到數(shù)時(shí)，壓入OPND棧。當(dāng)掃描到運(yùn)算符時(shí)，從OPND退出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果再壓入OPND棧。這個(gè)過(guò)程一直進(jìn)行到讀出表達(dá)式結(jié)束符$，這時(shí)OPND棧中只有一個(gè)數(shù)，就是結(jié)果。

floatexpr(){

//從鍵盤(pán)輸入逆波蘭表達(dá)式，以'$'表示輸入結(jié)束，本算法求逆波蘭表達(dá)式的值

floatOPND[30];

//OPND是操作數(shù)棧

init(OPND);

//兩棧初始化

floatnum=0.0;

//數(shù)字初始化

scanf("%c",&x);

//x是字符型變量

while(x!='$'){

switch(x){

case'0':

case'1':

case'2':

case'3':

case'4':

case'5':

case'6':

case'7':

case'8':

case'9':

while((x＞='0'&&x＜='9')||x=='.')//拼數(shù)

if(x!='.'){num=num*10+(ord(x)-ord('0'));scanf("%c",&x);}//處理整數(shù)

else{

//處理小數(shù)部分

scale=10.0;scanf("%c",&x);

while(x＞='0'&&x＜='9'){

num=num+(ord(x)-ord('0'))/scale;

scale=scale*10;scanf("%c",&x);

}

}//else

push(OPND,num);num=0.0;

//數(shù)壓入棧，下個(gè)數(shù)初始化

case'':break;

//遇空格，繼續(xù)讀下一個(gè)字符

case'+':push(OPND,pop(OPND)+pop(OPND));break;

case'-':x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;

case'*':push(OPND,pop(OPND)*pop(OPND));break;

case'/':x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;

default;

//其他符號(hào)不作處理

}//結(jié)束switch

scanf("%c",&x);

//讀入表達(dá)式中下一個(gè)字符

}//結(jié)束while(x!='$')

printf("后綴表達(dá)式的值為%f");pop(OPND);

}假設(shè)輸入的后綴表達(dá)式是正確的，未作錯(cuò)誤檢查。算法中拼數(shù)部分是核心。若遇到大于等于'0'且小于等于'9'的字符，認(rèn)為是數(shù)。這種字符的序號(hào)減去字符'0'的序號(hào)得出數(shù)。對(duì)于整數(shù)，每讀入一個(gè)數(shù)字字符，前面得到的部分?jǐn)?shù)要乘上10再加新讀入的數(shù)得到新的部分?jǐn)?shù)。當(dāng)讀到小數(shù)點(diǎn)時(shí)，認(rèn)為數(shù)的整數(shù)部分已完，要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10(或10的冪數(shù))變成十分位、百分位、千分位數(shù)等，與前面部分?jǐn)?shù)相加。在拼數(shù)過(guò)程中，若遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量nun恢復(fù)為0，準(zhǔn)備下一個(gè)數(shù)。這時(shí)對(duì)新讀入的字符進(jìn)入'+'、'-'、'*'、'/'及空格的判斷，因此在結(jié)束處理數(shù)字字符的case后，不能加入break語(yǔ)句。3.參考答案：C[解析]同義詞子表所鏈接的各個(gè)表項(xiàng)的關(guān)鍵字互為同義詞，意味著雖然這些關(guān)鍵字的值不同，但用同一個(gè)散列函數(shù)計(jì)算出的散列地址相同。4.參考答案：C此題考查的知識(shí)點(diǎn)是堆排序。應(yīng)選C。5.參考答案：C兩個(gè)棧共享一個(gè)內(nèi)存空間時(shí)，需要把兩個(gè)棧的棧底設(shè)在內(nèi)存空間的兩端。6.參考答案：C[解析]按照循環(huán)隊(duì)列的定義，因?yàn)樵匾苿?dòng)按照rear=(rear+1)MODm進(jìn)行，則當(dāng)數(shù)字Q[m-1]存放了元素之后，下一個(gè)入隊(duì)的元素將存放到Q[0]中，因此隊(duì)列的首元素的實(shí)際位置是(rear-length+1+m)MODm。7.參考答案：本算法是從A和B的最后兩個(gè)元素開(kāi)始比較，若相等，將其值放入C的第一個(gè)元素中，如此直到A和B中的所有元素比較完畢。實(shí)現(xiàn)本題功能的程序代碼如下：

intintersect(intA[],intna,intB[],intnb,intC[])

{

inti=na,j=nb,k=0;

while(i＞=0&&j＞=0)

if(A[i-1]＞B[j-1])

--i;

elseif(A[i-1]＜B[j-1])

--j;

else//A[i-1]=B[j-1]

{

C[k++]=A[i-1];

--i;

--j;

}

returnk-1;

}

本算法intersect(A，na，B，nb，C)的時(shí)間復(fù)雜度為O(na+nb)，其中na和nb分別為A和B的長(zhǎng)度。8.參考答案：本題非遞歸算法容易實(shí)現(xiàn)，在《數(shù)據(jù)結(jié)構(gòu)高分筆記》一書(shū)中已經(jīng)講過(guò)，核心算法即為序列的劃分，然后遞歸處理劃分好的子序列。非遞歸算法需要自己申請(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;

}

}

}9.參考答案：D哈夫曼樹(shù)中只有度為0和度為2的結(jié)點(diǎn)，即N=n0+n2，而根據(jù)二叉樹(shù)的性質(zhì)：n0=n2+1，可知n0=n，那么n2=n-1，N=n+n-1=2n-1。10.參考答案：D完全二叉樹(shù)中所有非終端結(jié)點(diǎn)的值均不大于(或不小于)其左、右孩子結(jié)點(diǎn)的值，則此序列可稱(chēng)為堆。據(jù)此，可畫(huà)出二叉樹(shù)，如下圖所示：

得出答案為D。11.參考答案：C前序序列是“根左右”，后序序列是“左右根”，若要這兩個(gè)序列相反，只有單支樹(shù)，所以本題的A和B均對(duì)，單支樹(shù)的特點(diǎn)是只有一個(gè)葉子結(jié)點(diǎn)，故C是最合適的，選C。12.參考答案：原順序棧的結(jié)構(gòu)體中是用靜態(tài)數(shù)組來(lái)存放數(shù)據(jù)，現(xiàn)在題目需要?jiǎng)討B(tài)創(chuàng)建數(shù)組，因此需要把靜態(tài)數(shù)組改掉，代碼如下：

typedefstruct

{

int*data;

//指向動(dòng)態(tài)數(shù)組的指針

inttop;

//棧頂指針

intmaxSize;

//因data數(shù)組是動(dòng)態(tài)變化的，所以將maxSize改為變量

}SqStack;

修改后的Push()函數(shù)代碼如下：

intPush(SqStack&st,intx)

{

if(st.top==st.maxSize-1)//棧滿執(zhí)行stackFull()

{

if(stackFull(st)==0)

//棧滿，且stackFull()函數(shù)失敗，返回0

return0;

//否則只執(zhí)行stackFull()

}

++(st.top);

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

st.data[st.top]=x;

return1;

}

stackFull()函數(shù)代碼如下：

intStackFull(SqStack&st)

{

int*temp=(int*)malloc(2*st.maxSize*sizeof(int));

//申請(qǐng)一個(gè)動(dòng)態(tài)數(shù)組空間長(zhǎng)度為2倍的maxSize，由temp指向其首地址

if(temp==NULL)

return0;

//空間申請(qǐng)失敗，返回0

for(inti=0;i＜=st.top;++i)

temp[i]=st.data[i];

//復(fù)制原棧中元素到新空間的前一半地址

free(st.data);

//釋放原棧元素空間

st.data=temp;

//用data指針指向新空問(wèn)首地址

return1;

//成功，返回1

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

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

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

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

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

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

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

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

14.參考答案：D考查拓?fù)渑判虻乃惴ā?/p>

以1開(kāi)頭的拓?fù)渑判蜻^(guò)程，如下圖所示：

以5開(kāi)頭的拓?fù)渑判蜻^(guò)程，答案中的過(guò)程如下圖所示：

15.參考答案：A[解析]由結(jié)點(diǎn)層號(hào)計(jì)算公式可得編號(hào)為i(假設(shè)結(jié)點(diǎn)編號(hào)從0開(kāi)始)的結(jié)點(diǎn)所在層號(hào)為+1。當(dāng)兩個(gè)結(jié)點(diǎn)位于同一層時(shí)，有，即。注意，如果結(jié)點(diǎn)編號(hào)從1開(kāi)始，則。16.參考答案：B冒泡排序每趟經(jīng)過(guò)比較、交換，從無(wú)序區(qū)中產(chǎn)生一個(gè)最大的元素，所以選B。17.參考答案：A本題考查關(guān)鍵路徑的定義。

關(guān)鍵路徑：從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度(路徑上各活動(dòng)持續(xù)時(shí)間之和)。

關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱(chēng)為關(guān)鍵活動(dòng)。18.參考答案：B對(duì)任何一棵二叉樹(shù)，如果終端結(jié)點(diǎn)數(shù)為n。，度為2的結(jié)點(diǎn)數(shù)為n2，則一定有n0=n2+1。所以n0=10+1=11，而與n1無(wú)關(guān)。19.參考答案：A[解析]因?yàn)閜既不是第一個(gè)，也不是最后一個(gè)結(jié)點(diǎn)，所以p的直接后繼存在。若想刪除結(jié)點(diǎn)p的直接后繼，只需要讓p的后繼的后繼成為p的后繼，即p→next=p→next→next。20.參考答案：A[解析]無(wú)向圖的鄰接矩陣是一個(gè)對(duì)稱(chēng)矩陣。對(duì)于同一條邊(vi，vj)，它是雙向的，所以在矩陣的第i行、第j列以及第j行、第i列都為1。21.參考答案：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)。22.參考答案：B[解析]線索二叉樹(shù)中共有2n個(gè)指針，子女指針有n-1個(gè)，其余的n+1個(gè)指針為線索。23.參考答案：D在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、帶有頭指針的單循環(huán)鏈表、雙鏈表都不合適。考慮在帶有尾指針的單循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)間性能是O(1)，所以答案是D。24.參考答案：C平衡二叉樹(shù)的特點(diǎn)為：左、右子樹(shù)深度之差的絕對(duì)值不大于1。25.參考答案：C[解析]根據(jù)快速排序算法，以46為基準(zhǔn)，其過(guò)程是將40放在第一個(gè)元素的位首，79放在40的位置，故選C。26.參考答案：C快速排序是對(duì)冒泡排序的一種改進(jìn)，其基本思想是：通過(guò)一趟排序?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)，在安置的過(guò)程中，L.r[1]的確切位置將被最終確定。設(shè)該支點(diǎn)(pivot)最后確定的位置為i，則將序列分割為左右兩部分。這個(gè)過(guò)程稱(chēng)為一趟快速排序。

設(shè)待排序序列用數(shù)組e[low..high]保存。設(shè)置兩個(gè)指針low和high，分別指向數(shù)組的開(kāi)始位置和終止位置。設(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)

過(guò)程如下：

初始狀態(tài)：

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

接著low開(kāi)始向右移動(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——)，沒(méi)有找到比t(49)還小的數(shù)，但是由于出現(xiàn)了high==low的情況，結(jié)束左移。如下：

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

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

{27，38，13}

49

{76，97，65，[49]}

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

{13)27{38}

49

{49，

65}

76

{97}

49

{65}

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

說(shuō)明：在一趟排序中，支點(diǎn)最后才確定位置，故只需最后一步賦值即可，中間不必交換。即，雖然快速排序是交換排序的一種，但是可以不用交換操作即可實(shí)現(xiàn)。該算法由于有不相鄰元素交換，故是不穩(wěn)定排序，其時(shí)間復(fù)雜度為O(nlogn2)，是內(nèi)排序中最好的方法之一。27.參考答案：C由題中所給的結(jié)點(diǎn)序列構(gòu)造二叉排序樹(shù)的過(guò)程如下圖：

當(dāng)插入48后，首次出現(xiàn)不平衡子樹(shù)，虛線框內(nèi)即為最小不平衡子樹(shù)。28.參考答案：[解析]二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)(一維數(shù)組)是按完全二叉樹(shù)的形狀存儲(chǔ)的，不按完全二叉樹(shù)的二叉樹(shù)順序存儲(chǔ)時(shí)，要加“虛結(jié)點(diǎn)”。數(shù)組中的第一個(gè)元素是根結(jié)點(diǎn)。本題中采用隊(duì)列結(jié)構(gòu)。本題中的虛結(jié)點(diǎn)用‘#’表示。

typedefstruct

BiTreebt；

∥二叉樹(shù)結(jié)點(diǎn)指針

intnum；

∥num是結(jié)點(diǎn)在一維數(shù)組中的編號(hào)

}tnode

tnode

Q[maxsize]；

∥循環(huán)隊(duì)列，容量足夠大

voidcreat(BiTreeT，ElemTypeBT[])

∥深度h的二叉樹(shù)存儲(chǔ)于一維數(shù)組BT[1:2h-1]中，本算法生成該二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)

{

tnodetq；

∥tq是隊(duì)列元素

intlen=2h-1；

∥數(shù)組長(zhǎng)度

T=(BiTree)malloc(sizeof(BiNode))；

∥申請(qǐng)結(jié)點(diǎn)

T->data=BT[1]；

∥根結(jié)點(diǎn)數(shù)據(jù)

tq.bt=T；

tq.num=1；

Q[1]=tq；

∥根入隊(duì)列

front=0：

rear=1；

∥循環(huán)隊(duì)列頭、尾指針

while(front!=rear)∥當(dāng)隊(duì)列不空時(shí)循環(huán)

{

front=(front+1)%maxsize；

tq=Q[front]；

p=tq.bt；

i=tq.num；∥出隊(duì)，取出結(jié)點(diǎn)及編號(hào)

if(BT[2*i]==‘#’‖2*i＞len)

p—＞lchild=null；

∥左子樹(shù)為空，‘#’表示虛結(jié)點(diǎn)

else∥建立左孩子結(jié)點(diǎn)并入隊(duì)列

{

p—＞lchild=(BiTree)malloc(sizeof(BiNode))；

∥申請(qǐng)結(jié)點(diǎn)空間

p—＞lchild——＞data=BT[2*i]；

∥左孩子數(shù)據(jù)

tq.bt=p—＞lchild；tq.num=2*i；rear=(rear+1)%maxsize；

∥計(jì)算

隊(duì)尾位置

Q[rear]=tq；∥左孩子結(jié)點(diǎn)及其編號(hào)入隊(duì)

}

if(BT[2*i+1]==‘#’‖2*i+l>len)

p—＞rchild=null；

∥右子樹(shù)為空

else∥建立右孩子結(jié)點(diǎn)并入隊(duì)列

{

p—＞rchild—(BiTree)malloc(sizeof(BiNode)；

∥申請(qǐng)結(jié)點(diǎn)空間

p—＞rchild—＞data=BT[2*i+1]；

tq.bt=p—＞rchild；

tq.num=2*i+1；

rear=(rear+1)%maxsize；

Q[rear]=tq；

∥計(jì)算隊(duì)尾位置，右孩子及其編號(hào)入隊(duì)

}

}

}29.參考答案：D不知道i，j的大小關(guān)系，所以無(wú)法確定。30.參考答案：

方法一：用順序表作存儲(chǔ)結(jié)構(gòu)

structSqList/{

ElemType*elem；∥存儲(chǔ)空間基址

intlength；∥當(dāng)前長(zhǎng)度

}；

voidInvertSqList(SqList＆L)

{

inti；ElemTypetemp；

for(i—0；i＜L．length/2；i++)

{

temp=L．elem；

L．elem=L．elem[L．1ength—i—1]；

L.elem[L.length—i—1]—temp；

}}

方法二：用順序表作存儲(chǔ)結(jié)構(gòu)

voidInvertSqList(SqList&L)6R{

inti，j；ElemTypetemp；

i=0；j=L．length—1；

while(i＜j)

{

temp=L．elem；

L．elem=L.elem[j]

L.elem[j]=temp

i++；j——；

}}

方法三：用帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)

structLNode{

ElemTypedata；

LNode*next：

}；

typedefLNode*LinkList；

VoidInvertLinkList(LinkList&L)

{

p—L；L—NULL；

while(p){

s—p；p—p—＞next；

S—＞next—L：

}}31.參考答案：本題程序使用了一些C++的常用語(yǔ)句，如：“＜＜”輸出符，“＞＞”輸入符，“cout”輸出到屏幕，“cin”從鍵盤(pán)輸入，“endl”換行格式符，“new”動(dòng)態(tài)存儲(chǔ)分配。

PolynomialcreatePoly(){

structpnode*head,*p,*pre,*s;

floatc;inte,i=0;

cout＜＜”建立一個(gè)多項(xiàng)式的單鏈表”＜＜endl;

//提示

head=newTerm;

//創(chuàng)建表頭結(jié)點(diǎn)和表頭指針

head-＞exp=-1;head-＞link=NULL;

//表頭結(jié)點(diǎn)的exp標(biāo)志為-1

while(1){

//創(chuàng)建結(jié)點(diǎn)

cout＜＜”輸入第”＜＜++i＜＜”個(gè)項(xiàng):”;

//提示:輸入第i個(gè)項(xiàng)

cin＞＞c＞＞e;

//輸入:c系數(shù),e指數(shù)

cout＜＜endl;

if(c==0)break;

//輸入系數(shù)為0,退出

S=newTerm;s-＞coef:c;s-＞exp=e;

//創(chuàng)建結(jié)點(diǎn)

p=head;pre=NULL;

//尋找按升冪插入的位置

while(p!=NULL&&P-＞exp＞e){pre=p;p=p-＞link;}

if(p!=NULL&&p-＞exp==e)

//指數(shù)與鏈中某項(xiàng)指數(shù)相等

cout＜＜”輸入項(xiàng)的指數(shù)重復(fù),此次輸入作廢!”＜＜endl;

else{s-＞link=p;pre-＞link=s;}

//按升冪插入

}

returnhead;

}32.參考答案：C[解析]由二叉樹(shù)的前序遍歷序列和后序遍歷序列不能唯一地確定這棵二叉樹(shù)。但是利用二叉樹(shù)前序遍歷序列的第一個(gè)結(jié)點(diǎn)和后序遍歷序列的最后一個(gè)結(jié)點(diǎn)為二叉樹(shù)的根結(jié)點(diǎn)的特性，可以確定一棵二叉樹(shù)，它的中序遍歷序列為dbeacf。33.參考答案：C[解析]哈夫曼二叉樹(shù)是只有度為2和度為0的結(jié)點(diǎn)的二叉樹(shù)，有n個(gè)葉結(jié)點(diǎn)，就有n-1個(gè)非葉結(jié)點(diǎn)，其最大高度是n，即從第1層起到次底層止，每層有一個(gè)非葉結(jié)點(diǎn)，最底層有兩個(gè)葉結(jié)點(diǎn)。例如，下圖所示的哈夫曼樹(shù)，n=5，葉結(jié)點(diǎn)的權(quán)值為{12，22，32，42，52}，該哈夫曼樹(shù)的高度是5，所以具有5個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)的高度最高可以是5。

34.參考答案：

35.參考答案：D由完全圖的定義可知本題答案為D。36.參考答案：n(n+1)/2(壓縮存儲(chǔ))或n2(不采用壓縮存儲(chǔ))。此問(wèn)題考查的知識(shí)點(diǎn)是數(shù)組的存放問(wèn)題。對(duì)稱(chēng)矩陣可以只存上三角或下三角。所用空間為1，2，3，…，n之和。37.參考答案：(1)鄰接表定義：

typedefstructArcNode{

intadjvex;

struetArcNode*next;

}ArcNode;

typedefstructVNode{

vertypedata;

ArcNode*firstarc;

}VNode,AdjList[MAX];

(2)全局?jǐn)?shù)組定義：

intvisited[]=0;finished[]=0;flag=1;

//flag測(cè)試拓?fù)渑判蚴欠癯晒?/p>

ArcNode*final=null;

//final是指向頂點(diǎn)鏈表的指針，初始化為0

(3)算法

voiddfs(AdjListg,vertypev){

//以頂點(diǎn)v開(kāi)始深度優(yōu)先遍歷有向圖g，頂點(diǎn)信息就是頂點(diǎn)編號(hào)

ArcNode*t;

//指向邊結(jié)點(diǎn)的臨時(shí)變量

printf("%d",v);

visited[v]=1;

p=g[v].firstarc;

while(p!=null){

j=p-＞adjvex;

if(visited[j]==1&&finished[j]==0)flag=0;

//dfs結(jié)束前出現(xiàn)回邊

elseif(visited[j]==0){dfs(g,j);finished[j]=1;}

p=p-＞next;

}//while

t=(ArcNode*)malloc(sizeof(ArcNode));

//申請(qǐng)邊結(jié)點(diǎn)

t-＞adjvex=v;t-＞next=final;final=t;

//將該頂點(diǎn)插入鏈表

}//dfs結(jié)束_

intdfs_Topsort(ndjlistg){

//對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖進(jìn)行拓?fù)渑判?，拓?fù)涑晒Ψ祷?，否則返回0

i=1;

while(flag&&i＜=n)

if(visited.[i]==0){dfs(g,i);finished[i]=1;}//if

return(flag);

}此題考查的知識(shí)點(diǎn)是圖的遍歷。對(duì)有向圖進(jìn)行深度優(yōu)先遍歷可以判定圖中是否有回路。若從有向圖某個(gè)頂點(diǎn)v出發(fā)遍歷，在dfs(v)結(jié)束之前，出現(xiàn)從頂點(diǎn)u到頂點(diǎn)v的回邊，圖中必存在環(huán)。由于dfs產(chǎn)生的是逆拓?fù)渑判颍试O(shè)一類(lèi)型是指向鄰接表的邊結(jié)點(diǎn)的全局指針變量final，在dfs函數(shù)退出時(shí)，把頂點(diǎn)v插入到final所指的鏈表中，鏈表中的結(jié)點(diǎn)就是一個(gè)正常的拓?fù)湫蛄小?8.參考答案：C[解析]此結(jié)論需要考生當(dāng)作定理一樣的牢記。39.參考答案：本題用被刪結(jié)點(diǎn)右子樹(shù)中最小值(中序遍歷第一個(gè))結(jié)點(diǎn)代替被刪結(jié)點(diǎn)。

voidDelete(BSTreebst,p,fp){

//在二叉排序樹(shù)bst上，刪除fp所指結(jié)點(diǎn)的左子女(由p所指向)

if(!p-＞lchild){fp-＞lchild=p-＞rchild;flee(p);}

//p無(wú)左子女

elseif(!p-＞rchild){fp-＞lchild=p-＞lchild;free(p);}

//p無(wú)右子女

else

//p有左子女和右子女

{q=p-＞rchild;s=q;

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

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

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

if(s==p-＞rchild)

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

{p-＞data=s-＞data;p-＞rchild=s-＞rchild;frees);}

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

}

}40.參考答案：

41.參考答案：D以元素C，D最先出棧的次序有三個(gè)：CDEBA、CDBEA、CDBAE。42.參考答案：D根據(jù)題目給出的中綴和后綴表達(dá)式可以得到其算術(shù)表達(dá)式為：(A+B*C)-D/E，前綴表達(dá)式：-+A*BC/DE。43.參考答案：A[解析]對(duì)于不帶頭結(jié)點(diǎn)的單鏈表，first指向開(kāi)始結(jié)點(diǎn)(第一個(gè)結(jié)點(diǎn))，鏈表為空則first為空。對(duì)于帶有頭結(jié)點(diǎn)的單鏈表，first指向表頭結(jié)點(diǎn)，鏈表為空則表頭結(jié)點(diǎn)后面沒(méi)有結(jié)點(diǎn)，即指針first→next為空。44.參考答案：A[解析]散列表的平均查找長(zhǎng)度與處理沖突的方法有關(guān)，與裝填因子a有關(guān)，與表的長(zhǎng)度無(wú)關(guān)。45.參考答案：D最常用的操作是最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用尾指針的單循環(huán)鏈表。46.參考答案：(1)棧s1、s2共享向量空間，將兩棧棧底設(shè)在向量?jī)啥?。初始時(shí)，s1棧項(xiàng)指針為-1，s2棧頂為maxsize。兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向，迎面增長(zhǎng)，棧頂指針指向棧頂元素。

(2)算法設(shè)計(jì)如下：

#definemaxsize

//兩棧共享順序存儲(chǔ)空間所能達(dá)到的最多元素?cái)?shù)

#defineelemtpint

//假設(shè)元素類(lèi)型為整型

typedefstnlct{

elemtpstack[maxsize];

//棧空間

inttop[2];

//top為兩個(gè)棧項(xiàng)指針

}stk;

stks;

//s是如上定義的結(jié)構(gòu)類(lèi)型變量，為全局變量

①入棧操作：

intpush(inti,intx){

//入棧操作。i為棧號(hào)，i=0表示左邊的棧s1，i=1表示右

//邊的棧s2，x是入棧元素。入棧成功返回1，否則返回0

if(i＜0||i＞1){

printf("棧號(hào)輸入不對(duì)");exit(0);}

if(s.top[1]-s.top[0]==1){printf("棧已滿\n");return(0);}

switch(i){

case0:s.stack[++s.top[0]]=x;return1;break;

case1:s.stack[--s.top[1]]=x;return1;

}

}

②退棧操作：

elemtppop(inti){

if(i＜0||i＞1){printf("棧號(hào)輸入錯(cuò)誤\n");exit(0);}

switch(i){

case0:if(s.top[0]==-1){printf("?？誠(chéng)n");return-1;}

elsereturns.stack[s.top[0]--];

case1:if(s.top[1]==maxsize){printf("?？誠(chéng)n");return-1;}

elsereturns.stack[s.top[1]++];

}

}47.參考答案：B輸出受限的雙端隊(duì)列是指刪除限制在一端進(jìn)行，而插入允許在兩端進(jìn)行的隊(duì)列。

分析選項(xiàng)A，輸入序列為abed，輸出序列為dacb，由輸出受限性質(zhì)可知以da開(kāi)頭的結(jié)果只有dabc，選項(xiàng)A為錯(cuò)誤答案。

分析選項(xiàng)B，輸入序列為abed，輸出序列為cadb，其輸入輸出順序?yàn)椋合仍谳敵龆溯斎隺，然后在非輸出端輸入b，這時(shí)隊(duì)列中的序列為ba。再在輸出端輸入c，這時(shí)隊(duì)列中的序列為bac；輸出c，再輸出a；再在輸出端輸入d，這時(shí)隊(duì)列中的序列為bd；輸出d，再輸出b。最后得到輸出序列為cadb。

分析選項(xiàng)C，輸入序列為abed，輸出序列為dbca，由輸出受限性質(zhì)可知以db開(kāi)頭的結(jié)果只有dbac，選項(xiàng)C為錯(cuò)誤答案。48.參考答案：D[解析]含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)，其中序遍歷序列都是一樣的，前序遍歷序列不同則對(duì)應(yīng)了不同形狀的二叉排序樹(shù)，不同形態(tài)的個(gè)數(shù)可以用catalan函數(shù)計(jì)算：

catalan函數(shù)為(n為結(jié)點(diǎn)數(shù))。

當(dāng)n=4時(shí)，有。49.參考答案：BiTreeCreat(ElemTypeA[],inti){

//n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存于一維數(shù)組A中，本算法

//據(jù)此建立以二叉鏈表表示的完全二叉樹(shù)

BiTreetree;

if(i＜=n){

tree=(BiTree)malloc(sizeof(BiNode));tree-＞data=A[i];

if(2*i＞n)tree-＞lchild=null;

elsetree-＞lchild=Creat(A,2*i);

if(2*i+1＞n)tree-＞rchild=null;

elsetree-＞rchild=Creat(A,2*i+1);

}

return(tree);

}//Creat初始調(diào)用時(shí)i=1。50.參考答案：本題代碼實(shí)現(xiàn)如下：

voidfun(inta[MaxLen][MaxLen],intn)//MaxLen是已經(jīng)定義的常量

{

inti,j,k=0,m;

if(n%2==0)//m=□n/2□

m=n/2;

else

m=n/2+1;

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

{

for(j=i;j＜n-i;++j)

{

++k;

a[i][j]=k;

}

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

{

++k;

a[j][n-i-1]=k;

}

for(j=n-i-2;j＞=i;--j)

{

++k;

a[n-i-1][j]=k;

}

for(j=n-i-2;j＞=i+1;--j)

{

++k;

a[j][i]=k;

}

}

}51.參考答案：B此題考查的知識(shí)點(diǎn)是歸并排序。第l遍歸并的子序列長(zhǎng)度為20，第2遍為21，…，第i遍為2i-1，所以由2i-1≥n知，對(duì)n個(gè)記錄的數(shù)據(jù)集合，總共需要?dú)w并log2n次。應(yīng)選B。52.參考答案：D[解析]判斷一個(gè)有向圖是否存在回路，可用的方法如下：

1)利用拓?fù)渑判蛩惴梢耘卸▓D中是否存在回路，即在拓?fù)渑判蛩惴ńY(jié)束后如果還有頂點(diǎn)沒(méi)有輸出，則說(shuō)明剩下這些結(jié)點(diǎn)都還有前驅(qū)，它們構(gòu)成一個(gè)有向回路。

2)設(shè)有向圖具有n個(gè)頂點(diǎn)，若圖的邊數(shù)e≥n，則該圖一定有一個(gè)閉合的環(huán)。

3)設(shè)圖是具有n個(gè)頂點(diǎn)的有向圖，若該圖的每個(gè)頂點(diǎn)的出度至少為1，入度也至少為1，則圖中一定有回路存在。

4)利用深度優(yōu)先遍歷算法可以判定一個(gè)有向圖中是否存在有向回路。如果從有向圖上的某個(gè)頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷，若在算法結(jié)束之前出現(xiàn)一條從頂點(diǎn)u到頂點(diǎn)v的回邊，因u在生成樹(shù)上是v的子孫，則有向圖必定存在包含頂點(diǎn)v和頂點(diǎn)u的環(huán)。53.參考答案：A[解析]由二叉樹(shù)的中序遍歷規(guī)則可以知道，在中序遍歷序列中，根結(jié)點(diǎn)右邊只含有右子樹(shù)上的結(jié)點(diǎn)。54.參考答案：(1)以居中的關(guān)鍵字值為根結(jié)點(diǎn)，按折半查找判定樹(shù)的生成方法構(gòu)造二叉排序樹(shù)，既有好的平衡性又簡(jiǎn)單。算法代碼如下：

voidCreate_BestBST(BTNode*&t,intlow,inthigh,intk[])

{

//low和high初始值分別為關(guān)鍵字值序列的下界和上界，t是創(chuàng)建

//子樹(shù)的根。由于新根要回填給實(shí)參，所以它是引用型指針參數(shù)

if(low＞high)

t=NULL;

else

{

intmid=(low+high)/2;

t=(BTNode*)malloc(sizeof(BTNode));

t→data=k[mid];

Create_BestBST(t→lchild,low,mid-1,k);

Create_BestBST(t→rchild,mid+1,high,k);

}

}

這是一個(gè)遞歸算法，通過(guò)引用型參數(shù)t把新創(chuàng)建起來(lái)的子樹(shù)根結(jié)點(diǎn)自動(dòng)鏈接到父結(jié)點(diǎn)的某個(gè)子指針。

(2)根據(jù)上述算法得如下圖所示的二叉排序樹(shù)。

55.參考答案：本題主要考查直接插入法的算法思想及性能分析。

根據(jù)題目所給出的條件，最好情況下的比較次數(shù)即為最少比較次數(shù)。

(1)在關(guān)鍵字自小到大有序的情況下，插入第i個(gè)(2≤i≤n)元素的比較次數(shù)為1，因此，總的比較次數(shù)為1+1+1+…+1=n-1。

(2)在關(guān)鍵字自大到小有序的情況下，插入第i個(gè)(2≤i≤n)元素的比較次數(shù)為i，因此，總的比較次數(shù)為2+3+4+…+n=[n(n+1)/2]-1=(n-1)(n+2)/2。

(3)在奇數(shù)關(guān)鍵字順序有序和偶數(shù)關(guān)鍵字順序有序的情況下，比較次數(shù)最少的情況是所有記錄關(guān)鍵字均按升序排列，這時(shí)，總的比較次數(shù)為n-1。

(4)在前半部分元素按關(guān)鍵字有序，后半部分按關(guān)鍵字逆序的情況下，后半部分元素的關(guān)鍵字均大于前半部分元素的關(guān)鍵字時(shí)比較次數(shù)最少，此時(shí)前半部分的比較次數(shù)為m-1，后半部分的比較次數(shù)為(n-m-1)(n-m+2)/2，因此，總的比較次數(shù)為m-1+(n-m-1)(n-m+2)/2=(n-2)(n+8)/8(假設(shè)n為偶數(shù)，m=n/2)。56.參考答案：B根據(jù)二叉樹(shù)的性質(zhì)可知，度為0的結(jié)點(diǎn)個(gè)數(shù)比度為2結(jié)點(diǎn)個(gè)數(shù)多一個(gè)，即n0=n2+1。57.參考答案：本題的遞歸模型如下：

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

intlike(BTNode*t1,BTNode*t2)

{

intlike1,like2;

if(t1==NULL&&t2==NULL)

return1;

elseif(t1==NULL||t2==NULL)

return0;

else

{

like1=like(t1→left,t2→left);

like2=like(t1→right,t2→right);

return(like1&&like2);

}

}58.參考答案：此處循環(huán)體里面是i=i*2，即每循環(huán)一次，i值增加一倍，所以執(zhí)行次數(shù)與n之間是以2為底的對(duì)數(shù)關(guān)系，故時(shí)間復(fù)雜度為O(log2n)。59.參考答案：A在線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，查找第i個(gè)元素的時(shí)間與i的位置成正比。而在順序存儲(chǔ)結(jié)構(gòu)中查找第i個(gè)元素的時(shí)間與i的位置無(wú)關(guān)。60.參考答案：取平均值，將所有關(guān)鍵字與平均值進(jìn)行比較，若小于平均值則屬于左半部；否則就屬于右半部。

intPartition(RecTyper[]，intl，h)

{

inti=l，j=h，avg=0；

for(；i＜=h；i++)

avg+=R[i].key；

i=l：

avg=avg/(h-1+1)；∥求得平均值

while(i＜j)

while(i＜j&&R[j]．key＞=avg)∥大于平均值

j——；

if(i＜j)

R[i]=R[j]；

while(i＜j&&R[i]．key＜=avg)∥小于平均值

i++：

if(i＜j)

R[j]=R[i]；

}

if(R[i]．key＜===avg)

return

i；

else

returni-1；

}

voidquicksort(RecTypeR[]，intS，T)；

{

if(S＜T)

{

k=partition(R，S，T)；

quicksort(R，S，k)；

quicksort(R，k+1，T)；

}

}61.參考答案：B一般情況下，在順序表的第i(1＜=i＜=n)個(gè)元素之前插入一個(gè)元素，需要將第n至i的元素(共n-i+1個(gè)元素)向后移動(dòng)一個(gè)位置。所以答案為B。62.參考答案：B此題考查的知識(shí)點(diǎn)是二部圖的定義與存儲(chǔ)。二部圖定義為：若能將無(wú)向圖G=＜V，E＞的頂點(diǎn)集V劃分成兩個(gè)子集V1和V2(V1∩V2)=使得G中任何一條邊的兩個(gè)端點(diǎn)一個(gè)屬于V1，另一個(gè)屬于V2，則稱(chēng)G為二部圖。由于其特點(diǎn)，其存儲(chǔ)矩陣必為分塊對(duì)稱(chēng)的，所以選B。63.參考答案：B有n個(gè)結(jié)點(diǎn)且為完全二叉樹(shù)的二叉排序樹(shù)的高度為log2n。64.參考答案：D[解析]當(dāng)一棵AVL樹(shù)中的所有非葉結(jié)點(diǎn)的平衡因子都是0的時(shí)候，說(shuō)明它每個(gè)非葉子結(jié)點(diǎn)的左、右子樹(shù)都是一樣高，則整棵樹(shù)是一棵滿二叉樹(shù)。高度為h的滿二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)等于2h-1。65.參考答案：intPartition(RecTypeR[],intn,inth){

//一趟快速排序算法，樞軸記錄到位，并返回其所在位置

inti=n,j=h,R[0]=R[i],x=R[i].key;

while(i＜j){

while(i＜j&&R[j].key＞=x)j--;

if(i＜j)R[i]=R[j];

while(i＜j&&R[i].key＜=x)i++;

if(i＜j)R[j]=R[i];

}//while

R[i]=R[0];

returni;

}此題考查的知識(shí)點(diǎn)是快速排序的思想。66.參考答案：C堆排序是另一種基于選擇的排序方法。n個(gè)元素的序列{k1，k2，k3，...kn}，當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱(chēng)之為堆：

ki＜=k2i

或者：

ki＞=k2i。

ki＜=k2i+1

ki＞=k2i+1

其中i=1，2，…，n/2。

若將同以上序列對(duì)應(yīng)的一維數(shù)組看成是