自考-數(shù)據(jù)結(jié)構(gòu)(考試題)

第1章緒論

1.1簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(shù)據(jù)類型、

算法。

答：

?數(shù)據(jù)：是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。

?數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)

數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)組成，也可以只由一個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素又被稱為元素、結(jié)

點(diǎn)或記錄。

?數(shù)據(jù)項(xiàng)：是指數(shù)據(jù)的不可分割的、含有獨(dú)立意義的最小單位，數(shù)據(jù)項(xiàng)有時(shí)也稱字段或域。

?數(shù)據(jù)邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)主要是研究數(shù)據(jù)元素之間的關(guān)聯(lián)方式。數(shù)據(jù)元素之間存在的i種

或多種特定的關(guān)系被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。通常有集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)四

類基本結(jié)構(gòu)。

?數(shù)據(jù)存儲結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的存放方式稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲結(jié)構(gòu)。數(shù)據(jù)的

存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn)。

?數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看

作是程序設(shè)計(jì)語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。

?算法：指解決特定問題的一種方法或一種描述。

1.2分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。

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

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

s++;

答：s++;語句頻度為：nXn,時(shí)間復(fù)雜度為：0(n?)

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

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

s++;

答:s++;語句頻度為：n+n-l+-+l=n(n+l)/2,時(shí)間復(fù)雜度為:0(n2)

(3)for(i=1;i<=n;i++)

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

s++;

答：s++;語句頻度為：1+2+…+n=n(n+l)/2,時(shí)間復(fù)雜度為：0(n2)

(4)i=l;k=0;

while(i<=n-1){

k+=10*i;

i++；

答:i++；語句頻度為：n-1,時(shí)間復(fù)雜度為：0(n)

1.4按n的增長率由小至大的順序排列下列各函數(shù):

J

(2/3)",(3/2)",n,n",n!,2"，n,log2n,n'

答：

常見的時(shí)間復(fù)雜度按數(shù)量級遞增排列，依次為：常數(shù)階0(1)、對數(shù)階0(log21')＞線性階

0(n)、線性對數(shù)階0(nlog2")、平方階0(n?)、立方階0(一)、k次方階0(祐)、指數(shù)階0(20)。

先將題中的函數(shù)分成如下幾類：

對數(shù)階:log2n

線性階:n

2

平方階:n

立方階:n

指數(shù)階(按指數(shù)由小到大排)：(3/2)\2、n!、n"

注意：(2/3)”由于底數(shù)小于1,所以是一個(gè)遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階。

根據(jù)以上分析按增長率由小至大的順序可排列如下：

(2/3)n<log2n<n<n<n3<(3/2)n<2"<n!<n"

1.5試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X,Y和Z的值。

答：

#include<stdio.h>

voidsort(int*a,intn)

(

inttemp,i,j;

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

for(j=0;j<n-i-l;j++)//冒泡法使數(shù)組元素按自大至小排列

if(a[j]<a[j+l])

(

temp=a[j];

a[j]=a[j+l];

a[j+l]=temp;

)

)

voidmainO

(

inti,a[3];

printf(“請輸入數(shù)組元素:“)；

for(i=0;i<3;i++)

scanf;〃輸入數(shù)組

sort(a,3);

for(i=0;i<3;i++)〃輸出數(shù)組

printf("自大至小數(shù)組元素%d",a[i]);

)

1.6編一程序，輸出所有小于等于n(n為一個(gè)大于2的正整數(shù))的素?cái)?shù)。

答：

#include<stdio.h>

#include<math.h>

intprime(intx)//判斷正整數(shù)x是否為素?cái)?shù)

(

inti;

for(i=2;i<(int)sqrt(x);i++)

if(x%i==O)

return0;

}

return1;

)

voidmain()

(

intn,i,j=0;〃j用于累計(jì)素?cái)?shù)個(gè)數(shù)

printf(z/n：");

scanf(級d”,&n);

printf("小于等于%d的素?cái)?shù):/n”,n);

if(n>2)

(

printf2);

j++；

}

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

(

if(prime(i)==l)

(

printf("%4d”,i);

if(j!=0&&++j%10==0)〃每行最多顯示10個(gè)素?cái)?shù)

printf("/n");

)

}

printf("/n");

1.7舉出一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及在其結(jié)構(gòu)上的操作內(nèi)容。

答：

例如有一張學(xué)生體檢情況登記表，記錄了一個(gè)班的學(xué)生的身高、體重等各項(xiàng)體檢信息。

這張登記表中，每個(gè)學(xué)生的各項(xiàng)體檢信息排在一行上。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄（有

姓名，學(xué)號，身高和體重等字段）就是一個(gè)結(jié)點(diǎn)，對于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)（它的

前面無記錄）和一個(gè)終端結(jié)點(diǎn)（它的后面無記錄），其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨

和直接后繼（它的前面和后面均有且只有一個(gè)記錄）。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)

是線性結(jié)構(gòu)。

這個(gè)表中的數(shù)據(jù)如何存儲到計(jì)算機(jī)里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢？即用一片

連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接

呢？這就是存儲結(jié)構(gòu)的問題。

在這個(gè)表的某種存儲結(jié)構(gòu)基礎(chǔ)上，可實(shí)現(xiàn)對這張表中的記錄進(jìn)行查詢，修改，刪除等操作。

