嚴蔚敏-數據結構課后習題與答案解析

./第一章緒論一、選擇題

1.組成數據的基本單位是〔

〔A數據項〔B數據類型〔C數據元素〔D數據變量

2.數據結構是研究數據的〔以及它們之間的相互關系.

〔A理想結構,物理結構〔B理想結構,抽象結構

〔C物理結構,邏輯結構〔D抽象結構,邏輯結構

3.在數據結構中,從邏輯上可以把數據結構分成〔

〔A動態(tài)結構和靜態(tài)結構〔B緊湊結構和非緊湊結構

〔C線性結構和非線性結構〔D內部結構和外部結構

4.數據結構是一門研究非數值計算的程序設計問題中計算機的〔①以及它們之間的〔②和運算等的學科.

①〔A數據元素〔B計算方法〔C邏輯存儲〔D數據映像

②〔A結構〔B關系〔C運算〔D算法

5.算法分析的目的是〔.

〔A找出數據結構的合理性〔B研究算法中的輸入和輸出的關系

〔C分析算法的效率以求改進〔D分析算法的易懂性和文檔性

6.計算機算法指的是〔①,它必須具備輸入、輸出和〔②等5個特性.

①〔A計算方法〔B排序方法〔C解決問題的有限運算序列〔D調度方法

②〔A可執(zhí)行性、可移植性和可擴充性〔B可行性、確定性和有窮性

〔C確定性、有窮性和穩(wěn)定性〔D易讀性、穩(wěn)定性和安全性

二、判斷題

1.數據的機內表示稱為數據的存儲結構.〔

2.算法就是程序.〔

3.數據元素是數據的最小單位.〔

4.算法的五個特性為：有窮性、輸入、輸出、完成性和確定性.〔

5.算法的時間復雜度取決于問題的規(guī)模和待處理數據的初態(tài).〔

三、填空題

1.數據邏輯結構包括________、________、_________和_________四種類型,其中樹形結構和圖形結構合稱為_____.

2.在線性結構中,第一個結點____前驅結點,其余每個結點有且只有______個前驅結點；最后一個結點______后續(xù)結點,其余每個結點有且只有_______個后續(xù)結點.

3.在樹形結構中,樹根結點沒有_______結點,其余每個結點有且只有_______個前驅結點；葉子結點沒有________結點,其余每個結點的后續(xù)結點可以_________.

4.在圖形結構中,每個結點的前驅結點數和后續(xù)結點數可以_________.

5.線性結構中元素之間存在________關系,樹形結構中元素之間存在______關系,圖形結構中元素之間存在_______關系.

6.算法的五個重要特性是_______、_______、______、_______、_______.

7.數據結構的三要素是指______、_______和________.

8.鏈式存儲結構與順序存儲結構相比較,主要優(yōu)點是________________________________.

9.設有一批數據元素,為了最快的存儲某元素,數據結構宜用_________結構,為了方便插入一個元素,數據結構宜用____________結構.四、算法分析題

1.求下列算法段的語句頻度及時間復雜度參考答案：一、選擇題1.C2.C3.C4.A、B5.C6.C、B二、判斷題:1、√2、×3、×4、×5、√三、填空題1、線性、樹形、圖形、集合?；非線性〔網狀2、沒有；1；沒有；13、前驅；1；后繼；任意多個4、任意多個5、一對一；一對多；多對多6、有窮性；確定性；可行性；輸入；輸出7、數據元素；邏輯結構；存儲結構8、插入、刪除、合并等操作較方便9、順序存儲；鏈式存儲四、算法分析題for<i=1;i<=n;i++>

for<j=1;j<=i;j++>

x=x+1;

分析：該算法為一個二重循環(huán),執(zhí)行次數為內、外循環(huán)次數相乘,但內循環(huán)次數不固定,與外循環(huán)有關,因些,時間頻度T<n>=1+2+3+…+n=n*<n+1>/2

有1/4≤T<n>/n2≤1,故它的時間復雜度為Ｏ<n2>,即Ｔ<n>與n2數量級相同.2、分析下列算法段的時間頻度及時間復雜度

for〔i=1;i<=n;i++

for<j=1;j<=i;j++>

for<k=1;k<=j;k++>

x=i+j-k;

分析算法規(guī)律可知時間頻度T<n>=1+<1+2>+<1+2+3>+...+<1+2+3+…+n>

由于有1/6≤T〔n/n3≤1,故時間復雜度為Ｏ<n3>第二章線性表一、選擇題

1.一個線性表第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是<>

〔A110〔B108〔C100〔D120

2.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動〔個元素.

〔A64〔B63〔C63.5〔D7

3.線性表采用鏈式存儲結構時,其地址〔.

<A>必須是連續(xù)的<B>部分地址必須是連續(xù)的

<C>一定是不連續(xù)的<D>連續(xù)與否均可以

4.在一個單鏈表中,若p所指結點不是最后結點,在p之后插入s所指結點,則執(zhí)行〔

〔As->next=p;p->next=s;〔Bs->next=p->next;p->next=s;

〔Cs->next=p->next;p=s;〔Dp->next=s;s->next=p;

5.在一個單鏈表中,若刪除p所指結點的后續(xù)結點,則執(zhí)行〔

〔Ap->next=p->next->next;〔Bp=p->next;p->next=p->next->next;

〔Cp->next=p->next;〔Dp=p->next->next;

6.下列有關線性表的敘述中,正確的是〔

〔A線性表中的元素之間隔是線性關系

〔B線性表中至少有一個元素

〔C線性表中任何一個元素有且僅有一個直接前趨

〔D線性表中任何一個元素有且僅有一個直接后繼

7.線性表是具有n個〔的有限序列〔n≠0>

〔A表元素〔B字符〔C數據元素〔D數據項

二、判斷題

1.線性表的鏈接存儲,表中元素的邏輯順序與物理順序一定相同.〔

2.如果沒有提供指針類型的語言,就無法構造鏈式結構.〔

3.線性結構的特點是只有一個結點沒有前驅,只有一個結點沒有后繼,其余的結點只有一個前驅和后繼.〔

4.語句p=p->next完成了指針賦值并使p指針得到了p指針所指后繼結點的數據域值.〔

5.要想刪除p指針的后繼結點,我們應該執(zhí)行q=p->next；p->next=q->next；free<q>.〔

三、填空題

1.已知P為單鏈表中的非首尾結點,在P結點后插入S結點的語句為：_______________________.

2.順序表中邏輯上相鄰的元素物理位置<>相鄰,單鏈表中邏輯上相鄰的元素物理位置_________相鄰.

3.線性表L＝〔a1,a2,...,an采用順序存儲,假定在不同的n＋1個位置上插入的概率相同,則插入一個新元素平均需要移動的元素個數是________________________

