一、單項選擇題

1. 若某線性表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最

后一個結(jié)點，則采用(3)存儲方式最節(jié)省運算時間。

(1)單鏈表 (2)雙鏈表

(3)容量足夠大的順序表 (4)帶頭結(jié)點的雙循環(huán)鏈表

若某線性表中最常用的操作是取第 I個元素的前驅(qū)元素，則采用(3)

存儲方式最節(jié)省運算時間。

(1)單鏈表 (2)雙鏈表

(3)順序表 (4)帶頭結(jié)點的雙循環(huán)鏈表

將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為

(A)。

A.98 B.99 C.50 D.48

一個具有n個頂點的無向完全圖的邊數(shù)為(B)。

A.n(n+1)/2B.n(n-1)/2 C.n(n-1)D.n(n+1)

折半查找要求查找表中各元素的關(guān)鍵字值必須是 A排列。

A.遞增或遞減 B.遞增C.遞減D.無序

棧操作的原則是 B。

A.先進先出 B,后進先出 C,只能進行插入 D.只能進行刪除

2. 設(shè)一個棧的輸入序列為A,B,C,D,則借助一個棧所得的輸出序列不可能

是(4)°

(1)A,B,C,D(2)D,C,B,A(3)A,C,D,B(4)D,A,B,C

將下三角矩陣A[1..10,1..10]的所有非0元素以行序為主序存放在首地址為2000的

存儲區(qū)中，每個元素占有4個單元，則元素A[9,5]的首地址為(D)

A.2340

B.2336

C.2164 D.2160

4.3.

串是

(4) 。

(1)

(1)

不少于一個字母的序列 (2)任意個字母的序列

(2)

(2)

不少于一個字符的序列 (4)有限個字符的序列

4. 鏈表不具有的特點是A.

(1)可隨機訪問任一元素 (2)插入刪除不需要移動元素

(3)不必事先估計存儲空間(4)所需空間與線性表長度成正比

5.在有n個結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為—4。

(1) (1) 不確定(2)2n(3)2n+1 (4)2n-1

6. 任何一個無向連通圖的最小生成樹B。

(1) (1) 只有一棵(2)有一棵或多棵(3)一定有多棵(4)可能不

存在

7. 將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次

對結(jié)點進行編號，根結(jié)點的編號為 1,則編號為49的結(jié)點的左孩子編號為

1。

(1)98 (2)99 (3)50 (4)48

將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的右孩子編號為—2。

(1)98 (2)99 (3)50 (4)48

將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的雙親編號為—2。

(1)23 (2)24 (3)25 (4)無法確定

設(shè)計一個判別表達式中左右括號是否配對出現(xiàn)的算法，采用(B)數(shù)據(jù)結(jié)構(gòu)最佳。

A.線性表的順序存儲結(jié)構(gòu) B.棧C.隊列D.線性表的鏈式存儲結(jié)

構(gòu)

8. 下列序列中，A是執(zhí)行第一趟快速排序后得到的序列(排序

的關(guān)鍵字類型是字符串)。

(1)[da,ax,eb,de,bb]ff[ha,gc](2)[cd,eb,ax,da]ff[ha,gc,bb]

(3)[gc,ax,eb,cd,bb]ff[da,ha](4)[ax,bb,cd,da]ff[eb,gc,ha]

9.用n個鍵值構(gòu)造一棵二叉排序樹，最低高度為—D。

(1)n/2 (2)m/2 (3)NLOG; (4)[LOG2N]+1

10.折半查找要求查找表中各元素的關(guān)鍵字值必須是1排列。

(1) (1)遞增或遞減(2)遞增(3)遞減 (4)無序

11.對于關(guān)鍵字值序列(12，13，11，18，60，15，7，18，25，100)，用篩選法

建堆，必須從關(guān)鍵字值為3的結(jié)點開始。

(1)100 (2)12 (3)60 (4)15