對這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問題了。

1.8判斷以下敘述的正確性。

(1)數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。

答：正確

(2)數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲形式。

答：正確

(3)順序存儲方式只能用于存儲線性結(jié)構(gòu)。

答：錯(cuò)誤。順序存儲方式只能用于存儲線性結(jié)構(gòu)，也可以用于存儲樹形結(jié)構(gòu)。

(4)邏輯結(jié)構(gòu)不相同的數(shù)據(jù)，要采用不同的存儲方法來存儲。

答：錯(cuò)誤。邏輯結(jié)構(gòu)不相同的數(shù)據(jù)，既可采用相同的存儲方法也可采用不同的存儲方法來存

儲。

1.9編寫一程序，計(jì)算任一輸入的正整數(shù)的各位數(shù)字之和。

答：

#include<stdio.h>

intmain()

(

intn,s,t;

while(scanf(〃％d〃，&n),n)

(

s=0;

t=n;

while(t)

(

s+=t%10;

t/=10;

)

printfC%d%d\n",n,s);

)

)

第2章線性表

2.1?個(gè)順序表元素值有序遞增，編寫算法，刪除順序表中值相同的多余元素。

答：

voidDeleteList(SEQUENLISTa)

(

inti=0,j;

while(i<a.last-1)

(

if(a.datas[i]!=a.datas[i+l])

i++；

else

{for(j=i;j<a,last-1;j++)

a.datas[j]=a.datas[j+1];

a.last一;

)

)

)

2.2一個(gè)順序表元素值無序，編寫算法，刪除順序表中值相同的多余元素。

答：

voidDelList(SEQUENLISTa)

(

inti,j,k;

DATATYPE1temp;

for(i=0;i<a.last;i++)

{

temp=a.datas[i];

for(j=i+l;j<a.last;j++)

if(temp==a.datas[j])

(

for(k=j;k<a.last;k++)

a.datas[k]=a.datas[k+1];

a.last—;

)

)

}

2.3編寫程序，將一順序表A中的元素逆置，要求算法所用的輔助空間盡可能地少。

答：

voidInvertList(SEQUENLISTa)

{inti,j;

DATATYPE1t;

i=0;

j=a.last-1;

while(i<j)

{t=a.datas[i];

a.datas[i]=a.datas[j];

a.datas[j]=t;

i++；

J—；

)

)

2.4編寫程序，輸出已知順序表A中元素的最大值和次最大值。

答：

voidPrintList(SEQUENLISTa)

(

DATATYPE1maxi,max2,i,j;

maxl=max2=a.datas[0];

for(i=l;i<a.last;i++)

{

if(a.datas[i]>max1)

(

max2=maxi;

maxi=a.datas[i];

)

elseif(a.datas[i]>max2)

{

max2=a.datas[i];

)

else;

)

printf("順序表A中的最大值為:%d,次大值為：%d\n,>,maxi,max2);

}

2.5設(shè)有兩個(gè)按元素值遞增有序的順序表A和表B,編寫程序?qū)⒈鞟和表B歸并成一個(gè)新的

遞增有序的順序表C(值相同的元素均保留在表C中)。

答：

voidMergeList(SEQUENLISTla,SEQUENLISTlb,SEQUENLIST1c)

inti=0,j=0,k=0;

while(i<la.last&&j<lb.last)

if(la.datas[i]<=lb.datas[j])

(

1c.datas[k]=la.datas[i];

k++;

i++；

)

else

(

1c.datas[k]=lb.datas[j];

k++;

j++；

}

while(i<la.last)

{

1c.datas[k]=la.datas[i];

k++;

i++；

)

while(j<lb.last)

(

1c.datas[k]=lb.datas[j];

k++;

j++；

)

1c.last=k;

)

2.6已知兩個(gè)順序表A和表B,同一表中無重復(fù)元素，編寫程序?qū)崿F(xiàn)表A和表B的并集運(yùn)算,

并集結(jié)果放在表A中。

答：

voidUnionList(SEQUENLIST*la,SEQUENLIST*lb)

(

inti,j;

for(j=0;j<lb->last;j++)

{

for(i=0;i<la->last&&la->datas[i]!=lb->datas[j];i++);

if(i>=la->last-l)

la->datas[la->last]=lb->datas[j];

la->last++;

)

)

)

2.7已知一順序表A,設(shè)計(jì)一個(gè)算法刪除順序表中值為item的數(shù)據(jù)元素。

答：

voidDelList(SEQUENLISTla,DATATYPE1item)

