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.具有6個頂點的無向圖至少應(yīng)有______條邊才能確保是一個連通圖。A.5B.6C.7D.82.假設(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)%maxSize;3.下列二叉樹中，不平衡的二叉樹是

。

4.一個n階矩陣A[0…n-1，0…n-1]采用一維數(shù)組s[0…n*n-1]按行序為主序，存放其上三角各元素，編寫一個算法求出S[k]在A[i][j]中的位置和A[i][j]在S[k]中的位置。5.設(shè)有5個初始歸并段，每個歸并段有20個記錄，采用5路平衡歸并排序，若不采用敗者樹，使用傳統(tǒng)的順序選小(簡單選擇排序算法)的方法，總的比較次數(shù)是______。A.20B.258C.396D.5006.編寫一個算法，將用二叉鏈表表示的完全二叉樹轉(zhuǎn)換為二叉樹的順序表示，假設(shè)數(shù)據(jù)類型為int型。7.構(gòu)建一個哈夫曼樹，如果給定權(quán)值的個數(shù)為n，那么哈夫曼樹的結(jié)點總數(shù)為______．A.不確定B.2nC.2n+1D.2n-18.在下列各種次序的線索二叉樹中，______對查找指定結(jié)點在該次序下的后序效率較差。A.前序線索二叉樹B.中序線索二叉樹C.后序線索二叉樹D.層次序線索二叉樹9.在一個單鏈表中，已知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;10.如果要求一個線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，可以采用下列哪一種查找方法?______A.分塊B.順序C.二分法D.哈希11.設(shè)循環(huán)隊列的存儲容量為maxSize，隊頭和隊尾指針分別為front和rear。若有一個循環(huán)隊列0，下列語句中可用來計算隊列元素個數(shù)的是______。A.(Q.rear-Q.front+maxSize)%maxSizeB.(Q.rear-Q.front)%mexSizeC.Q.rear-Q.front-1D.Q.rear-Q.front12.假設(shè)二叉樹采用鏈接存儲結(jié)構(gòu)進行存儲，t指向根結(jié)點，s所指結(jié)點為任意一個給定的結(jié)點，編寫一個求出從根結(jié)點到p所指結(jié)點之間路徑的函數(shù)。13.在10階B樹中根結(jié)點所包含的關(guān)鍵字個數(shù)最多為______，最少為1。A.7B.8C.9D.1014.利用串的基本運算，編寫一個算法，刪除串s1中所有的s2子串。15.線性表(a1，a2，…，an)以鏈式存儲方式存儲時，訪問第i位置元素的時間復(fù)雜度為______。A.O(i)B.O(1)C.O(n)D.O(i-1)16.下列4個序列中，哪一個是堆

。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，1517.若線性表最常用的運算是查找第i個元素及其前驅(qū)的值，則下列存儲方式中最節(jié)省時間的是______。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表18.在線性表中的每一個表元素都是數(shù)據(jù)對象，它們是不可再分的______。A.數(shù)據(jù)項B.數(shù)據(jù)記錄C.數(shù)據(jù)元素D.數(shù)據(jù)字段19.已知深度為h的二叉樹采用順序存儲結(jié)構(gòu)已存放于數(shù)組BT[1:2h一1]中，請寫一非遞歸算法，產(chǎn)生該二叉樹的二叉鏈表結(jié)構(gòu)。設(shè)二叉鏈表中鏈結(jié)點的構(gòu)造為(lchild，data，rchild)，根結(jié)點所在鏈結(jié)點的指針由T給出。20.設(shè)表達式以字符形式已存入數(shù)組E[n]中，‘#’為表達式的結(jié)束符，試寫出判斷表達式中括號(‘(’和‘)’)是否配對的C語言描述算法：EXYX(E)；(注：算法中可調(diào)用棧操作的基本算法。)21.沒有一個不帶表頭結(jié)點的單鏈表，表頭指針為head。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針head指向原鏈表的最后一個結(jié)點。22.當(dāng)一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組A[1..n]中時，數(shù)組中第i個結(jié)點的左孩子為

