中學信息學《數(shù)據(jù)結構》習題及參考答案

云南財經(jīng)大學信息學院

《數(shù)據(jù)結構》習題及參考答案

《數(shù)據(jù)結構》課程建設小組

第1章緒論

基礎知識題

1.1①簡述下列術語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、存儲結構、數(shù)據(jù)類型、和抽象數(shù)

據(jù)類型。

1.2②試描述數(shù)據(jù)結構和抽象類型的概念與程序設計語言中數(shù)據(jù)類型概念的區(qū)別。

1.3③設有數(shù)據(jù)結構(D,R),其中

D={d1,d2,d3,d4},R={r},r={(d1,<12),(d2,d3),(d3,d4)}。

試按圖論中的畫法慣例畫出其邏輯結構圖。

1.4②試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復數(shù)和有理數(shù)的定義(有

理數(shù)是其分子，分母均為自然數(shù)其分母不零的分數(shù))。

1.5②試畫出與下列程序段等價的框圖

(1)product：1;i=l;

while(i<=n){

product*=i;

i++；

)

(2)i=0;

do{

i++

}while((i!=n)&&(a[i]!=x));

(3)swith{

casex<y:z=y-x;break;

casex=y:z=abs(x*y);break;

defult:z=(x-y)/abs(x)*abs(y);

)

1.6②在程序設計中，常用下列三種不同的出錯處理方式：

(1)用exit語句終止執(zhí)行并報告錯誤；

(2)以函數(shù)的返回值區(qū)別正取返回或錯誤返回；

(3)設置一個整型變量的函數(shù)參數(shù)以區(qū)別正取返回或錯誤返回；

試討論這三種方法各自的優(yōu)點

1.7③在程序設計中，可采用下列三種方法實現(xiàn)輸出和輸入：

(1)通過scanf和printf語句；

(2)通過函數(shù)的參數(shù)顯示傳遞；

(3)通過全局變量隱式傳遞。

試討論這三種方法的優(yōu)缺點。

1.8④設n為正整數(shù)。試確定下列各程序段中前置以記號@的語句的頻度：

(1)i=1;k=0;

While(i<=n-1){

@k+=10*I;

1++;

)

(2)i=l;k=O;

do(i<=n-1){

@k+=10*1;

i++；

}while(I<=n-1);

(3)i=1；k=0;

While(i<=n-1){

i++；

@k+=10*i;

)

(4)k=0;

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

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

@k++;

)

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

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

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

@x+=delta;

)

(6)i=l;j=0;

While(i+j<=n){

@if(i>j)j++;

elsei++;

)

(7)x=n;y=o;

while(x>=(y+l)*(y+1)){

@y++;

)

(8)x=91;y=100;

while(y>0){

@if(x>100){x-=10;y-}

elsex++;

)

1.9③假設n為2的乘騫，并且n>2,試求下列算法的時間復雜度及變量count的值

(以的函數(shù)形式表示)。

intTime(intn){

Count=0;x=2;

While(x<n/2){

x*=2;count++;

)

return(count)

}//Time

1.10②按增長率由小到大的順序排列下列各函數(shù)：

2100(3/2)"(2/3)n(4/3)n

nnnn!

n,log2nlog22nlog2(log2n)

nlog2nnl＜，s2n

1.11③已知有現(xiàn)實同一功能的兩個算法，其時間復雜度分別為0(2D和0(n10),

假設現(xiàn)實計算機可連續(xù)運算的時間為1。7秒(100多天)，又每秒可執(zhí)行基本操

作(根據(jù)這些操作來估算算法時間復雜度)1()5次。試問在此條件下，這兩個

算法可解問題的規(guī)模(即n值的范圍)各為多少？哪個算法更適宜？請說明理由。

1.12③設有以下三個函數(shù)：

f(n)=21n4+n2+1000g(n)=15n4+500n3h(n)=5000n35+nlogn

請判斷以下斷言正確與否：

(1)f(n)和O(g(n))

(2)h(n)和O(f(n))

(3)g(n)和O(h(n))

(4)h(n)和O(n3.5)

(5)h(n)和O(nlogn)

1.13③試設定若干n的值，比較兩函數(shù)川和50nlog2n的增長趨勢，并確定n在什

么范圍內，函數(shù)的值大于50nlog2n的值

1.14③判斷下列各對函數(shù)f(n)和g(n).n趨進于8時，哪個函數(shù)增長更快？

1.15試用數(shù)學歸納法證明:

算法設計題

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

1.17③已知k階裴波那契序列的定義為：

試編寫k階裴波那契序列的第項值的函數(shù)算法,k和m均以值調用的形式在函數(shù)

參數(shù)表中出現(xiàn)。

1.18③假設有A,B,C,D,E五個高等院校進行田徑對抗賽，各院校的單項成績均

已存入計算機，并構成一張表，表中每一行的形式為：

項目名稱性別校名成績得分

編寫算法，處理上述表格，以統(tǒng)計各院校的男、女總分和團體總分，并輸出。

1.19.@試編寫算法，計算i!.2‘的值并存入數(shù)組a[O...arrsize-1]的第i-1個分量中

(1=1,2,n)?假設計算機中允許的整數(shù)最大值為maxint,則當n>arrsize或對某個k(lWk

Wn)使k!.2k>maxint時，應按出錯處理，注意選擇你認為較好的出錯處理方法。

1.20@試編寫算法求一元多項式的值的值P￡xo)并確定算法