(

inti,k;

k=0;

while(k<la.last&&la.datas[k]!=item)

k++;

if(k<la.last)

{

for(i=k;i<la.last-1;i++)

la.datas[i]=la.datas[i+1];

la.last——;

2.8已知一順序表A,表中都是不相等的整數(shù)。設(shè)計(jì)一個(gè)算法，把表中所有的奇數(shù)移到所有

的偶數(shù)前面去。

答：

voidMoveList(SEQUENLIST*la)

(

inti,j,k；

DATATYPE1x;

for(i=0;i<la->last;i++)

{

x=la->datas[i];

if(x%2==l)

(

for(k=i;k<la->last-l;k++)

la->datas[k]-la->datas[k+l];

la->last一;

for(j=la->last-l;j>=0;j-)

la->datas[j+l]=la->datas[j];

la->datas[O]=x;

la->last++;

2.9已知兩個(gè)順序表A和表B,同一表中無重復(fù)元素，編寫程序?qū)崿F(xiàn)表A和表B的交集運(yùn)算,

交集結(jié)果放在表A中。

答：

voidIntersectionList(SEQUENLIST*la,SEQUENLIST*lb)

(

inti,j,k；

for(i=0;i<la->last;i++)

(

for(j=0;j<lb->last&&lb->datas[j]!=la->datas[i];j++);

if(j>lb->last-l)

(

for(k=i;k<la->last-l;k++)

la->datas[k]=la->datas[k+1];

la->last一;

i—；

)

)

)

2.10已知兩個(gè)順序表A和表B,同一表中無重復(fù)元素，編寫程序?qū)崿F(xiàn)表A和表B的差集運(yùn)算,

差集結(jié)果放在表A中。

答：

voidDifferenceList(SEQUENLIST*la,SEQUENLIST*lb)

(

inti,j,k；

for(i=0;i<la->last;i++)

(

for(j=0;j<lb->last;j++)

if(lb->datas[j]==la->datas[i])

for(k=i;k<la->last-l;k++)

la->datas[k]=la->datas[k+l];

la->last―;

i一；

break;

)

)

)

)

第3章鏈?zhǔn)酱鎯Y(jié)構(gòu)

3.1若線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求快速存取表中元素，應(yīng)

采用哪種存儲結(jié)構(gòu)？為什么？

答：

應(yīng)采用順序存儲結(jié)構(gòu)。

順序表是一種向量結(jié)構(gòu)，它是隨機(jī)存取結(jié)構(gòu)，表中任一元素都可以通過計(jì)算直接得到地

址進(jìn)行存取，時(shí)間復(fù)雜度為0(1)o而鏈表中的數(shù)據(jù)元素需要從頭指針起順著鏈掃描才能取得。

在順序表中進(jìn)行元素的插入和刪除時(shí)，平均要移動近一半的元素，而在鏈表中插入和刪

除元素只需要修改指針。

因此，若線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求快速存取表中元

素，應(yīng)采用順序存儲結(jié)構(gòu)。

3.2對線性表而言，什么情況下采用鏈表比順序表好？

答：

順序表的存儲空間是靜態(tài)分配的，在程序運(yùn)行前必須明確規(guī)定它的存儲規(guī)模，鏈表的存

儲空間是動態(tài)分配的，只要內(nèi)存空間有空閑，就不會分配不到。因此，在線性表的長度變化

較大，預(yù)先難以確定的情況下，最好采用動態(tài)鏈表作為存儲結(jié)構(gòu)。

在順序表中進(jìn)行元素的插入和刪除時(shí)，平均要移動近一半的元素，而在鏈表中插入和刪

除元素只需要修改指針。因此，線性表上若頻繁進(jìn)行插入和刪除操作時(shí)，采用鏈表結(jié)構(gòu)為宜。

3.3分析單鏈表、循環(huán)鏈表和雙向鏈表的相同點(diǎn)和不同點(diǎn)，及各自的特點(diǎn)。

答：

相同點(diǎn)：

存儲空間是動態(tài)分配的，只要內(nèi)存空間有空閑，就不會分配不到，邏輯上相鄰的元素不

要求結(jié)點(diǎn)的空間連續(xù)，訪問鏈表中的結(jié)點(diǎn)是順序的存取方式，在插入與刪除數(shù)據(jù)時(shí)不需移動

大量的數(shù)據(jù)元素，只需要改變一些指針的鏈接。

不同點(diǎn)：

單鏈表中的每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域，尾結(jié)點(diǎn)的鏈域?yàn)镹ULL,從表中任一結(jié)點(diǎn)出發(fā)只能找

到該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。

循環(huán)鏈表是一種首尾相接的鏈表，尾結(jié)點(diǎn)的鏈域?yàn)殒湵眍^指針的值，從表中任一結(jié)點(diǎn)出

發(fā)均可找到表中其他所有結(jié)點(diǎn)。

雙向鏈表是一種對稱結(jié)構(gòu)，有兩個(gè)鏈域，它克服了單鏈表上指針單向性的缺點(diǎn)，既有前

向鏈乂有后向鏈，從表中任一結(jié)點(diǎn)出發(fā)能快速找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，而前面兩

種鏈表從任一結(jié)點(diǎn)出發(fā)找其前驅(qū)結(jié)點(diǎn)都需花費(fèi)一定的時(shí)間。另外，雙向鏈表上數(shù)據(jù)元素的插

入操作和刪除操作都很方便。

3.4已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首結(jié)點(diǎn)，也不是尾結(jié)點(diǎn)，試從下列提供

的語句中選出合適的語句序列，完成下面的操作。

(1)在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)：④①

(2)在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)：⑥⑧?⑨①

(3)在表首插入S結(jié)點(diǎn)：⑤?

(4)在表尾插入S結(jié)點(diǎn)：⑦⑧⑩(11)①

①P->next=S;

②P->next=P->next->next;

