數(shù)據(jù)結(jié)構(gòu)習(xí)題集C語言版嚴(yán)蔚敏

1、第1章 緒論1.1 簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。1.2 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。1.3 設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R)，其中，試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。1.4 試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù)）。1.5 試畫出與下列程序段等價(jià)的框圖。(1) product=1; i=1; while(i<=n) product *= i; i+; (2) i=0; do i+; while(i!=n) &&a

2、mp; (ai!=x);(3) switch case x<y: z=y-x; break; case x=y: z=abs(x*y); break; default: z=(x-y)/abs(x)*abs(y); 1.6 在程序設(shè)計(jì)中，常用下列三種不同的出錯(cuò)處理方式：(1) 用exit語句終止執(zhí)行并報(bào)告錯(cuò)誤；(2) 以函數(shù)的返回值區(qū)別正確返回或錯(cuò)誤返回；(3) 設(shè)置一個(gè)整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)。1.7 在程序設(shè)計(jì)中，可采用下列三種方法實(shí)現(xiàn)輸出和輸入：(1) 通過scanf和printf語句；(2) 通過函數(shù)的參數(shù)顯式傳遞；(3) 通過

3、全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。1.8 設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號的語句的頻度：(1) i=1; k=0; while(i<=n-1) k += 10*i; i+; (2) i=1; k=0; do k += 10*i; 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=1; j<=i; j+

4、) for(k=1; k<=j; k+) x += delta; (6) i=1; j=0; while(i+j<=n) if(i>j) j+; else i+; (7) x=n; y=0; / n是不小于1的常數(shù) while(x>=(y+1)*(y+1) y+; (8) x=91; y=100; while(y>0) if(x>100) x -= 10; y-; else x+; 1.9 假設(shè)n為2的乘冪，并且n>2，試求下列算法的時(shí)間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。int Time(int n) count = 0;x=2;whi

5、le(x<n/2) x *= 2;count+;return count;1.11 已知有實(shí)現(xiàn)同一功能的兩個(gè)算法，其時(shí)間復(fù)雜度分別為和，假設(shè)現(xiàn)實(shí)計(jì)算機(jī)可連續(xù)運(yùn)算的時(shí)間為秒（100多天），又每秒可執(zhí)行基本操作（根據(jù)這些操作來估算算法時(shí)間復(fù)雜度）次。試問在此條件下，這兩個(gè)算法可解問題的規(guī)模（即n值的范圍）各為多少？哪個(gè)算法更適宜？請說明理由。1.12 設(shè)有以下三個(gè)函數(shù)： ，請判斷以下斷言正確與否：(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 試設(shè)定若干n值，比較兩函數(shù)和的增

6、長趨勢，并確定n在什么范圍內(nèi)，函數(shù)的值大于的值。1.14 判斷下列各對函數(shù)和，當(dāng)時(shí)，哪個(gè)函數(shù)增長更快？(1) ，(2) ，(3) ，(4) ，1.15 試用數(shù)學(xué)歸納法證明：(1) (2) (3) (4) 1.16 試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X，Y和Z的值1.17 已知k階斐波那契序列的定義為，；， 試編寫求k階斐波那契序列的第m項(xiàng)值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。1.18 假設(shè)有A，B，C，D，E五個(gè)高等院校進(jìn)行田徑對抗賽，各院校的單項(xiàng)成績均已存入計(jì)算機(jī)，并構(gòu)成一張表，表中每一行的形式為項(xiàng)目名稱性別校名成績得分編寫算法，處理上述表格，以統(tǒng)計(jì)各院校的男、

7、女總分和團(tuán)體總分，并輸出。1.19 試編寫算法，計(jì)算的值并存入數(shù)組a0.arrsize-1的第i-1個(gè)分量中(i=1,2,n)。假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為maxint，則當(dāng)n>arrsize或?qū)δ硞€(gè)，使時(shí)，應(yīng)按出錯(cuò)處理。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。1.20 試編寫算法求一元多項(xiàng)式的值的值，并確定算法中每一語句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度。注意選擇你認(rèn)為較好的輸入和輸出方法。本題的輸入為，和，輸出為。第2章 線性表2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。2.2 填空題。(1) 在順序表中插入或刪除一個(gè)元素，需要平均移動 元素，具體移動的元素

8、個(gè)數(shù)與 有關(guān)。 (2) 順序表中邏輯上相鄰的元素的物理位置 緊鄰。單鏈表中邏輯上相鄰的元素的物理位置 緊鄰。 (3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由 指示。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 。2.3 在什么情況下用順序表比鏈表好？2.4 對以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。2.5 畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。L=(LinkList)malloc(sizeof(LNode);P=L;for(i=1;i<=4;i+)P->next=(LinkList)malloc(sizeof(LNode);P=P->next;P->

9、data=i*2-1;P->next=NULL;for(i=4;i>=1;i-) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i+) Del_LinkList(L,i);2.6 已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是_。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是_。c. 在表首插入S結(jié)點(diǎn)的語句序列是_。d. 在表尾插入S結(jié)點(diǎn)的語句序列是_。(1) P->next=S;(2) P->next=P->next->next;(

10、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;(11) P=L;(12) L=S;(13) L=P;2.7 已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。 a. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是_。 b. 刪

11、除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是_。 c. 刪除P結(jié)點(diǎn)的語句序列是_。 d. 刪除首元結(jié)點(diǎn)的語句序列是_。e. 刪除尾元結(jié)點(diǎn)的語句序列是_。(1) P=P->next;(2) P->next=P;(3) P->next=P->next->next;(4) P=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->n

12、ext->next!=Q) P=P->next;(9) while(P->next->next!=NULL) P=P->next;(10) Q=P;(11) Q=P->next;(12) P=L;(13) L=L->next;(14) free(Q);2.8 已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是_。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是_。c. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是_。d. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是_。e. 刪除P結(jié)點(diǎn)的語句序列是_。(1) P-&g

13、t;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;(11) P->next->priou=P;(12) P->next->

14、;priou=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) Status A(LinkedList L) /L是無表頭結(jié)點(diǎn)的單鏈表if(L && L->next) Q=L;L=L->next;P=L;while(P->next) P=P->next;P->next=Q;Q->next=NULL;

15、return OK;(2) void BB(LNode *s, LNode *q) p=s;while(p->next!=q) p=p->next;p->next =s;void AA(LNode *pa, LNode *pb) /pa和pb分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn)BB(pa,pb);BB(pb,pa);2.10 指出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè)既正確又高效的算法。Status DeleteK(SqList &a,int i,int k)/本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if(i<1|k<0|i+k>a

16、.length) return INFEASIBLE;/參數(shù)不合法else for(count=1;count<k;count+)/刪除第一個(gè)元素for(j=a.length;j>=i+1;j-) a.elemj-i=a.elemj;a.length-;return OK;2.11 設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。解：Status InsertOrderList(SqList &va,ElemType x)/在非遞減的順序表va中插入元素x并使其仍成為順序表的算法int i;if(va.length=va.li

17、stsize)return(OVERFLOW);for(i=va.length;i>0,x<va.elemi-1;i-)va.elemi=va.elemi-1;va.elemi=x;va.length+;return OK;2.12 設(shè)和均為順序表，和分別為和中除去最大共同前綴后的子表。若空表，則；若=空表，而空表，或者兩者均不為空表，且的首元小于的首元，則；否則。試寫一個(gè)比較，大小的算法。2.13 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(L,x);2.14 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Length(L)。2.15 已知指針ha和hb分別指

