數(shù)據(jù)結(jié)構(gòu)——C語言描述習(xí)題及答案耿國華

1、第1章緒論一、問答題1 .什么是數(shù)據(jù)結(jié)構(gòu)？2 .四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3 .算法的定義與特性。4 .算法的時間復(fù)雜度。5 .數(shù)據(jù)類型的概念。6 .線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。7 .面向?qū)ο蟪绦蛟O(shè)計語言的特點。8 .在面向?qū)ο蟪绦蛟O(shè)計中，類的作用是什么？9 .參數(shù)傳遞的主要方式及特點。10 .抽象數(shù)據(jù)類型的概念。二、判斷題1 .線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。2 .算法就是程序。3 .在高級語言(如C、或PASCAL)中，指針類型是原子類型。三、計算下列程序段中X=X+1的語句頻度for(i=1;i<=n;i+)for(j=1;j<=i;j+)

2、for(k=1;k<=j;k+)x=x+1;提示:i=1時：1=(1+1)1/2=(1+12)/2i=2時：1+2=(1+2)22=(2+22)/2i=3時：1+2+3=(1+3)3/2=(3+32)/2i=n時：1+2+3+n=(1+n)的2=(n+n2)/2f(n)=(1+2+3+n)+21+22+32+n2)/2=(1+n)n/2+n(n+1)(2n+1)/6/2=n(n+1)(n+2)/6=n3/6+n2/2+n/3區(qū)分語句頻度和算法復(fù)雜度：O(f(n)=O(n3)四、試編寫算法求一元多項式Pn(x)=a0+aix+a2X2+a3X3+-anxn的值Pn(x0),并確定算法中的每

3、一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能的小，規(guī)定算法中不能使用求備函數(shù)。注意：本題中的輸入ai(i=0,1,n)x和n,輸出為Pn(xo).通常算法的輸入和輸出可采用下列兩種方式之一：(1)通過參數(shù)表中的參數(shù)顯式傳遞；(2)通過全局變量隱式傳遞。試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認為較好的一種方式實現(xiàn)輸入和輸出。提示:floatPolyValue(floata,floatx,intn)核心語句：p=1;(x的零次募)s=0;i從0到n循環(huán)s=s+ai*p;p=p*x;p=x;(x的一次哥)s=a0;i從1到n循環(huán)s=s+ai*p;p=p*x;實習(xí)題設(shè)計實現(xiàn)抽象數(shù)

4、據(jù)類型“有理數(shù)”?；静僮靼ㄓ欣頂?shù)的加法、減法、乘法、除法,以及求有理數(shù)的分子、分母。第一章答案1.3 計算下列程序中x=x+1的語句頻度for(i=1;i<=n;i+)for(j=1;j<=i;j+)for(k=1;k<=j;k+)x=x+1;【解答】x=x+1的語句頻度為：T(n)=1+(1+2)+(1+2+3)+(1+2+n)=n(n+1)(n+2)/61.4 試編寫算法，求pn(x)=a0+ax+a2x2+.+anxn的值Pn(x0),并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能小，規(guī)定算法中不能使用求募函數(shù)。注意：本題中的輸入為ai(

5、i=0,1,n次和"輸出為Pn(x0)。算法的輸入和輸出采用下列方法(1)通過參數(shù)表中的參數(shù)顯式傳遞(2)通過全局變量隱式傳遞。討論兩種方法的優(yōu)缺點，并在算法中以你認為較好的一種實現(xiàn)輸入輸出?！窘獯稹?1)通過參數(shù)表中的參數(shù)顯式傳遞優(yōu)點：當(dāng)沒有調(diào)用函數(shù)時，不占用內(nèi)存，調(diào)用結(jié)束后形參被釋放，實參維持，函數(shù)通用性強，移置性強。缺點：形參須與實參對應(yīng)，且返回值數(shù)量有限。(2)通過全局變量隱式傳遞優(yōu)點：減少實參與形參的個數(shù)，從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時的時間消耗缺點：函數(shù)通用性降低，移植性差算法如下：通過全局變量隱式傳遞參數(shù)PolyValue()inti,n;floatx,a,p;prin

6、tf(nn=");scanf("%f",&n);printf(nx=");scanf("%f",&x);for(i=0;i<n;i+)scanf("%f,&ai);/*執(zhí)行次數(shù)：n次*/p=a0;for(i=1;i<=n;i+)/*執(zhí)行次數(shù)：n次*/p=p+ai*x;x=x*x;printf("%f",p);算法的時間復(fù)雜度：T(n)=O(n)通過參數(shù)表中的參數(shù)顯式傳遞floatPolyValue(floata,floatx,intn)(floatp,s;inti;p=

7、x;s=a0;for(i=1;i<=n;i+)s=s+ai*p;/*執(zhí)行次數(shù):n次*/p=p*x;return(p);算法的時間復(fù)雜度：T(n)=O(n)第2章線性表習(xí)題< 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。< 填空： 在順序表中插入或刪除一個元素，需要平均移動一半元素,具體移動的元素個數(shù)與一插入或刪除的位置_有關(guān)。 在順序表中，邏輯上相鄰的元素，其物理位置相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置相鄰。 在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由指示，首元素結(jié)點的存儲位置由指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由其直接前趨的next域指示。

8、< 已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點。按要求從下列語句中選擇合適的語句序列。a.在P結(jié)點后插入S結(jié)點的語句序列是：(4)、(1)。b.在P結(jié)點前插入S結(jié)點的語句序列是：(7)、(11)、(8)、(4)、(1)。c.在表首插入S結(jié)點的語句序列是：(5)、(12)。d.在表尾插入S結(jié)點的語句序列是：(11)、(9)、(1)、(6)。供選擇的語句有：(1) P->next=S;(2) P->next=P->next->next;(3) P->next=S->next;(4) S->next=P->next;(

9、5) S->next=L;(6) S->next=NULL;(7) Q=P;(3) while(P->next!=Q)P=P->next;(4) while(P->next!=NULL)P=P->next;(5) P=Q;(6) )P=L;(7) L=S;(8) L=P;1.1 已知線性表L遞增有序。試寫一算法，將X插入到L的適當(dāng)位置上，以保持線性表的有序性。提示:voidinsert(SeqList*L;ElemTypex)<方法1>(1)找出應(yīng)插入位置i,(2)移位，(3)<方法2>參P.2291.2 寫一算法，從順序表中刪除自第

10、i個元素開始的k個元素。提示:注意檢查i和k的合法性。(集體搬遷，“新房”、“舊房”)4 方法1>以待移動元素下標m(“舊房號”)為中心，計算應(yīng)移入位置(“新房號”)：for(m=i1+k;m<=L>last;m+)L>elemmk=L>elemm;5 方法2>同時以待移動元素下標m和應(yīng)移入位置j為中心：6 方法3>以應(yīng)移入位置j為中心，計算待移動元素下標：1.3 已知線性表中的元素(整數(shù))以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素(若表中存在這樣的元素)，分析你的算法的時間復(fù)雜度(注意：min

11、k和maxk是給定的兩個參變量，它們的值為任意的整數(shù))。提示:注意檢查mink和maxk的合法性：mink<maxk不要一個一個的刪除(多次修改next域)。(1)找到第一個應(yīng)刪結(jié)點的前驅(qū)prepre=L;p=L>next;while(p!=NULL&&p>data<=mink)pre=p;p=p>next;(2)找到最后一個應(yīng)刪結(jié)點的后繼s,邊找邊釋放應(yīng)刪結(jié)點s=p;while(s!=NULL&&s>data<maxk)t=s;s=s>next;free(t);(3)pre>next=s;1.4 試分別以不

12、同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表(a1，a2.,an)逆置為(a5an-1,.,a1)。(1)以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個分量中。(2)以單鏈表作存儲結(jié)構(gòu)。方法1：在原頭結(jié)點后重新頭插一遍方法2：可設(shè)三個同步移動的指針p,q,r,將q的后繼r改為p1.5 假設(shè)兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序的排列的線性表C,并要求利用原表(即A表和B表的)結(jié)點空間存放表C.提示:參P.28例2-1<方法1>voidmerge(LinkLi

13、stA;LinkListB;LinkList*C)pa=A>next;pb=B>next;*C=A;(*C)->next=NULL;while(pa!=NULL&&pb!=NULL)if(pa>data<=pb>data)smaller=pa;pa=pa>next;smaller>next=(*C)>next;/*頭插法*/(*C)>next=smaller;)else(smaller=pb;pb=pb>next;smaller>next=(*C)>next;(*C)>next=smaller;

14、)while(pa!=NULL)(smaller=pa;pa=pa>next;smaller>next=(*C)>next;(*C)>next=smaller;)while(pb!=NULL)(smaller=pb;pb=pb>next;smaller>next=(*C)>next;(*C)>next=smaller;)<方法2>LinkListmerge(LinkListA;LinkListB)LinkListC;pa=A>next;pb=B>next;C=A;C>next=NULL;returnC;1 假設(shè)有一個