快速排序的記錄移動次數(shù)(C)比較次數(shù)，其總執(zhí)行時間為0(NLOG2N)

大于B.大于等于 C.小于等于D.小于 2

3個結(jié)點可構(gòu)成(D)個不同形態(tài)的二叉樹。

2B.3 C.4D.5

對有n個記錄的有序表采用二分查找，其平均查找長度的量級為(A)

O(LOG2N)B.O(NLOG2N) C.O(N) D.O(N2)

對有n個記錄的表按記錄鍵值有序的順序建立二叉排序樹，在這種情況下，其平均查找長度的量級為(C)

O(LOG2N)B.O(NLOG2N) C.O(N) D.O(N2)

設(shè)矩陣A[1..8,1..8]是一對稱矩陣，若每個矩陣元素占3個單元，將其上三角部分按

行序為主序存放在數(shù)組B中，B的首址為1000，則矩陣元素A[6,7]的地址為(B)

A.1031B.1093 C.1096D.1032

鏈表適用于順序查找，但在鏈表中進行(D)操作的效率比在順序存儲結(jié)構(gòu)中進行同樣操作的效率高。

A.順序查找 B.二分法查找 C.快速查找。.插入

散列法中的沖突指的是(C)。

A.兩個元素具有相同的序號B.兩個元素的鍵值不同，而其它屬性相同

不同鍵值的元素對應(yīng)于相同的存儲地址D.數(shù)據(jù)元素過多

如果以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作時（C）

A.必須判斷棧是否滿 B.對棧不作任何判斷 C.必須判斷棧是否空

判斷棧元素的類型

設(shè)數(shù)組A[0..M]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為對尾指針，

則執(zhí)行出隊操作的語句為（D）

A.front=front+1 B.front=（front+1）%m

C.rear=rear+1 D.rear=（rear+1）%m

深度為6的二叉樹至多有（D）個結(jié)點

A.64B.32 C.31D.63

設(shè)高度為k的二叉樹上只有度為0和2的結(jié)點，則此類二叉樹中所含的結(jié)點數(shù)至少為（C）

A.K+1B.2K C.2K-1D.2K+1

堆的存儲表示（A）

A.順序存儲 B.靜態(tài)鏈接存儲C.動態(tài)鏈接存儲D.不一定

若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左右子樹的位置，利用（A）遍歷方法最合適。

A.前序B.中序C.后序 D.按層次

利用逐點插入法建立序列（50，72,43,85,75,20，35,45,65，30）對應(yīng)的二叉排序樹以后，查找元素35要進行（A）元素間的比較。

A.4次B.5次C.7次D.10次

下面給出的四種排序法中（D）排序法是不穩(wěn)定性排序法。

A—插入 B.冒泡 C.二路歸并 D.堆積

下面 方法可以判斷出一個有向圖中是否有環(huán)（回路）？

A.深度優(yōu)先遍歷B.拓樸排序C.求最短路徑D.求關(guān)鍵路徑

若結(jié)點的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為（D）

A.順序存儲結(jié)構(gòu) B.鏈式存儲結(jié)構(gòu)

C.索引存儲結(jié)構(gòu) D.散列存儲結(jié)構(gòu)

在長度為n的順序表的第i（1WiWn+1）個位置上插入一個元素，元素的移動次數(shù)為（A）

A.n-i+1 B.n-i

C.i D.i-1

對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為（C）

A.順序表B.用頭指針表示的單循環(huán)鏈表

C.用尾指針表示的單循環(huán)鏈表D.單鏈表

若進棧序列為a,b,c，則通過入出棧操作可能得到的a,b,c的不同排列個數(shù)為（）

A.4

B.5

C.6

D.7

為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的串運算是（D）

化插入B.刪除C.串聯(lián)接D.子串定位

已知函數(shù)Sub（s,i,j）的功能是返回串s中從第i個字符起長度為j的子串，函數(shù)Scopy（s,t）的功能為復制串t到s。若字符串S=〃SCIENCESTUDY7，則調(diào)用函數(shù)Scopy（P,Sub（S,1,7））后得到（A）