。A.A[2i](2i＜-n)B.A[2i+1](2i+1＜-n)C.A[i/2]D.無法確定23.以下關(guān)于圖的敘述中，正確的是______。A.強連通有向圖的任何頂點到其他所有頂點都有弧B.圖與樹的區(qū)別在于圖的邊數(shù)大于或等于頂點數(shù)C.無向圖的連通分量指無向圖中的極大連通子圖D.假設(shè)有圖G={V,{E}}，頂點集V'∈V，E'∈E，則V'和{E'}構(gòu)成G的子圖24.線性表(a1，a2，a3，…，an)中元素遞增有序且按順序存儲于計算機內(nèi)。要求設(shè)計算法完成以下內(nèi)容：

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

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

(3)若找不到將其插入表中并使表中元素仍遞增有序。25.用某種排序方法對線性表(25，84，21，47，15，27，68，35，20)進行排序時，元素序列的變化情況如下：

(1)25，84，21，47，15，27，68，35，20

(2)20，15，21，25，47，27，68，35，84

(3)15，20，21，25，35，27，47，68，84

(4)15，20，21，25，27，35，47，68，84

其所采用的排序方法是______。A.直接選擇排序B.希爾排序C.歸并排序D.快速排序26.下列有關(guān)圖的說法中正確的是______。A.在圖結(jié)構(gòu)中，頂點不可以沒有任何前驅(qū)和后繼B.具有n個頂點的無向圖最多有n(n-1)條邊，最少有n-1條邊C.在無向圖中，邊的條數(shù)是結(jié)點度數(shù)之和D.在有向圖中，各頂點的入度之和等于各頂點的出度之和27.由權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為

。A.24B.48C.72D.5328.最不適合用做鏈式隊列的鏈表是______。A.帶有隊頭指針的雙向非循環(huán)鏈表B.帶有隊頭指針的雙向循環(huán)鏈表C.只帶隊尾指針的雙向循環(huán)鏈表D.只帶隊尾指針的循環(huán)單鏈表29.由權(quán)值為8，4，5，7的4個葉結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為______。A.24B.36C.48D.7230.使用散列函數(shù)：

H(k)=3kmod11

采用鏈地址法處理沖突時，設(shè)計一個算法刪除一個指定的結(jié)點。31.已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。用C語言編寫一函數(shù)，求A和B的交集，并存放于A鏈表中。32.二叉樹若用順序方法存儲，則下列四種算法中運算時間復(fù)雜度最小的是______。A.先序遍歷二叉樹B.判斷兩個指定位置的結(jié)點是否在同一層上C.層次遍歷二叉樹D.根據(jù)結(jié)點的值查找其存儲位置33.非空的循環(huán)單鏈表head的鏈尾結(jié)點(由p所指向)滿足______。A.P→next==NULL;B.P==NULL;C.P→next==head;D.P==head;34.對長度為10的順序表進行查找，若查找前面5個元素的概率相同，均為1/8，查找后面5個元素的概率相同，均為3/40，則查找到表中任一元素的平均查找長度為______。A.5.5B.5C.39/8D.19/435.設(shè)計一個算法創(chuàng)建一個帶權(quán)(路徑)的無向圖，要求被創(chuàng)建的圖由用戶輸入，輸出從V0到其他各個頂點的最短路程長度和路徑。36.當(dāng)采用鄰接表方式存儲帶權(quán)連通圖時，求最小生成樹的Prim算法的時間復(fù)雜度為______。A.O(n)B.O(elog2e)C.O(n2)D.O(n3)37.假設(shè)以帶頭結(jié)點的單鏈表表示有序表，單鏈表的類型定義如下：

typedefstructnode{

DataTypedata：

structnode

*next

}LinkNode，

*LinkList；

編寫算法，從有序表A中刪除所有和有序表B中元素相同的結(jié)點。38.若對27個元素只進行3趟多路歸并排序，則選取的歸并路數(shù)為______。A.2B.3C.4D.539.對于一個使用鄰接表存儲的帶權(quán)有向圖G，試利用深度優(yōu)先搜索方法，對該圖中所有頂點進行拓撲排序。若鄰接表的數(shù)據(jù)類型為graph，則算法對應(yīng)函數(shù)的說明為

intdfs_toposort(graph*g)

若函數(shù)返回1，則表示拓撲排序成功，圖中不存在環(huán)；若函數(shù)返回0，則圖中存在環(huán)，拓撲排序不成功。在這個算法中嵌套調(diào)用一個遞歸的深度優(yōu)先搜索算法為

