嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu)課后習(xí)題與答案解析

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

1.組成數(shù)據(jù)的基本單位是〔

〔A數(shù)據(jù)項(xiàng)〔B數(shù)據(jù)類型〔C數(shù)據(jù)元素〔D數(shù)據(jù)變量

2.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的〔以及它們之間的相互關(guān)系.

〔A理想結(jié)構(gòu),物理結(jié)構(gòu)〔B理想結(jié)構(gòu),抽象結(jié)構(gòu)

〔C物理結(jié)構(gòu),邏輯結(jié)構(gòu)〔D抽象結(jié)構(gòu),邏輯結(jié)構(gòu)

3.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成〔

〔A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)〔B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

〔C線性結(jié)構(gòu)和非線性結(jié)構(gòu)〔D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

4.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的〔①以及它們之間的〔②和運(yùn)算等的學(xué)科.

①〔A數(shù)據(jù)元素〔B計(jì)算方法〔C邏輯存儲(chǔ)〔D數(shù)據(jù)映像

②〔A結(jié)構(gòu)〔B關(guān)系〔C運(yùn)算〔D算法

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

〔A找出數(shù)據(jù)結(jié)構(gòu)的合理性〔B研究算法中的輸入和輸出的關(guān)系

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

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

①〔A計(jì)算方法〔B排序方法〔C解決問(wèn)題的有限運(yùn)算序列〔D調(diào)度方法

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

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

二、判斷題

1.數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu).〔

2.算法就是程序.〔

3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位.〔

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

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

三、填空題

1.數(shù)據(jù)邏輯結(jié)構(gòu)包括________、________、_________和_________四種類型,其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_____.

2.在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn)____前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有______個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)______后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)后續(xù)結(jié)點(diǎn).

3.在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒(méi)有_______結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_________.

4.在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_________.

5.線性結(jié)構(gòu)中元素之間存在________關(guān)系,樹形結(jié)構(gòu)中元素之間存在______關(guān)系,圖形結(jié)構(gòu)中元素之間存在_______關(guān)系.

6.算法的五個(gè)重要特性是_______、_______、______、_______、_______.

7.數(shù)據(jù)結(jié)構(gòu)的三要素是指______、_______和________.

8.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比較,主要優(yōu)點(diǎn)是________________________________.

9.設(shè)有一批數(shù)據(jù)元素,為了最快的存儲(chǔ)某元素,數(shù)據(jù)結(jié)構(gòu)宜用_________結(jié)構(gòu),為了方便插入一個(gè)元素,數(shù)據(jù)結(jié)構(gòu)宜用____________結(jié)構(gòu).四、算法分析題

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

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

x=x+1;

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

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

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

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

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

x=i+j-k;

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

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

1.一個(gè)線性表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是<>

〔A110〔B108〔C100〔D120

2.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變,平均要移動(dòng)〔個(gè)元素.

〔A64〔B63〔C63.5〔D7

3.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),其地址〔.

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

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

4.在一個(gè)單鏈表中,若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn),在p之后插入s所指結(jié)點(diǎn),則執(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.在一個(gè)單鏈表中,若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn),則執(zhí)行〔

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

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

6.下列有關(guān)線性表的敘述中,正確的是〔

〔A線性表中的元素之間隔是線性關(guān)系

〔B線性表中至少有一個(gè)元素

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

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

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

〔A表元素〔B字符〔C數(shù)據(jù)元素〔D數(shù)據(jù)項(xiàng)

二、判斷題

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

2.如果沒(méi)有提供指針類型的語(yǔ)言,就無(wú)法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu).〔

3.線性結(jié)構(gòu)的特點(diǎn)是只有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū),只有一個(gè)結(jié)點(diǎn)沒(méi)有后繼,其余的結(jié)點(diǎn)只有一個(gè)前驅(qū)和后繼.〔

4.語(yǔ)句p=p->next完成了指針賦值并使p指針得到了p指針?biāo)负罄^結(jié)點(diǎn)的數(shù)據(jù)域值.〔

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

三、填空題

1.已知P為單鏈表中的非首尾結(jié)點(diǎn),在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句為：_______________________.

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

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

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

p->prior=q->prior;

q->prior->next=p;

p->next=q;

______________________;