A.P=〃SCIENCE7 B.P=〃STUDY7

C.S=〃SCIENCE7 D.S=7STUDY7

三維數(shù)組A[4][5][6]按行優(yōu)先存儲方法存儲在內(nèi)存中，若每個元素占2個存儲單元，且數(shù)組中第一個元素的存儲地址為120，則元素A[3][4][5]的存儲地址為（）

A.356 B.358 C.360 D.362

如右圖所示廣義表是一種（C）

題8圖

線性表

純表

結(jié)點共享表

遞歸表

下列陳述中正確的是（D）

二叉樹是度為2的有序樹

二叉樹中結(jié)點只有一個孩子時無左右之分

二叉樹中必有度為2的結(jié)點

二叉樹中最多只有兩棵子樹，并且有左右之分

n個頂點的有向完全圖中含有向邊的數(shù)目最多為(D)

A.n-1 B.n C.n(n-1)/2 D.n(n-l)

已知一個有向圖如右所示，則從頂點a出發(fā)進行深度優(yōu)先偏歷，不可能得到的DFS序列為(A)

TOC\o"1-5"\h\z

a d b e f c

a d c e f b

a d c b f e

a d e f c b

在最好和最壞情況下的時間復雜度均為O(nlogn)且穩(wěn)定的排序方法是(C)

A.快速排序B.堆排序C.歸并排序D.基數(shù)排序

不可能生成右圖所示二叉排序樹的關(guān)鍵字序列是(A)

■13圖

A.45312

42531

45213

42315

ALV樹是一種平衡的二叉排序樹，樹中任一結(jié)點的（B）

A.左、右子樹的高度均相同 B.左、右子樹高度差的絕對值不超過1

C.左子樹的高度均大于右子樹的高度D.左子樹的高度均小于右子樹的高度

在VSAM文件的控制區(qū)間中，記錄的存儲方式為（）

A.無序順序 B.有序順序

B. C.無序鏈接 D.有序鏈接

二、二、判斷題

（）串長度是指串中不同字符的個數(shù)。

（）數(shù)組可以看成是線性結(jié)構(gòu)的一種推廣，因此可以對它進行插入、刪除等運算。

（）在順序表中取出第i個元素所花費的時間與i成正比。

（）在棧滿的情況下不能作進棧的運算，否則產(chǎn)生“上溢”。

（）二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。

（）對任意一個圖，從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個頂點。

（）一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)一定相等。

8（）在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表的個數(shù)有關(guān)，而且與每一塊中的元素個數(shù)有關(guān)。

（）二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點的值大于其左孩子的值；若它的右子樹非空，則根結(jié)點的值小于其右孩子的值。

（）在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。

二、判斷題（判斷下列各題是否正確，若正確在括號內(nèi)打“J”，錯誤的打；

如果兩個串含有相同的字符，則這兩個串相等。（N）

數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對它進行插入、刪除等運算。（N），

在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每塊元素個數(shù)有關(guān)。（Y）

在順序表中取出第i個元素所花費的時間與i成正比。（N）

在棧滿情況下不能作進棧運算，否則產(chǎn)生“上溢”。（Y）

二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列，（Y）

對任意一個圖，從它的某個頂點出發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點。（N）

二叉排序樹或是一棵空二叉樹，或是具有下列性質(zhì)的二叉樹；若它的左子樹非空，則根結(jié)點的值大于其左孩子的值；若它的右子樹非空，則根結(jié)點的值小于其右孩子的值。（N）

在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的（N）。

一個有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)一定相等（Y）

&（101，88，46，70，34，39，45，58，66，10）是堆（Y）；

將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹（N）；

用二叉樹的前序遍歷和中序遍歷可以導出樹的后序遍歷（Y）；

即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同（N）；

哈夫曼樹是帶權(quán)路徑長度最短的二叉樹，路徑上權(quán)值較大的結(jié)點離很較近（Y）。