中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度。注意選擇你認為較好的輸入和輸出方法。

本題的輸入為aj(i=0,1,…n)x0和n,輸出為Pn(xo)。

第2章線性表

基礎知識題

2.1①描述以下三個概念的區(qū)別，頭指針，頭結點，首元結點(第一個元素結點)。

2.2①填空題。

(1)在順序表①中插入或刪除一個元素，需要平均移動元素，具體移

動的元素與有關。

(2)順序表中邏輯上相鄰的元素的物理位置緊鄰。單鏈表

中邏輯的元素物理位置緊鄰。

(3)在單鏈表中，除了首元結點外，任一結點的存儲位置由____________揖示。

(4)在單鏈表中設置頭結點的作用是___________________-o

2.3②在什么情況下用順序表比鏈表好？一

2.4①對以卜單鏈表分別執(zhí)行卜列各程序段，并畫出結果意圖。

(1)Q=P->next;

(2)L=P->next;

(3)R->data=R->data;

(4)R->data=P->next->data;

(5)P->next->next->next->data=P->data;

(6)T=P;

While(T!=NULL){T->data=T->data*2;T=T->next;}

(7)T=P

while(T->next!=NULL){T->data=T->data*2;T=T->next;}

2.5①畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。

L=(LinKList)malloc(sizeof(LNode));P=L;

for(i=l;i<=4;i++){

P->next=(LinKList)malloc(sizeof(LNode));

P=P->next;P->data=i*2-1;

)

P->next=NULL;

for(i=4;i>=4;i--;)Ins_LinkList(L,i+1,i*2);

for(i=l；I<=3;i++;)Del_LinkList(L,i);

2.6②已知L是無表頭結點的單鏈表，且P結點既不是首元結點，也不是尾元結點，

試從下列提供的答案中選擇合適的語句序列。

a.在P結點后插入S結點的語句序列是------------------------------------

b.在P結點前插入S結點的語句序列是_____________________________________

c.在表首插入S結點的語句序列是一

d.在表首插入S結點的語句序列是

(1)P->next=S;

(2)P->next=P->next->next;

(3)P->next=S->next;

(4)S->next=P->next;

(5)S->next=L;

(6)S->next=NULL;

(7)Q=P;

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

(9)while(P->next!=NULL)P=P->next;

(10)P=Q;

(H)P=L;

(12)L=S

(13)L=P;

2.7②已知L是帶頭結點的非空單鏈表，且P結點既不是首結點，也不是尾元結點，

試從下列提供的答案中選擇合適的語句序列是

a.刪除P結點的直接后繼結點的語句序列是

b.刪除P結點的直接后繼結點的語句序列是

c.刪除P結點的語句序列是____________

d.刪除首元結點的語句序列回—一

e.刪除尾元結點的語句序列是-.

(1)P=P->mext;

(2)P->next=P;

(3)P->next=P;

(4)S->next=P->next->next;

(5)While(P!=NULL)P=P->next;

(6)While(Q->next!=NULL){P=Q;Q=Q->next;}

(7)While(P->next!=Q)P=P->next;

(8)While(P->next->next!=Q)P=P->next;

(9)While(P->next->next!=NULL)P=P->next

(10)Q=P;

(1l)Q=P->next;

(12)P=L;

(13)L=L->next;

(14)free(Q);

2.8②已知P結點是某雙向鏈表的中間結點，試從下列提供的答案中選擇合適

