數(shù)據(jù)結(jié)構(gòu)課后部分習(xí)題答案

第1章緒論

1.填空

⑴數(shù)據(jù)元素⑵數(shù)據(jù)項(xiàng)，數(shù)據(jù)元素【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。

⑶集合，線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu)

⑷順序存儲(chǔ)結(jié)構(gòu)，鏈接存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系

⑸有零個(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出，有窮性，確定性，可行性

⑹自然語言，程序設(shè)計(jì)語言，流程圖，偽代碼，偽代碼

⑺問題規(guī)模⑻0(1),o(nlog2n)【分析】用大。記號(hào)表示算法的時(shí)間復(fù)雜度，需要將低次第去掉，將

最高次塞的系數(shù)去掉。

2.選擇題

⑴3D【分析】順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲(chǔ)位置(即元

素在數(shù)組中的下標(biāo))表示；鏈接存儲(chǔ)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，元素之間的邏輯關(guān)系由

結(jié)點(diǎn)中的指針表示。

(2)B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。

圖1-2遺產(chǎn)繼承邏輯結(jié)構(gòu)圖

(6)A【分析】計(jì)算機(jī)程序是對(duì)算法的具體實(shí)現(xiàn)：簡(jiǎn)單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算

法完成的。所以，只有A是算法的準(zhǔn)確定義。

(7)C【分析】高效性是好算法應(yīng)具備的特性。(8)C,E

3.判斷題

⑴錯(cuò)。時(shí)間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級(jí)來確定。

⑵錯(cuò)。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。

⑶錯(cuò)。是數(shù)據(jù)之間的邏輯關(guān)系的整體。

⑷對(duì)。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。

⑸錯(cuò)?；静僮鞯膶?shí)現(xiàn)是基于某種存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的，因而不是唯?的。

4.(1)基本語句是k=k+10*i,共執(zhí)行了n-2次，所以T(基本(n)。(2)基本語句是k=k+10*i,共執(zhí)行了n

次,所以T(以=0(n)。(3)分析條件語句，每循環(huán)一次，i+j整體加1,共循環(huán)n次,所以T(n)=0(n)。(4)

設(shè)循環(huán)體共執(zhí)行T(n)次,每循環(huán)一次,循環(huán)變量y加1,最終T(n)=y,即：(T(n)+1)2Wn,所以T(n)=0(nl/2)。

r(?)=ESS1=O(M3)

(5)x++是基本語句，所以i-lj-W-l

5.(1)其邏輯結(jié)構(gòu)圖如圖卜3所示，它是一種圖結(jié)構(gòu)。

(2)整數(shù)的抽象數(shù)據(jù)類型定義如下:

ADTinteger

Data

整數(shù)a：可以是正整數(shù)(1,2,3,…)、負(fù)整數(shù)(T,-2,-3,…)和零

Operation

Constructor

前置條件：整數(shù)a不存在

輸入：一個(gè)整數(shù)b

功能：構(gòu)造一個(gè)與輸入值相同的整數(shù)

輸出：無

后置條件：整數(shù)a具有輸入的值

Set

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同

輸出：無

后置條件：整數(shù)a的值發(fā)生改變

Add

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相加

輸出：相加后的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Sub

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相減

輸出：相減的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Multi

前置條件：存在?個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相乘

輸出：相乘的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Div

前置條件-：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：將整數(shù)a與輸入的整數(shù)b相除

輸出：若整數(shù)b為零，則拋出除零異常，否則輸出相除的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Mod

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù)

輸出：若整數(shù)b為零，則拋出除零異常，否則輸出取模的結(jié)果

后置條件：整數(shù)a的值發(fā)生改變

Equal

前置條件：存在一個(gè)整數(shù)a

輸入：一個(gè)整數(shù)b

功能：判斷整數(shù)a與輸入的整數(shù)b是否相等

輸出：若相等返回1,否則返回0

后置條件：整數(shù)a的值不發(fā)生改變

endADT

(3)第二種算法的時(shí)間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化，減少

了不必要的乘法運(yùn)算。

6、⑴【解答】下面是簡(jiǎn)單選擇排序算法的偽代碼描述。

國/對(duì)n個(gè)記錄進(jìn)行n-1趟簡(jiǎn)單選擇排序：

1.1在無序區(qū)[i，nT]中選取最小記錄，設(shè)其下標(biāo)為index；

[1.2將最小記錄與第1個(gè)記錄交換；

下面是簡(jiǎn)單選擇排序算法的C++描述。

簡(jiǎn)單選擇排序算法Selectsort

voidSdectSort(intr[],intn)

(

for(i=0,i<n-l;1++)網(wǎng)n個(gè)記錄進(jìn)行n-1趟簡(jiǎn)單選擇排序

(

index=i;

far(j=i+1;j<n,j++)”在無序區(qū)中選取最小記錄

if(r[j]<r[index])index=j,

if(index!=i)r[i]-<—[index];/皮換元素

)

}

n-2n-1、

T(ri)=ESI=0(n2}

分析算法，有兩層嵌套的for循環(huán)，所以，J-°>!+1。

⑵算法的偽代碼描述如下：

84將前兩個(gè)元素進(jìn)行比較，較大者放至1max中，較小者放到nrnax中；

.2.從第3個(gè)元素開始直到最后一個(gè)元素依次取元素A[i],執(zhí)行下列操作:

2.1如果A[i]>max,則A[i]為最大值，原來的最大值為次最大值；

2.2否則，如果A[i]>nmax,則最大值不變，A[i]為次最大值；

3.輸出最大值max,次最大值nmax；

算法的C++描述如下:

最大值和次最大值算法Max_NextMax[

voidMax_NextMax(intA[],intn,int&max,int&nmax)

(

if(A[O]>=A[1])(

max=A[0];

nmax=A[l];

)

else(

max=A[l];

nmax=A[0];

)

for(i=2;i<n;i++)

if(A[i]>=max){

nrnax==max;

max=A[i];

)

elseif(A[i]>nmax)nmax=A[i];

村山〈〈”最大值關(guān))："<<10的<<"也次最大值為："<<nniax<<endl;

}

分析算法，只有一層循環(huán)，共執(zhí)行n-2次，所以，T(n)=0(n)。

第2章線性表

填空

1.⑴表長的一半，表長，該元素在表中的位置⑵108第5個(gè)元素的存儲(chǔ)地址=第1個(gè)元素的存儲(chǔ)地址

+(5—1)x2=108(3)p->next=(p->next)->next

⑷為了運(yùn)算方便例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。

⑸p->next=head如圖2-8所示。

圖2-8尾結(jié)點(diǎn)p與頭指針head的關(guān)系示意圖

(6)s->next=rear->next;rear->next=s;rear=s;q=rear->next->next;rear->next->next=q->next;

deleteq;操作示意圖如圖2-9所示：

q

?

rearrear;s

圖2-9帶尾指針的循環(huán)鏈表中插入和刪除操作示意圖

(7)0(1),0(n)在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針，所以時(shí)間復(fù)雜度為。(1)；而在給定值為x

的結(jié)點(diǎn)后插入?個(gè)新結(jié)點(diǎn)需要先查找值為x的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為0(n)。

⑻循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表

2.選擇題⑴【解答】AfB【分析】參見2.2.1。

⑵【解答】D【分析】線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)

單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。⑶【解答】B(4)【解答】A

⑸【解答】A【分析】線性表中最常用的操作是取第i個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，

同時(shí)在順序表中查找第i個(gè)元素的前趨也很方便o單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元

素的前趨也不方便，雙鏈表雖然能快速查找第i個(gè)元素的前趨，但不能實(shí)現(xiàn)隨機(jī)存取。

(6)【解答】D【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單

鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)

