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

第一章緒論

一、選擇題

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

（A）數(shù)據(jù)項（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）動態(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ù)值計算的程序設(shè)計問題中計算機(jī)的（①）以及它們之間的（②）

和運(yùn)算等的學(xué)科。

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

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

5.算法分析的目的是（）。

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

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

6.計算機(jī)算法指的是（①），它必須具備輸入、輸出和（②）等5個特性。

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

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

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

二、判斷題

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

2.算法就是程序。（）

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

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

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

三、填空題

1.數(shù)據(jù)邏輯結(jié)構(gòu)包括__、__、.和—四種類型，其中樹形結(jié)構(gòu)

和圖形結(jié)構(gòu)合稱為_____。

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

一個結(jié)點(diǎn)_______后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有________個后續(xù)結(jié)點(diǎn)。

3.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有______結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有________個前驅(qū)結(jié)點(diǎn)；葉

子結(jié)點(diǎn)沒有_________結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_______o

4.在圖形結(jié)構(gòu)中，每個結(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.算法的五個重要特性是______、________、_______、________、________。

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

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

9.設(shè)有一批數(shù)據(jù)元素，為了最快的存儲某元素，數(shù)據(jù)結(jié)構(gòu)宜用________結(jié)構(gòu)，為了方便插入一

個元素，數(shù)據(jù)結(jié)構(gòu)宜用______________結(jié)構(gòu)。

四、算法分析題

1.求下列算法段的語句頻度及時間復(fù)雜度

參考答案：

一、選擇題

1.C2.C3.C4.A、B5.C6.C、B

二、判斷題：

1、J2、X3、X4、義5、J

三、填空題

1、線性、樹形、圖形、集合？；非線性（網(wǎng)狀）2、沒有；1；沒有；13、前驅(qū)；1;后繼;

任意多個4、任意多個5、一對一；一對多；多對多6、有窮性；確定性；可行性；輸入；

輸出7、數(shù)據(jù)元素；邏輯結(jié)構(gòu)；存儲結(jié)構(gòu)8、插入、刪除、合并等操作較方便9、順序存儲;

鏈?zhǔn)酱嬲?/p>

四、算法分析題

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

for(j=1;j<=i;j++)

x=x+1;

分析：該算法為一個二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與

外循環(huán)有關(guān)，因些，時間頻度T(n)=l+2+3+…+n=n*(n+l)/2

有l(wèi)/4WT(n)/n2Wl,故它的時間復(fù)雜度為0(n2),即T(n)與n2數(shù)量級相同。2、分析

下列算法段的時間頻度及時間復(fù)雜度

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

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

for(k=l;k〈=j;k++)

x=i+j-k;

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

由于有1/6WT(n)/n3W1,故時間復(fù)雜度為0(n3)

第二章線性表

一、選擇題

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

(A)110(B)108(C)100(D)120

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

個元素。

(A)64(B)63(C)63.5(D)7

3.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，其地址()。

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

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

4.在一個單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行()

(A)s->next=p;p->next=s;(B)s->next=p-〉next;p->next=s;

(C)s->next=p->next;p=s;(D)p->next=s;s->next=p;

5.在一個單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行()

(A)p->next=p->next->next;(B)p=p->next;p->next=p->next->next;

(C)p->next=p->next;(D)p=p->next->next;

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

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

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

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

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

7.線性表是具有n個（）的有限序列（nWO）

（A）表元素（B）字符（C）數(shù)據(jù)元素（D）數(shù)據(jù)項

二、判斷題

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

2.如果沒有提供指針類型的語言，就無法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)。（）

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

前驅(qū)和后繼。（）

4.語句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)的語句為：

2.順序表中邏輯上相鄰的元素物理位置（）相鄰，單鏈表中邏輯上相鄰的元素物理位置

__________相鄰。

3.線性表匕=（al,a2,an）采用順序存儲，假定在不同的n+1個位置上插入的概率

相同，則插入一個新元素平均需要移動的元素個數(shù)是____________________________

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

p->prior=q->prior;

q->prior->next=p;

p->next=q;

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

（1）表尾插入s結(jié)點(diǎn)的語句序列是_____________________________________

（2）表尾插入s結(jié)點(diǎn)的語句序列是_____________________________________