的合適語序序列。

a.在P結點后插入S結點的語句序列是------------------------------------

b.在P結點前插入S結點的語句序列是-------------------------------------

c.刪除P結點的直接后繼結點的語句序列是

d.刪除P結點的直接前驅結點的語句序列是

e.刪除P結點的語句序列是____________

(1)P->next=P->next->next;

(2)P->priou=P->priou->priou;

(3)P->next=S;

(4)P->priou=S;

(5)S->next=P;

(6)S->priou=P;

(7)S->next=P->next;

(8)S->priou=P->priou;

(9)P->priou->next=P->next;

(10)P->priou->next=P;

(1l)P->next->priou=P;

(12)P->priou->next=S;

(13)P->priou->next=S;

(14)P->next->priou=P->priou;

(15)Q=P->next;

(16)Q=P->priou;

(17)Free(p);

(18)Free(Q);

2.9②簡述以下算法的功能。

(1)StatusA(LinkedListL){//L是無表頭結點的單鏈表

If(L&&L->next){

Q=L;L=L->next;P=L;

While(P->next)P=P->next;

P->next=Q;Q->next=NULL;

)

returnOK;

}//A

(2)VoidBB(Lnode*s,Lodes*q){

p=s；

while(p->next!=q)q=p-next;

p->next=s;

}//BB

voidAA(Lnode*pa,Lnode*pb){

//pa和pb分別是指向單循環(huán)鏈表的類型定義如下：

BB(pa,pb);

BB(pb,pa);

}//AA

算法設計題

本章算法設計題涉及的順序表和線性表的類型定義如下：

#defineLIST_INIT_SIZE100

#defineLISTINCREMENT10

typedefstruct{

ElemType*elem;〃存儲空間基址

intlength;〃當前長度

intlistsize;〃當前分配的存儲容量

}SqList;//順序表類型

typedefstructLnode{

ElemTypedata;

StructLnode*next;

}Lnode,*LinkList;〃線性鏈表類型

2.10②指出以下算法中的錯誤和低效(既費時D之處，并將它改寫成一個既正確

又高效的算法。

StatusDeleteK(SqList&a,inti,intk){

〃本過程從順序存儲結構的線性表中a中刪除第i個元素起的k個元素

if(i,lllk<Olli+k>a.length)returnINFEASIBLE〃參數(shù)不合法

else{

for(count=l;count<k;count++){

〃刪除一個元素

for(j=a.length;j>=i+1;j-)a.elemfj-l]=a.elemfj];

a.length";

)

returnOK;

}//DeleteK

2.22②設順序表中的數(shù)據(jù)元素遞增有序。試寫一算法，將插入到順序表的適當

位置上，以保持該表的有序性。

2.12③設A=(a,,...a?)B=(b，…,b”)均為順序表，A'和B，分別為A和B中

同前綴為(x,y,y,z),在兩表中除最大共同前綴后的子表分別為A，=(x,z)和

B，=(y,x,x,z)若A，=B，=空表，貝ljA=B；若A，=空表，而夕中空表，或者

兩者均不為空表，且A，的首元小于B，的首元，則A<B；否則A>Bo試

寫一個比較A,B大小的算法(請注意：在算法中，不要破壞原表A與B,

并且也不一定先求得A，和B，才進行比較)?

2.13②試寫一算法在帶頭結點的單鏈表結構上的實現(xiàn)線性表操作LOCATE(L,X)。

2.14②試寫一算法在帶頭結點的單鏈表結構上的實現(xiàn)線性表操作LENGTH(L)?

2.15②已知指針ha和hb分別指向兩個單鏈表的頭結點，并且已知兩個鏈表的長

度分別為m和n?試寫一算法將這兩個鏈表連接在起(即令其中個表的

首元結點連在另個表的最后一個結點之后)，假設指針he指向連接后的鏈

表的頭結點，并要求算法以盡可能短的時間完成連接運算。請分析你的算

法的時間復雜度。

2.16③已知指針la和1b分別指向兩個無頭結點單鏈表的首元結點。下列算法是從

表la中刪除自第i個元素起共len個元素后，，將它們插入到表1b中第i個

元素之前，試問此算法是否正確？若有錯，則請改正之。