5.已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表,是從下列提供的答案中選擇合適的語(yǔ)句序列,分別實(shí)現(xiàn)：

〔1表尾插入s結(jié)點(diǎn)的語(yǔ)句序列是_______________________________

<2>表尾插入s結(jié)點(diǎn)的語(yǔ)句序列是_______________________________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;四、算法設(shè)計(jì)題

1.試編寫一個(gè)求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)〔數(shù)據(jù)域數(shù)據(jù)類型為整型.

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

3.某百貨公司倉(cāng)庫(kù)中有一批電視機(jī),按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表,每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域.現(xiàn)出庫(kù)〔銷售m臺(tái)價(jià)格為h的電視機(jī),試編寫算法修改原鏈表.

4.某百貨公司倉(cāng)庫(kù)中有一批電視機(jī),按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表,每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域.現(xiàn)新到m臺(tái)價(jià)格為h的電視機(jī),試編寫算法修改原鏈表.

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

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

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

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

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

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

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

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

9.用循環(huán)鏈表作線性表<a0,a1,...,an-1>和〔b0,b1,...,bm-1的存儲(chǔ)結(jié)構(gòu),頭指針?lè)謩e為ah和bh,設(shè)計(jì)C函數(shù),把兩個(gè)線性表合并成形如〔a0,b0,a1,b1,…的線性表,要求不開辟新的動(dòng)態(tài)空間,利用原來(lái)循環(huán)鏈表的結(jié)點(diǎn)完成合并操作,結(jié)構(gòu)仍為循環(huán)鏈表,頭指針為head,并分析算法的時(shí)間復(fù)雜度.

10.試寫出將一個(gè)線性表分解為兩個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表,并將兩個(gè)循環(huán)鏈表的長(zhǎng)度放在各自的頭結(jié)點(diǎn)的數(shù)據(jù)域中的C函數(shù).其中,線性表中序號(hào)為偶數(shù)的元素分解到第一個(gè)循環(huán)鏈表中,序號(hào)為奇數(shù)的元素分解到第二個(gè)循環(huán)鏈表中.

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

12.己知非空線性鏈表中x結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)為y,試寫出刪除x結(jié)點(diǎn)的C函數(shù).

參考答案：一、選擇題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>四、算法設(shè)計(jì)題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;/*假設(shè)數(shù)據(jù)域?yàn)檎?/

structnode*link;

}NODE;

voiddel_link<NODE*head,intx>/*刪除數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)*/

{

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<"無(wú)此產(chǎn)品">;

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之間的元素個(gè)數(shù),對(duì)于不滿足該條件的元素,前移k個(gè)位置,最后修改線性表的長(zhǎng)度.

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;/*修改線性表的長(zhǎng)度*/

}

循環(huán)鏈表:

voiddel<NODE*head,elemtypea,elemtypeb>

{

NODE*p,*q;

p=head;q=p->link;/*假設(shè)循環(huán)鏈表帶有頭結(jié)點(diǎ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.

順序存儲(chǔ):

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

{

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>;

}

該算法的時(shí)間復(fù)雜度為O<n+m>,空間復(fù)雜度為O<1>

鏈接存儲(chǔ):<不帶頭結(jié)點(diǎn)的單鏈表>

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結(jié)點(diǎn)*/

r=q->link;

q->link=NULL;

while<r->link!=NULL>

r=r->link;/*r指向最后一個(gè)bm-1結(jié)點(diǎn)*/

*head=q;

r->link=p;

}

該算法的時(shí)間復(fù)雜度為O<n+m>,但比順序存儲(chǔ)節(jié)省時(shí)間<不需要移動(dòng)元素,只需改變指針>,空間復(fù)雜度為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的結(jié)點(diǎn)個(gè)數(shù)小于等于b的結(jié)點(diǎn)個(gè)數(shù)*/

{

a->link=b;

while<b->link!=bh>

b=b->link;

b->link=head;

}

if<b->link==bh>/*b的結(jié)點(diǎn)個(gè)數(shù)小于a的結(jié)點(diǎn)個(gè)數(shù)*/

{

r=a->link;

a->link=b;

b->link=r;

}

return<head>;

}

該算法的時(shí)間復(fù)雜度為O<n+m>,其中n和m為兩個(gè)循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù).