4.在非空雙向循環(huán)鏈表中,在結點q的前面插入結點p的過程如下：

p->prior=q->prior;

q->prior->next=p;

p->next=q;

______________________;

5.已知L是無表頭結點的單鏈表,是從下列提供的答案中選擇合適的語句序列,分別實現：

〔1表尾插入s結點的語句序列是_______________________________

<2>表尾插入s結點的語句序列是_______________________________p->next=s;p=L;L=s;p->next=s->next;s->next=p->next;s->next=L;s->next=null;while<p->next!=Q>?p=p-next;while<p->next!=null>p=p->next;四、算法設計題

1.試編寫一個求已知單鏈表的數據域的平均值的函數〔數據域數據類型為整型.

2.已知帶有頭結點的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數據域值為x的所有結點的c函數.

3.某百貨公司倉庫中有一批電視機,按其價格從低到高的次序構成一個循環(huán)鏈表,每個結點有價格、數量和鏈指針三個域.現出庫〔銷售m臺價格為h的電視機,試編寫算法修改原鏈表.

4.某百貨公司倉庫中有一批電視機,按其價格從低到高的次序構成一個循環(huán)鏈表,每個結點有價格、數量和鏈指針三個域.現新到m臺價格為h的電視機,試編寫算法修改原鏈表.

5.線性表中的元素值按遞增有序排列,針對順序表和循環(huán)鏈表兩種不同的存儲方式,分別編寫C函數刪除線性表中值介于a與b〔a≤b之間的元素.

6.設A=<a0,a1,a2,...,an-1>,B=<b0,b1,b2,...,bm-1>是兩個給定的線性表,它們的結點個數分別是n和m,且結點值均是整數.

若n=m,且ai=bi〔0≤i<n,則A=B；

若n<m,且ai=bi〔0≤i<n,則A<B；

若存在一個j,j<m,j<n,且ai=bi〔0≤i<j,若aj<bj,則A<B,否則A>B.

試編寫一個比較A和B的C函數,該函數返回-1或0或1,分別表示A<B或A=B或A>B.

7.試編寫算法,刪除雙向循環(huán)鏈表中第k個結點.

8.線性表由前后兩部分性質不同的元素組成<a0,a1,...,an-1,b0,b1,...,bm-1>,m和n為兩部分元素的個數,若線性表分別采用數組和鏈表兩種方式存儲,編寫算法將兩部分元素換位成<b0,b1,...,bm-1,a0,a1,...,an-1>,分析兩種存儲方式下算法的時間和空間復雜度.

9.用循環(huán)鏈表作線性表<a0,a1,...,an-1>和〔b0,b1,...,bm-1的存儲結構,頭指針分別為ah和bh,設計C函數,把兩個線性表合并成形如〔a0,b0,a1,b1,…的線性表,要求不開辟新的動態(tài)空間,利用原來循環(huán)鏈表的結點完成合并操作,結構仍為循環(huán)鏈表,頭指針為head,并分析算法的時間復雜度.

10.試寫出將一個線性表分解為兩個帶有頭結點的循環(huán)鏈表,并將兩個循環(huán)鏈表的長度放在各自的頭結點的數據域中的C函數.其中,線性表中序號為偶數的元素分解到第一個循環(huán)鏈表中,序號為奇數的元素分解到第二個循環(huán)鏈表中.

11.試寫出把線性鏈表改為循環(huán)鏈表的C函數.

12.己知非空線性鏈表中x結點的直接前驅結點為y,試寫出刪除x結點的C函數.

參考答案：一、選擇題1.B2.C3.D4.B5.A6.A7、C二、判斷題:參考答案：1、×2、√3、×4、×5、√三、填空題1、s->next=p->next;p->next=s;2、一定；不一定3、n/24、q->prior=p;5、<1>6>3>

<2>2>91>7>四、算法設計題1、

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{intdata;

structnode*link;

}NODE;

intaver<NODE*head>

{inti=0,sum=0,ave;NODE*p;

p=head;

while<p!=NULL>

{p=p->link;++i;

sum=sum+p->data;}

ave=sum/i;

return<ave>;}2、

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{

intdata;/*假設數據域為整型*/

structnode*link;

}NODE;

voiddel_link<NODE*head,intx>/*刪除數據域為x的結點*/

{

NODE*p,*q,*s;

p=head;

q=head->link;

while<q!=head>

{if<q->data==x>

{p->link=q->link;

s=q;

q=q->link;

free<s>;}

else

{

p=q;

q=q->link;

}

}

}3、

voiddel<NODE*head,floatprice,intnum>

{

NODE*p,*q,*s;

p=head;q=head->next;

while<q->price<price&&q!=head>

{

p=q;

q=q->next;

}

if<q->price==price>

q->num=q->num-num;

else

printf<"無此產品">;

if<q->num==0>

{

p->next=q->next;

free<q>;

}

}4、

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{

floatprice;

intnum;

structnode*next;

}NODE;

voidins<NODE*head,floatprice,intnum>

{

NODE*p,*q,*s;

p=head;q=head->next;

while<q->price<price&&q!=head>

{

p=q;

q=q->next;

}

if<q->price==price>

q->num=q->num+num;

else

{

s=<NODE*>malloc<sizeof<NODE>>;

s->price=price;

s->num=num;

s->next=p->next;

p->next=s;

}

}5、順序表：

算法思想：從0開始掃描線性表,用k記錄下元素值在a與b之間的元素個數,對于不滿足該條件的元素,前移k個位置,最后修改線性表的長度.

voiddel〔elemtypelist[],int*n,elemtypea,elemtypeb

{

inti=0,k=0；

while〔i<n>

{

if<list[i]>=a&&list[i]<=b>k++;

else

list[i-k]=list[i];

i++;

}

*n=*n-k;/*修改線性表的長度*/

}

循環(huán)鏈表:

voiddel<NODE*head,elemtypea,elemtypeb>

{

NODE*p,*q;

p=head;q=p->link;/*假設循環(huán)鏈表帶有頭結點*/

while<q!=head&&q->data<a>

{

p=q;

q=q->link;

}

while<q!=head&&q->data<b>

{

r=q;

q=q->link;

free<r>;

}

if<p!=q>

p->link=q;

}6、

#defineMAXSIZE100

intlistA[MAXSIZE],listB[MAXSIZE];

intn,m;

intcompare<inta[],intb[]>

{

inti=0;

while<a[i]==b[i]&&i<n&&i<m>

i++;

if<n==m&&i==n>return<0>;

if<n<m&&i==n>return<-1>;

if<n>m&&i==m>return<1>;

if<i<n&&i<m>

if<a[i]<b[i]>return<-1>;

elseif<a[i]>b[i]>return<1>;

}7、

voiddel<DUNODE**head,inti>