StatusDleteAndInsertSub(Linkedla,LinkedListlb,inti,intj,intlen(

If(i<0llj<0lllen<0)returnINFEASIBLE;

p=la;k=l;

while(k<i){p==p->next;k++;}

q=p；

while(k<=len){q=q->next;k++;}

s=lb;k=l;

while(k<j){s=s->next;k++;}

s->next=p;q->next=s->next;

returnOK;

}//DeleteAndlnsertSub

2.17②試寫一算法，在無頭結點的動態(tài)單鏈表上實現(xiàn)線性表操作INSERT（L,i,b）,

并和在帶頭結點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。

2.18②同2.17題要求，試寫一算法，實現(xiàn)線性表操作DELETE（L,i）。

2.19③已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構，試寫出「

高效算法，刪除表中所有值大于mink且小于maxk的元素，（若表中存在這樣的元素）同時

釋放被刪除結點空間，并分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參

變量，它們的值可以和表中的元素相同，也可以不同）

2.20②同2.19題條件，試寫出?高效算法，刪除表中所有值相同的多余元素（使得

操作后的線性表中所有元素的值均不相同），同時釋放被刪除結點空間，并分析你的算法的

時間復雜度。

2.21③試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表中的存儲空間將線性表

（a.,...an）逆置為（an,

2.22③是寫一算法，對單鏈表實現(xiàn)就地逆置。

2.23③設線性表A=（a.,B=（b.....b,?）,試寫一個按下列規(guī)則合并A,B為

線性表C的算法，即使得

C=（a,,bi....am.bm,bm+i...bn）當m<n時；或者

C=（a：,bi...an.bn,an+i...3n>）當m>n時。

線性表A,B,C均以單鏈表作存儲結構，且C表利用A表利B表中的結點空間構成，注

意：單鏈表的長度值m和n均未顯示存儲。

2.24④假設有兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作為存儲結

構，請編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許表中含

有值相同的元素）排列的線性表C,并要求利用原表（即A表和B表）的結點空間構造C

表。

2.25④假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合（即同

,表中的元素各不相同），現(xiàn)要求另辟空間構成?個線性表C,其元素為A和B中元素的交

集，且表C中的元素也依值遞增有序排列，試對順序表編寫求C的算法。

2.26@對2.25題。試對單鏈表編寫求C的算法

2.27④對2.25題的條件作以下兩點修改，對順序表重新編寫求得C的算法。

（1）假設在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C

中的元素值各不相同；

（2）利用A表空間存放表C。

2.28④對2.25題的條件作以下兩點修改，對順序表重新編寫求得C的算法。

（1）假設在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C

中的元素值各不相同；

（2）利用原表（A表或B表）中的結點構造C,并釋放A表中的無用節(jié)點空

間。

2.29⑤已知A,B和C為三個遞增有序的線性表C,現(xiàn)要求對A表中作如下操作：刪

除那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對順序表編寫實現(xiàn)上述操作算法，并分

析你的算法的時間復雜度，（注意；題中沒有特別指明同一表中的元素各不相同）。

2.30⑤要求同2.29題，試對單鏈表編寫算法，請釋放A表中的無用結點空間。

2.31②假設某個單向循環(huán)鏈表的長度大于1,且表中即無頭結點也無頭指針。已知s

為指向鏈表中的某個結點的指針，試編寫算法在鏈表中刪除指針s所指結點的前驅節(jié)點。

2.32②已知有■個單向循環(huán)鏈表，其每一個結點中含三個域：pre,data和next,其中

data為數(shù)據(jù)域，next為指向后繼結點的指針域，pre也為指針域，但它的值為空（NULL）,

試編寫算法將此單向循環(huán)鏈表雙向循環(huán)鏈表，即使pre成為指向前驅結點的指針域。

2.33③已知由一個線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素(如：字母字

符、數(shù)字字符和其他字符)，試編寫算法將該線性鏈表分割為三個循環(huán)鏈表，其中每個循環(huán)

鏈表表示的線性表中均只含一類字符。

在2.34至2.26題中，“異或指針雙向鏈表”類型XorLinkedList和指針異域函數(shù)XorP

定義為：

typedefstructXorNode{

chardata;

structXorNodeLRPtr;

}XorNode,*XorPinter;

typedefstruct{〃無頭結點的異或指針雙向鏈表

XorPointerLeft,Right;//分別指向鏈表的左端和右端

JXorPointedList;

XorPointerXorP(XorPointerp,XorPinterq);

〃指針異域函數(shù)XorP返回指針p和q的異或(XOR)值

2.34④假設在算法描述語言中引入指針的二元運算“異或”(用表示)，若a和b

為指針，則的運算結果仍為原指針類型，利用一個指針域來實現(xiàn)雙向鏈表L。鏈表L中的每

個結點只含兩個域:data域和LRPtr域,其中LRPtr域存放該結點的左鄰與右鄰節(jié)點指針(不

存在時為NULL)的異域。若設指針L。Left指向鏈表中的最左結點，L.Right指向鏈表中的

最右結點，則可實現(xiàn)從左向右或從右向左遍歷此雙向鏈表的操作。試寫一算法按任一方向依

次輸出鏈表中各元素的值。

2.35④采用2.34題所述的存儲結構，寫出在第i個結點之前插入一個結點的算法。

2.36④采用2.34題所述的存儲結構，寫出刪除在第i個結點的算法。

2.37④設以帶頭結點的雙向循環(huán)鏈表表示的線性表L=(a,,試寫一時間復雜

度為O(n)的算法,將L改造為L=(a,,asan.....a&,a2)。

2.38④設有一個雙向循環(huán)鏈表，每個結點除有pre,data和next三個域外，還增設了

一個訪問頻度域freq。在鏈表被起用之前，頻度域frep的值均為初始化為零，而每當對鏈表

進行一次LOCATE(L,x)的操作后，被訪問的結點(即元素值等于x的結點)中的頻度

域frep的值便增1,同時調整鏈表中結點之間的次序，使其按訪問頻度非遞增的次序順序排

列，以便始終保持被頻繁訪問的結點總是靠近表頭結點。試編寫符合上述要求的LOCATE

操作的算法。

在2.39至2.40題中，稀疏多項式采用的順序存儲結構SqPoly定義為

typedefstruct{

intcoef;

intexp

}PolyTerm;

typedefstruct{

PolyTerm*data;

intlast;

}SqPoly;

2.39@已知稀疏多項式Pn(X)=Cix"+....+C2xem其中n=em>em.i>.....e(>=0,Cj

#0(i=l,2,...m),m》l。試采用存儲同多項式數(shù)m成正比的順序存儲結構，編寫求P。

(x0)的算法(X。為給定值)，并分析你的算法的時間復雜度。

2.40③采用2.39題給定的條件和存儲結構，編寫求P(x)=P?,(x)-Pn2(x)的算

法，將結果多項式存放在新辟的空間中，并分析你的算法的時間復雜度。

在2.41至2.42題中，稀疏多項式采用的循環(huán)鏈表存儲結構LinkedPoly定義為

typedefstructPolyNode{

PolyTermdata;

StructPolyNode*next;

}PolyNode,*PolyLink;

typedefPolylinkLinkedPoly;

2.41②試以循環(huán)鏈表作為稀疏多項式的存儲結構，編寫求其導函數(shù)的算法，要求利用

原多項式中的結點空間存放其導函數(shù)（多項式），同時釋放所有無用（被刪）結點。

2.42②試編寫算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使兩

個多項式中各自僅含有奇次項或偶次項，并要求利用原鏈表中的結點空間構成這兩個鏈表

第三章棧和隊列

基礎知識題

3」①若教科書3.1.1節(jié)中圖3.1(b)所示鐵道進行車廂調度(注意：兩側鐵道均為單向

行駛道)，則請回答：

(1)如果進站的車廂序列為123。則可能得到的出站車廂序列是什么？

(2)如果進站的車廂序列為123456,則能否得到435612和135426的出站序列，并請

說明為什么不能得到或者如何得到(即寫出以'S'表示進棧和以'X'表示出棧

的棧操作序列)。

3.2①簡述棧和線性表的差別。

3.3②寫出卜列程序段的輸出結果(棧的元素類型SelemType為char)。

Voidmain()

StackS;

Charx,y;

InitStack(S);

x=,c,;y='k';

Push(S,x);Push(S,'a');Push(S,y);

Pop(S,x);Push(S/f);Push(S,x);

Pop(S,x);Push(S,'s');

While(!StackEmpty(S)){Pop(S,y);printf(y);};

Print(x);

)

3.4②簡述以卜算法的功能(棧的元素類型SelemType為int)。

(1)statusalgol(StackS)

inti,n,A[256];

n=0;

while(!StackEmpty(S)){n++;Pop(S,A[n]);};

for(i=l;i<=n:i++)Push(S,A[i]);

)

(2)statusalgo2(StackS,inte){

StackT;intd;

InitStack(T);

While(!StackEmpty(S)){

Pop(S,d);

if(d!=e)Push(T,d);

)

while(!StackEmpty(T))

Pop(T,d);

Push(S,d);

)

}