③P->next=S->next;

④S->next=P->next;

⑤S->next=L;

⑥S->next=P;

⑦S->next=NULL;

⑧Q=P;

⑨while(P->next!=Q)P=P->next;

⑩while(Q->next!=NULL)Q=Q->next;

(11)P=Q;

?P=L;

?L=S;

(14)L=P;

3.5單項(xiàng)選擇題：

(1)在一個(gè)長度為n的順序表中向第i個(gè)元素(0<iWn+D之前插入一個(gè)新元素時(shí)，需向后移

動B個(gè)元素。

A.n-iB.n-i+1C.n-i-1D.i

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

A.必須是連續(xù)的B.一定是不連續(xù)的

C.部分地址必須是連續(xù)的D.連續(xù)與否均可以

(3)在一個(gè)單鏈表中，刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是D。

A.p->next=p;B.p->next->next=p->next;

C.p->next->next=p;D.p->next=p->next->next;

（4）在一個(gè)雙鏈表中，在*p結(jié)點(diǎn)之后插入結(jié)點(diǎn)*s的操作是.D。

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

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

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

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

（5）在不帶頭結(jié)點(diǎn)*head的單循環(huán)鏈表中，尾結(jié)點(diǎn)*p的條件是D。

A.head!=NULLB.head->next!=head

C.p==NULLD.p->next==head

3.6判斷以下敘述的正確性。

（1）分配給單鏈表的內(nèi)存單元地址必須是連續(xù)的。（錯(cuò)）

（2）與順序表相比，在鏈表上實(shí)現(xiàn)順序訪問，其算法的效率比較低。（錯(cuò)）

（3）向順序表中插入一個(gè)元素，平均要移動約一半的元素。（對）

（4）如果在循環(huán)單鏈表中，任何一個(gè)結(jié)點(diǎn)的指針都不可能為空。（對）

（5）在有n個(gè)元素的順序表中，刪除任意一個(gè)元素所需移動結(jié)點(diǎn)的平均次數(shù)為n-E（錯(cuò)

）

3.7設(shè)計(jì)一個(gè)算法，在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表上，用最少的輔助空間實(shí)現(xiàn)單鏈表元素的逆

置。

答：

voidInvertLink（LINKLIST**head）

（

LINKLIST*p,*s;

p=*head;

*head=NULL;

while（p!=NULL）

（

s=p;

p=p->next;

s->next=*head;

*head=s;

3.8按下列要求建立單鏈表，編寫程序?qū)崿F(xiàn):

（1）按頭插入法建立不帶頭結(jié)點(diǎn)的單鏈表。

（2）按頭插入法建立帶頭結(jié)點(diǎn)的單鏈表。

（3）按尾插入法建立不帶頭結(jié)點(diǎn)的單鏈表。

（4）按尾插入法建立帶頭結(jié)點(diǎn)的單鏈表。

答：

〃頭插法建立不帶頭結(jié)點(diǎn)的單鏈表

LINKLIST*CreateLink()