間性能是0(1),所以，答案是D。

⑺【解答】B【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈

表、單循環(huán)鏈表都不合適，刪除最后一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址，所以，帶尾指針的單

循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。

(8)【解答】B【分析】首先應(yīng)順序查找新結(jié)點(diǎn)在單鏈表中的位置。

⑼【解答】C【分析】該算法需要將n個(gè)元素依次插入到有序單鏈表中，而插入每個(gè)元素需0(n)。

(10)【解答】B【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因?yàn)殡p鏈表

中有兩個(gè)指針域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空間的速度是一樣的。由于雙鏈

表具有對(duì)稱性，所以，其插入和刪除操作更加方便。

卬)【解答】B【分析】注意此題是在q和p之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的順序。

(13【解答】D【分析】在鏈表中，對(duì)指針的修改必須保持線性表的邏輯關(guān)系，否則，將述背線性表的邏

輯特征，圖2-10給出備選答案C和D的圖解。

(a)備選答案C操作示意圖(第4步指針修改無法進(jìn)行)(b)備選答案D操作示意圖

圖2-10雙鏈表插入操作修改指針操作示意圖

3.判斷題

⑴錯(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。

⑵錯(cuò)。兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。

⑶錯(cuò)。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。

⑷錯(cuò)。每個(gè)元素最多只有?個(gè)直接前驅(qū)和個(gè)直接后繼，第個(gè)元素沒有前驅(qū)，最后?個(gè)元素沒有后繼。

⑸錯(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。

4.【解答】順序表的優(yōu)點(diǎn)：①無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；②可以快

速地存取表中任一位置的元素(即隨機(jī)存取)。順序表的缺點(diǎn)：①插入和刪除操作需移動(dòng)大量元索；②表

的容量難以確定；③造成存儲(chǔ)空間的''碎片"。

單鏈表的優(yōu)點(diǎn)：①不必事先知道線性表的長度；②插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單

鏈表的缺點(diǎn)：①指針的結(jié)構(gòu)性開銷：②存取表中任意元素不方便，只能進(jìn)行順序存取.

⑴應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進(jìn)行插入和刪除

操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。

⑵應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長度動(dòng)態(tài)發(fā)生變化。

⑶應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。因?yàn)閭€(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常修改、擴(kuò)充和刪除各種信息,

才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。

5.算法設(shè)計(jì)

⑴算法思想請(qǐng)參見主教材第一章思想火花。下面給出具體算法。

循環(huán)右移算法Converse

voidConverse(intA[],intn,intk)

(

Reverse(A,0,k-l);

Reverse(A,k,n-1);

Reverse(A,0,n-l);

}

voidReverse(intA[],intfrom,intto)陽數(shù)組A中元素從from到to逆置

(

for(i=0,i<(to-from+l)/2;i++)

A[from+i]"<-*A[to-i];佼換元素

2__________________________________

分析算法,第一次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(k),第二次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n-k),

第三次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n),所以，總的時(shí)間復(fù)雜度為O(n)。

⑵從數(shù)組的兩端向中間比較，設(shè)置兩個(gè)變量i和j,初始時(shí)i=0,j=n-l,若A[i]為偶數(shù)并且A[j]為奇數(shù)，則

將A[i]與A[j]交換。

數(shù)組奇偶調(diào)整算法Adjust]

voidAdjust(intA[],n)

(

i=0;j=n-l;

while(i<j)

(

while(A[i]%21=0)i++;

while(A[j]%2=0)j—

if(i<j)

)

)

分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時(shí)間復(fù)雜度為o(n)。

⑶參見2.2.3。

⑷順序表的逆置，即是將對(duì)稱元素交換，設(shè)順序表的長度為length,則將表中第i個(gè)元素與第length-i-1個(gè)

元素相交換。具體算法如下：

順序表逆置算法Reverse[

template<classT>

voidReverse(Tdata[],intlength)

(

for(i=0;i<=length/2;i++)

(

temp=data[i];

data[i]=data[length-i-1];

data[length-i-l]=temp;

)

J_________________________________

單鏈表的逆置請(qǐng)參見2.2.4算法2-4和算法2-6o

⑸利用單循環(huán)鏈表的特點(diǎn)，通過指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p,然后將結(jié)點(diǎn)門則除，如圖

2?11所示，具體算法如下：

循環(huán)矮表刪除算法D祖|

template<classT>

voidDel(Node<T>*s)

(

p=s；力工作指針p初始化，查找s的前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，用p指示

while(p->next->next!=s)

p=p->next;

r=p->next;fix為p的前驅(qū)結(jié)點(diǎn)，q為r的前驅(qū)結(jié)點(diǎn)

p->next=s;/姍除r所指結(jié)點(diǎn)

deleter;

)

圖2-11刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)操作示意圖

⑹在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表B中，若取出的元素是數(shù)字，則

把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B,D,A中分別存放字母、數(shù)字和其他字符。具體算

法如F：

單鞋表拆分算法Adjust

template<classT>

voidAdjust(Node<T>*A,Node<int>*D,Node<char>*B)

(

D=newNode<int>;D->next=D;"創(chuàng)建空循環(huán)鏈表D,存放數(shù)字

B=newNode<char>;B->next=B;//創(chuàng)建空循環(huán)鏈表B,存放字符

p=A;q=p->next;0工作指針q初始化

while(q)

(

if((,A,<=q->data)&&(q->data>='Z,)||('a1<=q->data)&&(q->data>-z')){

p->next=q->next;

q->next=B->next;

B->next=q;力采用頭插法插在循環(huán)鏈表B的頭結(jié)點(diǎn)的后面

)

elseif(C0,<=q->data)&&(q->data>=,91)){

p->next=q->next;

q->next=D->next;

D->next=q,/探用頭插法插在循環(huán)鏈表D的頭結(jié)點(diǎn)的后面

)

elsep=q,

q=p->next;

)

p->next=A;R=A;俯鏈表A構(gòu)造為循環(huán)鏈表，為除字母和數(shù)字的其他字符

}

⑺從頭到尾掃描單鏈衣，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除該后繼

結(jié)點(diǎn).具體算法如下：

單鏈表刪除相同值算法Purge

voidPurge(Node<T>*first)

(

p=first->next;

while(p->next)

if(p->data==p->next->data){

q=p->next;

p->next=q->next,

deleteq;

)

dsep=p->next;

)

⑻設(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等，則工

作指針p后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點(diǎn)(循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù))，

或結(jié)點(diǎn)q成為結(jié)點(diǎn)p的前驅(qū)(循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù))。如圖2-12所示。

圖2-12判斷循環(huán)雙鏈表對(duì)稱的操作示意圖

判斷雙犍表對(duì)稱算法Equal

template<classT>

structDulNode

(

Tdata;

DulNode<T>*prior,*next;

)；

template<classT>

boolEqual(DulNode<T>*first)

(

p=first->next,q=first->prior,

while(p!=q&&p->prior!=q)

if(p->data==q->data){

p=p->next;//工作指針p后移

q=q->prior;。工作指針q前移

)

elsereturn0;

return1;

)

第3章特殊線性表一棧、隊(duì)列和串

i.填空

⑴設(shè)有一個(gè)空棧，棧頂指針為1000H,現(xiàn)有輸入序列為L2、3,4、5,經(jīng)過push,push,pop.push,

pop,push,push后，輸出序列是()，棧頂指針為()。

【解答】23,1003H

⑵順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)(或順序棧和鏈棧)，棧頂指針top=-1和top=NULL,棧頂指針top