11、表示一個有1000個頂點、1000條邊的有向圖的鄰接矩陣有1000000個矩陣元素，是否稀疏矩陣是

三、填空題

在帶有頭結(jié)點的單鏈表L中，第一個元素結(jié)點的指針是L->next。

在雙循環(huán)鏈表中，在指針p所指結(jié)點前插入指針s所指的結(jié)點，需執(zhí)行下列語

句：

s->next=p; s->prior=p->prior; p->prior=s;

_s->prior->next =s;

設(shè)s[1..maxsize]為一個順序存儲的棧，變量top指示棧頂位置，棧為空的條

件是top==0，棧為滿的條件是top==maxsize。

具有100個結(jié)點的完全二叉樹的深度為7。

有向圖G用鄰接矩陣A[1..n,1..n]存儲，其第i行的所有元素之和等于頂點i

的出度。

二、填空題（每空2分，共28分）

設(shè)r指向單鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入e所指的結(jié)點，需執(zhí)行的

三條語句是r->next=s; r=s；r—>next=NULL。

在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是p->next==null

設(shè)一個鏈棧的棧頂指針是ls，棧中結(jié)點格式為info;link;?？盏臈l件是ls==null°&"果棧不為空，則退棧操作為p=ls；ls=ls->link：free（p）。

已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹中有12個葉子結(jié)點。

樹有三種常用的存儲結(jié)構(gòu)，即孩子鏈表法，孩子兄弟鏈表法和雙親表示法。

n個頂點的連通圖的生成樹有比1條邊。

一個有向圖G中若有弧<vi,vj>、<vj,vk>和<vi,vk>，則在圖G的拓撲序列中，頂點vi,vjvk的相對位置為i,j,k

設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進行排序（按遞增順序）:冒泡最省時間，快速最費時間。

下面是將鍵值為x的結(jié)點插入到二叉排序樹中的算法，請在劃線處填上適當?shù)膬?nèi)容。

typedefstructpnode

}intkey；

structnode*left,*right；}

voidsearchinsert(intx;pnodet)

/*t為二叉排序樹根結(jié)點的指針*/

{if(t==null)

{p=malloc(size);

p->key=x;p->left=null;

p->right=null;t=p;

}

else

if(x<t->key)searchinsert(x,t->left)

elsesearchinsert(x,t->right)

}

線性表的循環(huán)鏈表的主要優(yōu)點是從表中任一結(jié)點出發(fā)都能訪問到所有的結(jié)點。而使用雙向鏈表，可根據(jù)需要在前后兩個方向上方便地進行查找。

在帶有頭結(jié)點的單鏈表L中，則需執(zhí)行下列三條語句：u=L->next；L一>next=u->next:free(u);

有一個長度為20的有序表采用二分查找方法進行查找，共有」個元素的查找長度為3。

采用冒泡排序?qū)τ衝個記錄的表A按鍵值遞增排序：若L的初始狀態(tài)是按鍵值遞增，則排序過程中記錄的比較次數(shù)為n-1。若A初始狀態(tài)為遞減排列，則記錄的交換次數(shù)為n(n-1)/2

在無頭結(jié)點的雙鏈表中，指針p所指結(jié)點是第一結(jié)點的條件是p->prior==null.

G為無向圖，如果從q的某個頂點出發(fā)，進行一次廣度優(yōu)先搜索，即可訪問圖的每個頂點，則該圖一定是連通圖。

如果一個有向圖中沒有環(huán)，則該圖的全部結(jié)點可以排成一個拓撲序列。

深度為8(根的層次號為1)的滿二叉樹有—個葉子結(jié)點。

將一棵有100個結(jié)點的完全二叉樹按層編號，則編號為49的結(jié)辰，其雙親PARENT(X)的編號為24。