10.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voidanalyze<NODE*a

{

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

inti=0,j=0；/*i為序號(hào)是奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)j為序號(hào)是偶數(shù)的結(jié)點(diǎn)個(gè)數(shù)*/

p=a；

rh=〔NODE*malloc〔sizeof〔NODE；/*rh為序號(hào)是奇數(shù)的鏈表頭指針*/

qh=<NODE*>malloc<sizeof<NODE>>;/*qh為序號(hào)是偶數(shù)的鏈表頭指針*/

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>/*把后一個(gè)結(jié)點(diǎn)數(shù)據(jù)域前移到前一個(gè)結(jié)點(diǎn)*/

{

p->data=q->data;

q=q->link;

p=q;

p->link=NULL;/*刪除最后一個(gè)結(jié)點(diǎn)*/

free<q>;

}第三章棧和隊(duì)列一、選擇題

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

〔Aedcba〔Bdecba〔Cdceab〔Dabcde

2.棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是〔.

〔A線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)〔B散列方式和索引方式

〔C鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組〔D線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)

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

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

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

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

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

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

5.一個(gè)隊(duì)列的入列序列是1,2,3,4,則隊(duì)列的輸出序列是〔.

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

6.循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放其元素值,已知其頭尾指針?lè)謩e是front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是〔

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

7.棧和隊(duì)列的共同點(diǎn)是〔

〔A都是先進(jìn)后出〔B都是先進(jìn)先出

〔C只允許在端點(diǎn)處插入和刪除元素〔D沒(méi)有共同點(diǎn)

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

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

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

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

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

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

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

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

二、填空題

1.棧的特點(diǎn)是_______________________,隊(duì)列的特點(diǎn)是__________________________.

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

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

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

三、算法設(shè)計(jì)題

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

2.利用兩個(gè)棧s1,s2模擬一個(gè)隊(duì)列時(shí),如何用棧的運(yùn)算來(lái)實(shí)現(xiàn)該隊(duì)列的運(yùn)算?寫出模擬隊(duì)列的插入和刪除的C函數(shù).

一個(gè)棧s1用于插入元素,另一個(gè)棧s2用于刪除元素.參考答案：一、選擇題1.C2.A3.B4.B5.B6.B7、C8、C9、C10、D二、填空題1、先進(jìn)先出；先進(jìn)后出2、線性；任何；棧頂；隊(duì)尾；對(duì)頭3、正確的4、3三、算法設(shè)計(jì)題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.下列關(guān)于串的敘述中,正確的是〔

<A>一個(gè)串的字符個(gè)數(shù)即該串的長(zhǎng)度<B>一個(gè)串的長(zhǎng)度至少是1

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

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.串是一種特殊的線性表,其特殊性表現(xiàn)在〔

<A>可以順序存儲(chǔ)<B>數(shù)據(jù)元素是一個(gè)字符

<C>可以鏈?zhǔn)酱鎯?chǔ)<D>數(shù)據(jù)元素可以是多個(gè)字符

5．設(shè)串S1=‘ABCDEFG’,s2=‘PQRST’,函數(shù)CONCAT〔X,Y返回X和Y串的連接串,SUBSTR〔S,I,J返回串S從序號(hào)I開始的J個(gè)字符組成的字串,LENGTH〔S返回串S的長(zhǎng)度,則CONCAT〔SUBSTR〔S1,2,LENGTH〔S2,SUBSTR〔S1,LENGTH〔S2,2的結(jié)果串是〔

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

二、算法設(shè)計(jì)

1.分別在順序存儲(chǔ)和一般鏈接存儲(chǔ)兩種方式下,用C語(yǔ)言寫出實(shí)現(xiàn)把串s1復(fù)制到串s2的串復(fù)制函數(shù)strcpy<s1,s2>.

2.在一般鏈接存儲(chǔ)<一個(gè)結(jié)點(diǎn)存放一個(gè)字符>方式下,寫出采用簡(jiǎn)單算法實(shí)現(xiàn)串的模式匹配的C語(yǔ)言函數(shù)intL_index<t,p>.參考答案：一、選擇題1.A2.B3.D4.D5.D二、算法設(shè)計(jì)1.

順序存儲(chǔ)：

#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';

}

一般鏈接存儲(chǔ)：