dfs1(graph*g,intv)

在遍歷圖的同時進行拓撲排序，給出整個算法的實現(xiàn)。40.在AOE網(wǎng)絡(luò)中，可能同時存在幾條關(guān)鍵路徑，稱所有關(guān)鍵路徑都需通過的有向邊為______，如果加速這樣的關(guān)鍵路徑就能使整個工程提前完成。A.匯B.源C.橋D.潭41.在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作______型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR42.關(guān)于圖(Graph)的一些問題：

(1)有n個頂點的有向強連通圖最多有多少條邊?最少有多少條邊?

(2)表示有1000個頂點、1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否為稀疏矩陣?43.線性表的每一個表元素是否必須類型相同?為什么?44.設(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-145.下列二叉排序樹中，滿足平衡二叉樹定義的是______。

A．

B．

C．

D．46.設(shè)一棵二叉樹的中序序列為badce，后序遍歷為bdeca，則該二叉樹前序遍歷的順序是______。A.adbecB.decabC.debacD.abcde47.設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點，則B中右指針域為空的結(jié)點個數(shù)是______。A.n-1B.nC.n+1D.n+248.用鏈表表示線性表的優(yōu)點是______。A.便于隨機存取B.花費的存儲空間較順序存儲少C.便于插入和刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相同49.對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)逆鄰接表中該頂點的入邊表中的邊結(jié)點數(shù)為______。A.k1B.k2C.k1-k2D.k1+k250.對任何一棵二叉樹，如果終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則一定有n0=n2+1。第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：A[解析]有n個頂點的連通圖，至少需要n-1條邊才能保持圖的連通。多一條邊將形成回路，少一條邊將變成非連通圖。當(dāng)n=6時，n-1=5。2.參考答案：C[解析]當(dāng)隊尾指針rear追上隊頭指針front時隊列滿。一般以犧牲一個存儲單元來區(qū)分隊列空和隊列滿。3.參考答案：C平衡二叉樹的特點為：左、右子樹深度之差的絕對值不大于1。4.參考答案：這是一道簡單題，只要注意區(qū)分行主序和列主序即可：

已知S[k]，求A[i][j]的算法如下：

voidfindij(intk,intn,int&i,int&j)