1.p-〉next=s;

2.p=L;

3.L=s;

4.p->next=s->next;

5.s->next=p->next;

6.s->next=L;

7.s->next=nul1;

8.while(p->next!=Q)?p=p-next;

9.while(p->next!=nul1)p=p->next;

四、算法設(shè)計題

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

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

的c函數(shù)。

3.某百貨公司倉庫中有一批電視機(jī)，按其價格從低到高的次序構(gòu)成一個循環(huán)鏈表，每個結(jié)點(diǎn)

有價格、數(shù)量和鏈指針三個域?，F(xiàn)出庫(銷售)m臺價格為h的電視機(jī)，試編寫算法修改原

鏈表。

4.某百貨公司倉庫中有一批電視機(jī)，按其價格從低到高的次序構(gòu)成一個循環(huán)鏈表，每個結(jié)點(diǎn)

有價格、數(shù)量和鏈指針三個域?，F(xiàn)新到m臺價格為h的電視機(jī)，試編寫算法修改原鏈表。

5.線性表中的元素值按遞增有序排列，針對順序表和循環(huán)鏈表兩種不同的存儲方式，分別編

寫C函數(shù)刪除線性表中值介于a與b(aWb)之間的元素。

6.設(shè)A=(aO,al,a2,...,an-1),B=(bO,bl,b2..bmT)是兩個給定的線性表,它們的結(jié)點(diǎn)個數(shù)

分別是n和%且結(jié)點(diǎn)值均是整數(shù)。

若n=m,且ai=bi(OWi<n),則A=B；

若n<m,且ai=bi(OWi<n),則A<B；

若存在一個j,j<m,j<n,且ai=bi(OWi〈j),若aj<bj,則A<B,否則A〉B。

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

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

8.線性表由前后兩部分性質(zhì)不同的元素組成(aO,al,,an-1,bO,bl,...,bm-1),m和n為兩

部分元素的個數(shù)，若線性表分別采用數(shù)組和鏈表兩種方式存儲，編寫算法將兩部分元素?fù)Q位成

(bO,bl,,bm-1,aO,al,...,an-1),分析兩種存儲方式下算法的時間和空間復(fù)雜度。

9.用循環(huán)鏈表作線性表(aO,al,...,anT)和(bO,bl,...,bm-1)的存儲結(jié)構(gòu)，頭指針分別為

ah和bh,設(shè)計C函數(shù)，把兩個線性表合并成形如(aO,bO,al,bl,…)的線性表，要求不開辟

新的動態(tài)空間，利用原來循環(huán)鏈表的結(jié)點(diǎn)完成合并操作，結(jié)構(gòu)仍為循環(huán)鏈表，頭指針為head,并

分析算法的時間復(fù)雜度。

10.試寫出將一個線性表分解為兩個帶有頭結(jié)點(diǎn)的循環(huán)鏈表，并將兩個循環(huán)鏈表的長度放在各

自的頭結(jié)點(diǎn)的數(shù)據(jù)域中的C函數(shù)。其中，線性表中序號為偶數(shù)的元素分解到第一個循環(huán)鏈表中,

序號為奇數(shù)的元素分解到第二個循環(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、J3、X4、X5、V

三、填空題

1、s->next=p->next;p->next=s;2、一'定；不一(定3、n/24、q->prior=p;5、(1)6)3)

(2)2)9)1)7)

四、算法設(shè)計題

1、

#include〃stdio.h〃

^include/zmalloc.h"

typedefstructnode

{intdata;

structnode*1ink;

}N0DE;

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、

ttinclude"stdio.h〃

ttincludez，malloc.h〃

typedefstructnode

