數(shù)據(jù)結(jié)構(gòu)習(xí)題答案[試題題目]

1、第1章 緒論習(xí)題1簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。2試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。3簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。4存儲結(jié)構(gòu)由哪兩種基本的存儲方法實(shí)現(xiàn)？5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（ ）。A存儲結(jié)構(gòu) B存儲實(shí)現(xiàn)C邏輯結(jié)構(gòu) D運(yùn)算實(shí)現(xiàn)（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著

2、（ ）。 A數(shù)據(jù)具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等（4）以下說法正確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)（5）以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ ）。A順序隊(duì)列 B. 鏈表 C. 有序表 D. 鏈棧（6）以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊(duì) D棧6試分析下面各程序段的時(shí)間復(fù)雜度。（1）x=90; y=100;while(y0)if(x100) x=x-10;y-;e

3、lse x+;（2）for (i=0; in; i+)for (j=0; jm; j+)aij=0;（3）s=0; for i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;（4）i=1; while(i=n) i=i*3;（5）x=0;for(i=1; in; i+) for (j=1; j1y=0;while(x(y+1)* (y+1) y+;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因?yàn)閤+共執(zhí)行了n-1+n-2+1= n(n-1)/2，所以執(zhí)行時(shí)間為O（n2）（6）O()第2章 線性表1選擇題（1）一個(gè)向量第一個(gè)元素的

4、存儲地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是（ ）。A110 B108 C100 D120（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（ ）。A訪問第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） B在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）C刪除第i個(gè)結(jié)點(diǎn)（1in）D將n個(gè)結(jié)點(diǎn)從小到大排序（3） 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng) 的元素個(gè)數(shù)為（ ）。A8 B63.5 C63 D7（4）鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（ ）。A分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B只有一部分，存放結(jié)點(diǎn)值C只有一部

5、分，存儲表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（5）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以（6）線性表在（ ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A需經(jīng)常修改中的結(jié)點(diǎn)值 需不斷對進(jìn)行刪除插入 C中含有大量的結(jié)點(diǎn) 中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（7）單鏈表的存儲密度（ ）。A大于1 B等于1 C小于1 D不能確定（8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（ ）。An B2n-1 C2n Dn-1（9）在一個(gè)長度為n的順序表中，在第i個(gè)元素（1in+1）之

6、前插入一個(gè)新元素時(shí)須向后移動(dòng)（ ）個(gè)元素。An-i Bn-i+1 Cn-i-1 Di(10) 線性表L=(a1，a2,an)，下列說法正確的是（ ）。A每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B線性表中至少有一個(gè)元素C表中諸元素的排列必須是由小到大或由大到小D除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。(11) 若指定有n個(gè)元素的向量，則建立一個(gè)有序單鏈表的時(shí)間復(fù)雜性的量級是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)(12) 以下說法錯(cuò)誤的是（ ）。A求表長、定位這兩種運(yùn)算在采用順序存儲結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低B順