(

LINKLIST*head=NULL,*t;

intx;

scanf(〃%d〃,&x);

while(x!=-l)

(

t=(LINKLIST*)malloc(sizeof(LINKLIST));

t->data=x;

t->next=head;

head=t;

scanf(〃%d",&x);

}

return(head);

)

〃頭插法建立帶頭結(jié)點(diǎn)的單鏈表

LINKLIST*CreateLink()

(

LINKLIST*head,*t;

intx;

head=(LINKLISTmalloc(sizeof(LINKLIST));

head->next=NULL;

scanf&x);

while(x!=~l)

(

t=(LINKLIST*)malloc(sizeof(LINKLIST));

t->data=x;

t->next=head->next;

head-〉next二t;

scanf(〃%d”,&x);

)

return(head);

〃尾插法建立不帶頭結(jié)點(diǎn)的單鏈表

LINKLIST*CreateLink()

LINKLIST*head=NULL,*t,*r;

intx;

scanf(〃％d〃，&x);

while(x!=-l)

(

t=(LINKLIST*)malloc(sizeof(LINKLIST))：

t->data=x;

t->next=NULL;

if(head==NULL)

head=r=t;

else

(

r->next=t;

r=t;

)

scanf(〃%d”,&x);

)

return(head);

)

〃尾插法建立帶頭結(jié)點(diǎn)的單鏈表

LINKLIST*CreateLink()

{

LINKLIST*head,

intx;

head=r=(LINKLIST*)malloc(sizeof(LINKLIST));

scanf("%d〃,&x);

while(x!=-l)

(

t=(LINKLIST*)malloc(sizeof(LINKLIST));

t->data=x;

r->next=t;

r=t;

scanf(〃%d〃,&x);

)

r->next=NULL;

return(head);

3.9設(shè)L為帶頭結(jié)點(diǎn)的單鏈表，表中元素值遞增有序，編寫程序刪除表中值相同的多余元素。

答：

voidDeleteLink(LINKLIST*head)

(

LINKLIST*p=head->next,*q;

while(p->next!=NULL)

(

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

(

q=p->next;

p->next=q->next;

free(q);

)

else

p=p->next;

)

)

3.10設(shè)L為帶頭結(jié)點(diǎn)的單鏈表，表中元素值無序，編寫程序刪除表中值相同的多余元素。

答：

voidDeleteLink(LINKLIST*head)

(

LINKLIST*p,*q,*s;

p=head->next;

while(p->next!=NULL)

(

s=p;

q=p->next;

while(q!=NULL)

(

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

(

s->next=q->next;

free(q);

q=s->next;

}

else

s=q;

q=q->next;

)

)

p=p->next;

3.11在一個(gè)帶頭結(jié)點(diǎn)的單鏈表上，表中元素值遞增有序，編一程序，在單鏈表中插入一元素,

插入后表中元素值仍保持遞增有序。

答：

voidInsertLink(LINKLIST*head,intx)

(

LINKLIST*p=head,*s;

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

s->data=x;

while(p->next!=NULL&&p->next->data<x)

p=p->next;

s->next=p->next;

p->next=s;

)

3.12設(shè)有兩個(gè)按元素值遞增有序的帶頭結(jié)點(diǎn)的單鏈表A和表B,編寫程序?qū)⒈鞟和表B歸并

成一個(gè)新的遞增有序的帶頭結(jié)點(diǎn)的單鏈表C(值相同的元素均保留在表C中)。

答：

LINKLIST*MergeLink(LINKLIST*ha,LINKLIST*hb)

(

LINKLIST*hc,*p,*q,*s,*r;

hc=r=(LINKLIST*)malloc(sizeof(LINKLIST));

hc->next=NULL;

p=ha->next;

q=hb->next;

while(p!=NULL&&q!=NULL)

(

if(p->data<q->data)

(

r->next=p;

r=P；

p=p->next;

else

r->next=q;

r=q;

q=q->next;

)

)

if(p==NULL)

r->next=q;

if(q==NULL)

r->next=p;

returnhe;

)

3.13設(shè)有兩個(gè)線性表A和表B皆是單鏈表存儲結(jié)構(gòu)。同一個(gè)表中的元素各不相同，且遞增有

序。編寫一算法，將A和B的并集構(gòu)成一新的線性表C,且表C中元素也遞增有序。

答：

LINKLIST*UnionLink(LINKLIST*ha,LINKLIST*hb)

(

LINKLIST*hc,*p,*q,*s,*r;

hc=r=(LINKLIST*)malloc(sizeof(LINKLIST));

hc->next=NULL;

p=ha->next;

q=hb->next;

while(p!=NULL&&q!=NULL)

(

if(p->data<q->data)

(

r->next=p;

r=p;

p=p->next;

}

elseif(p->data>q->data)

(

r->next=q;

r=q;

q=q->next;

else

r->next=p;

r=p;

p=p->next;

s=q;

q=q->next;

free(s);

)

)

if(p==NULL)

r->next=q;

if(q==NULL)

r->next=p;

returnhe;

3.15敘述線性表的兩種存儲結(jié)構(gòu)各自的特點(diǎn)。

答：

順序表的存儲空間是靜態(tài)分配的，在程序運(yùn)行前必須明確規(guī)定它的存儲規(guī)模，占用連續(xù)

的內(nèi)存空間，元素的訪問是通過數(shù)組下標(biāo)來實(shí)現(xiàn)的，是隨機(jī)存取方式，在插入與刪除數(shù)據(jù)時(shí)

需移動大量的數(shù)據(jù)元素。

鏈表的存儲空間是動態(tài)分配的，只要內(nèi)存空間有空閑，就不會分配不到，不要求結(jié)點(diǎn)的

空間連續(xù)，訪問鏈表中的結(jié)點(diǎn)必須從表頭開始，是順序的存取方式，在插入與刪除數(shù)據(jù)時(shí)不

需移動大量的數(shù)據(jù)元素，只需要改變一些指針的鏈接，鏈表多了一個(gè)指針域，故較浪費(fèi)空間。

因此，在數(shù)據(jù)存取方面，順序表優(yōu)于鏈表；在對線性表進(jìn)行頻繁的插入和刪除操作時(shí)，

鏈表優(yōu)于順序表；在空間占用方面，順序表優(yōu)于鏈表；在進(jìn)行數(shù)據(jù)的合并與分離時(shí)，鏈表優(yōu)

于順序表。

3.16已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的語句中選出合適的語句序列，

完成下面的操作。

(1)在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)：⑦?⑥③

(2)在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)：⑤⑧?④

(3)刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)：?①(11)?

(4)刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)：?②⑩(18)

(5)刪除P結(jié)點(diǎn)：⑨(14)?

①P->next=P->next->next;

②P->prior=P->prior->prior;

③P->next=S;

④P->prior=S;

⑤S->next=P;

⑥S->prior=P;

⑦S->next=P->next;

⑧S->prior=P->prior;

⑨P->prior->nextP->next;

⑩P->prior->nextP;

(11)P->next->priorP；

?P->next->priorS;

(13)P->prior->nextS;

(14)P->next->priorP->prior;

(15)Q=P->next;

(16)Q=P->prior;

(17)free(P);

(18)free(Q);

3.17單項(xiàng)選擇題

（1）在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是D。

A.單鏈表B.雙鏈表C.循環(huán)鏈表D.順序表