18、向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長度分別為m和n。試寫一算法將這兩個(gè)鏈表連接在一起，假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。請分析你的算法的時(shí)間復(fù)雜度。2.16 已知指針la和lb分別指向兩個(gè)無頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。下列算法是從表la中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表lb中第i個(gè)元素之前。試問此算法是否正確？若有錯(cuò)，請改正之。Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)if(i<0|j<0|len<0) r

19、eturn INFEASIBLE;p=la;k=1;while(k<i)p=p->next;k+;q=p;while(k<=len)q=q->next;k+;s=lb; k=1;while(k<j)s=s->next;k+;s->next=p; q->next=s->next;return OK;2.17 試寫一算法，在無頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)線性表操作Insert(L,i,b)，并和在帶頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。2.18試寫一算法，實(shí)現(xiàn)線性表操作Delete(L,i)，并和在帶頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法

20、進(jìn)行比較。2.19 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素），同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度（注意，mink和maxk是給定的兩個(gè)參變量，它們的值可以和表中的元素相同，也可以不同）。2.20 同2.19題條件，試寫一高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度。2.21 試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表逆置為。2.22 試寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。

21、2.23 設(shè)線性表，試寫一個(gè)按下列規(guī)則合并A，B為線性表C的算法，即使得當(dāng)時(shí)；當(dāng)時(shí)。線性表A，B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。2.24 假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構(gòu)，請編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表。2.25 假設(shè)以兩個(gè)元素依值遞增有序排列的線性表A和B分別表示兩個(gè)集合（即同一表中的元素值各不相同），現(xiàn)要求另辟空間構(gòu)成一個(gè)線性表C，其元素為A和B中元素的交集，且表