7、序存儲的線性表可以隨機(jī)存取C由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)(13) 在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（ ）。As-next=p+1; p-next=s;B(*p).next=s; (*s).next=(*p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; (14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-ne

8、xt-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;(15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（ ）。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-ne

9、xt=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;2算法設(shè)計(jì)題（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La-next; pb=Lb-next; Lc=pc=La; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) while(pa & pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-ne

10、xt; else if(pa-datapb-data) pc-next=pb; pc=pb; pb=pb-next; else / 相等時(shí)取La的元素，刪除Lb的元素 pc-next=pa;pc=pa;pa=pa-next; q=pb-next;delete pb ;pb =q; pc-next=pa?pa:pb; /插入剩余段 delete Lb; /釋放Lb的頭結(jié)點(diǎn) （2）將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。void union(LinkList& La, LinkList& Lb,

11、LinkList& Lc, ) pa = La-next; pb = Lb-next; / 初始化 Lc=pc=La; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) Lc-next = NULL; while ( pa | pb ) if ( !pa ) q = pb; pb = pb-next; else if ( !pb ) q = pa; pa = pa-next; else if (pa-data data ) q = pa; pa = pa-next; else q = pb; pb = pb-next; q-next = Lc-next; Lc-next = q; / 插入 delete Lb

12、; /釋放Lb的頭結(jié)點(diǎn) （3）已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于A鏈表中。void Mix(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa=la-next;pb=lb-next;設(shè)工作指針pa和pb；Lc=pc=La; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(pa&pb) if(pa-data=pb-data)交集并入結(jié)果表中。 pc-next=pa;pc=pa;pa=pa-next; u=pb;pb=pb-next; delete u; else if(pa-datadata) u=pa;

13、pa=pa-next; delete u;else u=pb; pb=pb-next; delete u;while(pa) u=pa; pa=pa-next; delete u; 釋放結(jié)點(diǎn)空間while(pb) u=pb; pb=pb-next; delete u;釋放結(jié)點(diǎn)空間pc-next=null;置鏈表尾標(biāo)記。delete Lb; 注： 本算法中也可對B表不作釋放空間的處理（4）已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出兩個(gè)集合A和B 的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲，同時(shí)返回該集合的元素個(gè)數(shù)。void Differ

14、ence（LinkedList A，B，*n）A和B均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，分別存儲了一個(gè)集合，本算法求兩集合的差集，存儲于單鏈表A中，*n是結(jié)果集合中元素個(gè)數(shù)，調(diào)用時(shí)為0p=A-next； p和q分別是鏈表A和B的工作指針。 q=B-next； pre=A； pre為A中p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針。 while（p!=null & q!=null）if（p-datadata）pre=p；p=p-next；*n+； A鏈表中當(dāng)前結(jié)點(diǎn)指針后移。else if（p-dataq-data）q=q-next； B鏈表中當(dāng)前結(jié)點(diǎn)指針后移。else pre-next=p-next； 處理A，B中元

15、素值相同的結(jié)點(diǎn)，應(yīng)刪除。 u=p； p=p-next； delete u； 刪除結(jié)點(diǎn)（5）設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點(diǎn)）。（6）設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。ElemType Max (LinkList L )if(L-next=NULL) return NULL;pmax=L-next; /假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L-next-next;while(p != NULL )/如果下一個(gè)結(jié)點(diǎn)存在if(

16、p-data pmax-data) pmax=p;p=p-next;return pmax-data;（7）設(shè)計(jì)一個(gè)算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。void inverse(LinkList &L) / 逆置帶頭結(jié)點(diǎn)的單鏈表 L p=L-next; L-next=NULL; while ( p) q=p-next; / q指向*p的后繼 p-next=L-next; L-next=p; / *p插入在頭結(jié)點(diǎn)之后 p = q; （8）設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中

17、的元素相同，也可以不同 ）。void delete(LinkList &L, int mink, int maxk) p=L-next; /首元結(jié)點(diǎn) while (p & p-datanext; /查找第一個(gè)值mink的結(jié)點(diǎn) if (p) while (p & p-datanext; / 查找第一個(gè)值 maxk 的結(jié)點(diǎn) q=pre-next; pre-next=p; / 修改指針 while (q!=p) s=q-next; delete q; q=s; / 釋放結(jié)點(diǎn)空間 /if（9）已知p指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、prior、next三個(gè)域，寫出算法change(p

18、),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)（p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。void Exchange（LinkedList p）p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。q=p-llink； q-llink-rlink=p； p的前驅(qū)的前驅(qū)之后繼為p p-llink=q-llink； p的前驅(qū)指向其前驅(qū)的前驅(qū)。 q-rlink=p-rlink； p的前驅(qū)的后繼為p的后繼。 q-llink=p； p與其前驅(qū)交換 p-rlink-llink=q； p的后繼的前驅(qū)指向原p的前驅(qū) p-rlink=q；

19、 p的后繼指向其原來的前驅(qū)算法exchange結(jié)束。（10）已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分析 在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)（刪第i個(gè)元素，第i+1至第n個(gè)元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針（i=1，j=n），從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。void Delete（ElemType A ，int n）

20、A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。i=1；j=n；設(shè)置數(shù)組低、高端指針（下標(biāo)）。 while（ij） while（ij & Ai!=item）i+； 若值不為item，左移指針。 if（ij）while（ij & Aj=item）j-；若右端元素值為item，指針左移 if（idata;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；（5）設(shè)有一個(gè)遞歸算法如下 int fact(int n) /n大于等于0 if(n=0) return 1; else return

21、n*fact(n-1); 則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。An+1 Bn-1 C n D n+2（6）棧在（ ）中有所應(yīng)用。A遞歸調(diào)用 B函數(shù)調(diào)用 C表達(dá)式求值 D前三個(gè)選項(xiàng)都有（7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ ）。A隊(duì)列 B棧 C 線性表 D有序表（8）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是

22、（）。A2 B3 C4 D 6（9）在一個(gè)具有n個(gè)單元的順序棧中，假設(shè)以地址高端作為棧底，以top作為棧頂指針，則當(dāng)作進(jìn)棧處理時(shí)，top的變化為（）。 Atop不變 Btop=0 Ctop- Dtop+（10）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧（11）用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改（12）循環(huán)隊(duì)列存儲在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（）。A. rear=rear+1 B. rear=

23、(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) （13）最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front（14）棧和隊(duì)列的共同點(diǎn)是（）。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)（15）一個(gè)遞歸算法必須包括（）。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分（2）回文是指正讀反讀

24、均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)根據(jù)提示，算法可設(shè)計(jì)為：/以下為順序棧的存儲結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的?？臻g最多為100個(gè)元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , le

25、n;char temp;InitStack( &s);len=strlen(t); /求向量長度for ( i=0; ilen/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等則返回0else i+;return 1 ; / 比較完畢均相等則返回 1（3）設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an，試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（

26、入棧滿等）給出相應(yīng)的信息。#define maxsize ?？臻g容量 void InOutS(int smaxsize) /s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。 int top=0; /top為棧頂指針，定義top=0時(shí)為?？?。 for(i=1; i=n; i+) /n個(gè)整數(shù)序列作處理。 scanf(“%d”,&x); /從鍵盤讀入整數(shù)序列。 if(x!=-1) / 讀入的整數(shù)不等于-1時(shí)入棧。 if(top=maxsize-1)printf(“棧滿n”);exit(0);else s+top=x; /x入棧。 else /讀入的整數(shù)等于-1時(shí)退棧。 if(top=0)printf(

27、“?？課”);exit(0); else printf(“出棧元素是%dn”,stop-)； /算法結(jié)束。（4）從鍵盤上輸入一個(gè)后綴表達(dá)式，試編寫算法計(jì)算表達(dá)式的值。規(guī)定：逆波蘭表達(dá)式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運(yùn)算。例如：234 34+2*$。 題目分析逆波蘭表達(dá)式(即后綴表達(dá)式)求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND,對表達(dá)式從左到右掃描(讀入)，當(dāng)表達(dá)式中掃描到數(shù)時(shí)，壓入OPND棧。當(dāng)掃描到運(yùn)算符時(shí)，從OPND退出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果再壓入OPND棧。這個(gè)過程一直進(jìn)行到讀出表達(dá)式結(jié)束符$，這時(shí)OPND棧中只有一個(gè)數(shù)，就是結(jié)

28、果。 float expr( )/從鍵盤輸入逆波蘭表達(dá)式，以$表示輸入結(jié)束，本算法求逆波蘭式表達(dá)式的值。float OPND30; / OPND是操作數(shù)棧。init(OPND); /兩棧初始化。 float num=0.0; /數(shù)字初始化。 scanf (“%c”,&x);/x是字符型變量。 while(x!=$) switch case0=x=0&x=0&xj)printf(“序列非法n”)；exit(0); i+; /不論Ai是I或O，指針i均后移。 if(j!=k) printf(“序列非法n”)；return(false); else printf(“序列合法n”)；return(tr

29、ue); /算法結(jié)束。 算法討論在入棧出棧序列（即由I和O組成的字符串）的任一位置，入棧次數(shù)（I的個(gè)數(shù)）都必須大于等于出棧次數(shù)（即O的個(gè)數(shù)），否則視作非法序列，立即給出信息，退出算法。整個(gè)序列（即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記0），入棧次數(shù)必須等于出棧次數(shù)（題目中要求棧的初態(tài)和終態(tài)都為空），否則視為非法序列。(6）假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素站點(diǎn)(注意不設(shè)頭指針) ，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空 、入隊(duì)和出隊(duì)等算法。算法如下：/先定義鏈隊(duì)結(jié)構(gòu):typedef struct queuenodeDatatype data;struct queuenode *next

30、;QueueNode; /以上是結(jié)點(diǎn)類型的定義typedef structqueuenode *rear;LinkQueue; /只設(shè)一個(gè)指向隊(duì)尾元素的指針(1)置空隊(duì)void InitQueue( LinkQueue *Q) /置空隊(duì)：就是使頭結(jié)點(diǎn)成為隊(duì)尾元素QueueNode *s;Q-rear = Q-rear-next;/將隊(duì)尾指針指向頭結(jié)點(diǎn)while (Q-rear!=Q-rear-next)/當(dāng)隊(duì)列非空，將隊(duì)中元素逐個(gè)出隊(duì)s=Q-rear-next;Q-rear-next=s-next;free(s);/回收結(jié)點(diǎn)空間(2)判隊(duì)空int EmptyQueue( LinkQueue *

31、Q) /判隊(duì)空/當(dāng)頭結(jié)點(diǎn)的next指針指向自己時(shí)為空隊(duì)return Q-rear-next-next=Q-rear-next;(3)入隊(duì)void EnQueue( LinkQueue *Q, Datatype x) /入隊(duì)/也就是在尾結(jié)點(diǎn)處插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申請新結(jié)點(diǎn)p-data=x; p-next=Q-rear-next;/初始化新結(jié)點(diǎn)并鏈入Q-rear-next=p;Q-rear=p;/將尾指針移至新結(jié)點(diǎn)(4)出隊(duì)Datatype DeQueue( LinkQueue *Q)/出隊(duì),把頭結(jié)點(diǎn)之

32、后的元素摘下Datatype t;QueueNode *p;if(EmptyQueue( Q )Error(Queue underflow);p=Q-rear-next-next; /p指向?qū)⒁碌慕Y(jié)點(diǎn)x=p-data; /保存結(jié)點(diǎn)中數(shù)據(jù)if (p=Q-rear)/當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)，p結(jié)點(diǎn)出隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn)Q-rear = Q-rear-next; Q-rear-next=p-next;elseQ-rear-next-next=p-next;/摘下結(jié)點(diǎn)pfree(p);/釋放被刪結(jié)點(diǎn)return x;（7）假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素, 同時(shí)設(shè)置一個(gè)標(biāo)志tag，以ta