設(shè)有一個鏈隊，結(jié)點結(jié)構(gòu)為data;next；front為隊頭指針，rear為隊尾指針，當執(zhí)行入隊操作時需執(zhí)行下列語句：malloc(D);D->data=x;D->next=null;rear->next=p;rear=p;

在散列法中，元素個數(shù)越多，發(fā)生沖突的可能性越大。

在帶有頭結(jié)點的單鏈表L中，第一個元素結(jié)點的指針是L->next。

在順序文件中，存取第i個記錄，必須先存取第I-1號元素。

設(shè)s[1..maxsize]為一個順序存儲的棧，變量top指示棧頂位置，棧為空的條件是top==0，棧為滿的條件是top==maxsize

具有64個結(jié)點的完全二叉樹的深度為7

有向圖G用鄰接矩陣A[1..N,1..N]存儲，其第I列的所有元素之和等于頂點I的入度。

在雙循環(huán)鏈表中，若要在指針P所指結(jié)點前插人指針S所指的結(jié)點，則需執(zhí)行下列語句s-〉next=p:s-〉prior=p-〉prior:p-〉prior=s:s-〉prior-〉next=p:

對于下圖所示二叉樹：按前序遍歷所得到的結(jié)點序列A，B，D，E，H，C，F(xiàn).

分別采用堆排序、快速排序、冒泡排序和歸并排序算法對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時間的是冒泡排序，最費時間的是快速算法。

7. 對于下面的二叉樹，按中序遍歷所得到的結(jié)點序列為。

8. 分別采用堆排序、快速排序、插入排序和歸并排序算法為初始狀態(tài)為遞增序

歹U的表按遞增順序排序，最省時間是算法，最費時間的是

算法。

9. 對下圖所示的網(wǎng)，執(zhí)行prim算法可得到最小生成樹，試在下表的空白處填

上適當?shù)膬?nèi)容，以說明該算法的執(zhí)行過程。

頂點

1

3

4

U

V

（U，V）代價

（2，1）

8

（2，3）

4

（2，4）

2

{2}

{1，3，4}

（U，V）代價

（2，3）

4

{2,4}

{1，3}

（U，V）代價

（3，1）

1

{2，4，3}

{1}

（U，V）代價

{2,4,3，1}

10、 設(shè)廣義表L=（（），（））則head（L）是（）；tail（L）是m；L的長度是二；

深度是2—

11、 在n個記錄的有序順序表中進行折半查找，最大的比較次數(shù)是燮。

在如圖所示的鏈表中，若在指針p所指的結(jié)點之后插入數(shù)據(jù)域值相繼為a和b的兩個結(jié)點，則可用下列兩個語句實現(xiàn)該操作，它們依次是S-〉NEXT-〉NEXT=P-〉NEXT和P->NEXT=S。

串S="Iamaworker〃的長度是14

假設(shè)一個10階的下三角矩陣A按列優(yōu)順序壓縮存儲在一維數(shù)組C中，則C數(shù)組的大小應(yīng)為55 。

在n個結(jié)點的線索二叉鏈表中，有n+1個線索指針。

對關(guān)鍵字序列（52，80，63，44，48，91）進行一趟快速排序之后得到的結(jié)果為48.44.52.63.80.91 。

三、應(yīng)用題

已知二叉樹的后跟序列和中根序列如下，構(gòu)造出該二叉樹。

后根序列：ABCDEFG

中根序列：ACBGEDF

有一組關(guān)鍵碼序列{8，9，5，3，7，2，1}，分別采用冒泡排序、快速排序、直接選擇排序、直接插入排序、二路歸并排序方法由小到大進行排序，在下面的選項中請選擇各種排序第一趟排序的結(jié)果。

冒泡排序：E

快速排序：A

直接選擇排序：B

直接插入排序：C

二路歸并：

F

A.{1，2，

5，3，7，8，9}

B.{1，9，

5，3，7，2，8}

C.{9，8，

5，3，7，2，1}

D.{9，5，

3，7，2，1，8}

E.{8，5，

3，7，2，1，9}