(

intdata;/*假設(shè)數(shù)據(jù)域為整型*/

structnode*1ink;

INODE；

voiddel_link(NODE*head,intx)/*刪除數(shù)據(jù)域為x的結(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(〃無此產(chǎn)品〃)；

if(q->num==0)

(

p->next=q->next;

free(q);

)

)

4、

#include〃stdio.h〃

^include/zmalloc.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&ftq!=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之間的元素個數(shù)，對于不滿足

該條件的元素，前移k個位置，最后修改線性表的長度。

voiddel(elemtype1ist[],int*n,elemtypea,elemtypeb)

(

inti=0,k=0；

while(i<n)

(

if(1ist[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;/*假設(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],1istB[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|Ij>i)return(1);

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

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

free(p);

return(0);

}

8.

順序存儲:

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

inti;

elemtypetemp;

for(i=h;i<=(l+h)/2;i++)

(

temp=list[i];

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

list[1+h-i]=temp;

}

)

voidexchange(elemtype1ist[],intn,intm);

(

convert(1ist,0,n+m-1);

convert(1ist,0,m-1);

convert(1ist,m,n+m-1);

)

該算法的時間復(fù)雜度為0(n+m),空間復(fù)雜度為0(1)

鏈接存儲：(不帶頭結(jié)點(diǎn)的單鏈表)

typedefstructnode

(

elemtypedata;

structnode*1ink;

}N0DE;

voidconvert(NODE**head,intn,intm)

(

NODE*p,*q,*r;

inti;

p=*head;

q=*head;

for(i=0;i<n-l;i++)

q=q->link;/*q指向anT結(jié)點(diǎn)*/

r=q->link;

q->link=NULL;

while(r->link!=NULL)

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

*head=q;

r->link=p;

)

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

間復(fù)雜度為0(1)

9.

typedefstructnode

(

elemtypedata;

structnode*1ink;

}N0DE;

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)個數(shù)小于等于b的結(jié)點(diǎn)個數(shù)*/

a->1ink=b;

while(b->link!=bh)

b=b->link;

b->link=head;

)

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

(

r=a->link;

a->link=b;

b->link=r;

)

return(head);

)

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

10.

typedefstructnode

(

elemtypedata;

structnode*1ink;

}NODE;

voidanalyze(NODE*a)

(

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

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

p=a；

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

qh=(NODE*)malloc(sizeof(NODE));/*qh為序號是偶數(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*1ink;

)N0DE;

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;

elemtypedl;

P=y；

q=x;

while(q->next!=NULL)/*把后一個結(jié)點(diǎn)數(shù)據(jù)域前移到前?個結(jié)點(diǎn)*/

(

p->data=q->data;

q=q->link;

P二q；

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

free(q);

第三章棧和隊列

一、選擇題

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

(A)edcba(B)decba(C)dceab(D)abode

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

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

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

3.判定??個棧ST(最多元素為mO)為空的條件是()。

(A)ST->top!=0(B)ST->top==0

(C)ST-)top!=m0(D)ST-〉top=mO

4.判定一個棧ST(最多元素為mO)為棧滿的條件是()。

(A)ST->top!=0(B)ST->top-=0

(C)ST->top!=mO-l(D)ST->top==mO-l

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

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

6.循環(huán)隊列用數(shù)組A[0,m-l]存放其元素值，已知其頭尾指針分別是front和rear則當(dāng)前隊列

中的元素個數(shù)是()

(A)(rear-front+m)%m(B)rear-front+1(C)rear-front-1(D)rear-front

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

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

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

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

(A)abcd*+-(B)abc+*d-(C)abc*+d-(D)-+*abcd

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

是()

(A)a4,a3,a2,al(B)a3.a2,a4,al

(C)a3,al,a4,a2(D)a3,a4,a2,al

10.以數(shù)組Q[0..m-l]存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)隊列中隊尾

元素的實際位置和當(dāng)前隊列中元素的個數(shù)，隊列第一個元素的實際位置是()

(A)rear—qulen(B)rear—qulen+m

(C)m—qulen(D)1+(rear+m—qulen)%m

二、填空題

1.棧的特點(diǎn)是__________________________隊列的特點(diǎn)是_______________________________。

2.線性表、棧和隊列都是_______________________結(jié)構(gòu)，可以在線性表的________________位置

插入和刪除元素，對于棧只能在插入和刪除元素，對于隊列只能在插入元素

和__________刪除元素。

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

4.設(shè)棧S和隊列Q的初始狀態(tài)皆為空，元素al,a2,a3,a4,a5和a6依次通過一個棧，一

個元素出棧后即進(jìn)入隊列Q,若6個元素出隊列的順序是a3,a5,a4,a6,a2,al則棧S至