33、g = 0和tag = 1來區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(huán)隊(duì)列類定義#include template class Queue /循環(huán)隊(duì)列的類定義public: Queue ( int=10 ); Queue ( ) delete Q; void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = rear = tag = 0; /

34、置空隊(duì)列 int IsEmpty ( ) const return front = rear & tag = 0; /判隊(duì)列空否 int IsFull ( ) const return front = rear & tag = 1; /判隊(duì)列滿否private: int rear, front, tag;/隊(duì)尾指針、隊(duì)頭指針和隊(duì)滿標(biāo)志 Type *Q;/存放隊(duì)列元素的數(shù)組 int m;/隊(duì)列最大可容納元素個(gè)數(shù)構(gòu)造函數(shù)template Queue: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) /建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。

35、Q = new Typem;/創(chuàng)建隊(duì)列空間 assert ( Q != 0 );/斷言: 動(dòng)態(tài)存儲分配成功與否插入函數(shù)template void Queue : EnQueue ( Type &item ) assert ( ! IsFull ( ) );/判隊(duì)列是否不滿，滿則出錯(cuò)處理rear = ( rear + 1 ) % m;/隊(duì)尾位置進(jìn)1, 隊(duì)尾指針指示實(shí)際隊(duì)尾位置Qrear = item;/進(jìn)隊(duì)列tag = 1;/標(biāo)志改1，表示隊(duì)列不空刪除函數(shù)template Type Queue : DeQueue ( ) assert ( ! IsEmpty ( ) );/判斷隊(duì)列是否不空，空則