F.{8，9，

3，5，2，7，1}

設(shè)圖G=（V，E），V={1，2，3，4，5，6}，E={＜1，2＞，＜1，3＞，＜2，5＞，＜3，6＞，＜6,5＞，＜5,4＞，＜6,4＞}，請寫出圖G中頂點的所有拓撲序列。

設(shè)圖G=（V，E），V={1，2，3，4，5，6}，E={＜1，2＞，＜1，3＞，＜2，5＞，＜3，6＞，＜6,5＞，＜5,4＞，＜6,4＞}，請畫出其鄰接表，并說明每個頂點的入度和出度。

對如下所示的二叉樹，畫出其順序存儲結(jié)構(gòu)。

已知圖G的鄰接表如圖所示，畫出圖G的所有連通分量。

現(xiàn)有5個結(jié)點（A,B,C,D,E）,它們的權(quán)值分別為{5,10,12,15,30}，在下面

的選項中選擇一個編號，說明這5個結(jié)點的哈夫曼編碼。（2）

(1)

A：1,B

:001,C

:010,D:011,E

:000

(2)

A:000

B:001

C:010,D:011

E:1

(3)

A:001

B:011

C:010,D:000

E:1

(4)

A:000

B:1,C

:010,D:011,E

:001

已知一表為{23,45,24,6,57,45,35}，按表中順序依次插入初始為空的二叉排序樹，要求畫出建立的二叉排序樹。

設(shè)有序序列30,18,3,61,14,49，請按該序列構(gòu)成一棵二叉排序樹，并求其查找成功時的平均查找長度。

答：二叉排序樹：(3分)

平均查找長度二(1+2X2+3X2+4)*1/6

=2.5（2分）

對如下所示的交通網(wǎng)，頂點表示城市，邊表示連接城市間的公路，邊上的權(quán)表示修路的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案。

設(shè)有n個元素的有序表為A，K為一個給定的值，填空完成二分查找算法：binsrch(a,n,k)

inta[],k;

{intlow,hig,mid;

low=0;

hig=n;

while(low<=hig)

{mid=(low+hig)/2;

if(k<a[mid])hig=mid-1;

elseif(k==a[mid])low=hig+1;

elselow=mid+1;

}

if(a[mid]==k)

printf("\nsuccess\nthepositionof%dis%d\n”,k,mid);

else

printf("\nfall");

}

已知帶權(quán)圖的鄰接矩陣表示和鄰接表表示的形式說明分別如下：

#defineMaxNum50//圖的最大頂點數(shù)

#defineINFINITYINT_MAX//INT_MAX為最大整數(shù)，表示8

typedefstruct{

charvexs[MaxNum];//字符類型的頂點表

intedges[MaxNum][MaxMum];//權(quán)值為整型的鄰接矩陣

intn,e;//圖中當前的頂點數(shù)和邊數(shù)

}MGraph;//鄰接矩陣結(jié)構(gòu)描述

typedefstructnode{

intadjvex;//鄰接點域

intweight;//邊的權(quán)值

structnode*next;//鏈指針域

}EdgeNode;//邊表結(jié)點結(jié)構(gòu)描述

typedefstruct{

charvertex;//頂點域

EdgeNode*firstedge;//邊表頭指針

}VertexNode;//頂點表結(jié)點結(jié)構(gòu)描述

typedefstruct{

VertexNodeadjlist[MaxNum];//鄰接表

intn,e;//圖中當前的頂點數(shù)和邊數(shù)

}ALGraph;//鄰接表結(jié)構(gòu)描述

下列算法是根據(jù)一個帶權(quán)圖的鄰接矩陣存儲結(jié)構(gòu)G1建立該圖的鄰接表存儲結(jié)構(gòu)G2,請?zhí)钊牒线m的內(nèi)容，使其成為一個完整的算法。

voidconvertM(MGraph*G1,ALGraph*G2)