{

i=(k+1)/n;

j=k%n;

已知A[i][j]求S[k]的算法如下：

voidfindk(inti,intj,int&k,intn)

{

k=i*n+j;

}5.參考答案：C[解析]5路歸并就意味著在5個參加比較的記錄中選擇一個排序碼最小的記錄，用傳統(tǒng)的方法需做4次比較，總共5×20=100個記錄，需做99次選擇最小記錄的操作，需要的比較次數(shù)為99×4=396。6.參考答案：因為鏈表形式是遞歸的數(shù)據(jù)結(jié)構(gòu)，所以使用遞歸算法最簡單。將以t為根的二叉鏈表表示的二叉樹轉(zhuǎn)換為二叉樹的順序表示也可以采用遞歸算法，其思路是：假設(shè)子樹的根t存放于T[i]，則可將它的左子女存放于T[2*i]，右子女存放于T[2*i+1]。

在主程序調(diào)用時，t應(yīng)賦予root，i應(yīng)賦予1(根結(jié)點在T[1]中)。

voidLinkList_to_Array(BTNode*t,intA[],intn,inti)

{

if(t==NULL)return;

if(i＞n)

{

cout＜＜"arraymemorylimit"＜＜endl;

return;

}

A[i]=t→data;

LinkList_to_Array(t→lchild,A,n,2*i);

LinkList_to_Array(t→rchild,A,n,2*i+1);

}7.參考答案：D哈夫曼樹中只有度為0和度為2的結(jié)點，即N=n0+n2，而根據(jù)二叉樹的性質(zhì)：n0=n2+1，可知n0=n，那么n2=n-1，N=n+n-1=2n-1。8.參考答案：C[解析]對二叉樹進行后序線索化后，尋找指定結(jié)點的后序下的后序結(jié)點比較麻煩。因為它首先要找到這個結(jié)點的父結(jié)點，再到其父結(jié)點的右子樹中找后序下的第一個結(jié)點。9.參考答案：C10.參考答案：A[解析]由于題目只說明是線性表，因此排除二分法。哈希算法雖然有最快的查找效率，但建立哈希表無法適應(yīng)動態(tài)變化的要求。在數(shù)據(jù)量大的查找中，順序查找顯然缺乏效率，因此應(yīng)選擇使用分塊查找方法。11.參考答案：A[解析]為了做到讓隊列指針周而復(fù)始地在循環(huán)隊列中遍歷，可用取模(%)運算使得指針從存儲數(shù)據(jù)末端直接移到存儲數(shù)組的始端。12.參考答案：本題采用非遞歸后序遍歷樹t，當(dāng)后序遍歷訪問到s所指結(jié)點時，stack中所有結(jié)點均為p所指結(jié)點的祖先，由這些祖先便構(gòu)成了一條從根結(jié)點到p所指結(jié)點之間的路徑。

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

intpath(BTNode*t,BTNode*s)

{

BTNode*stack[MaxSize];

BTNode*p;

inti,flag,top=-1;

//棧指針置初值

do

{

while(t)

//將t的所有左結(jié)點入棧

{

++top;

stack[top]=t;

t=t→left;

}

p=NULL;

//p指向當(dāng)前結(jié)點的前一個已訪問的結(jié)點

flag=1;

//設(shè)置t的訪問標記為已訪問過

while(top!=1&&flag)

{

t=stack[top];

//取出當(dāng)前的棧頂元素

if(t→right==p)

//右子樹不存在或已被訪問，訪問之

{

if(t==s)

//要訪問的結(jié)點為要找的結(jié)點

{

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

cout＜＜stack[i]→data＜＜"";

return1;

}

else

{

--top;

p=t;

//p指向已被訪問的結(jié)點

}

}

else

{

t=t→right;

//t指向右子樹

flag=0;

//設(shè)置未被訪問的標記

}

}

}while(top!=-1);

return0;

}13.參考答案：C[解析]根據(jù)B樹的定義，10階B樹的根結(jié)點最多可以有9個關(guān)鍵字(m=10-1)，最少有1個關(guān)鍵字。14.參考答案：本題利用index()函數(shù)和刪除子串的函數(shù)循環(huán)來實現(xiàn)。其程序如下：

voiddelall(Str*s1,Str*s2)

{

intn;

n=index(s1,s2);

while(n＞=0)

{

del(s1,n,length(s2));

n=index(s1,s2);

}

disp(s1);

}

其中del函數(shù)實現(xiàn)如下：

intdel(Str*s,intpos,intn)

//從串s中刪除從位置pos開始的n個字符構(gòu)成的子串

{

inti;

if(pos+n＞s-＞length)

return0;

for(i=pos+n-1;i＜s-＞length;++i)

s-＞ch[i-n]=s-＞ch[i];

s-＞length=s-＞length-n;

s-＞ch[s-＞length]='\0';

return1;

}15.參考答案：C此題考查的知識點是線性表基本操作的時間復(fù)雜度。鏈式存儲的線性表訪問第i個位置的元素時需要從頭開始向后查找，平均查找次數(shù)為(n+1)/2，所以時間復(fù)雜度為O(n)，選C。16.參考答案：C堆排序是另一種基于選擇的排序方法。n個元素的序列{k1，k2，k3，...kn}，當(dāng)且僅當(dāng)滿足以下關(guān)系時，稱之為堆：

ki＜=k2i

或者：

ki＞=k2i。

ki＜=k2i+1

ki＞=k2i+1

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

若將同以上序列對應(yīng)的一維數(shù)組看成是一棵完全二叉樹，則堆的含義表明：該完全二叉樹的所有非終端結(jié)點均不大于(或不小于)其左、右孩子結(jié)點的值。由此，若{k1，k2，…kn)是堆，則堆頂元素(或完全二叉樹的根結(jié)點)必定是該序列n個元素中的最小值(或者最大值)。

若將堆看成是一棵以k1為根的完全二叉樹，則這棵完全二叉樹中的每個非終端結(jié)點的值均不大于(或不小于)其左、右孩子結(jié)點的值。由此可以看出，若一棵完全二叉樹是堆，則根結(jié)點一定是這n個結(jié)點中的最小者(或最大者)。下圖給出了兩個堆的示例。

從堆的定義可以看出，若將堆用一棵完全二叉樹表示．則根結(jié)點是當(dāng)前堆中所有結(jié)點的最小者(或最大者)。堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造一個堆，此時，選出了堆中所有記錄的最小者或最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小(或次大)的記錄，以此類推，直到堆中只有一個記錄為止，每個記錄出堆的順序就是一個有序序列。

假設(shè)當(dāng)前要進行篩選的結(jié)點編號為k，堆中最后一個結(jié)點的編號為m，且a[k+1]至a[m]之間的結(jié)點都已經(jīng)滿足堆的條件，則調(diào)整過程可以描述為：

(1)設(shè)置兩個指針i和j，i指向當(dāng)前(要篩選)的結(jié)點：|=k；j指向當(dāng)前結(jié)點的左孩子結(jié)點：j=2*i；

(2)比較當(dāng)前結(jié)點的左右孩子的關(guān)鍵字值，并用j指向關(guān)鍵字值較大的孩子結(jié)點。

if(j＜m&&a[j]．key＜a[j+1])．key)j++；