36、出錯(cuò)處理front = ( front + 1 ) % m;/隊(duì)頭位置進(jìn)1, 隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置tag = 0;/標(biāo)志改0, 表示棧不滿return Qfront;/返回原隊(duì)頭元素的值讀取隊(duì)頭元素函數(shù)template Type Queue : GetFront ( ) assert ( ! IsEmpty ( ) );/判斷隊(duì)列是否不空，空則出錯(cuò)處理return Q(front + 1) % m;/返回隊(duì)頭元素的值(8）如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。要求： 寫出循環(huán)隊(duì)列的類型定義； 寫出“從隊(duì)尾刪除”和“從隊(duì)頭插入”的算法。題目分析 用一維數(shù)組 v0.M-1實(shí)現(xiàn)

37、循環(huán)隊(duì)列，其中M是隊(duì)列長度。設(shè)隊(duì)頭指針 front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空，(rear+1)%m=front 為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。（1）#define M 隊(duì)列可能達(dá)到的最大長度typedef struct elemtp dataM; int front,rear; cycqueue;（2）elemtp delqueue ( cycqueue Q) /Q是如上定義的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)從隊(duì)尾刪除，若刪除成功，返回被刪除元素，否則給出出錯(cuò)信息。 if (Q.

38、front=Q.rear) printf(“隊(duì)列空”); exit(0); Q.rear=(Q.rear-1+M)%M; /修改隊(duì)尾指針。 return(Q.data(Q.rear+1+M)%M); /返回出隊(duì)元素。/從隊(duì)尾刪除算法結(jié)束void enqueue (cycqueue Q, elemtp x)/ Q是順序存儲的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)“從隊(duì)頭插入”元素x。if (Q.rear=(Q.front-1+M)%M) printf(“隊(duì)滿”; exit(0);) Q.dataQ.front=x; /x 入隊(duì)列Q.front=(Q.front-1+M)%M; /修改隊(duì)頭指針。/ 結(jié)束從隊(duì)頭插入算

39、法。（9）已知Ackermann函數(shù)定義如下: 寫出計(jì)算Ack(m,n)的遞歸算法，并根據(jù)此算法給出出Ack(2,1)的計(jì)算過程。 寫出計(jì)算Ack(m,n)的非遞歸算法。int Ack(int m,n) if (m=0) return(n+1); else if(m!=0&n=0) return(Ack(m-1,1); else return(Ack(m-1,Ack(m,m-1); /算法結(jié)束（1）Ack(2,1)的計(jì)算過程 Ack(2,1)=Ack(1,Ack(2,0) /因m0,n0而得 =Ack(1,Ack(1,1) /因m0,n=0而得 =Ack(1,Ack(0,Ack(1,0) / 因m0,n0而得 = Ack(1,Ack(0,Ack(0,1) / 因m0,n=0而得 =Ack(1,Ack(0,2) /