等于數(shù)組的長度和內(nèi)存無可用空間

⑶?！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。

⑷abc+*d-【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫下來，再將算符插在它

的兩個(gè)操作數(shù)的后面。

⑸后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同⑹假溢出

⑺(rear-front+n)%n【分析】也可以是(rear-front)%n,但rear-front的結(jié)果可能是負(fù)整數(shù)，而

對(duì)一個(gè)負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境卜可能會(huì)有所不同。

(8)0(1),0(n)【分析】在帶頭指針的循環(huán)鏈表中，出隊(duì)即是刪除開始結(jié)點(diǎn)，這只需修改相應(yīng)指針：入

隊(duì)即是在終端結(jié)點(diǎn)的后面插入?個(gè)結(jié)點(diǎn)，這需要從頭指針開始查找終端結(jié)點(diǎn)的地址。

2.選擇題

(1)C【分析】此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序(指的

是元素的序號(hào))的兩個(gè)元素。

(2)D【分析】此時(shí)，輸出序列一定是輸入序列的逆序。

(4)B【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。

(5)B【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。

(6)B【分析】隊(duì)列的入隊(duì)順序和出隊(duì)順序總是一致的。

⑺D【分析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，

但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問題時(shí)包含的運(yùn)算都可能不同。

⑻A【分析】?jī)蓷９蚕砜臻g首先兩個(gè)棧是相向增長的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，