(3)用當(dāng)前結(jié)點的關(guān)鍵字與j所指向的結(jié)點關(guān)鍵字值進行比較，根據(jù)比較結(jié)果采取相應(yīng)的操作，即結(jié)束篩選或交換結(jié)點內(nèi)容并繼續(xù)進行篩選。實現(xiàn)這個操作的語句為：

if(a[i]．key＞a[j]．key)

break；

∥結(jié)束篩選操作

else{

temp=a[i]；a[i]=a[j]；a[j]=temp；

∥交換結(jié)點內(nèi)容

i=j；

j=2*i；

∥準備繼續(xù)篩選

}

可以將交換改進為：

if(a[i]．key＞a[j]．key)

break：

else

{a[i]=a[j]；i=j；j=2*i；}

堆排序的篩選算法：

voidsift(DataTypea，intk，intm)

{i=k；；j=2*i；temp=a[i]；

while(j＜=m)

if(j＜m&&a[j]．keyr＜a[j+1]．key)

j++；

if(a[i]．key＞a[j]．key)

break：

else

{a[i]=a[j]；

i=j；

j=2*i；

}

}

a[i]=temp；

}

堆排序完整的算法為：

voidheapsort(DataTypea，intn)

{h=n/2；

∥最后一個非終端結(jié)點的編號

for(i=h；i＞=1；i——)

∥初建堆，從最后一個非終端結(jié)點至根結(jié)點

sift(a，i，n)；

for(i=n；i＞1；i——)

∥重復(fù)執(zhí)行移走堆頂結(jié)點及重建堆的操作

{

temp=a[l]；a[l]=a[i]．a(chǎn)[i]=temp；

sift(a，1，i-1)；

}

}

在堆排序中，除建初堆以外，其余調(diào)整堆的過程最多需要比較樹深度次，因此，與簡單選擇排序相比時間效率提高了很多；另外。不管原始記錄如何排列，堆排序的比較次數(shù)變化不大，所以說，堆排序?qū)υ加涗浀呐帕袪顟B(tài)并不敏感。

在堆排序算法中只需要一個暫存被篩選記錄內(nèi)容的單元和兩個簡單變量h和i，所以堆排序是一種速度快且省空間的排序方法。堆排序是一種不穩(wěn)定排序，其時間復(fù)雜度為O(nlog2n)。17.參考答案：D本題的考點是線性表的存儲結(jié)構(gòu)及其特點。在線性表中主要的存儲結(jié)構(gòu)有順序表和鏈表兩種，其特點如下：

(1)順序表可以實現(xiàn)隨機存取，其時間復(fù)雜度為O(1)。但在順序表中，進行插入和刪除操作需要移動大量的元素，其時間復(fù)雜度為O(n)；

(2)鏈表中只能實現(xiàn)順序查找，其時間復(fù)雜度為O(n)。但鏈表中進行插入和刪除操作不需要移動元素，只需要修改指針，其時間復(fù)雜度為O(1)。

本題中，線性表中常用的操作是取第i個元素，所以應(yīng)選擇隨機存取結(jié)構(gòu)，即順序表；同時在順序表中查找第i個元素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i個元素的前驅(qū)也不方便；雙鏈表雖然能快速查找第i個元素的前驅(qū)，但不能實現(xiàn)隨機存取。18.參考答案：C[解析]線性表是n(n≥0)個數(shù)據(jù)元素的有限序列。數(shù)據(jù)記錄、數(shù)據(jù)字段是數(shù)據(jù)庫文件組織中的術(shù)語。數(shù)據(jù)項相當(dāng)于數(shù)據(jù)元素中的屬性。