15、循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。提示:設(shè)指針p指向s結(jié)點的前趨的前趨，則p與s有何關(guān)系？1 已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素(如字母字符、數(shù)字字符和其它字符)，試編寫算法來構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。1 設(shè)線性表A=(ai,a2,sm),B=(b1,b2,bn),試寫一個按下列規(guī)則合并A、B為線性表C的算法，使得：C=(a1,b1,am,bm,bm+1,bn)當(dāng)mn時；或者C=(a1,b

16、1,an,bn,an+1,am)當(dāng)m>n時。線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。提示:voidmerge(LinkListA;LinkListB;LinkList*C)或：LinkListmerge(LinkListA;LinkListB)1 將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。提示:注明用頭指針還是尾指針。1 建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位。并

17、在此鏈表上實現(xiàn)對二進制數(shù)加1的運算。提示:可將低位放在前面。1 設(shè)多項式P(x)采用課本中所述鏈接方法存儲。寫一算法，對給定的x值，求P(x)的值。提示:floatPolyValue(Polylistp;floatx)實習(xí)題1 .將若干城市的信息存入一個帶頭結(jié)點的單鏈表，結(jié)點中的城市信息包括城市名、城市的位置坐標。要求：4 給定一個城市名，返回其位置坐標；5 給定一個位置坐標P和一個距離D,返回所有與P的距離小于等于D的城市。2,約瑟夫環(huán)問題。約瑟夫問題的一種描述是：編號為1,2,，n的n個人按順時針方向圍坐一圈，每人持有一個密碼(正整數(shù))。一開始任選一個整數(shù)作為報數(shù)上限值m,從第一個人開始順