#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>;

}第五章數(shù)組和廣義表

一、選擇題

1.常對(duì)數(shù)組進(jìn)行的兩種基本操作是〔

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

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

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

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

〔A80〔B100〔C240〔D270

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

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

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

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

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

〔A二維數(shù)組和三維數(shù)組〔B三元組和散列

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

7.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣,只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換,就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算,這種觀點(diǎn)〔.

〔A正確〔B錯(cuò)誤

8.設(shè)矩陣A是一個(gè)對(duì)稱矩陣,為了節(jié)省存儲(chǔ),將其下三角部分按行序存放在一維數(shù)組B[1,n<n-1>/2]中,對(duì)下三角部分中任一元素ai,j<i<=j>,在一組數(shù)組B的下標(biāo)位置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.己知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ),每個(gè)元素占k個(gè)存儲(chǔ)單元,并且第一個(gè)元素的存儲(chǔ)地址是LOC<A[0][0]>,則A[0][0]的地址是_____________________.

2.二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ),每個(gè)元素占一個(gè)存儲(chǔ)單元,并且A[0][0]的存儲(chǔ)地址是200,則A[6][12]的地址是________________.

3.有一個(gè)10階對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式<以行序?yàn)橹?且A[0][0]=1>,則A[8][5]的地址是__________________.

4.設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組S[1..n*<n+1>/2]中,若按行序?yàn)橹鞔鎯?chǔ),則A[i][j]對(duì)應(yīng)的S中的存儲(chǔ)位置是________________.

5.若A是按列序?yàn)橹餍蜻M(jìn)行存儲(chǔ)的4×6的二維數(shù)組,其每個(gè)元素占用3個(gè)存儲(chǔ)單元,并且A[0][0]的存儲(chǔ)地址為1000,元素A[1][3]的存儲(chǔ)地址為___________,該數(shù)組共占用_______________個(gè)存儲(chǔ)單元.

三、算法設(shè)計(jì)

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

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

3.數(shù)組和廣義表的算法驗(yàn)證程序

編寫下列程序:

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

<2>計(jì)算廣義表原子結(jié)點(diǎn)個(gè)數(shù)的函數(shù)count_GL<>.

<3>計(jì)算廣義表所有原子結(jié)點(diǎn)數(shù)據(jù)域<設(shè)數(shù)據(jù)域?yàn)檎汀抵偷暮瘮?shù)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三、算法設(shè)計(jì)題1.

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

#include<stdio.h>

#definem3

#definen4

voidminmax<inta[m][n]>

{

inti1,j,have=0;

intmin[m],max[n];

for<i1=0;i1<m;i1++>/*計(jì)算出每行的最小值元素,放入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++>/*計(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<"沒(méi)有鞍點(diǎn)＼n">;

}

2.

算法思想:本題用一個(gè)含有n個(gè)元素的數(shù)組a,初始時(shí)a[i]中存放猴子的編號(hào)i,計(jì)數(shù)器似的值為0.從a[i]開始循環(huán)報(bào)數(shù),每報(bào)一次,計(jì)數(shù)器的值加1,凡報(bào)到m時(shí)便打印出a[i]值<退出圈外的猴子的編號(hào)>,同時(shí)將a[i]的值改為O<以后它不再參加報(bào)數(shù)>,計(jì)數(shù)器值重新置為0.該函數(shù)一直進(jìn)行到n只猴子全部退出圈外為止,最后退出的猴子就是大王.因此,現(xià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>/*求表頭函數(shù)*/

{

return<p->dd.sublist>;

}

NODE*tail<NODE*p>/*求表尾函數(shù)*/

{

return<p->link>;

}

intsum<NODE*p>/*求原子結(jié)點(diǎn)的數(shù)據(jù)域之和函數(shù)*/

{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>/*求表的深度函數(shù)*/

{

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所指結(jié)點(diǎn)沒(méi)有左子樹的充要條件是〔

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

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

2.二叉樹按某種順序線索化后,任一結(jié)點(diǎn)均有指向其前趨和后繼的線索,這種說(shuō)法

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

3.二叉樹的前序遍歷序列中,任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面,這種說(shuō)法〔

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

4.由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹是一種特殊的樹,這種說(shuō)法〔

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

5.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn),則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為〔.

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

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

〔Aacbed〔Bdecab〔Cdeabc〔Dcedba

7.如果T2是由有序樹T轉(zhuǎn)換而來(lái)的二叉樹,那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的〔

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

8.某二叉樹的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是〔.

〔Abdgcefha〔Bgdbecfha〔Cbdgaechf〔Dgdbehfca

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

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

10.按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹有〔種.

〔A3〔B4〔C5〔D6

11.在一非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊〔

〔A只有右子樹上的所有結(jié)點(diǎn)〔B只有右子樹上的部分結(jié)點(diǎn)

〔C只有左子樹上的部分結(jié)點(diǎn)〔D只有左子樹上的所有結(jié)點(diǎn)

12.樹最適合用來(lái)表示〔.

〔A有序數(shù)據(jù)元素〔B無(wú)序數(shù)據(jù)元素

〔C元素之間具有分支層次關(guān)系的數(shù)據(jù)〔D元素之間無(wú)聯(lián)系的數(shù)據(jù)

13.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序〔

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

14.實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu),最佳方案是二叉樹采用〔存儲(chǔ)結(jié)構(gòu).

〔A二叉鏈表〔B廣義表存儲(chǔ)結(jié)構(gòu)〔C三叉鏈表〔D順序存儲(chǔ)結(jié)構(gòu)

15.對(duì)一個(gè)滿二叉樹,m個(gè)樹葉,n個(gè)結(jié)點(diǎn),深度為h,則〔

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

16.如果某二叉樹的前序?yàn)閟tuwv,中序?yàn)閡wtvs,那么該二叉樹的后序?yàn)椤?/p>