本題考查的依然是線性表的基本定義。19.參考答案：[解析]二叉樹采用順序存儲結(jié)構(gòu)(一維數(shù)組)是按完全二叉樹的形狀存儲的，不按完全二叉樹的二叉樹順序存儲時，要加“虛結(jié)點”。數(shù)組中的第一個元素是根結(jié)點。本題中采用隊列結(jié)構(gòu)。本題中的虛結(jié)點用‘#’表示。

typedefstruct

BiTreebt；

∥二叉樹結(jié)點指針

intnum；

∥num是結(jié)點在一維數(shù)組中的編號

}tnode

tnode

Q[maxsize]；

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

voidcreat(BiTreeT，ElemTypeBT[])

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

{

tnodetq；

∥tq是隊列元素

intlen=2h-1；

∥數(shù)組長度

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

∥申請結(jié)點

T->data=BT[1]；

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

tq.bt=T；

tq.num=1；

Q[1]=tq；

∥根入隊列

front=0：

rear=1；

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

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

{

front=(front+1)%maxsize；

tq=Q[front]；

p=tq.bt；

i=tq.num；∥出隊，取出結(jié)點及編號

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

p—＞lchild=null；

∥左子樹為空，‘#’表示虛結(jié)點

else∥建立左孩子結(jié)點并入隊列

{

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

∥申請結(jié)點空間

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

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

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

∥計算

隊尾位置

Q[rear]=tq；∥左孩子結(jié)點及其編號入隊

}

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

p—＞rchild=null；

∥右子樹為空

else∥建立右孩子結(jié)點并入隊列

{

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

∥申請結(jié)點空間

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

tq.bt=p—＞rchild；

tq.num=2*i+1；

rear=(rear+1)%maxsize；

Q[rear]=tq；

∥計算隊尾位置，右孩子及其編號入隊

}

}

}20.參考答案：判斷表達式中括號是否匹配，可通過棧，簡單說是左括號時進棧．右括號時退棧。退棧時，若棧頂元素是左括號，則新讀入的右括號與棧頂左括號就可消去。如此下去，輸入表達式結(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è)棧容量足夠大，因此入棧時未判斷溢出。21.參考答案：

voidInverse(LinkList&head){

//head設(shè)為引用型,因要返回head改變后的值

if(head==NULL)return;

//空表無需逆轉(zhuǎn)

LinkedNode*p=head-＞link,*pr=NULL;

while(p!=NULL){

head-＞link=pr;

//逆轉(zhuǎn)head指針

pr=head;head=p;p=p-＞link;

//指針前移

}

head-＞link=pr;

}22.參考答案：D如果2i+1＜=n，則左孩子為A[2i+1]，否則就沒有左孩子。所以無法確定。23.參考答案：C強連通有向圖的任何頂點到其他所有頂點都有路徑，但未必有弧，A錯誤。圖與樹的區(qū)別是邏輯上的，而不是邊數(shù)的區(qū)別，圖的邊數(shù)也可能小于樹的邊數(shù)。若E'中的邊對應(yīng)的頂點不是V'中的元素時，則V'和{E'}無法構(gòu)成圖，D錯誤。24.參考答案：(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--)

a[i+1]=a[i];

//后移元素

a[i+1]=x;

//插入x

}

//結(jié)束插入

}

//結(jié)束本算法

(2)算法討論

首先是線性表的描述。算法中使用一維數(shù)組a表示線性表，未使用包含數(shù)據(jù)元素的一維數(shù)組和指示線性表長度的結(jié)構(gòu)體。若使用結(jié)構(gòu)體，對元素的引用應(yīng)使用a.elem[i]。另外，元素類型就假定是ElemType，未指明具體類型。其次，C中一維數(shù)組下標從0開始，若說有n個元素的一維數(shù)組，其最后一個元素的下標應(yīng)是n-1。最后，本算法可以寫成三個函數(shù)，即查找函數(shù)、交換后繼函數(shù)與插入函數(shù)，寫成三個函數(shù)顯得邏輯清晰、易讀。25.參考答案：A可以看到，每趟從無序區(qū)中找出一個最大的元素定位，所以答案為A。26.參考答案：D[解析]如果有向圖中只有一個頂點，則此頂點沒有前驅(qū)，也沒有后繼；對于無向圖，圖中頂點沒有次序關(guān)系，所以也談不上前驅(qū)和后繼，因此選項A錯誤。