并注意C++中的數(shù)組下標(biāo)是從0開始的。

(9)C【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、

e3、e6、e5、el。

3.判斷題

(2w)l

⑴【解答】錯(cuò)。應(yīng)該有6+1)(川)種。(2)【解答】對(duì)。只要操作滿足后進(jìn)先出性，都可以采用棧作

為輔助數(shù)據(jù)結(jié)構(gòu)。

⑶【解答】對(duì)。⑷【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。

4.(1)【解答】⑴不能，因?yàn)樵贑、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B

出棧。⑵可以，設(shè)I為進(jìn)棧操作，0為入棧操作，則其操作序列為nioooioio。

(2)假設(shè)有一個(gè)順序隊(duì)列，如圖3-6所示，隊(duì)尾指針rear=4,隊(duì)頭指針front=l,如果再有元素入隊(duì)，

就會(huì)產(chǎn)生''上溢"，此時(shí)的‘'上溢"又稱為''假溢出"，因?yàn)殛?duì)列并不是真的溢出了，存儲(chǔ)隊(duì)列的數(shù)組中還有2

個(gè)存儲(chǔ)單元空閑，其下標(biāo)分別為。和1。

rear

圖3-6順序隊(duì)列的假溢出(3)棧頂元素為6,棧底元素為1。其執(zhí)行過程如圖3?7所示。

入棧出棧

76

55

11

(a)push(1)pushQ)(b)pop?push(5)?push(7)(c)pop?push(6)

圖3-7棧的執(zhí)行過程示意圖(4)隊(duì)頭元素為5,隊(duì)

尾元素為9。其執(zhí)行過程如圖3-8所示。

(a)EnQueue(1)iEnQueue(3)(b)DeQueue，EnQueue(5)>EnQueue(7)(c)DeQueue^EnQueue(9)

圖3-8隊(duì)列的執(zhí)行過程示意圖5、

算法設(shè)計(jì)⑴出隊(duì)操作是在循環(huán)鏈表的頭部進(jìn)行，相當(dāng)于刪除開始結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部

進(jìn)行，相當(dāng)于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。由于循環(huán)鏈表不帶頭結(jié)點(diǎn)，需要處理空表的特殊情況。

入隊(duì)算法如卜.:

循環(huán)隊(duì)列入隊(duì)算法Enqueue]

template<classT>

voidEnqueue(Node<T>*rear,Tx)

(

s=newNode<T>;

s->data=x;

if(rear-=NULL)("處理空表的特殊情況

rear=s;

rear->next=s;

)

else{。處理除空表以外的一般情況

s->next=rear->next;

rear->next=s;

rearms;

)

)

出隊(duì)算法如下:

循尻隊(duì)列出隊(duì)算售Dequeue]

template<classT>

TDequeue(Node<T>*rear)

(

if(rear==NULL)throw'?underflow";例斷表空

else(

s=rear->next;

if(s==rear)rear=NULL;傀S表中只有一個(gè)結(jié)點(diǎn)

elserear->next=s->next,

deletes;

)

)

⑵操作步驟為：

①將所有元素出棧并入隊(duì)：②依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn)，則再入隊(duì)，如果是奇數(shù)結(jié)點(diǎn)，

則入棧；③將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)；④將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧；⑤將所有元素出棧并入隊(duì)；⑥將所

有元素出隊(duì)并入棧即為所求。

第4章廣義線性表一多維數(shù)組和廣義表

i.填空

(3)存取，修改，順序存儲(chǔ)【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能

做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。

(4)1140【分析】數(shù)組A中每行共有6個(gè)元素，元素A[15][10]的前面共存儲(chǔ)了(15-10)x6+5個(gè)元素，

每個(gè)元素占4個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是1000+140=1140。