（2）在單鏈表中，若*p結(jié)點(diǎn)不是末尾結(jié)點(diǎn)，在其后插入*s結(jié)點(diǎn)的操作是.B。

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;

（3）在帶頭結(jié)點(diǎn)*head的單循環(huán)鏈表中，至少有一個(gè)結(jié)點(diǎn)的條件是B。

A.head->next!=NULLB.head->next!=head

C.p==NULLD.p->next==head

3.18判斷以下敘述的正確性。

（1）順序存儲方式的優(yōu)點(diǎn)是存儲率高，且插入元素和刪除元素效率高。（錯(cuò)）

（2）線性表的鏈?zhǔn)酱鎯Ψ绞絻?yōu)于順序存儲方式。（錯(cuò)）

（3）順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。（對）

（4）對于單鏈表，只有從頭結(jié)點(diǎn)（或第一個(gè)元素結(jié)點(diǎn)）開始才能掃描表中全部結(jié)點(diǎn)。（對

）

（5）對于單循環(huán)鏈表，從表中任一結(jié)點(diǎn)出發(fā)都能掃描表中全部結(jié)點(diǎn)。（對）

（6）雙鏈表的特點(diǎn)是找結(jié)點(diǎn)的前趨結(jié)點(diǎn)很容易，找結(jié)點(diǎn)的后繼結(jié)點(diǎn)不容易。

（錯(cuò)）

3.19對應(yīng)書中圖3.11所示的循環(huán)鏈表的結(jié)構(gòu)，寫出下列兩個(gè)算法。

（1）在表尾的最后元素后插入一個(gè)元素X。

（2）在表的第一個(gè)元素前插入元素X。

答：

〃在表尾的最后元素后插入一個(gè)元素X

voidInsertDLink(DLINKLIST*head,intx)

DLINKLIST*p=head->next,*s;

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

s->data=x;

while(p->next!=head)

p=p->next;

s->next=head;

p->next=s;

s->prior=p;

head->prior=s;

)

〃在表的第一個(gè)元素前插入元素X

voidInsertDLink(DLINKLIST*head,intx)

{

DLINKLIST*s;

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

s->data=x;

s->next=head->next;

head->next->prior=s;

s->prior=head;

head-〉next=s;

)

3.20設(shè)計(jì)一個(gè)算法判定一個(gè)帶頭結(jié)點(diǎn)的單鏈表的元素值是否是遞增的。

答：

voidIsAscentSortLink(LINKLIST*head)

(

LINKLIST*p,*q;

p=head->next;

q=p->next;

while(q!=NULL)

(

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

(

P=q；

q=q->next;

)

else

break;

)

if(q==NULL)

printf(",AA'±IHAOaE0OgEQHYO6ODDdHA￡i\n");

else

printf(",AA'±iMOaE0OM2?回應(yīng)依?氏叫￡i\n");

)

3.21設(shè)有兩個(gè)線性表A和表B,都是單鏈表存儲結(jié)構(gòu)。同一個(gè)表中的元素各不相同，且遞增

有序。編寫一程序，構(gòu)一新的線性表C,C為A和B的交集，且C中元素也遞增有序。

答：

LINKLIST*IntersectionLink(LINKLIST*ha,LINKLIST*hb)