具有n個頂點的無向圖最少可以有0條邊，只有在連通圖的情形下最少是n-1條邊，因此選項B錯誤。

在無向圖中，所有頂點的度數(shù)之和是邊的條數(shù)的2倍，選項C錯誤。27.參考答案：D

生成的哈夫曼樹如上圖所示，路徑長度為：3*(2+3)+2*(8+5+6)=53。28.參考答案：A[解析]即使是雙向鏈表，如果是非循環(huán)鏈表，只有隊頭指針也是不夠的。29.參考答案：C[解析]由權(quán)值為8，4，5，7的4個葉結(jié)點構(gòu)造出的一棵哈夫曼樹如下圖所示。它的帶權(quán)路徑長度WPL的計算有兩種方法：一是先求每一個葉結(jié)點的帶權(quán)路徑長度，加起來得到WPL=4×2+5×2+7×2+8×2=48；另一種方法是把所有非葉結(jié)點的權(quán)值加起得到WPL=24+9+15=48。

30.參考答案：實現(xiàn)本題功能的函數(shù)代碼如下：

intdelnode(ints)

{

hashnode*p,*q;

inti;

i=(3*s)%M;

p=ht[i].next;q=p;

while(p!=NULL&&p-＞key!=s)

{

cout＜＜p-＞key＜＜endl;

q=p;

p=p-＞next;

}

if(p!=NULL&&p==q)

//p為第一個結(jié)點

{

ht[i].next=p-＞next;

free(p);

return1;

}

elseif(p!=NULL)

//p為其他結(jié)點

{

q-＞next=p-＞next;

free(p);

return1;

}

else

{

return0;

}

}31.參考答案：LinkedListla;

la=(LinkedList)malloc(sizeof(LNode));

la-＞next=ha;

//申請頭結(jié)點,以便操作

pa=ha;

//pa是ha鏈表的工作指針

pb=hb;

//pb是hb鏈表的工作指針

pre=la;

//pre指向當(dāng)前待合并結(jié)點的前驅(qū)

while(pa&&pb)

if(pa-＞data＜pb-＞data)//處理ha中的數(shù)據(jù)

{

pre-＞next=pa:

pre=pa;

pa=pa-＞next:

}

elseif(pa-＞data＞pb-＞data)

//處理hb中的數(shù)據(jù)

{

R=(LinkedList)malloc(sizeof(LNode));

//申請空間

R-＞data=pb-＞data;

pre-＞next=r;

pre=r;

//將新結(jié)點鏈入結(jié)果鏈表

pb=pb-＞next;

//hb鏈表中工作指針后移

}

else

//處理pa-＞data=pb-＞data;

pre-＞next=pa;

Pre=pa;

pa=pa-＞next;

//兩結(jié)點數(shù)據(jù)相等時,只將ha的數(shù)據(jù)鏈入

pb=pb-＞next;

//不要hb的相等數(shù)據(jù)

}

if(pa!=null)pre-＞next=pa;

//將兩鏈表中剩余部分鏈入結(jié)果鏈表

elsepre-＞next=pb;

free(la);

//釋放頭結(jié)點,ha、hb指針未被破壞

}

//算法Union結(jié)束[解析]因為兩鏈表已按元素值遞增次序排列，將其合并時，均從第一個結(jié)點起進行比較，將小的鏈入鏈表中，同時后移鏈表工作指針。如果遇上相等的元素，只需記錄一個，并同時向后移動鏈表工作指針。32.參考答案：B[解析]選項A、C、D運算的時間復(fù)雜度都是O(n)，而選項B的運算的時間復(fù)雜度為O(1)，因為對于指定位置p和q的兩個結(jié)點，判斷是否在同一層上，只需判斷兩者|log2p|=|log2q|是否成立。33.參考答案：C[解析]非空單循環(huán)鏈表的尾結(jié)點為p，則其后繼結(jié)點為鏈表的頭結(jié)點head，即p→next==head。34.參考答案：C[解析]在查找概率不等的情況下，前5個元素的查找概率均為1/8，后5個元素的查找概率均為3/40，則：