{

DUNODE*p;

if<i==0>

{

*head=*head->next;

*head->prior=NULL;

return<0>;

}

Else

{for<j=0;j<i&&p!=NULL;j++>

p=p->next;

if<p==NULL||j>i>return<1>;

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

p->next->prior=p->proir;

free<p>;

return<0>;

}8.

順序存儲:

voidconvert<elemtypelist[],intl,inth>/*將數組中第l個到第h個元素逆置*/

{

inti;

elemtypetemp;

for<i=h;i<=<l+h>/2;i++>

{

temp=list[i];

list[i]=list[l+h-i];

list[l+h-i]=temp;

}

}

voidexchange<elemtypelist[],intn,intm>;

{

convert<list,0,n+m-1>;

convert<list,0,m-1>;

convert<list,m,n+m-1>;

}

該算法的時間復雜度為O<n+m>,空間復雜度為O<1>

鏈接存儲:<不帶頭結點的單鏈表>

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voidconvert<NODE**head,intn,intm>

{

NODE*p,*q,*r;

inti;

p=*head;

q=*head;

for<i=0;i<n-1;i++>

q=q->link;/*q指向an-1結點*/

r=q->link;

q->link=NULL;

while<r->link!=NULL>

r=r->link;/*r指向最后一個bm-1結點*/

*head=q;

r->link=p;

}

該算法的時間復雜度為O<n+m>,但比順序存儲節(jié)省時間<不需要移動元素,只需改變指針>,空間復雜度為O<1>

9.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

NODE*union<NODE*ah,NODE*bh>

{

NODE*a,*b,*head,*r,*q;

head=ah;

a=ah;

b=bh;

while<a->link!=ah&&b->link!=bh>

{

r=a->link;

q=b->link;

a->link=b;

b->link=r;

a=r;

b=q;

}

if<a->link==ah>/*a的結點個數小于等于b的結點個數*/

{

a->link=b;

while<b->link!=bh>

b=b->link;

b->link=head;

}

if<b->link==bh>/*b的結點個數小于a的結點個數*/

{

r=a->link;

a->link=b;

b->link=r;

}

return<head>;

}

該算法的時間復雜度為O<n+m>,其中n和m為兩個循環(huán)鏈表的結點個數.

10.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voidanalyze<NODE*a

{

NODE*rh,*qh,*r,*q,*p；

inti=0,j=0；/*i為序號是奇數的結點個數j為序號是偶數的結點個數*/

p=a；

rh=〔NODE*malloc〔sizeof〔NODE；/*rh為序號是奇數的鏈表頭指針*/

qh=<NODE*>malloc<sizeof<NODE>>;/*qh為序號是偶數的鏈表頭指針*/

r=rh;

q=qh;

while<p!=NULL>

{

r->link=p;

r=p;

i++;

p=p->link;

if<p!=NULL>

{

q->link=p;

q=p;

j++;

p=p->link;

}

}

rh->data=i;

r->link=rh;

qh->data=j;

q->link=qh;

}

11.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voidchange<NODE*head>

{

NODE*p;

p=head;

if<head!=NULL>

{

while<p->link!=NULL>

p=p->link;

p->link=head;

}

}

12.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voiddel<NODE*x,NODE*y>

{

NODE*p,*q;

elemtyped1;

p=y;

q=x;

while<q->next!=NULL>/*把后一個結點數據域前移到前一個結點*/

{

p->data=q->data;

q=q->link;

p=q;

p->link=NULL;/*刪除最后一個結點*/

free<q>;

}第三章棧和隊列一、選擇題

1.一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是〔.

〔Aedcba〔Bdecba〔Cdceab〔Dabcde

2.棧結構通常采用的兩種存儲結構是〔.

〔A線性存儲結構和鏈表存儲結構〔B散列方式和索引方式

〔C鏈表存儲結構和數組〔D線性存儲結構和非線性存儲結構

3.判定一個棧ST<最多元素為m0>為空的條件是〔.

〔AST-〉top!=0〔BST-〉top==0

〔CST-〉top!=m0〔DST-〉top=m0

4.判定一個棧ST<最多元素為m0>為棧滿的條件是〔.

〔AST->top!=0〔BST->top==0

〔CST->top!=m0-1〔DST->top==m0-1

5.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是〔.

〔A4,3,2,1〔B1,2,3,4〔C1,4,3,2〔D3,2,4,1

6.循環(huán)隊列用數組A[0,m-1]存放其元素值,已知其頭尾指針分別是front和rear則當前隊列中的元素個數是〔

〔A<rear-front+m>%m〔Brear-front+1〔Crear-front-1〔Drear-front

7.棧和隊列的共同點是〔

〔A都是先進后出〔B都是先進先出

〔C只允許在端點處插入和刪除元素〔D沒有共同點

8.表達式a*<b+c>-d的后綴表達式是〔.

〔Aabcd*+-〔Babc+*d-〔Cabc*+d-〔D-+*abcd

9.4個元素a1,a2,a3和a4依次通過一個棧,在a4進棧前,棧的狀態(tài),則不可能的出棧序是〔

<A>a4,a3,a2,a1<B>a3,a2,a4,a1

<C>a3,a1,a4,a2<D>a3,a4,a2,a1

10.以數組Q[0..m－1]存放循環(huán)隊列中的元素,變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當前隊列中元素的個數,隊列第一個元素的實際位置是〔

<A>rear－qulen<B>rear－qulen＋m

<C>m－qulen<D>1＋〔rear＋m－qulen%m

二、填空題

1.棧的特點是_______________________,隊列的特點是__________________________.

2.線性表、棧和隊列都是_____________________結構,可以在線性表的______________位置插入和刪除元素,對于棧只能在________插入和刪除元素,對于隊列只能在_______插入元素和_________刪除元素.

3.一個棧的輸入序列是12345,則棧有輸出序列12345是____________.<正確/錯誤>

4.設棧S和隊列Q的初始狀態(tài)皆為空,元素a1,a2,a3,a4,a5和a6依次通過一個棧,一個元素出棧后即進入隊列Q,若6個元素出隊列的順序是a3,a5,a4,a6,a2,a1則棧S至少應該容納_____個元素.

三、算法設計題

1.假設有兩個棧s1和s2共享一個數組stack[M],其中一個棧底設在stack[0]處,另一個棧底設在stack[M-1]處.試編寫對任一棧作進棧和出棧運算的C函數push〔x,i>和pop<i>,i=l,2.其中i=1表示左邊的棧,,i=2表示右邊的棧.要求在整個數組元素都被占用時才產生溢出.

2.利用兩個棧s1,s2模擬一個隊列時,如何用棧的運算來實現該隊列的運算?寫出模擬隊列的插入和刪除的C函數.

一個棧s1用于插入元素,另一個棧s2用于刪除元素.參考答案：一、選擇題1.C2.A3.B4.B5.B6.B7、C8、C9、C10、D二、填空題1、先進先出；先進后出2、線性；任何；棧頂；隊尾；對頭3、正確的4、3三、算法設計題1.

#defineM100

elemtypestack[M];

inttop1=0,top2=m-1;

intpush<elemtypex,inti>

{

if<top1-top2==1>return<1>;/*上溢處理*/

else

if<i==1>stack[top1++]=x;

if<i==2>stack[top2--]=x;

return<0>;

}

intpop<elemtype*px,inti>

{

if<i==1>

if<top1==0>return<1>;

else

{

top1--;

*px=stack[top1];

return<0>;

}

else

if<i==2>

if<top2==M-1>return<1>;

else

{

top2++;

*px=stack[top2];

return<0>;

}

}

2.

elemtypes1[MAXSIZE],s2[MAZSIZE];

inttop1,top2;

voidenqueue<elemtypex>

{

if<top1==MAXSIZE>return<1>;

else

{

push<s1,x>;

return<0>;

}}

voiddequeue<elemtype*px>

{

elemtypex;

top2=0;

while<!empty<s1>>

{

pop<s1,&x>;

push<s2,x>;

}

pop<s2,&x>;

while<!empty<s2>>

{

pop<s2,&x>;

push<s1,x>;

}

}第四章串一、選擇題

1.下列關于串的敘述中,正確的是〔

<A>一個串的字符個數即該串的長度<B>一個串的長度至少是1

<C>空串是由一個空格字符組成的串<D>兩個串S1和S2若長度相同,則這兩個串相等

2.字符串"abaaabab"的nextval值為<?>

<A><0,1,01,1,0,4,1,0,1><B><0,1,0,0,0,0,2,1,0,1>

<C><0,1,0,1,0,0,0,1,1><D><0,1,0,1,0,1,0,1,1>

3.字符串滿足下式,其中head和tail的定義同廣義表類似,如head<‘xyz’>=‘x’,tail<‘xyz’>=‘yz’,則s=<>.concat<head<tail<s>>,head<tail<tail<s>>>>=‘dc’.

<A>abcd<B>acbd<C>acdb<D>adcb

4.串是一種特殊的線性表,其特殊性表現在〔

<A>可以順序存儲<B>數據元素是一個字符

<C>可以鏈式存儲<D>數據元素可以是多個字符

5．設串S1=‘ABCDEFG’,s2=‘PQRST’,函數CONCAT〔X,Y返回X和Y串的連接串,SUBSTR〔S,I,J返回串S從序號I開始的J個字符組成的字串,LENGTH〔S返回串S的長度,則CONCAT〔SUBSTR〔S1,2,LENGTH〔S2,SUBSTR〔S1,LENGTH〔S2,2的結果串是〔

〔ABCDEF<B>BCDEFG<C>BCPQRST<D>BCDEFEF

二、算法設計

1.分別在順序存儲和一般鏈接存儲兩種方式下,用C語言寫出實現把串s1復制到串s2的串復制函數strcpy<s1,s2>.

2.在一般鏈接存儲<一個結點存放一個字符>方式下,寫出采用簡單算法實現串的模式匹配的C語言函數intL_index<t,p>.參考答案：一、選擇題1.A2.B3.D4.D5.D二、算法設計1.

順序存儲：

#include"string.h"

#defineMAXN100

chars[MAXN];

intS_strlen<chars[]>

{

inti;

for<i=0;s[i]!='\0';i++>;

return<i>;

}

voidS_strcpy<chars1[],chars2[]>//4.3題

{

inti;

for<i=0;s1[i]!='\0';i++>

s2[i]=s1[i];

s2[i]='\0';

}

一般鏈接存儲：

#include"stdio.h"

typedefstructnode

{

chardata;

structnode*link;

}NODE;

NODE*L_strcpy<NODE*s1>

{

NODE*s2,*t1,*t2,*s;

if<s1==NULL>return<NULL>;

else

{

t1=s1;

t2=<NODE*>malloc<sizeof<NODE>>;

s2=t2;

while<t1!=NULL>

{

s=<NODE*>malloc<sizeof<NODE>>;

s->data=t1->data;

t2->link=s;

t2=s;

t1=t1->link;

}

t2->link=NULL;

s=s2;

s2=s2->link;

free<s>;

return<s2>;

}

}

2.

#include"stdio.h"

typedefstructnode

{

chardata;

structnode*link;

}NODE;

intL_index<NODE*t,NODE*p>

{

NODE*t1,*p1,*t2;

?inti;

t1=t;i=1;

while<t1!=NULL>

{

p1=p;

t2=t1->link;

while<p1->data==t1->data&&p1!=NULL>

{

p1=p1->link;

t1=t1->link;

}

if<p1==NULL>return<i>;

i++;

t1=t2;

}

return<0>;

}第五章數組和廣義表

一、選擇題

1.常對數組進行的兩種基本操作是〔

〔A建立與刪除〔B索引和修改〔C查找和修改〔D查找與索引

2.二維數組M的元素是4個字符<每個字符占一個存儲單元>組成的串,行下標i的范圍從0到4,列下標j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素<>的起始地址相同.

〔AM[2][4]〔BM[3][4]〔CM[3][5]〔DM[4][4]

3.數組A[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內,存放該數組至少需要的單元數是〔.

〔A80〔B100〔C240〔D270

4.數組A[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內,該數組按行存放時,元素A[7][4]的起始地址為〔.

〔ASA+141〔BSA+144〔CSA+222〔DSA+225

5.數組A[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內,該數組按列存放時,元素A[4][7]的起始地址為〔.

〔ASA+141〔BSA+180〔CSA+222〔DSA+225

6.稀疏矩陣一般的壓縮存儲方法有兩種,即〔.

〔A二維數組和三維數組〔B三元組和散列

〔C三元組和十字鏈表〔D散列和十字鏈表

7.若采用三元組壓縮技術存儲稀疏矩陣,只要把每個元素的行下標和列下標互換,就完成了對該矩陣的轉置運算,這種觀點〔.

〔A正確〔B錯誤

8.設矩陣A是一個對稱矩陣,為了節(jié)省存儲,將其下三角部分按行序存放在一維數組B[1,n<n-1>/2]中,對下三角部分中任一元素ai,j<i<=j>,在一組數組B的下標位置k的值是〔.

〔Ai<i-1>/2+j-1〔Bi<i-1>/2+j〔Ci<i+1>/2+j-1<D>i<i+1>/2+j

二、填空題

1.己知二維數組A[m][n]采用行序為主方式存儲,每個元素占k個存儲單元,并且第一個元素的存儲地址是LOC<A[0][0]>,則A[0][0]的地址是_____________________.

2.二維數組A[10][20]采用列序為主方式存儲,每個元素占一個存儲單元,并且A[0][0]的存儲地址是200,則A[6][12]的地址是________________.

3.有一個10階對稱矩陣A,采用壓縮存儲方式<以行序為主,且A[0][0]=1>,則A[8][5]的地址是__________________.

4.設n行n列的下三角矩陣A已壓縮到一維數組S[1..n*<n+1>/2]中,若按行序為主存儲,則A[i][j]對應的S中的存儲位置是________________.

5.若A是按列序為主序進行存儲的4×6的二維數組,其每個元素占用3個存儲單元,并且A[0][0]的存儲地址為1000,元素A[1][3]的存儲地址為___________,該數組共占用_______________個存儲單元.

三、算法設計

1.如果矩陣A中存在這樣的一個元素A[i][j]滿足條件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,則稱之為該矩陣的一個馬鞍點.編寫一個函數計算出1×n的矩陣A的所有馬鞍點.

2.n只猴子要選大王,選舉辦法如下:所有猴子按1,2,...,n編號圍坐一圈,從1號開始按1、2、...、m報數,凡報m號的退出到圈外,如此循環(huán)報數,直到圈內剩下只猴子時,這只猴子就是大王.n和m由鍵盤輸入,打印出最后剩下的猴子號.編寫一程序實現上述函數.

3.數組和廣義表的算法驗證程序

編寫下列程序:

<1>求廣義表表頭和表尾的函數head<>和tail<>.

<2>計算廣義表原子結點個數的函數count_GL<>.

<3>計算廣義表所有原子結點數據域<設數據域為整型〉之和的函數sum_GL<>.參考答案：一、選擇題1.C2.B3.C4.C5.B6.C7、B8、B二、填空題1、loc<A[0][0]>+<n*i+j>*k2、3323、424、i*<i+1>/2+j+15、1039；72三、算法設計題1.

算法思想：依題意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,則該元素A[i][j]便是馬鞍點,找出所有這樣的元素,即找到了所有馬鞍點.因此,實現本題功能的程序如下:

#include<stdio.h>

#definem3

#definen4

voidminmax<inta[m][n]>

{

inti1,j,have=0;

intmin[m],max[n];

for<i1=0;i1<m;i1++>/*計算出每行的最小值元素,放入min[m]之中*/

{

min[i1]=a[i1][0];

for<j=1;j<n;j++>

if<a[i1][j]<min[i1]>min[i1]=a[i1][j];

}

for<j=0;j<n;j++>/*計算出每列的最大值元素,放入max[n]之中*/

{

max[j]=a[0][j];

for<i1=1;i1<m;i1++>

if<a[i1][j]>max[j]>max[j]=a[i1][j];

}

for<i1=0;i1<m;i1++>

for<j=0;j<n;j++>

if<min[i1]==max[j]>

{

printf<"<%d,%d>:%d\n",i1,j,a[i1][j]>;

have=1;

}

if<!have>printf<"沒有鞍點＼n">;

}

2.

算法思想:本題用一個含有n個元素的數組a,初始時a[i]中存放猴子的編號i,計數器似的值為0.從a[i]開始循環(huán)報數,每報一次,計數器的值加1,凡報到m時便打印出a[i]值<退出圈外的猴子的編號>,同時將a[i]的值改為O<以后它不再參加報數>,計數器值重新置為0.該函數一直進行到n只猴子全部退出圈外為止,最后退出的猴子就是大王.因此,現本題功能的程序如下:

#include"stdio.h"

main<>

{

inta[100];

intcount,d,j,m,n;

scanf<"%d%d",&m,&n>;/*n>=m*/

for<j=0;j<n;j++>

a[j]=j+1;

count=0;d=0;

while<d<n>

for<j=0;j<n;j++>

if<a[j]!=0>

{

count++;

if<count==m>

{

printf<"%d",a[j]>;

a[j]=0;

count=0;

d++;

}

}

}

3.

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{inttag;

union

{structnode*sublist;

chardata;

}dd;

structnode*link;

}NODE;

NODE*creat_GL<char**s>

{

NODE*h;

charch;

ch=*<*s>;

<*s>++;

if<ch!='\0'>

{

h=<NODE*>malloc<sizeof<NODE>>;

if<ch=='<'>

{

h->tag=1;

h->dd.sublist=creat_GL<s>;

}

Else

{

h->tag=0;

h->dd.data=ch;

}

}

else

h=NULL;

ch=*<*s>;

<*s>++;

if<h!=NULL>

if<ch==','>

h->link=creat_GL<s>;

else

h->link=NULL;

return<h>;

}

voidprn_GL<NODE*p>

{

if<p!=NULL>

{

if<p->tag==1>

{

printf<"<">;

if<p->dd.sublist==NULL>

printf<"">;

else

prn_GL<p->dd.sublist>;

}

else

printf<"%c",p->dd.data>;

if<p->tag==1>

printf<">">;

if<p->link!=NULL>

{

printf<",">;

prn_GL<p->link>;

}

}

}

NODE*copy_GL<NODE*p>

{

NODE*q;

if<p==NULL>return<NULL>;

q=<NODE*>malloc<sizeof<NODE>>;

q->tag=p->tag;

if<p->tag>

q->dd.sublist=copy_GL<p->dd.sublist>;

else

q->dd.data=p->dd.data;

q->link=copy_GL<p->link>;

return<q>;

}

NODE*head<NODE*p>/*求表頭函數*/

{

return<p->dd.sublist>;

}

NODE*tail<NODE*p>/*求表尾函數*/

{

return<p->link>;

}

intsum<NODE*p>/*求原子結點的數據域之和函數*/

{intm,n;

if<p==NULL>return<0>;

else

{if<p->tag==0>n=p->dd.data;

else

n=sum<p->dd.sublist>;

if<p->link!=NULL>

m=sum<p->link>;

elsem=0;

return<n+m>;

}

}

intdepth<NODE*p>/*求表的深度函數*/

{

inth,maxdh;

NODE*q;

if<p->tag==0>return<0>;

else

if<p->tag==1&&p->dd.sublist==NULL>return1;

else

{

maxdh=0;

while<p!=NULL>

{

if<p->tag==0>h=0;

else

{q=p->dd.sublist;

h=depth<q>;

}

if<h>maxdh>maxdh=h;

p=p->link;

}

return<maxdh+1>;

}

}

main<>

{

NODE*hd,*hc;

chars[100],*p;

p=gets<s>;

hd=creat_GL<&p>;

prn_GL<head<hd>>;

prn_GL<tail<hd>>;

hc=copy_GL<hd>;

printf<"copyafter:">;

prn_GL<hc>;

printf<"sum:%d\n",sum<hd>>;

printf<"depth:%d\n",depth<hd>>;

}第六章樹和二叉樹一、選擇題

1.在線索化二叉樹中,t所指結點沒有左子樹的充要條件是〔

〔At-〉left==NULL〔Bt-〉ltag==1

〔Ct-〉ltag=1且t-〉left=NULL〔D以上都不對

2.二叉樹按某種順序線索化后,任一結點均有指向其前趨和后繼的線索,這種說法

〔A正確〔B錯誤〔C不同情況下答案不確定

3.二叉樹的前序遍歷序列中,任意一個結點均處在其子女結點的前面,這種說法〔

<A>正確<B>錯誤〔C不同情況下答案不確定

4.由于二叉樹中每個結點的度最大為2,所以二叉樹是一種特殊的樹,這種說法〔

〔A正確〔B錯誤〔C不同情況下答案不確定

5.設高度為h的二叉樹上只有度為0和度為2的結點,則此類二叉樹中所包含的結點數至少為〔.

〔A2h〔B2h-1〔C2h+1〔Dh+1

6.已知某二叉樹的后序遍歷序列是dabec.中序遍歷序列是debac,它的前序遍歷序列是〔.

〔Aacbed〔Bdecab〔Cdeabc〔Dcedba

7.如果T2是由有序樹T轉換而來的二叉樹,那么T中結點的前序就是T2中結點的〔

〔A前序〔B中序〔C后序〔D層次序

8.某二叉樹的前序遍歷結點訪問順序是abdgcefh,中序遍歷的結點訪問順序是dgbaechf,則其后序遍歷的結點訪問順序是〔.

〔Abdgcefha〔Bgdbecfha〔Cbdgaechf〔Dgdbehfca

9.二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值.這種說法〔

〔A正確〔B錯誤〔C不同情況下答案不確定

10.按照二叉樹的定義,具有3個結點的二叉樹有〔種.

〔A3〔B4〔C5〔D6

11.在一非空二叉樹的中序遍歷序列中,根結點的右邊〔

〔A只有右子樹上的所有結點〔B只有右子樹上的部分結點

〔C只有左子樹上的部分結點〔D只有左子樹上的所有結點

12.樹最適合用來表示〔.

〔A有序數據元素〔B無序數據元素

〔C元素之間具有分支層次關系的數據〔D元素之間無聯系的數據

13.任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序〔

〔A不發(fā)生改變〔B發(fā)生改變〔C不能確定D.以上都不對

14.實現任意二叉樹的后序遍歷的非遞歸算法而不使用棧結構,最佳方案是二叉樹采用〔存儲結構.

〔A二叉鏈表〔B廣義表存儲結構〔C三叉鏈表〔D順序存儲結構

15.對一個滿二叉樹,m個樹葉,n個結點,深度為h,則〔

〔An=h+m〔Bh+m=2n〔Cm=h-1〔Dn=2h-1

16.如果某二叉樹的前序為stuwv,中序為uwtvs,那么該二叉樹的后序為〔

〔Auwvts〔Bvwuts〔Cwuvts〔Dwutsv

17.具有五層結點的二叉平衡樹至少有〔個結點.

〔A10〔B12〔C15〔D17

二、判斷題

1.二叉樹中任何一個結點的度都是2.〔

2.由二叉樹結點的先根序列和后根序列可以唯一地確定一棵二叉樹.〔

3.一棵哈夫曼樹中不存在度為1的結點.〔

4.平衡二叉排序樹上任何一個結點的左、右子樹的高度之差的絕對值不大于2〔

三、填空題

1.指出樹和二叉樹的三個主要差別___________,___________,_______________.

2.從概念上講,樹與二叉樹是兩種不同的數據結構,將樹轉化為二叉樹的基本目的是____________

3.若結點A有三個兄弟<包括A本身>,并且B是A的雙親結點,B的度是_______________

4.若一棵具有n個結點的二叉樹采用標準鏈接存儲結構,那么該二叉樹所有結點共有_______個空指針域.

5.已知二叉樹的前序序列為ABDEGCFHIJ,中序序列為DBGEAHFIJC,寫出后序序列_______________.

6.已知二叉樹的后序序列為FGDBHECA,中序序列為BFDGAEHC,并寫出前序序列_________________.

7.找出滿足下列條件的二叉樹

1先序和中序遍歷,得到的結點訪問順序一樣._________________________

2后序和中序遍歷,得到的結點訪問順序一樣._________________________

3先序和后序遍歷,得到的結點訪問順序一樣.__________________________

8.一棵含有n個結點的k叉樹,可能達到的最大深度和最小深度各是多少？____________________

9.一棵二叉樹有67個結點,這些結點的度要么是0,要么是2.這棵二叉樹中度為2的結點有______________________個.

10.含有100個結點的樹有_______________________________________條邊.

四、問答題

1.一棵深度為h的滿m叉樹具有如下性質:第h層上的結點都是葉結點,其余各層上每個結點都有m棵非空子樹.若按層次從上到下,每層從左到右的順序從1開始對全部結點編號,試計算:

<1>第k層結點數<1≤k≤h>.

<2>整棵樹結點數.

<3>編號為i的結點的雙親結點的編號.

<4>編號為i的結點的第j個孩子結點<若有>的編號.

2.證明：一個滿k叉樹上的葉子結點數n0和非葉子結點數n1之間滿足以下關系：n0=〔k-1n1+1

3.已知一組元素為<50,28,78,65,23,36,13,42,71,請完成以下操作:

<1>畫出按元素排列順序逐點插入所生成的二叉排序樹BT.

<2>分別計算在BT中查找各元素所要進行的元素間的比較次數及平均比較次數.

<3>畫出在BT中刪除<23〉后的二叉樹.

4.有七個帶權結點,其權值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~結點構造一棵哈夫曼樹<請按照每個結點的左子樹根結點的權小于等于右子樹根結點的權的次序構造〉,并計算出帶權路徑長度WPL及該樹的結點總數.

5.有一電文共使用五種字符a,b,c,d,e,五、算法設計

已知一棵具有n個結點的完全二叉樹被順序存儲在一維數組A[n]中,試編寫一個算法輸出A[i]結點的雙親和所有孩子.參考答案：一、選擇題1.B2.B3.A4.B5.B6.D7、A8、D9、B10、C11、A12、C13、A14、C15、D16、C17C二、判斷題1×2×3√4√三、填空題1、①樹的結點個數至少為1,而二叉樹的結點個數可以為0；

②樹種結點的最大讀書沒有限制,而二叉樹結點的最大度數不能超過2；

③樹的結點無左右之分,而二叉樹的結點有左右之分.

2、樹可采用二叉樹的存儲結構并利用二叉樹的已有算法解決樹的有關問題.3、44、n+15、DGEBHJIFCA6、ABDEGCEH

7、①無左子樹②無右子樹③僅一個結點的二叉樹8、最大n,最小┕log2n┙+19、2210、99四、問答題

1.

答：〔1mk-1〔2〔mh-1/〔m-1

〔3i=1時,該結點為根,無雙親結點；否則其雙親結點的編號為〔i+m-2/m

〔4編號為i的結點的第j個孩子結點<若有>的編號為i*m+〔j-〔m-1

2.

證明：設樹結點為n,則n=n0+n1

因是滿k叉樹,每個非葉子結點引出k個分支,故有k*n1個分支.

除根外,每個分支引出一個結點,則樹共有k*n1+1個結點.

所以n0+n1=k*n1+1

n0=<k-1>*n1+1五、算法設計

voidparent<inta[],intn,inti>

{

if<i==1>

{

printf<"無雙親\n">;

return;

}

Else

printf<"雙親:%d\n",a[<i-1>/2]>;

}

voidchild<inta[],intn,inti>/*i為序號*/

{

intqueue[MAX],front=0,tail=0,p;/*隊列作為輔助,存儲孩子的序號*/

queue[0]=i;tail++;

while<front<tail>

{

p=queue[front++];

if<p!=i>

printf<"%d",a[p-1]>;/*自身不輸出*/

if<2*p<=n>

queue[tail++]=2*p;

if<2*p+1<=n>queue[tail++]=2*p+1;

}

main<>

{

inta[MAX],n,i;

printf<"請輸入二叉樹的結點個數:">;

scanf<"%d",&n>;

input<a,n>;

printf<"請輸入i:">;

scanf<"%d",&i>;

parent<a,n,i>;

child<a,n,i>;

}

二叉樹其他運算的算法〔只作參考

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{

chardata;

structnode*lchild,*rchild;

}NODE;

NODE*T;

voidcreate<NODE**T>//創(chuàng)建二叉樹

{charch;

ch=getchar<>;

if<ch==''>*T=NULL;

else

{*T=<NODE*>malloc<sizeof<NODE>>;

<*T>->data=ch;

create<&<<*T>->lchild>>;

create<&<<*T>->rchild>>;?}}

voidinorder<NODE*p>//中序編歷二叉樹

{if<p!=NULL>

{inorder<p->lchild>;??

printf<"%c",p->data>;?

inorder<p->rchild>;???}?}

intnum=0;

voidcount<NODE*p>//統(tǒng)計出二叉樹中單孩子的結點數方法1

{

if<p!=NULL>

{

count<p->lchild>;

if<p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL>

num++;

count<p->rchild>;

}

}

voidcount1<NODE*p,int*num1>

{

if<p!=NULL>

{

count1<p->lchild,num1>;

if<p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL>

<*num1>++;

count1<p->rchild,num1>;

}

}

intonechild<NODE*t>//統(tǒng)計出二叉樹中單孩子的結點數方法2

{

intnum1,num2;

if<t==NULL>return<0>;

elseif<t->lchild==NULL&&t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL>

return<onechild<t->lchild>+onechild<t->rchild>+1>;

else

{

num1=onechild<t->lchild>;

num2=onechild<t->rchild>;

return<num1+num2>;

}

}

intsum<NODE*t>//統(tǒng)計出二叉樹中所有結點數

{if<t==NULL>return<0>;

else

return<sum<t->lchild>+sum<t->rchild>+1>;

}

intleaf<NODE*t>//統(tǒng)計出二叉樹中葉子結點數

{

if<t==NULL>return<0>;

else

if<t->lchild==NULL&&t->rchild==NULL>

return<leaf<t->lchild>+leaf<t->rchild>+1>;

else

return<leaf<t->lchild>+leaf<t->rchild>>;

}

voidpreorder1<NODE*root>//非遞歸二叉樹前序編歷

{NODE*p,*s[100],*q;//q為p的雙親結點

inttop=0;//top為棧頂指針

p=root;q=p;

while<<p!=NULL>||<top>0>>

{while<p!=NULL>

{printf<"%d",p->data>;

s[++top]=p;p=p->lchild;}

p=s[top--];p=p->rchild;}}

voiddelk<NODE**root,chark>//刪去并釋放數據值為k的葉結點

{NODE*p,*s[100],*q;//q為p的雙親結點

inttop=0;//top為棧頂指針

if<<*root>==NULL>return;

if<<*root>->lchild==NULL&&<*root>->rchild==NULL&&<*root>->data==k>{*root=NULL;return;}

p=*root;q=p;

while<<p!=NULL>||<top>0>>

{

while<p!=NULL>

{

if<p->lchild==NULL&&p->rchild==NULL&&p->data==k>

{if<q->lchild==p>q->lchild=NULL;

elseq->rchild=NULL;

free<p>;

return;

}

s[++top]=p;q=p;p=p->lchild;}

p=s[top--];q=p;p=p->rchild;}}

voidlev_traverse<NODE*T>//按層次從上到下,每層從右到左的順序列出二叉樹所有結點的數據信息

{NODE*q[100],*p;

inthead,tail;

q[0]=T;head=0;tail=1;

while<head<tail>

{p=q[head++];

printf<"%c",p->data>;

if<p->rchild!=NULL>

q[tail++]=p->rchild;

if<p->lchild!=NULL>

q[tail++]=p->lchild;

}}

intdepth<NODE*t>//求二叉樹的深度

{

intnum1,num2;

if<t==NULL>return<0>;

if<t->lchild==NULL&&t->rchild==NULL>return<1>;

else

{

num1=depth<t->lchild>;

num2=depth<t->rchild>;

if<num1>num2>

return<num1+1>;

else

return<num2+1>;

}

}

intonechild3<NODE*root>//非遞歸統(tǒng)計出二叉樹共有多少個度為1的結點

{NODE*p,*s[100];

inttop=0,num=0;//top為棧頂指針

p=root;

while<<p!=NULL>||<top>0>>

{while<p!=NULL>

{if<p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL>

num++;

s[++top]=p;p=p->lchild;}

p=s[top--];p=p->rchild;}

returnnum;

}

intlike<NODE*t1,NODE*t2>//判定兩顆二叉樹是否相似

{

intlike1,like2;

if<t1==t2&&t2==NULL>return<1>;

else

if<t1==NULL&&t2!=NULL||t1!=NULL&&t2==NULL>return<0>;

else

{

like1=like<t1->lchild,t2->lchild>;

like2=like<t1->rchild,t2->rchild>;

return<like1&&like2>;

}

}

chara[100];//數組順序存儲二叉樹

voidchange<NODE*t,inti>//將二叉樹的鏈接存儲轉換為順序存儲

{

if<t!=NULL>

{a[i]=t->data;

change<t->lchild,2*i>;

change<t->rchild,2*i+1>;

}

}

intcomplete<NODE*t>//判斷二叉樹是否為完全二叉樹

{

inti,flag=0;

change<t,1>;

for<i=1;i<100;i++>

{if<!flag&&a[i]=='\0'>flag=1;

if<flag&&a[i]!='\0'>break;

}

if<i==100>return<1>;

elsereturn<0>;

}第七章圖一、判斷題

1.一個無向圖的鄰接矩陣中各非零元素之和與圖中邊的條數相等.〔

2.一個有向圖的鄰接矩陣中各非零元素之和與圖中邊的條數相等.〔

3.一個對稱矩陣一定對應著一個無向圖.〔

4.一個有向圖的鄰接矩陣一定是一個非對稱矩陣.〔

二、選擇題

1.在一個圖中,所有頂點的度數之和等于所有邊數的〔倍.

〔A1/2〔B1〔C2〔D4

2.在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的〔倍.

〔A1/2〔B1〔C2〔D4

3.一個有n個頂點的無向圖最多有〔條邊.

〔An〔Bn<n-1>〔Cn<n-1/2〔D2n

4.具有4個頂點的無向完全圖有〔條邊.

〔A6〔B12〔C16〔D20

5.具有6個頂點的無向圖至少應有〔條邊才能確保是一個連通圖.

〔A5〔B6〔C7〔D8

6.在一個具有n個頂點的無向圖中,要連通全部頂點至少需要〔條邊.

〔An〔Bn+1〔Cn-1〔Dn/2

7.對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大小〔

〔An〔B<n-1>2〔Cn-1〔Dn2

8.對于一個具有n個頂點和e條邊的無向圖,若采用鄰接表表示,則表頭向量的大小為〔,所有鄰接表中的結點總數是〔.

①〔An〔Bn+1〔Cn-1〔Dn+e

②〔Ae/2〔Be〔C2e〔Dn+e

9.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的〔.

〔A先序遍歷〔B中序遍歷〔C后序遍歷〔D按層遍歷

10.采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的〔.

〔A先序遍歷〔B中序遍歷〔C后序遍歷〔D按層遍歷

11.判定一個有向圖是否存在回路除了可以利用拓撲排序方法外,還可以利用〔.

〔A求關鍵路徑的方法〔B求最短路徑的Dijkstm方法

〔C寬度優(yōu)先遍歷算法〔D深度優(yōu)先遍歷算法

12.用Prim算法求下列連通的帶權圖的最小代價生成樹,在算法執(zhí)行的某刻,已選取的頂點集合U＝{1,2,5},邊的集合TE＝{〔1,2,〔2,5},要選取下一條權值最小的邊,應當從〔組中選取.

<A>{〔1,4,〔3,4,〔3,5,〔2,5}

<B>{〔5,4,〔5,3,〔5,6}

<C>{〔1,2,〔2,3,〔3,5}

<D>{〔3,4,〔3,5,〔4,5,〔1,4}

三、填空題

1.n個頂點的連通圖至少_____________條邊.

2.在一個無環(huán)有向圖G中,若存在一條從頂點i到頂點j的弧,則在頂點的拓撲序列中,頂點i與頂點j的先后次序是_________________.

3.在一個無向圖的鄰接表中,若表結點的個數是m,則圖中邊的條數是________________條.

4.如果從一個頂點出發(fā)又回到該頂點,則此路徑叫做_______.

5.如果從一無向圖的任意頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點,則該圖一定是____________.

6.若采用鄰接表的存儲結構,則圖的廣度優(yōu)先搜索類似于二叉樹的________遍歷.

7.一個連通圖的生成樹是該圖的________連通子圖.若這個連通圖有n個頂點,則它的生成樹有________條邊.

四、算法設計：

1.試在無向圖的鄰接矩陣和鄰接鏈表上實現如下算法：

<1>往圖中插入一個頂點

<2>往圖中插入一條邊

<3>刪去圖中某頂點

<4>刪去圖中某條邊

2.下面的偽代碼是一個廣度優(yōu)先搜索算法,試以下圖中的v0為源點執(zhí)行該算法,請回答下述問題：

<1>對圖中頂點vn+1,它需入隊多少次？它被重復訪問多少次?

<2>若要避免重復訪問同一個頂點的錯誤,應如何修改此算法?

voidBFS<ALGraph*G,intk>

{//以下省略局部變量的說明,visited各分量初值為假

InitQueue<&Q>;//置空隊列

EnQueue<&Q,k>;//k入隊

while<!QueueEmpty<&Q>>{

i=DeQueue<&Q>;//vi出隊

visited[i]=TRUE;//置訪問標記

printf<"%c",G->adjlist[i].vertex;//訪問vi

for<p=G->adjlist[i].firstedge;p;p=p->next>

//依次搜索vi的鄰接點vj<不妨設p->adjvex=j>

if<!visited[p->adjvex]>//若vj沒有訪問過

EnQueue<&Q,p->adjvex>;//vj入隊

}//endofwhile

}//BFS

3.試以鄰接表和鄰接矩陣為存儲結構,分別寫出基于DFS和BFS遍歷的算法來判別頂點vi和vj<i<>j>之間是否有路徑.

4.試分別寫出求DFS和BFS生成樹<或生成森林>的算法,要求打印出所有的樹邊.

5.寫一算法求連通分量的個數并輸出各連通分量的頂點集.

6.設圖中各邊的權值都相等,試以鄰接矩陣和鄰接表為存儲結構,分別寫出算法：

<1>求頂點vi到頂點vj<i<>j>的最短路徑

<2>求源點vi到其余各頂點的最短路徑

要求輸出路徑上的所有頂點<提示：利用BFS遍歷的思想>

7.以鄰接表為存儲結構,寫一個基于DFS遍歷策略的算法,求圖中通過某頂點vk的簡單回路<若存在>.

8.寫一算法求有向圖的所有根<若存在>,分析算法的時間復雜度.參考答案：一、判斷題1、×2、√3、×4、×二、選擇題1.C2.B3.C4.A5.A6.C7、B8、A、C9、A10、D11、D12、B三、填空題1、n-12、i在前,j在后3、m/24、回路5、強連通圖6、按層7、極大；n-1第八章查找一、判斷題

1.用二分查找法對一個順序表進行查找,這個順序表可以是按各鍵值排好序的,也可以是沒有按鍵值排好序的.〔

2.哈希表的查找不用進行關鍵字的比較.〔

3.哈希表的定義函數H〔key=key%p<p<=m>這種方法是直接定址法.〔

4.裝填因子α的值越大,就越不容易發(fā)生沖突.<>

5.選擇hash函數的標準為：隨機性好、均勻性好和盡量避免沖突.<>

二、填空題

1.順序查找法的平均查找長度為__________,二分查找法的平均查找長度為________,分塊查找法<以順序查找確定塊>的平均查找長度為____