22、C中的元素有依值遞增有序排列。試對順序表編寫求C的算法。2.26 要求同2.25題。試對單鏈表編寫求C的算法。2.27 對2.25題的條件作以下兩點(diǎn)修改，對順序表重新編寫求得表C的算法。(1) 假設(shè)在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2) 利用A表空間存放表C。2.28 對2.25題的條件作以下兩點(diǎn)修改，對單鏈表重新編寫求得表C的算法。(1) 假設(shè)在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2) 利用原表（A表或B表）中的結(jié)點(diǎn)構(gòu)成表C，并釋放A表中的無用結(jié)點(diǎn)空間。2.29 已知A，B和C為三個(gè)遞增有序的線性表，

23、現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對順序表編寫實(shí)現(xiàn)上述操作的算法，并分析你的算法的時(shí)間復(fù)雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。2.30 要求同2.29題。試對單鏈表編寫算法，請釋放A表中的無用結(jié)點(diǎn)空間。2.31 假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。2.32 已知有一個(gè)單向循環(huán)鏈表，其每個(gè)結(jié)點(diǎn)中含三個(gè)域：pre，data和next，其中data為數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，pre也為指針域，但它的值為空，試編寫算法將此單向循

24、環(huán)鏈表改為雙向循環(huán)鏈表，即使pre成為指向前驅(qū)結(jié)點(diǎn)的指針域。2.33 已知由一個(gè)線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其他字符），試編寫算法將該線性表分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類字符。2.34 假設(shè)在算法描述語言中引入指針的二元運(yùn)算“異或”，若a和b為指針，則ab的運(yùn)算結(jié)果仍為原指針類型，且a(ab)=(aa)b=b(ab)b=a(bb)=a則可利用一個(gè)指針域來實(shí)現(xiàn)雙向鏈表L。鏈表L中的每個(gè)結(jié)點(diǎn)只含兩個(gè)域：data域和LRPtr域，其中LRPtr域存放該結(jié)點(diǎn)的左鄰與右鄰結(jié)點(diǎn)指針（不存在時(shí)為NULL）的異或。若設(shè)指針L.Left指向

25、鏈表中的最左結(jié)點(diǎn)，L.Right指向鏈表中的最右結(jié)點(diǎn)，則可實(shí)現(xiàn)從左向右或從右向左遍歷此雙向鏈表的操作。試寫一算法按任一方向依次輸出鏈表中各元素的值。2.35 采用2.34題所述的存儲結(jié)構(gòu)，寫出在第i個(gè)結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)的算法。2.36 采用2.34題所述的存儲結(jié)構(gòu)，寫出刪除第i個(gè)結(jié)點(diǎn)的算法。2.37 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表。試寫一時(shí)間復(fù)雜度O(n)的算法，將L改造為。2.38 設(shè)有一個(gè)雙向循環(huán)鏈表，每個(gè)結(jié)點(diǎn)中除有pre，data和next三個(gè)域外，還增設(shè)了一個(gè)訪問頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當(dāng)對鏈表進(jìn)行一次Locate(L,x)的操作

26、后，被訪問的結(jié)點(diǎn)（即元素值等于x的結(jié)點(diǎn)）中的頻度域freq的值便增1，同時(shí)調(diào)整鏈表中結(jié)點(diǎn)之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點(diǎn)總是靠近表頭結(jié)點(diǎn)。試編寫符合上述要求的Locate操作的算法。2.39 已知稀疏多項(xiàng)式，其中，。試采用存儲量同多項(xiàng)式項(xiàng)數(shù)m成正比的順序存儲結(jié)構(gòu)，編寫求的算法（為給定值），并分析你的算法的時(shí)間復(fù)雜度。2.40 采用2.39題給定的條件和存儲結(jié)構(gòu)，編寫求的算法，將結(jié)果多項(xiàng)式存放在新辟的空間中，并分析你的算法的時(shí)間復(fù)雜度。2.41 試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲結(jié)構(gòu)，編寫求其導(dǎo)函數(shù)的方法，要求利用原多項(xiàng)式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)多項(xiàng)式，同

27、時(shí)釋放所有無用結(jié)點(diǎn)。2.42 試編寫算法，將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間構(gòu)成這兩個(gè)鏈表。第3章 棧和隊(duì)列3.1 若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進(jìn)行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請回答：(1) 如果進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？(2) 如果進(jìn)站的車廂序列為123456，則能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到（即寫出以 S表示進(jìn)棧和以 X表示出棧的棧操作序列）。3.2 簡述棧和線性表的差別。3.3 寫出下列程序段