18、時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序，求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號。例如m的初值為20;n=7,7個人的密碼依次是：3,1,7,2,4,8,4,出列的順序為6,1,4,7,2,3,5。第二章答案實習(xí)題二：約瑟夫環(huán)問題約瑟夫問題的一種描述為：編號1,2,n的n個人按順時針方向圍坐一圈，每個人持有一個密碼(正整數(shù))。一開始任選一個報數(shù)上限值m,從第一個人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出

19、列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序，求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號。例如，m的初值為20;n=7,7個人的密碼依次是：3,1,7,2,4,8,4,出列順序為6,1,4,7,2,3,5。【解答】算法如下：typedefstructNode(intpassword;intnum;structNode*next;Node,*Linklist;voidJosephus()(LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)ma

20、lloc(sizeof(Node);/*初始化單向循環(huán)鏈表*/if(L=NULL)printf("n鏈表申請不到空間！");return;L->next=NULL;r=L;printf("請輸入數(shù)據(jù)n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j+)/*建立鏈表*/(p=(Node*)malloc(sizeof(Node);if(p!=NULL)(printf("請輸入第%d個人的密碼：",j);scanf("%d",&C);p

21、->password=C;p->num=j;r->next=p;r=p;r->next=L->next;printf("請輸入第一個報數(shù)上限值m(m>0):");scanf("%d",&m);printf("*n");printf("出列的順序為：n");q=L;p=L->next;while(n!=1)/*計算出列的順序*/(j=1;while(j<m)/*計算當(dāng)前出列的人選p*/(q=p;/*q為當(dāng)前結(jié)點p的前驅(qū)結(jié)點*/p=p->next;j+;pr

22、intf("%d->",p->num);/*獲得新密碼*/m=p->password;n-;q->next=p->next;/*p出歹U*/r=p；p=p->next;free(r);)printf("%dn",p->num);)2.7試分別以不同的存儲結(jié)構(gòu)實現(xiàn)單線表的就地逆置算法，即在原表的存儲空間將線性表(a1,a2,向)逆置為(an,an-1,向)。【解答】(1)用一維數(shù)組作為存儲結(jié)構(gòu)voidinvert(SeqList*L,int*num)intj;ElemTypetmp;for(j=0;j<=(*

23、num-1)/2;j+)tmp=Lj;Lj=L*num-j-1;L*num-j-1=tmp;)(2)用單鏈表作為存儲結(jié)構(gòu)voidinvert(LinkListL)Node*p,*q,*r;if(L->next=NULL)return;/*鏈表為空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一個結(jié)點，生成初始逆置表*/while(q!=NULL)/*從第二個結(jié)點起依次頭插入當(dāng)前逆置表*/r=q->next;q->next=L->next;L->next=q;q=r;)2.11將線性表A=(a1,a2,am),B=

24、(b1,b2,bn)合并成線性表C,C=(a1,b1,am,bm,bm+1,.bn)當(dāng)m<=n時，或C=(a1,b1,an,bn,an+1,am)當(dāng)m>n時，線性表A、B、C以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲?！窘獯稹克惴ㄈ缦拢篖inkListmerge(LinkListA,LinkListB,LinkListC)Node*pa,*qa,*pb,*qb,*p;pa=A->next;/*pa表示A的當(dāng)前結(jié)點*/pb=B->next;p=A;/*利用p來指向新連接的表的表尾，初始值指向表A的頭結(jié)點*/while

25、(pa!=NULL&&pb!=NULL)/*利用尾插法建立連接之后的鏈表*/qa=pa->next;qb=qb->next;p->next=pa;/*交替選擇表A和表B中的結(jié)點連接到新鏈表中；*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;)if(pa!=NULL)p->next=pa;/*A的長度大于B的長度*/if(pb!=NULL)p->next=pb;/*B的長度大于A的長度*/C=A;return(C);第3章限定性線性表棧和隊列習(xí)題1,按圖3.1（b）所示鐵道（兩側(cè)鐵道均為單向行駛道）進行車廂調(diào)度，回答：如進

26、站的車廂序列為123,則可能得到的出站車廂序列是什么？123、213、132、231、321（312）如進站的車廂序列為123456,能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表示進棧、以“X”表示出棧的棧操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X62.設(shè)隊列中有A、B、C、D、E這5個元素，其中隊首元素為Ao如果對這個隊列重復(fù)執(zhí)行下列4步操作：(1) 輸出隊首元素；(2) 把隊首元素值插入到隊尾；(3) 刪除隊首元素；(4) 再次刪除隊首元素。直到隊列成為空隊列為止，則是否可能得到輸出序列：7 A、C、E、C、C（2）

27、A、C、E(5) A、C、E、C、C、C（4）A、C、E、C提示：A、B、C、D、E（輸出隊首元素A）A、B、C、D、E、A（把隊首元素A插入到隊尾）B、C、D、E、A（刪除隊首元素A）C、D、E、A（再次刪除隊首元素B）C、D、E、A（輸出隊首元素C）C、D、E、A、C（把隊首元素C插入到隊尾）D、E、A、C（刪除隊首元素C）E、A、C（再次刪除隊首元素D）3,給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別?？张c棧滿？15 .按照四則運算加、減、乘、除和哥運算（T）優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程:AB*C/D+ETF16 .試寫一個算法，

28、判斷依次讀入的一個以為結(jié)束符的字母序列，是否為形如序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'且序列2是序列1的逆序列。例如，'a+b&b+a'是屬該模式的字符序列，而1+3&31'則不是。提示:3 邊讀邊入棧，直到&4 邊讀邊出棧邊比較，直到17 .假設(shè)表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法，將一個通常書寫形式(中綴)且書寫正確的表達式轉(zhuǎn)換為逆波蘭式(后綴)。提示:例：中綴表達式：a+b后綴表達式：ab+中綴表達式：a+bxc后綴表達式：abc/中綴表達式：a+bx

29、c-d后綴表達式：abc/d-中綴表達式：a+bxc-d/e后綴表達式：abcx+de/-中綴表達式：a+bx(c-d)-e/f后綴表達式：abcd->+ef/-6 后綴表達式的計算過程：(簡便)順序掃描表達式，(1)如果是操作數(shù)，直接入棧；(2)如果是操作符op,則連續(xù)退棧兩次，得操作數(shù)X,Y,計算XopY,并將結(jié)果入棧。7 如何將中綴表達式轉(zhuǎn)換為后綴表達式？順序掃描中綴表達式，(1)如果是操作數(shù)，直接輸出；(2)如果是操作符op2,則與棧頂操作符0Pl比較：如果op2>op1,貝Uop2入棧；如果op2=op1,則脫括號；如果op2<op1,貝U輸出OPi;18 .假設(shè)以

30、帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點(注意不設(shè)頭指針)，試編寫相應(yīng)的隊列初始化、入隊列和出隊列的算法。提示:參P.56P.70先畫圖.typedefLinkListCLQueue;intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTypex)intDeleteQueue(CLQueueQ,QueueElementType*x)19 .要求循環(huán)隊列不損失一個空間全部都能得到利用，設(shè)置一個標志域tag,以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此結(jié)構(gòu)相應(yīng)的入隊與出隊算法。提示:初始狀態(tài)：