少應(yīng)該容納_____個元素。

三、算法設(shè)計題

1.假設(shè)有兩個棧si和s2共享一個數(shù)組stack[M],其中一個棧底設(shè)在stack[0]處，另一個棧

底設(shè)在stack[M-l]處。試編寫對任一棧作進(jìn)棧和出棧運(yùn)算的C函數(shù)push（X,i）和

pop（i）,i=l,2。其中i=l表示左邊的棧，，i=2表示右邊的棧。要求在整個數(shù)組元素都被占用

時才產(chǎn)生溢出。

2.利用兩個棧si,s2模擬一個隊列時，如何用棧的運(yùn)算來實現(xiàn)該隊列的運(yùn)算？寫出模擬隊列的

插入和刪除的C函數(shù)。

一個棧si用于插入元素，另一個棧s2用于刪除元素.

參考答案：

一、選擇題

1.C2.A3.B4.B5.B6.B7、C8、C9、C10、D

二、填空題

1,先進(jìn)先出；先進(jìn)后出2、線性；任何；棧頂：隊尾；對頭3、正確的4、3

三、算法設(shè)計題

1.

ttdefineM100

elemtypestack[M];

inttopl=0,top2=m-l;

intpush(elemtypex,inti)

if(topl-top2==l)return(1);/*上溢處理*/

else

if(i==l)stack[topl++]=x;

if(i==2)stack[top2--]=x;

return(0);

}

intpop(elemtype*px,inti)

(

if(i==l)

if(topl==0)return(1);

else

(

topi--；

*px=stack[topi];

return(0);

)

else

if(i==2)

if(top2==M-l)return(1);

else

(

top2++;

*px=stack[top2];

return(0);

}

}

2.

elemtypesi[MAXSIZE],s2[MAZSIZE];

inttopi,top2;

voidenqueue(elemtypex)

if(topl==MAXSIZE)return(1);

else

(

push(si,x);

return(0);

))

voiddequeue(elemtype*px)

(

elemtypex;

top2=0;

while(!empty(si))

(

pop(si,&x);

push(s2,x);

)

pop(s2,&x);

while(!empty(s2))

(

pop(s2,&x);

push(si,x);

}

}

第四章串

一、選擇題

1.下列關(guān)于串的敘述中，正確的是()

(A)一個串的字符個數(shù)即該串的長度(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(tai1(s)),head(tail(tail(s))))=

，dc'?

(A)abed(B)aebd(C)aedb(D)adeb

4.串是一種特殊的線性表，其特殊性表現(xiàn)在()

(A)可以順序存儲(B)數(shù)據(jù)元素是一個字符

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

5.設(shè)串Sl='ABCDEFG',s2='PQRST',函數(shù)CONCAT(X,Y)返回X和Y串的連接串，SUBSTR

(S,I,J)返回串S從序號I開始的J個字符組成的字串，LENGTH(S)返回串S的長度，

則CONCAT(SUBSTR(SI,2,LENGTH(S2)),SUBSTR(SI,LENGTH(S2),2))的結(jié)果串

是()

(A)BCDEF(B)BCDEFG(C)BCPQRST(D)BCDEFEF

二、算法設(shè)計

1.分別在順序存儲和一般鏈接存儲兩種方式下，用C語言寫出實現(xiàn)把串si復(fù)制到串s2的串復(fù)

制函數(shù)strepy(si,s2)?

2.在一般鏈接存儲(一個結(jié)點(diǎn)存放?個字符)方式下，寫出采用簡單算法實現(xiàn)串的模式匹配的C

語言函數(shù)intLindex(t,p)?

參考答案：

一、選擇題

1.A2.B3.D4.D5.D

二、算法設(shè)計

1.

順序存儲：

ttinclude"string,h”

^defineMAXN100

chars[MAXN];

intSstr1en(chars[1)

inti;

for(i=0;s[i]!='\0';i++);

return(i);

)

voidSstrcpy(charsi[],chars2[])〃4.3題