(5)d+41【分析】元素A[8]⑸的前面共存儲(chǔ)了(1+2+...+8)+5=41個(gè)元素。

(6)三元組順序表，十字鏈表

2.選擇題

(2)D,E,K【分析】數(shù)組A為9行10列，共有90個(gè)元素，所以，存放A至少需要90x6=540個(gè)存

儲(chǔ)單元，第8列和第5行共有18個(gè)元素(注意行列有一個(gè)交叉元素)，所以，共占108個(gè)字節(jié)，元素

A[8][5]按行優(yōu)先存儲(chǔ)的起始地址為d+8xl0+5=d+85,設(shè)元素按列優(yōu)先存儲(chǔ)的起始地址與之相

同，則d+jx9+i=d+85,解此方程，得i=4,j=9。

(3)B(4)C【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是確定的，

所以，數(shù)組通常沒有插入和刪除操作。

(5)D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素

重復(fù)存儲(chǔ)。(6)C

(7)D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲(chǔ)。如果零元素的分

布有規(guī)律，就沒有必要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。

3.判斷題

⑴【解答】錯(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。

⑵【解答】對(duì)。因?yàn)槿M表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。

⑶【解答】對(duì)。因?yàn)閴嚎s存儲(chǔ)后，非零元素的存儲(chǔ)位置和行號(hào)、列號(hào)之間失去了確定的關(guān)系。

4.?個(gè)稀疏矩陣如圖4-4所示，寫出對(duì)應(yīng)的三元組順序表和十字鏈表存儲(chǔ)表示。

0020

3000

00-15

0000

圖4-4稀疏矩陣

【解答】對(duì)應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。

圖4-6稀疏矩陣的十字鏈表

5、(2)【解答】在矩陣中逐行尋找該行中的最小值，然后對(duì)其所在的列尋找最大值，如果該列上的最

大值與該行上的最小值相等，則說明該元素是鞍點(diǎn)，將它所在行號(hào)和列號(hào)輸出。具體算法如下：

馬軟,E算法Andian]

voidAndian(inta[][],intm,intn)

(

for(i=0,i<n,i++)

(

d=a[i][0];k=0,l/d為第i行中的最小值

for(j=l;j<m;j++)

if(a[i][j]<d){

k=i；

)，門臼因?yàn)榈趇行最小值

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

if(a[j][k]>d)break,

if(j==n)coutcv輸出鞍點(diǎn)a[i][k];

)

分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個(gè)for循環(huán)執(zhí)行m次，第二個(gè)for循環(huán)最壞情況下執(zhí)行

n次，所以，最壞情況下的時(shí)間復(fù)雜度為0(mn+n2)。

第5章樹和二叉樹

1.填空題

⑴有且僅有?個(gè)，互不相交⑵度，孩子，雙親

(3)2i-l,(n+l)/2,(n-l)/2【分析】設(shè)滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為nO,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,由于滿

二叉樹中不存在度為1的結(jié)點(diǎn)，所以n=n0+n2；由二叉樹的性質(zhì)n0=n2+l,得n0=(n+l)/2,n2=(n-l)/2。

(4)2h-1,2h”【分析】最小結(jié)點(diǎn)個(gè)數(shù)的情況是第1層有1個(gè)結(jié)點(diǎn)，其他層上都只有2個(gè)結(jié)點(diǎn)。

(5)2k-l【分析】在滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)達(dá)到最多。

⑹50【分析】100個(gè)結(jié)點(diǎn)的完全二叉樹中最后一個(gè)結(jié)點(diǎn)的編號(hào)為100,其雙親即最后一個(gè)分支結(jié)點(diǎn)的編號(hào)

為50,也就是說，從編號(hào)51開始均為葉子。

(7)12【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+l(n0、n2、n3分別為葉子結(jié)點(diǎn)、度為2

的結(jié)點(diǎn)和度為3的結(jié)點(diǎn)的個(gè)數(shù))。

⑻CDBGFEA【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。

⑼2n,n-1,n+1⑩n,n-1【分析】n-1個(gè)分支結(jié)點(diǎn)是經(jīng)過n-1次合并后得到的。

2、選擇題

⑴D⑵D【分析】此題并沒有指明是完全二叉樹，則其深度最多是n,最少是h°g2T+io

(3)B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。

(4)C【分析】線索二叉樹中某結(jié)點(diǎn)是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是

否為1。

⑸B,c【分析】深度為k的完全二叉樹最少結(jié)點(diǎn)數(shù)的情況應(yīng)是第k層上只有1個(gè)結(jié)點(diǎn)，最多的情況是滿

二叉樹，編號(hào)最小的葉子應(yīng)該是在結(jié)點(diǎn)數(shù)最少的情況下，葉子結(jié)點(diǎn)的編號(hào)。

⑹D【分析】滿二叉樹中沒有度為1的結(jié)點(diǎn)，所以有m個(gè)葉子結(jié)點(diǎn)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為m-E

(7)A【分析】三種遍歷次序均是先左子樹后右子樹。(8)A,B

⑼D,A【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點(diǎn)即為第?棵樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹是由第一棵樹中