31、front=0,rear=0,tag=0tag=0tag=1tag=0(或1、2)隊空條件：front=rear,隊滿條件：front=rear,其它狀態(tài)：front!=rear,入隊操作：(入隊)if(front=rear)tag=1;(或直接tag=1)出隊操作：(出隊)tag=0;問題:如何明確區(qū)分隊空、隊滿、非空非滿三種情況？20 .簡述以下算法的功能(其中棧和隊列的元素類型均為int):3.3 voidproc_1(StackS)iinti,n,A255;n=0;while(!EmptyStack(S)n+;Pop(&S,&An);for(i=1;i<=n;i+

32、)Push(&S,Ai);將棧S逆序。voidproc_2(StackS,inte)(StackT;intd;InitStack(&T);while(!EmptyStack(S)(Pop(&S,&d);if(d!=e)Push(&T,d);while(!EmptyStack(T)(Pop(&T,&d);Push(&S,d);刪除棧S中所有等于e的元素。6 voidproc_3(Queue*Q)(StackS;intd;InitStack(&S);while(!EmptyQueue(*Q)(DeleteQueue(Q,&am

33、p;d);Push(&S,d);while(!EmptyStack(S)(Pop(&S,&d);EnterQueue(Q,d)將隊列Q逆序。實習(xí)題5.6 .回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。試寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母序列，是否為形如序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&',且序列2是序列1的逆序列。例如，'a+b&b+a'是屬該模式的字符序列，而1+3&31'則不是。6.6 .停車場管理。設(shè)停車場是一個可停放n輛車的狹長通

34、道，且只有一個大門可供汽車進出。在停車場內(nèi)，汽車按到達的先后次序，由北向南依次排列（假設(shè)大門在最南端）。若車場內(nèi)已停滿n輛車，則后來的汽車需在門外的便道上等候，當(dāng)有車開走時，便道上的第一輛車即可開入。當(dāng)停車場內(nèi)某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門后，其它車輛再按原次序返回車場。每輛車離開停車場時，應(yīng)按其停留時間的長短交費（在便道上停留的時間不收費）。試編寫程序，模擬上述管理過程。要求以順序棧模擬停車場，以鏈隊列模擬便道。從終端讀入汽車到達或離去的數(shù)據(jù)，每組數(shù)據(jù)包括三項：是“到達”還是“離去”；汽車牌照號碼；“到達”或“離去”的時刻。與每組輸入信息相應(yīng)的輸出

35、信息為：如果是到達的車輛，則輸出其在停車場中或便道上的位置；如果是離去的車輛，則輸出其在停車場中停留的時間和應(yīng)交的費用。（提示：需另設(shè)一個棧，臨時停放為讓路而從車場退出的車。）車庫便道暫時退車道7.6 .商品貨架管理。商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置。用隊列和棧作為周轉(zhuǎn)，實現(xiàn)上述管理過程。第三章答案7 按3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進行車廂調(diào)度，回答：(1)如進站的車廂序列為123,則可能得到的出站車廂序列是什么？(2)如進站的車廂序列為123456,能否得到435612和1354

36、26的出站序列，并說明原因(即寫出以“S”表示進棧、“X”表示出棧的棧序列操作)?！窘獯稹?1)可能得到的出站車廂序列是：123、132、213、231、321。(2)不能得到435612的出站序列。因為有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此時按照“后進先出”的原則，出棧的順序必須為X(2)X(1)。能得到135426的出站序列。因為有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。(1) 給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別棧空與棧滿？【解答】(1)順序棧(top用來存放棧頂元素

37、的下標)判斷棧S空：如果S->top=-1表示?？?。判斷棧S滿：如果S->top=Stack_Size-1表示棧滿。(2)鏈棧(top為棧頂指針，指向當(dāng)前棧頂元素前面的頭結(jié)點)判斷?？眨喝绻鹴op->next=NULL表示?？?。判斷棧滿：當(dāng)系統(tǒng)沒有可用空間時，申請不到空間存放要進棧的元素，此時棧滿。(1) 照四則運算加、減、乘、除和哥運算的優(yōu)先慣例，畫出對下列表達式求值時操作數(shù)棧和運算符棧的變化過程：A-B*C/D+ETF【解答】(1) 寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母序列，是否形如序列1&序列2'的字符序列。序列1和序列2中都不含&&#

38、39;,且序列2是序列1的逆序列。例如，'a+b&b+a'是屬于該模式的字符序列，而1+3&31'則不是?！窘獯稹克惴ㄈ缦拢篿ntIsHuiWen()Stack*S;Charch,temp;InitStack(&S);Printf(n請輸入字符序列：");Ch=getchar();While(ch!=&)/*序列1入棧*/(Push(&S,ch);ch=getchar();do(ch=getchar();Pop(&S,&temp);if(ch!=temp)(return(FALSE);printf(nN&

39、#39;。);while(ch!=&&!IsEmpty(&S)if(ch=&&IsEmpty(&S)return(TRUE);printf(nYES');else/*判斷序列2是否是序列1的逆序列*/*序列2不是序列1的逆序列*/*序列2是序列1的逆序列*/return(FALSE);printf(nNO);/*IsHuiWen()*/5 要求循環(huán)隊列不損失一個空間全部都能得到利用，設(shè)置一個標志tag,以tag為?；?來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此相應(yīng)的入隊與出隊算法?！窘獯稹咳腙犓惴ǎ篿ntEnterQueue(Se

40、qQueue*Q,QueueElementTypex)/*將元素x入隊*/if(Q->front=Q->front&&tag=1)/*隊滿*/return(FALSE);if(Q->front=Q->front&&tag=0)/*x入隊前隊空，x入隊后重新設(shè)置標志*/tag=1;Q->elememtQ->rear=x;Q->rear=(Q->rear+1)%MAXSIZE;/*設(shè)置隊尾指針*/Return(TRUE);出隊算法：intDeleteQueue(SeqQueue*Q,QueueElementType*x

41、)/*刪除隊頭元素，用x返回其值*/if(Q->front=Q->rear&&tag=0)/*隊空*/return(FALSE);*x=Q->elementQ->front;Q->front=(Q->front+1)%MAXSIZE;/*重新設(shè)置隊頭指針*/if(Q->front=Q->rear)tag=0;/*隊頭元素出隊后隊列為空，重新設(shè)置標志域*/Return(TUUE);編寫求解Hanoi問題的算法，并給出三個盤子搬動時的遞歸調(diào)用過程?！窘獯稹克惴ǎ簐oidhanoi(intn,charx,chary,charz)/*將塔

42、座X上按直徑由小到大且至上而下編號為1到n的n個圓盤按規(guī)則搬到塔座Z上，Y可用做輔助塔座*/if(n=1)move(x,1,z);elseHanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);Hanoi(3,A,B,C)的遞歸調(diào)用過程：Hanoi(2,A,C,B):Hanoi(1,A,B,C)move(A->C)1號搬到CMove(A->B)2號搬到BHanoi(1,C,A,B)move(C->B)1號搬到BMove(A->C)3號搬到CHanoi(2,B,A,C)Hanoi(1,B,C,A)move(B->A)1號搬到AMo

43、ve(B->C)2號搬到CHanoi(1,A,B,C)move(A->C)1號搬到C第4章串習(xí)題5.5 .設(shè)s='IAMASTUDENT',t='GOOD,q='WORKER。給出下列操作的結(jié)果：StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,'A',StrReplace(s,'STUDENT,q);StrCat(StrCat(sub1,t),StrCat(sub2,q);參考答案StrLength(s)=14;sub1='IAMA

44、二'sub2='工'StrIndex(s,'A'6;4)=StrReplace(s,'STUDENT,q)=IAMAWORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q)='IAMAGOODWORKER;6.6 .編寫算法，實現(xiàn)串的基本操作StrReplace(S,T,V)。7.7 .假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1,且附設(shè)頭結(jié)點。試編寫算法，實現(xiàn)串的下列基本操作：StrAsign(S,chars);StrCopy(S,T);StrCompare(S,T);StrLength(S);StrCat(S,T)

45、;SubString(Sub,S,pos,len)。說明:用單鏈表實現(xiàn)。8.8 .敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。9.9 .已知：S="(xyz)*“萬="(x+z)*y利'用聯(lián)接、求子串和置換等操作，將S轉(zhuǎn)換為T.10.10 .S和T是用結(jié)點大小為1的單鏈表存儲的兩個串，設(shè)計一個算法將串S中首次與T匹配的子串逆置。11.11 .S是用結(jié)點大小為4的單鏈表存儲的串，分別編寫算法在第k個字符后插入串T,及從第k個字符刪除len個字符。以下算法用定長順序串：8.寫下列算法:8 將順序串9 將順序串10 從順序串

46、11 從順序串12 從順序串r中所有值為chi的字符換成ch2的字符。r中所有字符按照相反的次序仍存放在r中。r中刪除其值等于ch的所有字符。ri中第index個字符起求出首次與串r2相同的子串的起始位置。r中刪除所有與串ri相同的子串。12.12 .寫一個函數(shù)將順序串si中的第提小:(1)用靜態(tài)順序串13.13 .寫算法，實現(xiàn)順序串的基本操作14.14 .寫算法，實現(xiàn)順序串的基本操作提示:(1)被替換子串定位(相當(dāng)于第i個字符到第j個字符之間的字符用s2串替換。(2)先移位，后復(fù)制StrCompare(s,t)。StrReplace(&s,t,v)。9題中i)(2)被替換子串后面的字

47、符左移或右移(為替換子串準備房間)(3)替換子串入住(復(fù)制)(4)重復(fù)上述，直到答案q='WORKER。給出下列操作的結(jié)果：sub1='IAMA'；sub2='；s='IAMAWORKER；sub1='IAMAGOODWORKER。第四章1 設(shè)s='IAMASTUDENT',t='GOOD【解答】StrLength(s)=14;SubString(sub1,s,1,7)SubString(sub2,s,7,1)StrIndex(s,4,'A)=6;StrReplace(s,'STUDENT,q);StrCa

48、t(StrCat(sub1,t),StrCat(sub2,q)1 編寫算法，實現(xiàn)串的基本操作StrReplace(S,T,V)?！窘獯稹克惴ㄈ缦拢篿ntstrReplace(SStringS,SStringT,SStringV)/*用串V替換S中的所有子串T*/intpos,i;pos=strIndex(S,1,T);/*求S中子串T第一次出現(xiàn)的位置*/if(pos=0)return(0);/*用串V替換S中的所有子串T*/while(pos!=0)switch(T.len-V.len)case0:for(i=0;i<=V.len;i+)S->chpos+i=V.chi;case&

49、gt;0:for(i=pos+t.ien;i<S->len;i-)S->chi-t.len+v.len=S->chi;for(i=0;i<=V.len;i+)S->chpos+i=V.chi;S->len=S->len-T.len+V.len;case<0:if(S->len-T.len+V.len)<=MAXLEN/*將S中子串T后的所有字符后移/*串T的長度等于串V的長度*/*用V替換T*/*串T的長度大于串V的長度*/*將S中子串T后的所有字符前移T.len-V.len個位置*/*用V替換T*/*串T的長度小于串V的長度*

50、/*插入后串長小于MAXLEN*/V.len-T.len個位置*/for(i=S->len-T.len+V.len;i>=pos+T.len;i-)S->chi=S->chi-T.len+V.len;for(i=0;i<=V.len;i+)/*用V替換T*/S->chpos+i=V.chi;S->len=S->len-T.len+V.len;else/*替換后串長>MAXLEN,但串V可以全部替換*/if(pos+V.len<=MAXLEN)for(i=MAXLEN-1;i>=pos+T.len;i-)S->chi=s-&

51、gt;chi-T.len+V.lenfor(i=0;i<=V.len;i+)/*用V替換T*/S->chpos+i=V.chi;S->len=MAXLEN;else/*串V的部分字符要舍棄*/for(i=0;i<MAXLEN-pos;i+)S->chi+pos=V.chi;S->len=MAXLEN;pos=StrIndex(S,pos+V.len,T);/*求S中下一個子串T的位置*/*switch()*/*while()*/return(1);/*StrReplace()*/附加題：用鏈式結(jié)構(gòu)實現(xiàn)定位函數(shù)?！窘獯稹縯ypedefstructNodecha

52、rdata;structNode*next;Node,*Lstring;intstrIndex(LstringS,intpos,LstringT)/*從串S的pos序號起，串T第一次出現(xiàn)的位置*/Node*p,*q,*Ppos;inti=0,j=0;if(T->next=NULL|S->next=NULL)return(0);p=S->next;q=T->next;while(p!=NULL&&j<pos)/*p指向串S中第pos個字符*/p=p->next;j+;if(j!=pos)return(0);while(p!=NULL&&

53、amp;q!=NULL)Ppos=p;/*Ppos指向當(dāng)前匹配的起始字符*/if(p->data=q->data)p=p->next;q=q->next;else/*從Ppos指向字符的下一個字符起從新匹配*/p=Ppos->next;q=T->head->next;i+;/*匹配成功*/*失敗*/if(q=NULL)return(pos+i);elsereturn(0);第五章數(shù)組和廣義表習(xí)題.假設(shè)有6行8列的二維數(shù)組A,每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000,計算：000000000000 數(shù)組A共占用多少字節(jié)；(288)

54、111111111111 數(shù)組A的最后一個元素的地址；(1282)222222222222 按行存儲時，元素A36的地址；(1126)333333333333 按列存儲時，元素A36的地址；(1192)注意:本章自定義數(shù)組的下標從1開始。.設(shè)有三對角矩陣(a"nxn，將其三條對角線上的元素逐行地存于數(shù)組B(1:3n-2)中，使得Bk=aij,求：用i,j表示k的下標變換公式；用k表示i,j的下標變換公式。i=k/3+1,j=k%3+i-1=k%3+k/3或：=k/3+1,j=k-2X(k/3).假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組表C存放結(jié)果矩

55、陣。提示:參考P.28例、P.47例。.在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算positioncol的方法稍加改動，使算法只占用一個輔助向量空間。提示:positionk中為第k列非零元素個數(shù)，k=1,2,-nposition0=1;(第1列中第一個非零元素的正確位置)positionk=positionk-1+positionk,k=1,2,，npositionk=positionk-1,k=n,n-1,1.寫一個在十字鏈表中刪除非零元素aj的算法。提示:“刪除”兩次，釋放一次。.畫出下面廣義表的兩種存儲結(jié)構(gòu)圖示:(a),b),(),d),(e,f)1IA0e第一種存儲結(jié)構(gòu)(自底向上看).

56、求下列廣義表運算的結(jié)果：HEAD(a,b),(c,d);TAIL(a,b),(c,d);TAILHEAD(a,b),(c,d);HEADTAILHEAD(a,b),(c,d);bTAILHEADTAIL(a,b),(c,d);(d)參考題.試設(shè)計一個算法，將數(shù)組A(0:n-1)中的元素循環(huán)右移k位，并要求只用一個元素大小的附加存儲，元素移動或交換次數(shù)為O(n)。.假設(shè)按低下標優(yōu)先(以最左的下標為主序)存儲整數(shù)數(shù)組A(1:8,1:2,1:4,1:7)時，第一個元素的字節(jié)地址是100,每個整數(shù)占4個字節(jié)，問元素A(4,2,3,5)的存儲地址是什么？.高下標優(yōu)先(以最右的下標為主序)存儲整數(shù)數(shù)組A(1:8,1:2,1:4,1:7)時，順序列出數(shù)組A的所有元素。.試編寫一個以三元組形式輸出用十字鏈表表示的稀疏矩陣中非零元素及其下標的算法。實習(xí)題1,若矩陣A亦n中的某個元素a。是第i行中的最小值，同時又是第j列中的最大值，則稱此元素為該矩陣中的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣，試編寫算法求出矩陣中的所有馬鞍