3.5④假設以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為?？盏娜霔：?/p>

出棧的操作序列可以表示為僅由S和X組成的序列，稱可以操作的序列為合法序列(例如,

SXSX為合法序列，SXSX為非法序列)。試給出區(qū)分給定序列為合法序列或非法序列的一

般準則，并證明：兩個不同的合法(棧操作)序列(對同?輸入序列)不可能得到相同的輸

出元素(注意：在此指的是元素實體，而不是值)序列。

3.6④試證明：若借助棧由輸入序列12...n得到的輸出序列為P1p2p3……pn(它是輸

入序列的一個排列)，則在輸出序列中不可能出現(xiàn)這樣的情形:存在著i<j<k使用pk<ft.

3.7①按照四則運算加、減、乘、除和慕運算(f)優(yōu)先關系的慣例，并仿效教

科書3.2節(jié)例3-2的格式，畫出對下列算術表達式求值時操作數(shù)棧和運算符棧的變化過程：

A-BXC/D+EtF

3.8③試推導求解n階梵塔問題至少要執(zhí)行的move操作的次數(shù)。

3.9③試將下列遞推過程改寫為遞歸過程。

Voidditui(intn){

inti;

i=n;

while(i>1)

printf(i—);

)

3.10③試將下列遞歸過程改寫為非遞歸過程。