除了根結(jié)點(diǎn)以外其余結(jié)點(diǎn)組成的，根結(jié)點(diǎn)的右子樹是由森林中除第一棵樹外其他樹轉(zhuǎn)換來的。⑩B

3.判斷題

⑴錯(cuò)。某結(jié)點(diǎn)是否有前驅(qū)或后繼的線索，取決于該結(jié)點(diǎn)的標(biāo)志域是否為1。

⑵對(duì)。由前序遍歷的操作定義可知。

⑶錯(cuò)。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為L

⑷對(duì)。因?yàn)楦Y(jié)點(diǎn)無兄弟結(jié)點(diǎn)。

⑸錯(cuò)。二叉樹的順序存儲(chǔ)結(jié)構(gòu)是按層序存儲(chǔ)的，一般適合存儲(chǔ)完全二叉樹。

4.(1)因?yàn)樵跐M二叉樹中沒有度為1的結(jié)點(diǎn)，所以有：

n=n0+n2

設(shè)B為樹中分枝數(shù)，則

n=B+l

所以

B=nO+n2-l

再由二叉樹性質(zhì)：

n0=n2+l

代入上式有：

B=n0+n0-l-l=2(n0-l)

（2）【解答】證明采用歸納法。

設(shè)二叉樹的前序遍歷序列為ala2a3…an,中序遍歷序列為bib2b3…bn。

當(dāng)n=l時(shí)，前序遍歷序列為al,中序遍歷序列為bl,二叉樹只有一個(gè)根結(jié)點(diǎn)，所以，al=bl,可以唯一

確定該二叉樹；

假設(shè)當(dāng)n<=k時(shí)，前序遍歷序列ala2a3…ak和中序遍歷序列bib2b3...bk可唯一確定該二叉樹，下面證

明當(dāng)n=k+l時(shí),前序遍歷序列ala2a3...akak+l和中序遍歷序列bib2b3...bkbk+1可唯一確定一棵二叉

樹。

在前序遍歷序列中第一個(gè)訪問的一定是根結(jié)點(diǎn)，即：叉樹的根結(jié)點(diǎn)是al,在中序遍歷序列中杳找值為al

的結(jié)點(diǎn)，假設(shè)為bi,則al=bi且blb2...bi-1是對(duì)根結(jié)點(diǎn)al的左子樹進(jìn)行中序遍歷的結(jié)果，前序遍歷序列

a2a3...ai是對(duì)根結(jié)點(diǎn)al的左子樹進(jìn)行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3...ai和中序遍歷

序列blb2...bi-1唯一確定了根結(jié)點(diǎn)的左子樹，同樣可證前序遍歷序列ai+lai+2...ak+1和中序遍歷序列

bi+lbi+2...bk+1唯一確定了根結(jié)點(diǎn)的右子樹。

（3）【解答】設(shè)該樹的總結(jié)點(diǎn)數(shù)為n,則

n=n0+nl+n2+……+nm

又：

n=分枝數(shù)+l=0xn0+lxnl+2xn2++mxnm+l

由上述兩式可得：

nO=n2+2n3+……+（m-l）nm+l

（4）二叉樹的構(gòu)造過程如圖5-12所示。

圖5-12構(gòu)造二叉樹的過程

（5）.構(gòu)造的哈夫曼樹如圖5-13所示。

圖5T3構(gòu)造的哈夫曼樹及帶權(quán)路徑長度

樹的帶權(quán)路徑長度為：

WPL=2x4+3x4+5x3+7x3+8x3+9x2+llx2=120

（6）.以各字符出現(xiàn)的次數(shù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼編碼樹如圖5-14所示。其帶權(quán)路徑長度

=2x5+1x5+3x4+5x3+9x2+4x3+4x3+7x2=98,所以，該字符串的編碼長度至少為98位。

35

5.算法設(shè)計(jì)

⑴木算法不是要打印每個(gè)結(jié)點(diǎn)的值，而是求出結(jié)點(diǎn)的個(gè)數(shù)。所以可將遍歷算法中的''訪問"操作改為''計(jì)數(shù)操

作“，將結(jié)點(diǎn)的數(shù)目累加到一個(gè)全局變量中，每個(gè)結(jié)點(diǎn)累加一次即完成了結(jié)點(diǎn)個(gè)數(shù)的求解。

具體算法如下：

求二叉樹結(jié)點(diǎn)個(gè)數(shù)算法Co;T]

voidCount(BiNode*root)//n為全局量并已初始化為0

{

if(root)(

Count(root->lchild);

n++;

Count(root->rchild);

)

)

⑵【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，

不同之處是此處不是打印每個(gè)結(jié)點(diǎn)的值，而是打印出其中的葉子結(jié)點(diǎn)，即為有條件打印。為此，將前序遍

歷算法中的訪問操作改為條件打印即可。算法如下：

打印葉子結(jié)點(diǎn)算法Predrdl]

voidPreOrder(BiNode*root)

(

if(root){

if(!root->lchild&&!root->rchild)cout?root->data;

PreOrder(root->lchild);

PreOrder(root->rchild);

}

)

⑶【解答】當(dāng)二又樹為空時(shí)，深度為0；若二叉樹不為空，深度應(yīng)是其左右子樹深度的最大值加1,而其