(

inti;

for(i=0;si[i]!=，\0*;i++)

s2[i]=sl[i];

s2[i"\0';

}

一般鏈接存儲：

ttinclude〃stdio.h〃

typedefstructnode

(

chardata;

structnode*1ink;

}NODE;

NODE*L_strcpy(NODE*sl)

(

NODE*s2,*tl,*t2,*s;

if(sl==NULL)return(NULL);

else

(

tl=sl;

t2=(NODE*)malloc(sizeof(NODE));

s2=t2;

while(tl!=NULL)

(

s=(NODE*)malloc(sizeof(NODE));

s->data=tl->data;

t2->link=s;

12二s;

tl=tl->link;

)

t2->link=NULL;

s=s2;

s2=s2->link;

free(s);

return(s2);

}

)

2.

ttinclude〃stdio.h〃

typedefstructnode

(

chardata;

structnode*1ink;

}NODE;

intL_index(NODE^t,NODE*p)

(

NODE*tl,*pl,*t2;

?inti;

tl=t;i=l;

while(tl!=NULL)

(

pl二P；

t2=t1->1ink;

while(pl->data==tl->data&&pl!=NULL)

(

pl=pl->link;

tl=tl->link;

if(pl==NULL)return(i);

i++；

tl=t2;

)

return(0);

}

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

一、選擇題

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

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

2.二維數(shù)組M的元素是4個字符(每個字符占一個存儲單元)組成的串，行下標(biāo)i的范圍從0到

4,列下標(biāo)j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素()的

起始地址相同。

(A)M[2][4](B)M[3][4](C)M[3][5](D)M[4][4]

3.數(shù)組A[8][10]中，每個元素A的長度為3個字節(jié)，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存

放該數(shù)組至少需要的單元數(shù)是()。

(A)80(B)100(C)240(D)270

4.數(shù)組A[8][10]中，每個元素A的長度為3個字節(jié)，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該

數(shù)組按行存放時，元素A[7][4]的起始地址為()。

(A)SA+141(B)SA+144(C)SA+222(D)SA+225

5.數(shù)組A[8][10]中，每個元素A的長度為3個字節(jié)，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該

數(shù)組按列存放時，元素A[4][7]的起始地址為()。

(A)SA+141(B)SA+180(C)SA+222(D)SA+225

6.稀疏矩陣一般的壓縮存儲方法有兩種，即()。

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

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

7.若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標(biāo)和列下標(biāo)互換，就完成了對

該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)()。

(A)正確(B)錯誤

8.設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組

B[l,n(n-l)/2]中，對下三角部分中任一元素ai,j(i<=j),在一組數(shù)組B的下標(biāo)位置k的值是

()。

(A)i(i-l)/2+j-l(B)i(i-l)/2+j(C)i(i+l)/2+j-l(D)i(i+l)/2+j

二、填空題

1.己知二維數(shù)組采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素

的存儲地址是LOC(A[O][0]),則A[0][0]的地址是_________________________o

2.二維數(shù)組A[10][20]采用列序為主方式存儲，每個元素占一個存儲單元，并且A[0][0]的存

儲地址是200,則A[6][12]的地址是___________________。

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

是_____________________。

4.設(shè)n行n列的下三角矩陣A已壓縮到??維數(shù)組S[1..n*(n+1)/2]中，若按行序為主存儲，則

對應(yīng)的S中的存儲位置是__________。

5.若A是按列序為主序進(jìn)行存儲的4X6的二維數(shù)組，其每個元素占用3個存儲單元，并且

A[0][0]的存儲地址為1000,元素的存儲地址為____________，該數(shù)組共占用

_________________個存儲單元。

三、算法設(shè)計

1.如果矩陣A中存在這樣的一個元素人[門[只滿足條件：人口][只是第i行中值最小的元素，且

又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點(diǎn)。編寫?個函數(shù)計算出IXn的矩

陣A的所有馬鞍點(diǎn)。

2.n只猴子要選大王，選舉辦法如下：所有猴子按1,2,...,n編號圍坐一圈，從1號開始按1、

2...........m報數(shù)，凡報m號的退出到圈外，如此循環(huán)報數(shù)，直到圈內(nèi)剩下只猴子時，這只猴子就

是大王。n和m由鍵盤輸入，打印出最后剩下的猴子號。編寫-程序?qū)崿F(xiàn)上述函數(shù)。

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

編寫下列程序：

(1)求廣義表表頭和表尾的函數(shù)head。和tail0。

(2)計算廣義表原子結(jié)點(diǎn)個數(shù)的函數(shù)count_GL()。

(3)計算廣義表所有原子結(jié)點(diǎn)數(shù)據(jù)域(設(shè)數(shù)據(jù)域為整型〉之和的函數(shù)sumGL()?

參考答案：

一、選擇題

1.C2.B3.C4.C5.B6.C7、B8、B

二、填空題

1、loc(A[0][O])+(n*i+j)*k2、3323、424、i*(i+1)/2+j+15、1039；72

三、算法設(shè)計題

1.

算法思想：依題意，先求出每行的最小值元素，放入之中，再求出每列的最大值元素，放

入max[n]之中，若某元素既在min[i]中，又在max[j]中，則該元素A[i][j]便是馬鞍點(diǎn)，找出所

有這樣的元素，即找到了所有馬鞍點(diǎn)。因此，實現(xiàn)本題功能的程序如下：

#include<stdio.h>

#definem3

#definen4

voidminmax(inta[m][n])

(

inti1,j,have=0;

intmin[m],max[n];

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

(

min[il]=a[il][0];

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

if(a[il][j]<min[il])min[il]=a[il][j];

}

for(j=0;j〈n;j++)/*計算出每列的最大值元素，放入max[n]之中*/

(

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

for(i1=1;il<m;i1++)

if(a[il][j]>max[j])max[j]=a[il][j];

for(i1=0;il<m;i1++)

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

if(min[i1]==max[j])

(

printf(〃(％d,%d):%d\n”,il,j,a[il][j]);

have=l;

}

if(!have)printf(〃沒有鞍點(diǎn)\n〃);

)

2.

算法思想：本題用一個含有n個元素的數(shù)組a,初始時a[i]中存放猴子的編號i,計數(shù)器似的值

為0。從a[i]開始循環(huán)報數(shù)，每報一次，計數(shù)器的值加1,凡報到m時便打印出a[i]值(退出圈

外的猴子的編號)，同時將a[i]的值改為0(以后它不再參加報數(shù))，計數(shù)器值重新置為0o該函

數(shù)一直進(jìn)行到n只猴子全部退出圈外為止，最后退出的猴子就是大王。因此，現(xiàn)本題功能的程

序如下：

ttinclude〃stdio.h〃

main()

(

inta[100];

intcount,d,j,m,n;

scanf(，z%d%d”,&m,&n);/*n>=m*/

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

a[j]=j+l;

count=0;d=0;

while(d<n)

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

if(a[j]!=O)

(

count++;

if(count二二m)

printf(〃％d〃，a[j]);

a[j]=O;

count=O;

d++;

3.

ttinclude〃stdio.h〃

ttinclude"malloc.h〃

typedefstructnode

{inttag;

union

{structnode*sublist;

chardata;

}dd;

structnode*1ink;

}NODE;

NODE*creat_GL(char**s)

(

NODE*h;

charch;

ch=*(*s);

(*s)++;

if<ch!=，\0,)

(

h=(NODE*)malloc(sizeof(NODE));

if(ch=='(')

(

h->tag=l;

h->dd.sublist=creatGL(s);

Else

h->tag=O;

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==l)

(

printf(〃(〃);

if(p->dd.sublist二二NULL)

printf(z，〃)；

else

prnGL(p->dd.sublist);

}

else

printf(〃％c〃，p->dd.data);

if(p->tag==l)

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->1ink=copyGL(p->link);

return(q);

}

NODE*head(N0DE*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==l&&p->dd.sublist==NULL)return1;

else

(

maxdh=O;

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(tai1(hd));

hc=copy_GL(hd);

printf(/zcopyafter:z");

prn_GL(he);

printf("sum:%d\n”,sum(hd));

printf("depth:%d\n”,depth(hd));

}

第六章樹和二叉樹

一、選擇題

L在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是()

(A)t->left==NULL(B)t-)ltag==l

(C)t->ltag=l且t-〉left=NULL(D)以上都不對

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

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

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

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

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

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

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

()o

(A)2h(B)2h-l(C)2h+l(D)h+1

6.已知某二叉樹的后序遍歷序列是dabec