〔Auwvts〔Bvwuts〔Cwuvts〔Dwutsv

17.具有五層結(jié)點(diǎn)的二叉平衡樹至少有〔個(gè)結(jié)點(diǎn).

〔A10〔B12〔C15〔D17

二、判斷題

1.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都是2.〔

2.由二叉樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵二叉樹.〔

3.一棵哈夫曼樹中不存在度為1的結(jié)點(diǎn).〔

4.平衡二叉排序樹上任何一個(gè)結(jié)點(diǎn)的左、右子樹的高度之差的絕對(duì)值不大于2〔

三、填空題

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

2.從概念上講,樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu),將樹轉(zhuǎn)化為二叉樹的基本目的是____________

3.若結(jié)點(diǎn)A有三個(gè)兄弟<包括A本身>,并且B是A的雙親結(jié)點(diǎn),B的度是_______________

4.若一棵具有n個(gè)結(jié)點(diǎn)的二叉樹采用標(biāo)準(zhǔn)鏈接存儲(chǔ)結(jié)構(gòu),那么該二叉樹所有結(jié)點(diǎn)共有_______個(gè)空指針域.

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

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

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

1先序和中序遍歷,得到的結(jié)點(diǎn)訪問(wèn)順序一樣._________________________

2后序和中序遍歷,得到的結(jié)點(diǎn)訪問(wèn)順序一樣._________________________

3先序和后序遍歷,得到的結(jié)點(diǎn)訪問(wèn)順序一樣.__________________________

8.一棵含有n個(gè)結(jié)點(diǎn)的k叉樹,可能達(dá)到的最大深度和最小深度各是多少？____________________

9.一棵二叉樹有67個(gè)結(jié)點(diǎn),這些結(jié)點(diǎn)的度要么是0,要么是2.這棵二叉樹中度為2的結(jié)點(diǎn)有______________________個(gè).

10.含有100個(gè)結(jié)點(diǎn)的樹有_______________________________________條邊.

四、問(wèn)答題

1.一棵深度為h的滿m叉樹具有如下性質(zhì):第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn),其余各層上每個(gè)結(jié)點(diǎn)都有m棵非空子樹.若按層次從上到下,每層從左到右的順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào),試計(jì)算:

<1>第k層結(jié)點(diǎn)數(shù)<1≤k≤h>.

<2>整棵樹結(jié)點(diǎn)數(shù).

<3>編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào).

<4>編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)<若有>的編號(hào).

2.證明：一個(gè)滿k叉樹上的葉子結(jié)點(diǎn)數(shù)n0和非葉子結(jié)點(diǎn)數(shù)n1之間滿足以下關(guān)系：n0=〔k-1n1+1

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

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

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

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