35.參考答案：本題屬于基礎(chǔ)題，考查圖的創(chuàng)建和迪杰斯特拉算法。

intcost[maxSize][maxSize];

//cost為帶權(quán)鄰接矩陣

intdist[maxSize],n;

//dist為從V0到各頂點的最短路程

struct

{

intnum;

intpnode[maxSize];

}path[maxSize];

//path為從V0到各頂點的最短路徑

voidcreatgraph()

//創(chuàng)建帶權(quán)無向圖

{

intitj,s,e,len,contin=1;

cout＜＜"頂點個數(shù):";

cin＞＞n;

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

{

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

cost[i][j]=cost[j][i]=up;

//up是已定義的最大值，表示無窮大

cost[i][i]=0;

}

cout＜＜"輸入各邊，以0，0，0表示結(jié)束：\n";

i=1:

while(contin==1)

{

cout＜＜"\t第"＜＜i＜＜"條邊-＞頂點，頂點，邊長:";

cin＞＞s＞＞e＞＞len;

if(s==0&&e==0&&len==0)

contin=0;

else

{

cost[s][e]=len;

++i;

}

}

}

voidshortdjs()

//求最短路徑

{

ints[maxSize];

intmindisfdis,i,j,v0=0,u;

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

{

dist[i]=cost[v0][i];

path[i].pnode[0]=v0;

path[i].num=0;

s[i]=0;

}

s[v0]=1;

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

{

mindis=up;

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

if(s[j]==0&&dist[j]＜mindis)

{

u=j;

mindis=dist[j];

}

s[u]=1;

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

if(s[j]==0)

{

dis=dist[u]+cost[u][j];

if(dist[j]＞dis)

{

dist[j]=dis;

++(path[j].num);

path[j].pnode[path[j].num]=u;

}

}

++(path[i].num);/*將終點i添加到路徑中*/

path[i].pnode[path[i].num]=i;

}

}

voiddispath()

//輸出最短路徑

{

inti,j;

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

{

if(dist[i]＜up)

cout＜＜dist[i];

else

cout＜＜"∝";

//顯示無窮大

for(j=0;j＜path[i].num;++j)

cout＜＜"V"＜＜path[i].pnode[j]＜＜",";

}

}36.參考答案：B[解析]求最小生成樹的Prim算法中，如果采用小根堆來組織那些一個端點在S中、另一個端點在V-S中的邊，最壞情況下所有邊都進一次堆，在堆內(nèi)把權(quán)值最小的邊調(diào)整到堆頂需要的時間是O(log2e)，則總的時間應(yīng)是O(elog2e)。37.參考答案：

voiddeleted_list(LinkListA，LinkListB){

LinkListp，q，r；

r=A：

p=A—＞next；

q=B—＞next；

while(p!—NULL&&q!=NULL)

{

if(p—＞data＞q—＞data)

q=q—＞next

elseif(p—＞data＜q—＞data)

{

r=P：

p—p—＞next；

}

else

{

r—＞next=p—＞next；

free(p)；

p=r—＞next：

}

}}38.參考答案：B[解析]設(shè)需要的路數(shù)為m，則對于11個元素做m路歸并排序所需趟數(shù)。當(dāng)n=27，s=3時，則，m=271/3=3。39.參考答案：intvisited[Vnum];

intfinished[Vnum];//表示對頂點i的DFS搜索是否結(jié)束

voiddfs1(graph*g,intv,int&flag)

//在深度優(yōu)先遍歷時輸出頂點號。若圖中不存在環(huán)，則輸出全部頂點

//號，即為有向圖的頂點拓撲排序，否則將flag置為0

{

arcnode*p;

cout＜＜v＜＜"";finished[v]=0;

visited[v]=1;

p=g→adjlist[v].firstarc;

while(p!=NULL)

{

if(visited[p→adjvex]==1&&finished[p→adjvex]==0)

flag=0;

elseif(visited[p→adjvex]==0)

{

dfs1(g,p→adjvex,flag);

finished[p→adjvex]=1;

}

p=p→nextarc;

}

}

intdfs_topo