(

LINKLIST*hc,*p,*q,*s,*r;

hc=r=(LINKLIST*)malloc(sizeof(LINKLIST));

hc->next=NULL;

p=ha->next;

q=hb->next;

while(p!=NULL&&q!=NULL)

(

if(p->data<q->data)

p=p->next;

elseif(p->data>q->data)

q=q->next;

else

(

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

s->data=p->data;

r->next=s;

r=s;

p=p->next;

q=q->next;

)

)

r->next=NULL;

returnhe;

3.22設(shè)有兩個(gè)線性表A和表B,都是單鏈表存儲結(jié)構(gòu)。同一個(gè)表中的元素各不相同，且遞增

有序。編寫一程序，構(gòu)一新的線性表C,C為A和B的差集，且C中元素也遞增有序。

答：

LINKLIST*DifferenceLink(LINKLIST*ha,LINKLIST*hb)

(

LINKLIST*hc,*p,*q,*s,*r;

hc=r=(LINKLIST*)malloc(sizeof(LINKLIST))：

hc->next=NULL;

p=ha->next;

q=hb->next;

while(p!=NULL&&q!=NULL)

{

if(p->data<q->data)

(

r->next=p;

r=p;

p=p->next;

)

elseif(p->data>q->data)

q=q->next;

else

{

s=p;

p=p->next;

q=q->next;

free(s);

)

)

if(p==NULL)

r->next=NULL;

if(q==NULL)

r->next=p;

q=hb->next;

while(q!=NULL)

(

s=q；

q=q->next;

free(s);

hb->next=NULL;

returnhe;

)

第4章棧和隊(duì)列

4.1簡述棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)，以及它們與線性表的相同點(diǎn)和不同

點(diǎn)。

答：

棧和隊(duì)列的相同點(diǎn)：棧和隊(duì)列都是操作受限的線性表。

棧和隊(duì)列的不同點(diǎn)：棧只能在一端進(jìn)行插入和刪除操作，是一種后進(jìn)先出表；隊(duì)列在一

端進(jìn)行插入操作，在另一端進(jìn)行刪除操作，是一種先進(jìn)先出表

棧和隊(duì)列與線性表的相同點(diǎn)：都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。

棧和隊(duì)列與線性表的不同點(diǎn)：和線性表相比，它們的插入和刪除操作受更多的約束和限

定。

4.2如果進(jìn)棧的元素序列為A、B、C、D,則可能得到的出棧序列有多少？寫出全部的可能

序列。

答：

可能得到的出棧序列有14種。

ABCDABDCACBDACDBADCBBACDBADC

BCADBCDABDCACBADCBDACDBADCBA

4.3如果進(jìn)棧的元素序列為1,2,3,4,5,6,能否得到4,3,5,6,1,2和1,3,5,4,

2,6的出棧序列？并說明為什么不能得到或如何得到。

答：

不能得到4,3,5,6,1,2的出棧序列，因棧的特點(diǎn)是后進(jìn)先出，2在1之后入棧且并

未出棧，故2必須在1之前出棧；

能得到1,3,5,4,2,6的出棧序列，具體操作如下：

1進(jìn)1出，2進(jìn)，3進(jìn)3出，4進(jìn)，5進(jìn)5出，4出，2出，6進(jìn)6出，即可得到出棧序列：

1,3,5,4,2,6o

4.4寫出下列程序段的運(yùn)行結(jié)果(隊(duì)列中的元素類型是char)。

main()

SEQQUEUEa,*q;

charx,y;

q=&a;

x=，e，;

y='c,;

initqueue(q);

enqueue(q,'h');

enqueue(q,'r');

enqueue(q,y);

x=dequeue(q);

enqueue(q,x);

x=dequeue(q);

enqueue(q,'a');

while(!empty(q))

{

y=dequeue(q);

printf("%c”,y);

)

printf("％c\n”，x);

}

答：

char

4.5假設(shè)以I和0分別表示入棧和出棧操作，棧的初始和終態(tài)均為空，入棧和出棧的操作序

列可表示為僅由I和0組成的序列，下面所示的序列中那些是正確的？

(1)IOIIOIOO(2)IOOIOIIO(3)IIIOIOIO(4)IIIOOIOO

答：

正確的序列有：(1)和(4)

4.6對于向量結(jié)構(gòu)的循環(huán)隊(duì)列，寫出計(jì)算隊(duì)列中元素個(gè)數(shù)的公式。

答：

公式如下(設(shè)front指向隊(duì)首元素的前一位置，rear指向隊(duì)尾元素，向量空間大?。?/p>

MAXSIZE)

QUEUELEN=(MAXSIZE+rear-front)%MAXSIZE

4.7單項(xiàng)選擇題：

(1)已知一個(gè)棧的進(jìn)棧序列是1,2,3,…,n,其輸出序列是pl,p2,…,pn,若pl=n,則pi的

值.C。

A.iB.n-iC.n-i+1D.不確定

(2)設(shè)n個(gè)元素的進(jìn)棧序列是1,2,3,…，n,其輸出序列是pl,p2,…,pn,若pl=3,則p2的

值A(chǔ)o

A.可能是2B.一定是2C.可能是1D.一定是1

（3）設(shè)n個(gè)元素進(jìn)棧的序列是pl,p2,…,pn,其輸出序列是1,2,3,…,n,若p3=3,則pl的

值A(chǔ)。

A.可能是2B.一定是2C.不可能是1D.一定是1

4.8判斷以下敘述的正確性。

（1）棧底元素是不能刪除的元素。（錯(cuò)）

（2）順序棧中元素值的大小必須是有序的。（錯(cuò)）

（3）棧是一種對進(jìn)棧、出棧操作總次數(shù)做了限制的線性表。（錯(cuò)）

（4）對順序棧進(jìn)行進(jìn)棧、出棧操作，不涉及元素的前、后移動問題。（對）

（5）空棧沒有棧頂指針。（錯(cuò)）

4.9編寫一個(gè)程序?qū)崿F(xiàn)在順序棧上的各種基本操作，用一個(gè)主程序串成。

（1）棧的初始化。

（2）棧不滿的情況下元素進(jìn)棧。

（3）棧不空的情況下元素出棧。

（4）輸出棧中元素。

（5）計(jì)算棧中元素個(gè)數(shù)。

答：

#include<stdio.h>

#defineMAXSIZE100

typedefstruct

（

intdata[MAXSIZE];

inttop;

}SEQSTACK;

voidinitstack(SEQSTACK*s)