4.有七個(gè)帶權(quán)結(jié)點(diǎn),其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹<請(qǐng)按照每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造〉,并計(jì)算出帶權(quán)路徑長(zhǎng)度WPL及該樹的結(jié)點(diǎn)總數(shù).

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

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

②樹種結(jié)點(diǎn)的最大讀書沒(méi)有限制,而二叉樹結(jié)點(diǎn)的最大度數(shù)不能超過(guò)2；

③樹的結(jié)點(diǎn)無(wú)左右之分,而二叉樹的結(jié)點(diǎn)有左右之分.

2、樹可采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問(wèn)題.3、44、n+15、DGEBHJIFCA6、ABDEGCEH

7、①無(wú)左子樹②無(wú)右子樹③僅一個(gè)結(jié)點(diǎn)的二叉樹8、最大n,最小┕log2n┙+19、2210、99四、問(wèn)答題

1.

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

〔3i=1時(shí),該結(jié)點(diǎn)為根,無(wú)雙親結(jié)點(diǎn)；否則其雙親結(jié)點(diǎn)的編號(hào)為〔i+m-2/m

〔4編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)<若有>的編號(hào)為i*m+〔j-〔m-1

2.

證明：設(shè)樹結(jié)點(diǎn)為n,則n=n0+n1

因是滿k叉樹,每個(gè)非葉子結(jié)點(diǎn)引出k個(gè)分支,故有k*n1個(gè)分支.

除根外,每個(gè)分支引出一個(gè)結(jié)點(diǎn),則樹共有k*n1+1個(gè)結(jié)點(diǎn).

所以n0+n1=k*n1+1

n0=<k-1>*n1+1五、算法設(shè)計(jì)

voidparent<inta[],intn,inti>

{

if<i==1>

{

printf<"無(wú)雙親\n">;

return;

}

Else

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

}

voidchild<inta[],intn,inti>/*i為序號(hào)*/

{

intqueue[MAX],front=0,tail=0,p;/*隊(duì)列作為輔助,存儲(chǔ)孩子的序號(hào)*/

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<"請(qǐng)輸入二叉樹的結(jié)點(diǎn)個(gè)數(shù):">;

scanf<"%d",&n>;

input<a,n>;

printf<"請(qǐng)輸入i:">;

scanf<"%d",&i>;

parent<a,n,i>;

child<a,n,i>;

}

二叉樹其他運(yùn)算的算法〔只作參考

#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)計(jì)出二叉樹中單孩子的結(jié)點(diǎn)數(shù)方法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)計(jì)出二叉樹中單孩子的結(jié)點(diǎn)數(shù)方法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)計(jì)出二叉樹中所有結(jié)點(diǎn)數(shù)

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

else

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

}

intleaf<NODE*t>//統(tǒng)計(jì)出二叉樹中葉子結(jié)點(diǎn)數(shù)

