




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
第1章緒論
1.1簡述下列術(shù)語:數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(shù)據(jù)類型、
算法。
答:
?數(shù)據(jù):是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。
?數(shù)據(jù)元素:是數(shù)據(jù)的基本單位,在計算機程序中通常作為一個整體進行考慮和處理。一個
數(shù)據(jù)元素可以由若干數(shù)據(jù)項組成,也可以只由一個數(shù)據(jù)項組成。數(shù)據(jù)元素又被稱為元素、結(jié)
點或記錄。
?數(shù)據(jù)項:是指數(shù)據(jù)的不可分割的、含有獨立意義的最小單位,數(shù)據(jù)項有時也稱字段或域。
?數(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ù)在計算機中的存放方式稱為數(shù)據(jù)的物理結(jié)構(gòu),又稱存儲結(jié)構(gòu)。數(shù)據(jù)的
存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機存儲器中的實現(xiàn)。
?數(shù)據(jù)類型:是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看
作是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。
?算法:指解決特定問題的一種方法或一種描述。
1.2分析下面語句段執(zhí)行的時間復(fù)雜度。
(1)for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;
答:s++;語句頻度為:nXn,時間復(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,時間復(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,時間復(fù)雜度為:0(n2)
(4)i=l;k=0;
while(i<=n-1){
k+=10*i;
i++;
答:i++;語句頻度為:n-1,時間復(fù)雜度為:0(n)
1.4按n的增長率由小至大的順序排列下列各函數(shù):
J
(2/3)",(3/2)",n,n",n!,2",n,log2n,n'
答:
常見的時間復(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,所以是一個遞減函數(shù),其數(shù)量級應(yīng)小于常數(shù)階。
根據(jù)以上分析按增長率由小至大的順序可排列如下:
(2/3)n<log2n<n<n<n3<(3/2)n<2"<n!<n"
1.5試寫一算法,自大至小依次輸出順序讀入的三個整數(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為一個大于2的正整數(shù))的素數(shù)。
答:
#include<stdio.h>
#include<math.h>
intprime(intx)//判斷正整數(shù)x是否為素數(shù)
(
inti;
for(i=2;i<(int)sqrt(x);i++)
if(x%i==O)
return0;
}
return1;
)
voidmain()
(
intn,i,j=0;〃j用于累計素數(shù)個數(shù)
printf(z/n:");
scanf(級d”,&n);
printf("小于等于%d的素數(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個素數(shù)
printf("/n");
)
}
printf("/n");
1.7舉出一個數(shù)據(jù)結(jié)構(gòu)的例子,敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及在其結(jié)構(gòu)上的操作內(nèi)容。
答:
例如有一張學(xué)生體檢情況登記表,記錄了一個班的學(xué)生的身高、體重等各項體檢信息。
這張登記表中,每個學(xué)生的各項體檢信息排在一行上。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有
姓名,學(xué)號,身高和體重等字段)就是一個結(jié)點,對于整個表來說,只有一個開始結(jié)點(它的
前面無記錄)和一個終端結(jié)點(它的后面無記錄),其他的結(jié)點則各有一個也只有一個直接前趨
和直接后繼(它的前面和后面均有且只有一個記錄)。這幾個關(guān)系就確定了這個表的邏輯結(jié)構(gòu)
是線性結(jié)構(gòu)。
這個表中的數(shù)據(jù)如何存儲到計算機里,并且如何表示數(shù)據(jù)元素之間的關(guān)系呢?即用一片
連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機存放各結(jié)點數(shù)據(jù)再用指針進行鏈接
呢?這就是存儲結(jié)構(gòu)的問題。
在這個表的某種存儲結(jié)構(gòu)基礎(chǔ)上,可實現(xiàn)對這張表中的記錄進行查詢,修改,刪除等操作。
對這個表可以進行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。
1.8判斷以下敘述的正確性。
(1)數(shù)據(jù)項是數(shù)據(jù)的最小單位。
答:正確
(2)數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。
答:正確
(3)順序存儲方式只能用于存儲線性結(jié)構(gòu)。
答:錯誤。順序存儲方式只能用于存儲線性結(jié)構(gòu),也可以用于存儲樹形結(jié)構(gòu)。
(4)邏輯結(jié)構(gòu)不相同的數(shù)據(jù),要采用不同的存儲方法來存儲。
答:錯誤。邏輯結(jié)構(gòu)不相同的數(shù)據(jù),既可采用相同的存儲方法也可采用不同的存儲方法來存
儲。
1.9編寫一程序,計算任一輸入的正整數(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?個順序表元素值有序遞增,編寫算法,刪除順序表中值相同的多余元素。
答:
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一個順序表元素值無序,編寫算法,刪除順序表中值相同的多余元素。
答:
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è)有兩個按元素值遞增有序的順序表A和表B,編寫程序?qū)⒈鞟和表B歸并成一個新的
遞增有序的順序表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已知兩個順序表A和表B,同一表中無重復(fù)元素,編寫程序?qū)崿F(xiàn)表A和表B的并集運算,
并集結(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è)計一個算法刪除順序表中值為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è)計一個算法,把表中所有的奇數(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已知兩個順序表A和表B,同一表中無重復(fù)元素,編寫程序?qū)崿F(xiàn)表A和表B的交集運算,
交集結(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已知兩個順序表A和表B,同一表中無重復(fù)元素,編寫程序?qū)崿F(xiàn)表A和表B的差集運算,
差集結(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)定,且很少進行插入和刪除,但要求快速存取表中元素,應(yīng)
采用哪種存儲結(jié)構(gòu)?為什么?
答:
應(yīng)采用順序存儲結(jié)構(gòu)。
順序表是一種向量結(jié)構(gòu),它是隨機存取結(jié)構(gòu),表中任一元素都可以通過計算直接得到地
址進行存取,時間復(fù)雜度為0(1)o而鏈表中的數(shù)據(jù)元素需要從頭指針起順著鏈掃描才能取得。
在順序表中進行元素的插入和刪除時,平均要移動近一半的元素,而在鏈表中插入和刪
除元素只需要修改指針。
因此,若線性表的元素總數(shù)基本穩(wěn)定,且很少進行插入和刪除,但要求快速存取表中元
素,應(yīng)采用順序存儲結(jié)構(gòu)。
3.2對線性表而言,什么情況下采用鏈表比順序表好?
答:
順序表的存儲空間是靜態(tài)分配的,在程序運行前必須明確規(guī)定它的存儲規(guī)模,鏈表的存
儲空間是動態(tài)分配的,只要內(nèi)存空間有空閑,就不會分配不到。因此,在線性表的長度變化
較大,預(yù)先難以確定的情況下,最好采用動態(tài)鏈表作為存儲結(jié)構(gòu)。
在順序表中進行元素的插入和刪除時,平均要移動近一半的元素,而在鏈表中插入和刪
除元素只需要修改指針。因此,線性表上若頻繁進行插入和刪除操作時,采用鏈表結(jié)構(gòu)為宜。
3.3分析單鏈表、循環(huán)鏈表和雙向鏈表的相同點和不同點,及各自的特點。
答:
相同點:
存儲空間是動態(tài)分配的,只要內(nèi)存空間有空閑,就不會分配不到,邏輯上相鄰的元素不
要求結(jié)點的空間連續(xù),訪問鏈表中的結(jié)點是順序的存取方式,在插入與刪除數(shù)據(jù)時不需移動
大量的數(shù)據(jù)元素,只需要改變一些指針的鏈接。
不同點:
單鏈表中的每個結(jié)點只有一個鏈域,尾結(jié)點的鏈域為NULL,從表中任一結(jié)點出發(fā)只能找
到該結(jié)點的后繼結(jié)點。
循環(huán)鏈表是一種首尾相接的鏈表,尾結(jié)點的鏈域為鏈表頭指針的值,從表中任一結(jié)點出
發(fā)均可找到表中其他所有結(jié)點。
雙向鏈表是一種對稱結(jié)構(gòu),有兩個鏈域,它克服了單鏈表上指針單向性的缺點,既有前
向鏈乂有后向鏈,從表中任一結(jié)點出發(fā)能快速找到該結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點,而前面兩
種鏈表從任一結(jié)點出發(fā)找其前驅(qū)結(jié)點都需花費一定的時間。另外,雙向鏈表上數(shù)據(jù)元素的插
入操作和刪除操作都很方便。
3.4已知L是無表頭結(jié)點的單鏈表,且P結(jié)點既不是首結(jié)點,也不是尾結(jié)點,試從下列提供
的語句中選出合適的語句序列,完成下面的操作。
(1)在P結(jié)點后插入S結(jié)點:④①
(2)在P結(jié)點前插入S結(jié)點:⑥⑧?⑨①
(3)在表首插入S結(jié)點:⑤?
(4)在表尾插入S結(jié)點:⑦⑧⑩(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單項選擇題:
(1)在一個長度為n的順序表中向第i個元素(0<iWn+D之前插入一個新元素時,需向后移
動B個元素。
A.n-iB.n-i+1C.n-i-1D.i
(2)線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時,其地址D。
A.必須是連續(xù)的B.一定是不連續(xù)的
C.部分地址必須是連續(xù)的D.連續(xù)與否均可以
(3)在一個單鏈表中,刪除*p結(jié)點之后的一個結(jié)點的操作是D。
A.p->next=p;B.p->next->next=p->next;
C.p->next->next=p;D.p->next=p->next->next;
(4)在一個雙鏈表中,在*p結(jié)點之后插入結(jié)點*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é)點*head的單循環(huán)鏈表中,尾結(jié)點*p的條件是D。
A.head!=NULLB.head->next!=head
C.p==NULLD.p->next==head
3.6判斷以下敘述的正確性。
(1)分配給單鏈表的內(nèi)存單元地址必須是連續(xù)的。(錯)
(2)與順序表相比,在鏈表上實現(xiàn)順序訪問,其算法的效率比較低。(錯)
(3)向順序表中插入一個元素,平均要移動約一半的元素。(對)
(4)如果在循環(huán)單鏈表中,任何一個結(jié)點的指針都不可能為空。(對)
(5)在有n個元素的順序表中,刪除任意一個元素所需移動結(jié)點的平均次數(shù)為n-E(錯
)
3.7設(shè)計一個算法,在一個不帶頭結(jié)點的單鏈表上,用最少的輔助空間實現(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é)點的單鏈表。
(2)按頭插入法建立帶頭結(jié)點的單鏈表。
(3)按尾插入法建立不帶頭結(jié)點的單鏈表。
(4)按尾插入法建立帶頭結(jié)點的單鏈表。
答:
〃頭插法建立不帶頭結(jié)點的單鏈表
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é)點的單鏈表
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é)點的單鏈表
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é)點的單鏈表
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é)點的單鏈表,表中元素值遞增有序,編寫程序刪除表中值相同的多余元素。
答:
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é)點的單鏈表,表中元素值無序,編寫程序刪除表中值相同的多余元素。
答:
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在一個帶頭結(jié)點的單鏈表上,表中元素值遞增有序,編一程序,在單鏈表中插入一元素,
插入后表中元素值仍保持遞增有序。
答:
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è)有兩個按元素值遞增有序的帶頭結(jié)點的單鏈表A和表B,編寫程序?qū)⒈鞟和表B歸并
成一個新的遞增有序的帶頭結(jié)點的單鏈表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è)有兩個線性表A和表B皆是單鏈表存儲結(jié)構(gòu)。同一個表中的元素各不相同,且遞增有
序。編寫一算法,將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)各自的特點。
答:
順序表的存儲空間是靜態(tài)分配的,在程序運行前必須明確規(guī)定它的存儲規(guī)模,占用連續(xù)
的內(nèi)存空間,元素的訪問是通過數(shù)組下標(biāo)來實現(xiàn)的,是隨機存取方式,在插入與刪除數(shù)據(jù)時
需移動大量的數(shù)據(jù)元素。
鏈表的存儲空間是動態(tài)分配的,只要內(nèi)存空間有空閑,就不會分配不到,不要求結(jié)點的
空間連續(xù),訪問鏈表中的結(jié)點必須從表頭開始,是順序的存取方式,在插入與刪除數(shù)據(jù)時不
需移動大量的數(shù)據(jù)元素,只需要改變一些指針的鏈接,鏈表多了一個指針域,故較浪費空間。
因此,在數(shù)據(jù)存取方面,順序表優(yōu)于鏈表;在對線性表進行頻繁的插入和刪除操作時,
鏈表優(yōu)于順序表;在空間占用方面,順序表優(yōu)于鏈表;在進行數(shù)據(jù)的合并與分離時,鏈表優(yōu)
于順序表。
3.16已知P結(jié)點是某雙向鏈表的中間結(jié)點,試從下列提供的語句中選出合適的語句序列,
完成下面的操作。
(1)在P結(jié)點后插入S結(jié)點:⑦?⑥③
(2)在P結(jié)點前插入S結(jié)點:⑤⑧?④
(3)刪除P結(jié)點的直接后繼結(jié)點:?①(11)?
(4)刪除P結(jié)點的直接前驅(qū)結(jié)點:?②⑩(18)
(5)刪除P結(jié)點:⑨(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單項選擇題
(1)在線性表的下列存儲結(jié)構(gòu)中,讀取元素花費時間最少的是D。
A.單鏈表B.雙鏈表C.循環(huán)鏈表D.順序表
(2)在單鏈表中,若*p結(jié)點不是末尾結(jié)點,在其后插入*s結(jié)點的操作是.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é)點*head的單循環(huán)鏈表中,至少有一個結(jié)點的條件是B。
A.head->next!=NULLB.head->next!=head
C.p==NULLD.p->next==head
3.18判斷以下敘述的正確性。
(1)順序存儲方式的優(yōu)點是存儲率高,且插入元素和刪除元素效率高。(錯)
(2)線性表的鏈?zhǔn)酱鎯Ψ绞絻?yōu)于順序存儲方式。(錯)
(3)順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu),鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。(對)
(4)對于單鏈表,只有從頭結(jié)點(或第一個元素結(jié)點)開始才能掃描表中全部結(jié)點。(對
)
(5)對于單循環(huán)鏈表,從表中任一結(jié)點出發(fā)都能掃描表中全部結(jié)點。(對)
(6)雙鏈表的特點是找結(jié)點的前趨結(jié)點很容易,找結(jié)點的后繼結(jié)點不容易。
(錯)
3.19對應(yīng)書中圖3.11所示的循環(huán)鏈表的結(jié)構(gòu),寫出下列兩個算法。
(1)在表尾的最后元素后插入一個元素X。
(2)在表的第一個元素前插入元素X。
答:
〃在表尾的最后元素后插入一個元素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;
)
〃在表的第一個元素前插入元素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è)計一個算法判定一個帶頭結(jié)點的單鏈表的元素值是否是遞增的。
答:
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è)有兩個線性表A和表B,都是單鏈表存儲結(jié)構(gòu)。同一個表中的元素各不相同,且遞增
有序。編寫一程序,構(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è)有兩個線性表A和表B,都是單鏈表存儲結(jié)構(gòu)。同一個表中的元素各不相同,且遞增
有序。編寫一程序,構(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章棧和隊列
4.1簡述棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點和不同點,以及它們與線性表的相同點和不同
點。
答:
棧和隊列的相同點:棧和隊列都是操作受限的線性表。
棧和隊列的不同點:棧只能在一端進行插入和刪除操作,是一種后進先出表;隊列在一
端進行插入操作,在另一端進行刪除操作,是一種先進先出表
棧和隊列與線性表的相同點:都是線性結(jié)構(gòu),即數(shù)據(jù)元素之間的關(guān)系相同。
棧和隊列與線性表的不同點:和線性表相比,它們的插入和刪除操作受更多的約束和限
定。
4.2如果進棧的元素序列為A、B、C、D,則可能得到的出棧序列有多少?寫出全部的可能
序列。
答:
可能得到的出棧序列有14種。
ABCDABDCACBDACDBADCBBACDBADC
BCADBCDABDCACBADCBDACDBADCBA
4.3如果進棧的元素序列為1,2,3,4,5,6,能否得到4,3,5,6,1,2和1,3,5,4,
2,6的出棧序列?并說明為什么不能得到或如何得到。
答:
不能得到4,3,5,6,1,2的出棧序列,因棧的特點是后進先出,2在1之后入棧且并
未出棧,故2必須在1之前出棧;
能得到1,3,5,4,2,6的出棧序列,具體操作如下:
1進1出,2進,3進3出,4進,5進5出,4出,2出,6進6出,即可得到出棧序列:
1,3,5,4,2,6o
4.4寫出下列程序段的運行結(jié)果(隊列中的元素類型是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)隊列,寫出計算隊列中元素個數(shù)的公式。
答:
公式如下(設(shè)front指向隊首元素的前一位置,rear指向隊尾元素,向量空間大小:
MAXSIZE)
QUEUELEN=(MAXSIZE+rear-front)%MAXSIZE
4.7單項選擇題:
(1)已知一個棧的進棧序列是1,2,3,…,n,其輸出序列是pl,p2,…,pn,若pl=n,則pi的
值.C。
A.iB.n-iC.n-i+1D.不確定
(2)設(shè)n個元素的進棧序列是1,2,3,…,n,其輸出序列是pl,p2,…,pn,若pl=3,則p2的
值A(chǔ)o
A.可能是2B.一定是2C.可能是1D.一定是1
(3)設(shè)n個元素進棧的序列是pl,p2,…,pn,其輸出序列是1,2,3,…,n,若p3=3,則pl的
值A(chǔ)。
A.可能是2B.一定是2C.不可能是1D.一定是1
4.8判斷以下敘述的正確性。
(1)棧底元素是不能刪除的元素。(錯)
(2)順序棧中元素值的大小必須是有序的。(錯)
(3)棧是一種對進棧、出棧操作總次數(shù)做了限制的線性表。(錯)
(4)對順序棧進行進棧、出棧操作,不涉及元素的前、后移動問題。(對)
(5)空棧沒有棧頂指針。(錯)
4.9編寫一個程序?qū)崿F(xiàn)在順序棧上的各種基本操作,用一個主程序串成。
(1)棧的初始化。
(2)棧不滿的情況下元素進棧。
(3)棧不空的情況下元素出棧。
(4)輸出棧中元素。
(5)計算棧中元素個數(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編寫一個程序?qū)崿F(xiàn)在循環(huán)隊列上的各種基本操作,用一個主程序串成。
(1)循環(huán)隊列的初始化。
(2)隊列不滿的情況下元素入隊列。
(3)隊列不空的情況下元素出隊列。
(4)輸出隊列中元素。
(5)計算隊列中元素個數(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(〃隊列空\n〃);
return;
)
else
(
*temp=Q->data[Q->front];
Q->front=(Q->fror)t+l)%QueueSize;
}
)
voidenQueue(CirQueue*Q,intx)
(
if(fullQueue(Q))
(
printf(〃隊列滿\n〃);
return;
)
else
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
)
intfrontQueue(CirQueue*Q)
(
if(emptyQueue(Q))
{
printf(〃隊列空\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("隊列中的元素個數(shù)為:%d,其值依次為:\n”,counlQueue(&p));
printQueue(&p);
4.11編一程序,將輸入的非負(fù)十進制整數(shù)轉(zhuǎn)換為八進制數(shù)輸出(在順序棧結(jié)構(gòu)上實現(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在一個表達式中含有括號“和“)”并可嵌套使用,編一程序,判斷表達式中的括
號是否正確配對。
答:
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;//無左括號配對,則出錯
else
pop(s);//有左括號配對,則去左括號
ch=getchar();
}
if(gettop(s)!='#')//左括號數(shù)目多于右括號,出錯
bool=0;
if(bool)
printfC,right");
else
printferrorff);
}
main()
(
SEQSTACKst,*s;
s=&st;
initstack(s);
check(s);
)
4.13編寫一個鏈隊列管理的程序。這是一個加深理解在鏈隊列結(jié)構(gòu)上元素插入和刪除的程
序。在建立的帶頭結(jié)點的空鏈隊列上,如果輸入奇數(shù),則奇數(shù)入隊列;如果輸入偶數(shù),則隊
列中的第一個元素出隊列;如果輸入0,則退出程序。
答:
voidout1inkqueue(LINKQUEUE*q)〃顯示隊列中的值
(
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("
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO/IEC 27403:2024 EN Cybersecurity – IoT security and privacy – Guidelines for IoT-domotics
- 2025年無機分離膜材料合作協(xié)議書
- 2025版安置房買賣合同范本:限價房交易政策范本
- 2025年度廠區(qū)門衛(wèi)智能化升級改造服務(wù)合同范本
- 2025年高壓清洗車合作協(xié)議書
- 社團活動反饋與改進方案計劃
- 教學(xué)資源整合與優(yōu)化策略計劃
- 企業(yè)未來發(fā)展的創(chuàng)新思考計劃
- 財務(wù)企劃管理計劃
- 建立健全院內(nèi)溝通反饋機制的計劃
- 蛤蟆先生去看心理醫(yī)生
- 懸挑式卸料平臺安拆作業(yè)安全技術(shù)交底
- 疾病診斷編碼庫ICD-10
- 蘭州市規(guī)范醫(yī)療服務(wù)價格項目基準(zhǔn)價格表
- 西漢-北京大學(xué)歷史學(xué)系教學(xué)課件
- 產(chǎn)品設(shè)計材料及工藝PPT完整版全套教學(xué)課件
- 2006年度銀行業(yè)金融機構(gòu)信息科技風(fēng)險評價審計要點
- 反恐C-TPAT程序文件整套(通用)
- 2022年全國高考詩歌鑒賞試題-教學(xué)課件
- 化學(xué)檢驗工高級工理論知識試題題及答案
- 廣東省五年一貫制語文試卷
評論
0/150
提交評論