Voidtest(int&sum){

intx;

scanf(x);

if(x=0)sum=0;

else{test(sum);sum+=x;}

printf(sum);

)

3.11①簡述隊列和棧這兩種數(shù)據(jù)類型的相同點和差異處。

3.12②寫出以下程序段的輸出結果(隊列中的元素類型QelemType為char)。

Voidmain()

QueueQ;InitQueue(Q);

Charx=,e,,y=,c,;

EnQueue(Q,,h,);EnQueue(Q,,r,);EnQueue(Q,y);

DeQueue(Q,'h');EnQueue(Q,x)；

DeQueue(Q,,h,);EnQueue(Q/a,);

While(!QueueEmpty(Q)){

DeQueue(Q,y);

Printf(y);

)

printf(x);

)

3.13②簡述以下算法的功能(棧和隊列的元素類型均為int)。

voidalgo3(Queue&Q){

StackS;intd;

While(!QueueEmpty(s)){

DeQueue(Q,d);

Push(S,d);

while(!StackEmpty(s)){

Pop(S,d);

EnQueue(Q,d);

)

)

3.14@若以1234作為雙端隊列的輸入序列，試分別求出滿足以下條件的輸出序歹I」；

(1)能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序

列；

(2)能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序

列；

(3)既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸

出序列；

算法設計

3.15③假設以順序存儲結構實現(xiàn)一個雙向棧，即在一維數(shù)組的存儲空間中存在著兩

個棧，它們的棧底分別設在數(shù)組的兩個端點。試編寫實現(xiàn)這個雙向棧tws的三個操作：初始

化inistack(tws)、入棧push(tws,i,s)和出棧pop(tws,i)的算法,其中i為0或1。

用以分別指示設在數(shù)組的兩個棧，并討論按過程(正/誤狀態(tài)變量可設為變參)或函

數(shù)設計這些操作算法各有什么優(yōu)缺點。

3.16②假使如題3.1所述火車調度站的入口處有n節(jié)硬席或軟席車廂(分別以H和S

表示)等待調度，輸入對這n節(jié)車廂進行調度的操作(即入?；虺鰲２僮?序列，以使所

有的軟席車廂都被調整到硬席車廂之前。

3.17③試寫一個算法，識別依次讀入的一個以@為結束符的字符序列是否為形如‘序

列1&序歹I」2'模式的字符序列。其中序列1和序列2中不包含字符，&，，且序歹IJ2是序列

1的逆序列。例如，'a+b&b+a'是屬于該模式的字符序列，而'1+2&2-1'則不是。

3.18②試寫出一個判別表達式中開、閉括號是否配對出現(xiàn)的算法。

3.19④假設一個算術表達式中可以包含三種符號；圓括號“(”和“)”、方括號

和“]”和花括號“{”和且這三種括號可按任意的次序嵌套使用(in：

.)o編寫判別給定表達式所含括號是否正確配對出現(xiàn)的算法(已知

表達式已存入數(shù)據(jù)元素為字符的順序表中)。

3.20③假設以二維數(shù)組為表示一個圖象區(qū)域,g[i,j]表示該區(qū)域中點(i,j)

所具有顏色，其值為從0到k的整數(shù).編寫算法置換點(i°jo)所在區(qū)域的顏色，約定和(i(Jo)同

色的上、下、左、右的鄰結點為同色區(qū)域的點。

3.21③假設表達式由單字母變量和雙目四則運算算符構成。試寫一個算法，將一個

通常書寫形式且書寫正確的表達式轉換為逆波蘭式。

3.22③如題3.21的假設條件，試編寫一算法，對逆波蘭式表示的表達式求值。

3.23⑤如題3.21試寫一算法。判斷給定的非空后綴表達式是否為正確的逆波蘭式(即

后綴表達式)，如果是，則將它轉化為波蘭式(既前綴表達式)。

3.24③試編寫如下定義的遞歸函數(shù)的遞歸算法，并根據(jù)算法畫出求g(5,2)時棧

的變化過程。

MOm=0,n>=()

3.25④試寫出遞歸函數(shù)F(u)的遞歸算法，并消除遞歸:

3.26④求解平方根的迭代函數(shù)定義如下；

其中，P是A的近似平方根，e是結果誤差，試寫出相應的遞歸函數(shù)算法，并消

除遞歸。

3.27⑤已知Ackennan函數(shù)定義如下：

（I）寫出遞歸算法；

（2）寫出非遞歸算法，

（3）根據(jù)非遞歸算法，畫出求akm（2,1）時棧的變化過程。

3.28②假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向對尾元素結

點（注意不設頭指針），試編寫相應的隊列初始化、入隊列和出隊列的算法。

3.29②如果希望循環(huán)隊列中的元素都能得到利用，則需要設置一個標志域tag,并

以tag的值為0或1來區(qū)分，尾指針和頭指針相同時的隊列狀態(tài)是“空”還是“滿”。試編

寫與此結構相應的入隊列和出隊列的算法，并從時間和空間角度討論設標志和不設標志這兩

種方法的使用范圍（如當循環(huán)隊列較小而隊列中每個元素占的空間較多時，哪一種方法較

好）。

3.30②假設將循環(huán)隊列定義為：以域變量rear和length分別指示循環(huán)隊列中對尾

元素的位置和內含元素的個數(shù)，試給出此循環(huán)隊列的對滿條件，并寫出相應的入隊列和出

隊列的算法（在出隊列的算法中要返回對頭元素）。

3.31③假設稱正讀和反讀都相同的字符序列為“回文”，例如，'abba'和'abcba'

是回文，'bcde'和'ababa'則不是回文，試寫一個算法判別讀入的一個以為結束符

的字符序列是否是“回文”。

3.32④試利用循環(huán)隊列編寫求k階斐波那契序列中前n+1項，（f0,f1,....fn）

的算法，要求滿足:fnWmax而fe>max,其中max為某個約定的常數(shù)。（注意：本題所用循環(huán)

隊列的容量僅為k,則在算法執(zhí)行結束時，留在循環(huán)隊列中的元素應是所求k階斐波那契序

列中的最后k項fn-k+l，….fn）o

3.33③在順序存儲結構上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列（只允許隊

頭出列）算法。設每一個原始表示一個待處理表示一個待處理的作業(yè)，元素值表示作業(yè)的預

計時間。入隊列采取簡化的短作亞優(yōu)先原則，若一個新提交的作業(yè)的預計執(zhí)行時間小于對頭

和對尾作業(yè)的平均時間，則插入在對頭，否則插入在對尾。

3.34③假設在教科書3.4.1節(jié)中圖3.9所示，鐵道轉軌網(wǎng)的輸入端有n節(jié)車廂：硬

座、硬臥、和軟臥（分別以P,H和S表示）等待調度，要求這三種車廂在輸出端鐵道上的

排隊次序為：硬座在前，軟臥在中，硬臥在后。試利用輸出受限的雙端隊列對這n節(jié)車廂

進行調度，編寫算法輸出調度的操作序列：分別以字符'E'和'D'表示對雙端隊列的頭

端進行入隊列和出隊列的操作；以字符A表示對雙端隊列的尾端進行入隊列的操作。

第4章串

基礎知識題

4.1①簡述空串和空格串

4.2②對于教科書4.1節(jié)所述串的各個基本操作，討論是否可由其他基本操作構造

而得？如何構造？

4.3①設$=*1AMASTUDENT',t='GOOD,,q=,WORKER,.

求：StrLength(s),StrLength(t),SubString(s,8,7),SubString。,2』)，

Index。,'A'),Index(s,I),Replace(s,'STUDENT',q),

Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))).