{

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的雙親結(jié)點(diǎn)

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>//刪去并釋放數(shù)據(jù)值為k的葉結(jié)點(diǎn)

{NODE*p,*s[100],*q;//q為p的雙親結(jié)點(diǎn)

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>//按層次從上到下,每層從右到左的順序列出二叉樹所有結(jié)點(diǎn)的數(shù)據(jù)信息

{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)計(jì)出二叉樹共有多少個(gè)度為1的結(jié)點(diǎn)

{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];//數(shù)組順序存儲(chǔ)二叉樹

voidchange<NODE*t,inti>//將二叉樹的鏈接存儲(chǔ)轉(zhuǎn)換為順序存儲(chǔ)

{

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.一個(gè)無(wú)向圖的鄰接矩陣中各非零元素之和與圖中邊的條數(shù)相等.〔

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

3.一個(gè)對(duì)稱矩陣一定對(duì)應(yīng)著一個(gè)無(wú)向圖.〔

4.一個(gè)有向圖的鄰接矩陣一定是一個(gè)非對(duì)稱矩陣.〔

二、選擇題

1.在一個(gè)圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的〔倍.

〔A1/2〔B1〔C2〔D4

2.在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的〔倍.

〔A1/2〔B1〔C2〔D4

3.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有〔條邊.

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

4.具有4個(gè)頂點(diǎn)的無(wú)向完全圖有〔條邊.

〔A6〔B12〔C16〔D20

5.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有〔條邊才能確保是一個(gè)連通圖.

〔A5〔B6〔C7〔D8

6.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中,要連通全部頂點(diǎn)至少需要〔條邊.

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

7.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖,若采用鄰接矩陣表示,則該矩陣的大小〔

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

8.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,若采用鄰接表表示,則表頭向量的大小為〔,所有鄰接表中的結(jié)點(diǎn)總數(shù)是〔.

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

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

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

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

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

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

11.判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?還可以利用〔.

〔A求關(guān)鍵路徑的方法〔B求最短路徑的Dijkstm方法

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

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

<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個(gè)頂點(diǎn)的連通圖至少_____________條邊.

2.在一個(gè)無(wú)環(huán)有向圖G中,若存在一條從頂點(diǎn)i到頂點(diǎn)j的弧,則在頂點(diǎn)的拓?fù)湫蛄兄?頂點(diǎn)i與頂點(diǎn)j的先后次序是_________________.

3.在一個(gè)無(wú)向圖的鄰接表中,若表結(jié)點(diǎn)的個(gè)數(shù)是m,則圖中邊的條數(shù)是________________條.

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

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

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

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

四、算法設(shè)計(jì)：

1.試在無(wú)向圖的鄰接矩陣和鄰接鏈表上實(shí)現(xiàn)如下算法：

<1>往圖中插入一個(gè)頂點(diǎn)

<2>往圖中插入一條邊

<3>刪去圖中某頂點(diǎn)

<4>刪去圖中某條邊

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

<1>對(duì)圖中頂點(diǎn)vn+1,它需入隊(duì)多少次？它被重復(fù)訪問(wèn)多少次?

<2>若要避免重復(fù)訪問(wèn)同一個(gè)頂點(diǎn)的錯(cuò)誤,應(yīng)如何修改此算法?

voidBFS<ALGraph*G,intk>

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

InitQueue<&Q>;//置空隊(duì)列

EnQueue<&Q,k>;//k入隊(duì)

while<!QueueEmpty<&Q>>{

i=DeQueue<&Q>;//vi出隊(duì)

visited[i]=TRUE;//置訪問(wèn)標(biāo)記

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

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

//依次搜索vi的鄰接點(diǎn)vj<不妨設(shè)p->adjvex=j>

if<!visited[p->adjvex]>//若vj沒(méi)有訪問(wèn)過(guò)

EnQueue<&Q,p->adjvex>;//vj入隊(duì)

}//endofwhile

}//BFS

3.試以鄰接表和鄰接矩陣為存儲(chǔ)結(jié)構(gòu),分別寫出基于DFS和BFS遍歷的算法來(lái)判別頂點(diǎn)vi和vj<i<>j>之間是否有路徑.

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

5.寫一算法求連通分量的個(gè)數(shù)并輸出各連通分量的頂點(diǎn)集.

6.設(shè)圖中各邊的權(quán)值都相等,試以鄰接矩陣和鄰接表為存儲(chǔ)結(jié)構(gòu),分別寫出算法：

<1>求頂點(diǎn)vi到頂點(diǎn)vj<i<>j>的最短路徑

<2>求源點(diǎn)vi到其余各頂點(diǎn)的最短路徑

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

7.以鄰接表為存儲(chǔ)結(jié)構(gòu),寫一個(gè)基于DFS遍歷策略的算法,求圖中通過(guò)某頂點(diǎn)vk的簡(jiǎn)單回路<若存在>.

8.寫一算法求有向圖的所有根<若存在>,分析算法的時(shí)間復(fù)雜度.參考答案：一、判斷題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、強(qiáng)連通圖6、按層7、極大；n-1第八章查找一、判斷題

1.用二分查找法對(duì)一個(gè)順序表進(jìn)行查找,這個(gè)順序表可以是按各鍵值排好序的,也可以是沒(méi)有按鍵值排好序的.〔

2.哈希表的查找不用進(jìn)行關(guān)鍵字的比較.〔

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

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

5.選擇hash函數(shù)的標(biāo)準(zhǔn)為：隨機(jī)性好、均勻性好和盡量避免沖突.<>

二、填空題

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