28、的輸出結(jié)果（棧的元素類型SElemType為char）。void main()Stack S;char x,y;InitStack(S);x= c; y= k;Push(S,x);Push(S, a);Push(S,y);Pop(S,x);Push(S, t);Push(S,x);Pop(S,x);Push(S, s);while(!StackEmpty(S) Pop(S,y); printf(y); printf(x);3.4 簡述以下算法的功能（棧的元素類型SElemType為int）。(1) status algo1(Stack S) int i,n,A255;n=0;while(!St

29、ackEmpty(S) n+; Pop(S,An); for(i=1;i<=n;i+) Push(S,Ai);(2) status algo2(Stack S,int e)Stack T; int d;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 假設(shè)以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列

30、）。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個(gè)不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體，而不是值）序列。 3.6 試證明：若借助棧由輸入序列12n得到的輸出序列為(它是輸入序列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k使<<。3.7 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算()優(yōu)先關(guān)系的慣例，并仿照教科書3.2節(jié)例3-2的格式，畫出對下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：A-B×C/D+EF3.8 試推導(dǎo)求解n階梵塔問題至少要執(zhí)行的move操作的次數(shù)。3.9

31、試將下列遞推過程改寫為遞歸過程。void ditui(int n)int i;i = n;while(i>1)cout<<i-;3.10 試將下列遞歸過程改寫為非遞歸過程。void test(int &sum)int x;cin>>x;if(x=0) sum=0;elsetest(sum);sum+=x;cout<<sum;3.11 簡述隊(duì)列和堆棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處。3.12 寫出以下程序段的輸出結(jié)果（隊(duì)列中的元素類型QElemType為char）。void main()Queue Q;InitQueue(Q);char x= e,

32、 y= c;EnQueue(Q, h);EnQueue(Q, r);EnQueue(Q, y);DeQueue(Q, x);EnQueue(Q, x);DeQueue(Q, x);EnQueue(Q, a);While(!QueueEmpty(Q)DeQueue(Q,y);cout<<y;cout<<x;3.13 簡述以下算法的功能（棧和隊(duì)列的元素類型均為int）。 void algo3(Queue &Q)Stack S;int d;InitStack(S);while(!QueueEmpty(Q)DeQueue(Q, d);Push(S, d);while(!

33、StackEmpty(S)Pop(S, d);EnQueue(Q, d);3.14 若以1234作為雙端隊(duì)列的輸入序列，試分別求出滿足以下條件的輸出序列： (1) 能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列。 (2) 能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列。 (3) 既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列。3.15 假設(shè)以順序存儲結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧，即在一維數(shù)組的存儲空間中存在著兩個(gè)棧，它們的棧底分別設(shè)在數(shù)組的兩個(gè)端點(diǎn)。試編寫實(shí)現(xiàn)這個(gè)雙向棧tws的三個(gè)操作：初始化inistack(tws)、入棧push(

34、tws,i,x)和出棧pop(tws,i)的算法，其中i為0或1，用以分別指示設(shè)在數(shù)組兩端的兩個(gè)棧，并討論按過程(正/誤狀態(tài)變量可設(shè)為變參)或函數(shù)設(shè)計(jì)這些操作算法各有什么有缺點(diǎn)。3.16 假設(shè)如題3.1所屬火車調(diào)度站的入口處有n節(jié)硬席或軟席車廂（分別以H和S表示）等待調(diào)度，試編寫算法，輸出對這n節(jié)車廂進(jìn)行調(diào)度的操作（即入棧或出棧操作）序列，以使所有的軟席車廂都被調(diào)整到硬席車廂之前。3.17 試寫一個(gè)算法，識別一次讀入的一個(gè)以為結(jié)束符的字符序列是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而1+3&3-1則不是。3.18 試寫一個(gè)判別表達(dá)式中開、閉括號是否配對出現(xiàn)的算法。3.20 假設(shè)以二維數(shù)組g(1m, 1n)表示一個(gè)圖像區(qū)域，gi,j表示該區(qū)域中點(diǎn)(i,j)所具顏色，其值為從0到k的整數(shù)。編寫算法置換點(diǎn)(i0,j0)所在區(qū)域的顏色。約定和(i0,j0)同色的上、下、左、右的鄰接點(diǎn)為同色區(qū)域的點(diǎn)。3.21 假設(shè)表達(dá)式有單字母變量和雙目四則運(yùn)算符構(gòu)成。試寫一個(gè)算法，將一個(gè)通常書寫形式且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭表達(dá)式。3.22 如題3.21的假設(shè)條件，試寫一個(gè)算法，對以