4.4①已知下列字符串

a='THIS',f='ASAMPLE',c='GOOD',d='NE',b="，

s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),

t=Replac(f,SubString(f,3,6),c),

u=Concat(SubString(c,3?1),d),g=,IS,

v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),

試問：s,t,v,StrLenglh(s),Index(v,g),Index(u,g)各是什么?

4.5①試問執(zhí)行以下函數(shù)會產生怎樣的輸出結果？

Voiddemonstrate(){

StrAssignCs/THISISABOOK');

Replace(s,SubString(s,3,7),),ESEARE');

StrAssign(t,Concat(s,'S'));

StrAssign(u；XYXYXYXYXYXY,);

StrAssign(v,SubSting(u,6,3))；

StrAssign(w,,W,);

Printf(4t=,,t,,v=,,v/u=,,Replace(u,v,w,));

}//demonstrate

4.6②已知；5=?丫@+*：=，(*+2)*丫八試利用|聯(lián)接、求子串和置換等基本運算，將s

轉化為to

4.7②令='aaab',t='abcabaa',u='abcaabbabcabaacbacba'.。試分別求出它們的next

函數(shù)值和nextrval函數(shù)值。

4.8②已知主串s='ABADABBAABADABBADADA',

模式串pa仁'ADABBADADA',

寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程

4.9③在以鏈表存儲串值時，存儲密度是結點大小和串長的函數(shù)假設每個字符占一個

字節(jié)，每個指針占4個字節(jié)，每個結點的大小為4的整數(shù)倍。已知串長的分布函數(shù)為f(1)

且，求結點大小為4k,串長為1時的存儲密度d(4k,D(用公式表示)。

算法設計題

在編寫4.10至4.14題的算法時，請采用StringType數(shù)據(jù)類型；

StringType是串的一個抽象數(shù)據(jù)類型，它包含以下五種基本操作：

VoidStrAssign(StringType&t,StringTypes)

〃將s的值賦給t。s的實際參數(shù)可以是串變量或者串常量(如abed')。

iniSlringCompare(StringTypes,StringTypet)

〃比較S和t。若s>t,返回值>0,若$=匕返回值=0；若set,返回值<0。

intStrLength(StringTypes)

返回s中的元素個數(shù)，即該串的長度。

StringTypeConcat(StringTypes,StringTypet)

〃返回由s和t聯(lián)接而成的新串

StringTypeSubString(StringTypes,intstart,intlen)

〃當lWstart<StrLength(s)且0<len^StrLength(s)-start+1時，

〃返回s中第start個字符起長度為len的子串，否則返回空串。

4.10③編寫對串求逆的遞推算法。

4.11③編寫算法，求得所有包含在串s中而不包含在串t中的字符(s中重復的字符

只選?個)構成的新串r,以及r中每個字符在s中第一次出現(xiàn)的位置。

4.12③編寫一個實現(xiàn)串的置換操作Replace(&S,T,V)的算法。

4.13③編寫算法，從串s中刪除所有和串t相同的子串。

4.14④利用串的基本操作以及棧和集合的基本操作，編寫“一個算術表達式的前綴

式求后綴式”的遞推算法(假設前綴式不含語法錯誤)。

在編寫4.15至4.20題的算法時，請采用教科書421節(jié)中所定義的定長順序存儲

表示，而不允許調用串的基本操作。

4.15③編寫算法，實現(xiàn)串的基本操作StringAssign(&T,chars).

4.16③編寫算法，實現(xiàn)串的基本操作StrCompare(S,T)。

4.17③編寫算法，實現(xiàn)串的基本操作Replace(&S,T,V)。

4.18③編寫算法，求串s所含不同字符的總數(shù)和每種字符的個數(shù)。

4.19③在串的定長順序存儲結構上直接實現(xiàn)4.11題要求的算法。

4.20③編寫算法，從s中刪除所有和串相同的子串。

4.21④假設以結點大小為1且附設頭結點的鏈表結構表示串，試編寫實現(xiàn)下列六種

串的基本操作StrAssign,StrCopy,StrCopare,StrLength,Contact和SubSring的函數(shù)。

4.22④假設以塊鏈結構表示串，試編寫將串s