{

inti,j;

EdgeNode*p;

G2->n=G1->n;

G2->e=G1->e;

for(i=0;i<G1->n;i++)

{

G2->adjlist[i].vertex=G1->vexs[i];

G2->adjlist[i].firstedge=(1) ;

}

for(i=0;i<G1->n;i++)

for(j=0;j<G1->n;j++)

if(G1->edges[i][j]<INFINITY)

{

p=(EdgeNode*)malloc(sizeof(EdgeNode));

p->weight=(2) ;

p->adjvex=j;

p->next=G2->adjlist[i].firstedge;

(3) ;

}

}

NULL

G1->edges[i][j]

G2->adjlist[i].firstedge=p

33.閱讀下列算法，并回答下列問題：

(1)該算法采用何種策略進行排序？插入排序

(2)算法中R[n+1]的作用是什么？監(jiān)視哨

Typedefstruct{

KeyTypekey;

infoTypeotherinfo;

}nodeType;

typedefnodeTypeSqList[MAXLEN];

voidsort(SqListR,intn)

{

//n小于MAXLEN-1

intk;i;

for(k=n-1;k>=1;k--)

if(R[k].key>R[k+1].key)

{

R[n+1]=R[k];

for(i=k+1;R[i].key<R[n+1].key;i++)

R[i-1]=R[i];

R[i-1]=R[n+1];

}

}

設(shè)某二叉樹以二叉鏈表為存儲結(jié)構(gòu)，請寫出求其高度的遞歸算法。

答：voidBTdepth(BinTreeBT,inth)

(

inthr,h1;

if(BT==null)h=0; (1分)

else

(

BTdepth(BT-lchild,h1);2分

BTdepth(BT^rchild,hr);

if(h1>=hr)h=h1+1; 2分

elseh=hr+1

}

}

1、 ListInsert_L(LinkListL,intpos,ElemTypee)

//在帶頭結(jié)點的單鏈表L中第pos個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e

StatusListInsert_L(LinkListL,intpos,ElemTypee)

(

p=L;j=0;

while(p&&j<pos-1)

(p=p->next;++j;}//尋找第pos-1個結(jié)點

if(!p||j>pos-1)

returnERROR;//pos小于1或者大于表長

s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點

s->data=e;s->next=p->next;//插入L中

p->next=s;

returnOK;

}

2、 voidMerge(ElemSR[],ElemTR[],inti,intm,intn)

(

//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]

for(j=m+1,k=i;i<=m&&j<=n;++k)

(//將SR中記錄由小到大地并入TR

if(SR[i].key<=SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];

}

if(i<=m)TR[k..n]=SR[i..m];

//將剩余的SR[i..m]復制到TR

if(j<=n)TR[k..n]=SR[j..n];

//將剩余的SR[j..n]復制到TR

}//Merge

3、

intPartition(ElemR[],intlow,inthigh)

(//交換記錄子序列R[low..high]中的記錄，使樞軸記錄到位，并返回〃其所

在位置，此時，在它之前(后)的記錄均不大(小)于它

R[0]=R[low];//用子表的第一個記錄作樞軸記錄

pivotkey=R[low].key;//樞軸記錄關(guān)鍵字

while(low<high)

//從表的兩端交替地向中間掃描

while(low<high&&R[high].key>=pivotkey)

—high;

R[low]=R[high];//將比樞軸記錄小的記錄移到低端

while(low<high&&R[low].key<=pivotkey)

++low;

R[high]=R[low];//將比樞軸記錄大的記錄移到高端

}

R[low]=R[01;//樞軸記錄到位

returnlow;//返回樞軸位置

}//Partition

4、 折半查找算法：

intbinsrch(JDr[],intn,intk)

(intlow,high,mid,found;

low=1;high=n;found=0;

while((low<=high)&&(found==0))

(mid=(low+high)/2;

if(k>r[mid].key)low=mid+1;

elseif(k==r[mid].key)found=1;

elsehigh=mid-1;

}

if(f