(

s->top=0;

intempty(SEQSTACK*s)

(

if(s->top==0)

return1;

else

return0;

voidpush(SEQSTACK*s,intx)

(

if(s->top==MAXSIZE-l)

(

printf(z，0verflow\n，/);

return;

)

else

{

s->top++;

s->data[s->top]=x;

}

)

voidpop(SEQSTACK*s,int*m)

(

if(empty(s))

(

printf("Underflow、');

return;

)

else

(

*m=s->data[s->top];

s->top一;

voidprintstack(SEQSTACK*s)

(

inty;

while(!empty(s))

(

pop(s,&y);

printf(〃%4d〃，y);

)

printf(〃\n〃)；

intcountstack(SEQSTACK*s)

(

returns->top;

)

voidmainO

{

SEQSTACKp;

initstack(&p);

push(&p,10);

push(&p,20);

push(&p,30);

push(&p,11);

push(&p,100);

printf(z/0?0D0aE0M,6fiyia￡°%d￡-OA，IIa￡°\n〃,countstack(&p))；

printstack(&p);

)

4.10編寫一個(gè)程序?qū)崿F(xiàn)在循環(huán)隊(duì)列上的各種基本操作，用一個(gè)主程序串成。

(1)循環(huán)隊(duì)列的初始化。

(2)隊(duì)列不滿的情況下元素入隊(duì)列。

(3)隊(duì)列不空的情況下元素出隊(duì)列。

(4)輸出隊(duì)列中元素。

(5)計(jì)算隊(duì)列中元素個(gè)數(shù)。

答：

#include<stdio.h>

#defineQueueSize100

typedefstruct{

intfront;

intrear;

intdata[QueueSize];

}CirQueue;

voidinitQueue(CirQueue*Q)

Q->front=Q->rear=0;

intemptyQueue(CirQueue*Q)

(

returnQ->front==Q->rear;

)

intfullQueue(CirQueue*Q)

(

return(Q->rear+l)%QueueSize==Q->front;

)

voiddeQueue(CirQueue*Q,int*temp)

(

if(emptyQueue(Q))

(

printf(〃隊(duì)列空\n〃);

return;

)

else

(

*temp=Q->data[Q->front];

Q->front=(Q->fror)t+l)%QueueSize;

}

)

voidenQueue(CirQueue*Q,intx)

(

if(fullQueue(Q))

(

printf(〃隊(duì)列滿\n〃);

return;

)

else

Q->data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;

)

intfrontQueue(CirQueue*Q)

(

if(emptyQueue(Q))

{

printf(〃隊(duì)列空\n〃);

returnNULL;

}

else

returnQ->data[Q->front];

I

intcountQueue(CirQueue*Q)

(

intnum;

num=(QueueSize+Q->rear-Q->front)%QueueSize;

returnnum;

)

voidprintQueue(CirQueue*Q)

(

inty;

while(!emptyQueue(Q))

(

deQueue(Q,&y);

printfC%4dz/,y)：

)

printf("\n");

)

voidmain()

(

inti,m;

CirQueuep;

initQueue(&p);

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

scanf(級d”,&m);

enQueue(&p,m);

)

printf("隊(duì)列中的元素個(gè)數(shù)為:%d,其值依次為：\n”,counlQueue(&p));

printQueue(&p);

4.11編一程序，將輸入的非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)輸出(在順序棧結(jié)構(gòu)上實(shí)現(xiàn))。

答：

voidinitstack(SEQSTACK*s)

(

s->top=0;

)

intempty(SEQSTACK*s)

(

if(s->top==0)

return1;

else

return0;

)

voidpush(SEQSTACK*s,intx)

(

if(s->top==MAXSIZE-l)

{

printf("Overflow"");

return;

)

else

(

s->top++;

s->data[s->top]=x;

)

)

voidpop(SEQSTACK*s,int*m)

if(empty(s))

printf("Underflow\n〃);

return;

)

else

(

*m=s->data[s->top];

s->top一;

voidd_to_o(unsignedx)

(

SEQSTACKs;

intm;

initstack(&s);

while(x!=0)

(

push(&s,x%8);

x=x/8;

)

while(!empty(&s))

(

pop(&s,&m);

printfCW;m);

)

printfCW);

4.12在一個(gè)表達(dá)式中含有括號“和“)”并可嵌套使用，編一程序，判斷表達(dá)式中的括

號是否正確配對。

答：

intcheck(SEQSTACK*s)

{

intbool;

charch;

push(s,';

ch=getchar();

bool=1;

while(ch!='\n'&&bool)

(

if(ch=二'(')

push(s,ch);〃遇左括號，左括號入棧

if(ch=')')〃遇右括號

if(gettop(s)==，#')

bool=0;//無左括號配對，則出錯(cuò)

else

pop(s);//有左括號配對，則去左括號

ch=getchar();

}

if(gettop(s)!='#')//左括號數(shù)目多于右括號，出錯(cuò)

bool=0;

if(bool)

printfC,right");

else

printferrorff);

}

main()

(

SEQSTACKst,*s;

s=&st;

initstack(s);

check(s);

)

4.13編寫一個(gè)鏈隊(duì)列管理的程序。這是一個(gè)加深理解在鏈隊(duì)列結(jié)構(gòu)上元素插入和刪除的程

序。在建立的帶頭結(jié)點(diǎn)的空鏈隊(duì)列上，如果輸入奇數(shù)，則奇數(shù)入隊(duì)列；如果輸入偶數(shù)，則隊(duì)

列中的第一個(gè)元素出隊(duì)列；如果輸入0,則退出程序。

答：

voidout1inkqueue(LINKQUEUE*q)〃顯示隊(duì)列中的值

(

LINKQLIST*p;

p=q->front;

printf("Queue:");

while(p!=q->rear)

p=p->next;

printf("%d",p->data);

printf(,z\n");

main()

LINKQUEUElq,*p;

intj;

p=&lq;

initlinkqueue(p);

printf("Inputainteger:");

scanf("