左右子樹深度的求解又可通過遞歸調(diào)用本算法來完成。具體算法如下：

求二叉樹深度算法Depth1

intDepth(BiNode*root)

(

if(!root)return0;

else{

hl=Depth(root->lchild);

hr=Depth(root->rchild);

returnmax(hl,hr)+1;

}

)

(4)【解答】要想得到后序的逆序，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點(diǎn)，再遍歷根結(jié)點(diǎn)的

右子樹，最后遍歷根結(jié)點(diǎn)的左子樹。注意和前序遍歷的區(qū)別，具體算法如下：

房序的逆序通歷算法PostQrder[

voidPostOrder(BiNode*root)

(

if(root)(

cout?root->data,

PostOrder(root->rchild);

PostOrder(root-"child);

)

}

⑸【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點(diǎn)x并記載其雙親。具體算法如下：

五:找某■結(jié)點(diǎn)的雙親算法ParenQ

BiNode*Parent(BiNo加*root,Tx)//p是全局量，初值為空

(

if(root){

if(root->data==x)retump;

else{

p=root,

Parent(root->lchild,x);

Parent(root->rchild,x);

)

)

)

⑹【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點(diǎn)x并記載其雙親，然后將結(jié)點(diǎn)x的雙親結(jié)點(diǎn)中

指向結(jié)點(diǎn)X的指針置空。具體算法如下：

刪除結(jié)點(diǎn)x?算法Delete[

voidDelete(BiNode*root,Tx)ffp是全局量，初值為空

(

if(root)(

if(root->data==x)

if(!p)root=NULL;

dseif(p->lchild==root)p->lchild=NULL;

elsep->rchild=NULL,

else(

p=rooU

Delete(root->lchild,x);

Delete(root->rchild,x);

)

)

⑺【解答】按照題目要求，設(shè)置一個(gè)工作棧以完成對(duì)該樹的非遞歸算法，思路如下：

①每訪問一個(gè)結(jié)點(diǎn)，將此結(jié)點(diǎn)壓棧，查看此結(jié)點(diǎn)是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過程直到

左子樹為空。

②從棧彈出一個(gè)結(jié)點(diǎn)，如果此結(jié)點(diǎn)有右子樹，訪問右子樹執(zhí)行步驟①，否則重復(fù)執(zhí)行步驟②。

具體算法如下：

順序存儲(chǔ)的前序遍歷靠法Exchange|

template<classT>

voidPreOrder(TA[],intn)

{

top-1;俄初始化，采用順序棧并假定不會(huì)發(fā)生溢出

i=l;cout?A[i];S[++top]=i;

J=2*i;

while(top!=-l)

(

while(j<=n)

(

cout?A[j];

S[++top]=j;

H；j=2*i;

}

i=S[top-];

i=2*i+l;

)

}

(8)【解答】對(duì)二叉樹進(jìn)行后序遍歷，在遍歷過程中訪問某結(jié)點(diǎn)時(shí)交換該結(jié)點(diǎn)的左右子樹。

具體算法如下：

交換左右干樹算法Exchange

voidExchange(BiNode*root)

(

if(root){

Exchange(root->lchild);

Exchange(root->rchild);

root->lchild-*~*-root->rchild;/皮換左右子樹

}

}

⑼【解答】先在鏈表中進(jìn)行遍歷，在遍歷過程中查找值等于x的結(jié)點(diǎn)，然后由此結(jié)點(diǎn)的最左孩子域firstchild

找到值為x結(jié)點(diǎn)的第?個(gè)孩子，再沿右兄弟域rightsib找到值為x結(jié)點(diǎn)的第i個(gè)孩子并返回指向這個(gè)孩子的

指針。

樹的孩子兄弟表示法中的結(jié)點(diǎn)結(jié)構(gòu)定義如下：

template

structTNode

{Tdata;TNode*firstchild,*rightsib;};具體算法如下：

查找第i個(gè)孩孑算法Search

template<classT>

TNode*Search(TNode*root,Tx,inti)

{

if(root->data==x){

j=l；

p=root->firstchild,

while(p!=NULL&&j<i)

(

j++；

p=p->rightsib;

)

if(p)returnp;

elsereturnNULL;

}

Search(root->firstchild,x,i);

Search(root->rightsib,x,i);

)

第6章圖

i.填空題

(DO,n(n-l)/2,0,n(n-l)【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱

為完全圖，在完全圖中，任意兩個(gè)頂點(diǎn)之間都存在邊。⑵其自身

⑶鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲(chǔ)結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組

等。

⑷O(n+e)【分析】在無向圖的鄰接表中，頂點(diǎn)表有n個(gè)結(jié)點(diǎn)，邊表有2e個(gè)結(jié)點(diǎn)，共有n+2e

個(gè)結(jié)點(diǎn)，其空間復(fù)雜度為O(n+2e)=O(n+e)。⑸求第j列的所有元素之和⑹出度

⑺前序，棧，層序，隊(duì)列

⑻O(n2),O(elog2e)【分析】Prim算法采用鄰接矩陣做存儲(chǔ)結(jié)構(gòu)，適合于求稠密圖的最小生成樹；Kruskal

算法采用邊集數(shù)組做存儲(chǔ)結(jié)構(gòu)，適合于求稀疏圖的最小生成樹。⑼回路

?o)vi,vj,vk【分析】對(duì)由頂點(diǎn)vi,vj,vk組成的圖進(jìn)行拓?fù)渑判颉?/p>

2.選擇題

￡。(匕)=2e

⑴C【分析】設(shè)無向圖中含有n個(gè)頂點(diǎn)e條邊，則J】。(2)A,G

⑶C【分析】若超過n-1,則路徑中必存在重復(fù)的頂點(diǎn)。(5)D(6)C,F

(7)B【分析】連通分量是無向圖的極大連通了圖，其中極大的含義是將依附于連通分量中頂點(diǎn)的所有邊

都加上，所以，連通分量中可能存在回路。

(8)D【分析】n個(gè)頂點(diǎn)的無向圖中，邊數(shù)evn(n-l)/2,將e=28代入，有nN8,現(xiàn)已知無向圖非連通，

則n=9o

(15)B【分析】AOE網(wǎng)中的關(guān)鍵路徑可能不止?條，如果某?個(gè)關(guān)鍵活動(dòng)提前完成，還不能提前整個(gè)工

程，而必須同時(shí)提高在幾條關(guān)鍵路徑上的關(guān)鍵活動(dòng)。

3.判斷題

<1)對(duì)。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中邊的個(gè)數(shù)。

⑵對(duì)。鄰接矩陣的空間復(fù)雜度為O(n2),與邊的個(gè)數(shù)無關(guān)。

⑶錯(cuò)。必須包含全部頂點(diǎn)。

⑷錯(cuò)。有向圖的鄰接矩陣不一定對(duì)稱，例如有向完全圖的鄰接矩陣就是對(duì)稱的。

⑸錯(cuò)。只有連通圖從某頂點(diǎn)出發(fā)進(jìn)行一次遍歷，可訪問圖的所有頂點(diǎn)。

⑹錯(cuò)。只能說明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。⑺對(duì)。參見第11題的證明。

(8)【解答】錯(cuò)。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長度相同。

4.(1)【解答】⑴邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。⑵第i個(gè)邊表中是否含有結(jié)點(diǎn)j。

⑶該頂點(diǎn)所對(duì)應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。

(2)【解答】⑴鄰接矩陣中非零元素個(gè)數(shù)的總和除以2。⑵當(dāng)鄰接矩陣A中(或A[j][i]=l)

時(shí)，表示兩頂點(diǎn)之間有邊相連。⑶計(jì)算鄰接矩陣上該頂點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。

(3)用反證法證明。

設(shè)vl,v2,...,vk是生成樹的一條最長路徑，其中，vl為起點(diǎn)，vk為終點(diǎn)。若vk的度為2,取vk的另一個(gè)

鄰接點(diǎn)v,由于生成樹中無回路，所以，v在最長路徑上，顯然vl,v2,...,vk,v的路徑最長，與假設(shè)矛盾。

所以生成樹中最長路徑的終點(diǎn)的度為lo

同理可證起點(diǎn)vl的度不能大于1,只能為lo

(4)【解答】鄰接矩陣表示如卜.：

010101

101110

010010

110011

011100

100100膝度優(yōu)先遍歷序列為：vlv2v3v5v4v6廣度優(yōu)先遍歷序列為：vlv2v4v6v3v5

?o

3

0

(1)(2)

按Kruskal算法求最小生成樹的過程如卜.:

(6)【解答】從源點(diǎn)vl到其他各頂點(diǎn)的最短路徑如下表所示。

源點(diǎn)終點(diǎn)最短路徑最短路徑長度

vlv3vlv315：vlv5vlv515：vlv2vlv3v225：

vlv6vlv3v2v640vlv4vlv3v2v445；

(7)任意n個(gè)結(jié)點(diǎn)的有向無環(huán)圖都可以得到個(gè)拓?fù)湫蛄?。設(shè)拓?fù)湫蛄袨関0vlv2…vn-l,我們來證明此

時(shí)的鄰接矩陣A為上三角矩陣。證明采用反證法。

假設(shè)此時(shí)的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j(i>j),使得不等于零,即圖中存在從

vi到vj的一條有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄?，vi的位置一定在yj之前，而在上述拓

撲序歹Uv0vlv2...vn-l中，由于i>j,即vi的位置在vj之后，導(dǎo)致矛盾。因此命題正確。

5算法設(shè)計(jì)

⑴先設(shè)置個(gè)空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對(duì)應(yīng)單鏈表中插入

相應(yīng)的邊表結(jié)點(diǎn)。

鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義如下:

constintMaxSize=10;

template

structAdjMatrix

{Tvertex[MaxSize];〃存放圖中頂點(diǎn)的數(shù)組

intarc[MaxSize][MaxSize];〃存放圖中邊的數(shù)組

intvertexNum,arcNum;〃圖的頂點(diǎn)數(shù)和邊數(shù)

}；

鄰接表存儲(chǔ)結(jié)構(gòu)定義如下：

constintMax