數(shù)據(jù)結(jié)構(gòu)(C語言版)第2版習(xí)題答案解析-嚴(yán)蔚敏(2)

1、數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）課后習(xí)題答案李冬梅2015.341第1章緒論 .第2章線性表.第3章棧和隊(duì)列 .第4章串、數(shù)組和廣義表 .第5章樹和二叉樹 .第6章圖 .第7章查找第8章排序第1章緒論1 簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié) 構(gòu)、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的 總稱。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、 圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個整體進(jìn)行考慮和處理。在有些 情況下，數(shù)據(jù)元

2、素也稱為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個 學(xué)生記錄，樹中棋盤的一個格局（狀態(tài)）、圖中的一個頂點(diǎn)等。數(shù)據(jù)項(xiàng)：是組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。例如，學(xué)生基本信 息表中的學(xué)號、姓名、性別等都是數(shù)據(jù)項(xiàng)。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是 集合N=0, 士 1， 2,，字母字符數(shù)據(jù)對象是集合C= A, B,，Z, a,b ， z ，學(xué)生基本信息表也可是一個數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié) 構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)

3、構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此， 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。存儲結(jié)構(gòu)： 數(shù)據(jù)對象在計(jì)算機(jī)中的存儲表示，也稱為物理結(jié)構(gòu)。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學(xué)模型，以及定義在這個模型上的一 組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的基本操 作的集合。2 試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號、姓名、性別、籍貫、專業(yè)等。每個學(xué)生 基本信息記錄對應(yīng)一個數(shù)據(jù)元素，學(xué)生記錄按順序號排列，形成了學(xué)生基本信息記錄的線性 序列

4、。對于整個表來說，只有一個開始結(jié)點(diǎn)（它的前面無記錄 ）和一個終端結(jié)點(diǎn) （它的后面無記錄），其他的結(jié)點(diǎn)則各有一個也只有一個直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學(xué)生記錄在計(jì)算機(jī)中的存儲表示就是存儲結(jié)構(gòu)。如果用連續(xù)的存儲單元（如用數(shù)組表示）來存放這些記錄，則稱為順序存儲結(jié)構(gòu)；如果存儲單元不連續(xù)，而是隨機(jī)存放各個記錄， 然后用指針進(jìn)行鏈接，則稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對應(yīng)不同的存儲結(jié)構(gòu)。3 簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫岀它們的關(guān)系圖。答案：(1 )集合結(jié)構(gòu)數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無其他關(guān)系。例如，確定一名學(xué)生是 否為班

5、級成員，只需將班級看做一個集合結(jié)構(gòu)。(2)線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報(bào)到的時(shí)間先后順 序進(jìn)行排列，將組成一個線性結(jié)構(gòu)。(3)樹結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。例如，在班級的管理體系中，班長管理多個組長，每 位組長管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。(4)圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可 以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。4 存儲結(jié)構(gòu)由哪兩種基本基存邏輯結(jié)實(shí)現(xiàn)系圖答案：(1)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，

6、通常 借助程序設(shè)計(jì)語言的數(shù)組類型來描述。(2)鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈?zhǔn)酱鎯Y(jié)構(gòu)，無 需占用一整塊存儲空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個結(jié)點(diǎn)附加指針字段，用于 存放后繼元素的存儲地址。所以鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計(jì)語言的指針類型來描述。5 選擇題(1)在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()。A.動態(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)答案：C(2)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的()A.存儲結(jié)構(gòu)B存儲實(shí)現(xiàn)C.邏輯結(jié)構(gòu)D運(yùn)算實(shí)現(xiàn)答案：C(3)通常要求同一邏輯結(jié)

7、構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著()A 數(shù)據(jù)具有同一特點(diǎn)B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C. 每個數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相等答案：B(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)答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu) 的各數(shù)據(jù)元素的集合。(5)算法的時(shí)間復(fù)雜度取決于()。A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.計(jì)算機(jī)的配置D. A和B答案：D解釋：算

8、法的時(shí)間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些 排序的算法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會對算法有最好、最壞 以及平均時(shí)間復(fù)雜度的評價(jià)。(6) 以下數(shù)據(jù)結(jié)構(gòu)中，()是非線性數(shù)據(jù)結(jié)構(gòu)A.樹 B字符串C 隊(duì)列 D棧答案：A6 試分析下面各程序段的時(shí)間復(fù)雜度。(1)x=90; y=100;?while(y0)if(x100)x=x-10;y-; else x+;答案：0(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。(2)for (i=0; in; i+)for (j=0; jm; j+) aij=0;答案：O(m* n)解釋：語句 aij=0;的執(zhí)行次數(shù)為m*n。(3)

9、s=0;for i=0; in; i+) for(j=0; jn; j+)s+=Bijsum=s;2答案：O(n )解釋：語句 y+;的執(zhí)行次數(shù)為？：.n :。+ 1= n(n-1)/22解釋：語句 s+=Bij;的執(zhí)行次數(shù)為n。(4)i=1；while(i=n)i=i*3;答案：O(log an)解釋：語句 i=i*3;的執(zhí)行次數(shù)為？ log an :。(5)x=0;for(i=1; i1y=0;while(x (y+1)* (y+1)y +;答案：0( .n )1 選擇題(1)順序表中第一個元素的存儲地址是地址是()OA. 110B答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲，所以第在n個結(jié)點(diǎn)的順

10、序表中，算法的時(shí)間復(fù)雜度是訪問第i個結(jié)點(diǎn)(1 i n)和求第在第i個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)(刪除第將.108 Cloo，每個元素的長度為2，則第5個元素的.100 D(2)A.B.C.D.答案：解釋：或 O(nlog 2n)i個結(jié)點(diǎn)(1 i n) n個結(jié)點(diǎn)從小到大排序A5個元素的地址為：0(1)的操作是(i個結(jié)點(diǎn)的直接前驅(qū)(1 i n)100+2*4=108 。在順序表中插入一個結(jié)點(diǎn)的時(shí)間復(fù)雜度都是。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問第0(n2)，排序的時(shí)間復(fù)雜度為0(n2)i個結(jié)點(diǎn)和求第 i個結(jié)點(diǎn)的直接前驅(qū)都0(1)?？梢灾苯油ㄟ^數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是127個元素的順序表中插入一個新元素

11、并保持原來順序不變，平均要移)O(3) 向一個有 動的元素個數(shù)為(B部分地址必須是連續(xù)的D連續(xù)或不連續(xù)都可以)情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A.需經(jīng)常修改L中的結(jié)點(diǎn)值E.需不斷對L進(jìn)行刪除插入C.L中含有大量的結(jié)點(diǎn)D.L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案：B第2章線性表A. 8 B.63.5C. 63 D. 7答案：B解釋：平均要移動的兀素個數(shù)為：n/2 O(4)鏈接存儲的存儲結(jié)構(gòu)所占存儲空間()OA 分兩部分，部分存放結(jié)點(diǎn)值，另一-部分存放表示結(jié)點(diǎn)間關(guān)系的指針B 只有一部分,存放結(jié)點(diǎn)值C.只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針D.分兩部分，部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單兀數(shù)答案：A(5)線性表若采用鏈

12、式存儲結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址(A.必須是連續(xù)的C. 一定是不連續(xù)的答案：D(6)線性表1在(解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要移動數(shù)據(jù)，直接修改指針即可。(7)單鏈表的存儲密度()。A. 大于1 B 等于1 C 小于1 D 不能確定答案：C解釋：存儲密度是指一個結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲空間和整個結(jié)點(diǎn)所占的存儲空 間之比，假設(shè)單鏈表一個結(jié)點(diǎn)本身所占的空間為D,指針域所占的空間為N,則存儲密度為：D/(D+N)，定小于 1。(8) 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是()。A.nB 2n-1 C . 2n D . n-1答案：A解釋：當(dāng)?shù)谝粋€有序表中所

13、有的元素都小于(或大于)第二個表中的元素，只需 要用第二個表中的第一個元素依次與第一個表的元素比較，總計(jì)比較n次。(9)在一個長度為n的順序表中，在第i個元素(1 i next=p+1; p-next=s;B.(*p). next=s; (*s).next=(*p).next;C.s-next=p-next; p-next=s-next;D.s-next=p-next; p-next=s;答案：D(14)在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針()。A.p-next-prior=p-prior; p-prior-next=p-next;B.p-next=p-next-next; p-

14、next-prior=p;C.p-prior-next=p; p_prior=p_prior-prior;D.p-prior=p-next-next; p-next=p-prior-prior;答案：A(15)在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是()。A.p_next=q; q-prior=p; p_next-prior=q; q_next=q;B.p_next=q; p_next-prior=q; q-prior=p; q_next=p-next;C.q-prior=p; q_next=p-next; p_next-prior=q; p_next=q

15、;D.q-prior=p; q_next=p-next; p_next=q; p_next-prior=q;答案：C2 算法設(shè)計(jì)題(1)將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。題目分析合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表 La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn)，從第一個結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。當(dāng)一個

16、表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素直接鏈接在Lc表的最后。算法描述void MergeList(Li nkList & La,L in kList & Lb,Li nkList & Lc)合并鏈表La和Lb，合并后的新表使用頭指針Lc指向pa=La-n ext; pb=Lb-n ext;/pa 和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn)Lc=pc=La; / 用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(pa & pb)if(pa-datadata)pc- n ext=pa;pc=pa;pa=pa-n ext;/取較小者La中的元素，將 pa鏈接在pc的后面，pa指

17、針后移else if(pa-datapb-data) pc- n ext=pb; pc=pb; pb=pb-n ext;/取較小者Lb中的元素，將 pb鏈接在pc的后面，pb指針后移else / 相等時(shí)取 La中的元素，刪除 Lb中的元素pc-n ext=pa;pc=pa;pa=pa-n ext;q=pb-n ext;delete pb ;pb =q;pc-n ext=papa:pb; /插入剩余段delete Lb; /釋放Lb的頭結(jié)點(diǎn)(2)將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。題目分析合并

18、后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn)，從第一個結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的表頭結(jié)點(diǎn)之后，如果兩個表中的元素相等，只摘取La表中的元素，保留 Lb表中的元素。當(dāng)一個表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩 余元素依次摘取，鏈接在 Lc表的表頭結(jié)點(diǎn)之后。算法描述void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc,)/合并鏈表La和Lb，合并后的新表使用頭指針Lc指向pa=La-n ext; pb=Lb-n ext;/

19、pa和pb分別是鏈表 La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn)Lc=pc=La; / 用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)Lc- next=NULL;while(pa|pb )/只要存在一個非空表，用q指向待摘取的元素if(!pa) q=pb; pb=pb-n ext;/La表為空，用 q指向pb， pb指針后移else if(!pb) q=pa; pa=pa-n ext;/Lb表為空，用 q指向pa， pa指針后移else if(pa-datadata) q=pa; pa=pa-n ext;/取較小者(包括相等)La中的元素，用 q指向pa， pa指針后移else q=pb; pb=pb

20、-n ext;/取較小者 Lb中的元素，用 q指向pb， pb指針后移q-n ext = Lc- n ext; Lc- n ext = q;/將q指向的結(jié)點(diǎn)插在 Lc表的表頭結(jié)點(diǎn)之后delete Lb;/釋放Lb的頭結(jié)點(diǎn)(3)已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于A鏈表中。題目分析只有同時(shí)岀現(xiàn)在兩集合中的元素才岀現(xiàn)在結(jié)果表中，合并后的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn)，從第一個結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個表中相等的元素時(shí)，摘取La表中的元素，刪除

21、Lb表中的元素；如果其中一個表中的元素較小時(shí)，刪除此表中較小的 元素，此表的工作指針后移。當(dāng)鏈表La和Lb有一個到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，依次刪除另一個非空表中的所有元素。算法描述void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) pa=La-n ext;pb=Lb-n ext;pa和pb分別是鏈表 La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn)Lc=pc=La; / 用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(pa&pb) if(pa-data=pb- data) /交集并入結(jié)果表中。pc- n ext=pa;pc=pa;pa=pa-n ext

22、;u=pb;pb=pb-n ext;Delete u;else if(pa-data data)u=pa; pa=pa-n ext; delete u;elseu=pb; pb=pb-n ext; delete u;while(pa) u=pa; pa=pa-next; deleteu; / 釋放結(jié)點(diǎn)空間while(pb) u=pb; pb=pb-next; deleteu; /釋放結(jié)點(diǎn)空間pc- next=null; /置鏈表尾標(biāo)記。delete Lb; / 釋放Lb的頭結(jié)點(diǎn)A和B分別表示兩個集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出兩個集 合A和B的差集(即僅由在A中岀現(xiàn)而不在B中岀現(xiàn)的元素所構(gòu)

23、成的集合)，并以同樣的形式存儲，同時(shí)返回該集合的元素個數(shù)。題目分析求兩個集合 A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)點(diǎn)，所以要保存待刪除結(jié)點(diǎn)的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點(diǎn)。pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn)，從第一個結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果La表中的元素小于 Lb表中的元素， pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時(shí)，刪除此表中較小的元素， 此表的工作指針后移。當(dāng)鏈表La和Lb有一個為空時(shí)，依次刪除另一個非空表中的所有元素。算法描述void Diffe

24、renee( LinkList& La, LinkList& Lb,int *n /差集的結(jié)果存儲于單鏈表pa=La-n ext; pb=Lb-n ext;II pa和pb分別是鏈表pre=La;IIwhile (pa&pb)if ( pa-datadata(4)已知兩個鏈表Lapre)La中，*n是結(jié)果集合中元素個數(shù)，調(diào)用時(shí)為和Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點(diǎn) 為La中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針pre=pa;pa=pa-n ext;* n+;II A鏈表中當(dāng)前結(jié)點(diǎn)指針后移else if ( pa-dataq-dataelse pre-n ext=pa-n ext;u=pa; p

25、a=pa-n ext; delete u;(5)設(shè)計(jì)算法將一個帶頭結(jié)點(diǎn)的單鏈表 表的結(jié)點(diǎn)為 A表中值小于零的結(jié)點(diǎn)，而q=q-next;II B鏈表中當(dāng)前結(jié)點(diǎn)指針后移/處理 A, B中元素值相同的結(jié)點(diǎn)，應(yīng)刪除/刪除結(jié)點(diǎn)A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C,其中BC表的結(jié)點(diǎn)為 A表中值大于零的結(jié)點(diǎn)(鏈表 A中的元素為非零整數(shù)，要求B、C表利用A表的結(jié)點(diǎn))。題目分析B表的頭結(jié)點(diǎn)使用原來A表的頭結(jié)點(diǎn)，為 C表新申請一個頭結(jié)點(diǎn)。從A表的第一個結(jié)點(diǎn)開始，依次取其每個結(jié)點(diǎn)p，判斷結(jié)點(diǎn) p的值是否小于 0,利用前插法，將小于 0的結(jié)點(diǎn)插入B表，大于等于 0的結(jié)點(diǎn)插入 C表。算法描述void DisCompos

26、e(L in kedList A) B=A;B- next= NULL;C=new LNode; / 為C- next=NULL;p=A _n ext;II B表初始化C申請結(jié)點(diǎn)空間II C初始化為空表II p為工作指針存儲空間。題目分析 從首元結(jié)點(diǎn)開始，逐個地把鏈表算法描述void in verse(L in kList &L)/逆置帶頭結(jié)點(diǎn)的單鏈表Lp=L-next; L-next=NULL;while ( p) q=p-n ext; / qp-n ext=L-n ext;L-n ext=p;/ *pL的當(dāng)前結(jié)點(diǎn) p插入新的鏈表頭部。指向*p的后繼插入在頭結(jié)點(diǎn)之后while(p!= NUL

27、L) r=p-next;/暫存 p的后繼if(p-datanext=B-next; B-next=p; /將小于 0的結(jié)點(diǎn)鏈入 B表，前插法elsep-next=C-next;C-next=p; /將大于等于0的結(jié)點(diǎn)鏈入 C表，前插法p=r; lip指向新的待處理結(jié)點(diǎn)。(6) 設(shè)計(jì)一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。題目分析假定第一個結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個元素比較，若其小于下一個元素，則 設(shè)其下一個元素為最大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。算法描述ElemType Max (Li nkList L )if(L-next=NULL) return NULL;pmax

28、=L- next; /假定第一個結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L-n ext-n ext;while(p != NULL )/如果下一個結(jié)點(diǎn)存在if(p-data pmax-data) pmax=p;/如果 p的值大于pmax的值，則重新賦值p=p- next;/遍歷鏈表retur n pmax-data;(7) 設(shè)計(jì)一個算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的p = q;(8)設(shè)計(jì)一個算法，刪除遞增有序鏈表中值大于mink且小于 maxk的所有元素(mink和maxk是給定的兩個參數(shù)，其值可以和表中的元素相同，也可以不同)。題目分析分別查找第一個值mink的結(jié)點(diǎn)和第一個值

29、maxk的結(jié)點(diǎn)，再修改指針，刪除值大于mink且小于 maxk的所有元素。算法描述void delete(L in kList &L, int mink, int maxk) p=L-n ext; II首元結(jié)點(diǎn)while (p & p-datanext; /查找第一個值mink 的結(jié)點(diǎn)if (p)while (p & p-datan ext;/查找第一個值q=pre _n ext; pre_n ext=p; / while (q!=p) s=q-n ext; delete q; q=s; /if(9)已知p指向雙向循環(huán)鏈表中的一個結(jié)點(diǎn)， maxk的結(jié)點(diǎn)修改指針釋放結(jié)點(diǎn)空間其結(jié)點(diǎn)結(jié)構(gòu)為寫岀算法c

30、hange(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。題目分析知道雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，與前驅(qū)交換涉及到四個結(jié)點(diǎn)( 驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn))六條鏈。算法描述void Exchange ( LinkedList p )II p是雙向循環(huán)鏈表中的一個結(jié)點(diǎn)，本算法將q=p-lli nk；q-lli nk-rl in k=p p-lli nk=q-lli nk q-rl in k=p-rli nk q-lli nk=p ； p-rl in k-lli nk=q p-rli nk=q ； / 算法 exchange (10)已知長度為IIIIIIIIIIII結(jié)束。n的線性表data、prior、

31、n ext三個域,p結(jié)點(diǎn),前驅(qū)結(jié)點(diǎn)，前p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。的前驅(qū)的前驅(qū)之后繼為p的前驅(qū)指向其前驅(qū)的前驅(qū)。的前驅(qū)的后繼為p的后繼。pp與其前驅(qū)交換p的后繼的前驅(qū)指向原 p的前驅(qū)p的后繼指向其原來的前驅(qū)A采用順序存儲結(jié)構(gòu)，請寫一時(shí)間復(fù)雜度為 雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分析0(n)、空間復(fù)void Delete ( ElemType A ， int n )II A是有n個元素的一維數(shù)組，本算法刪除i=1 ; j=n ；/設(shè)置數(shù)組低、高端指針(下標(biāo)) while (ij )while ( ij & Ai!=item) i+ ；if (ij ) wh

32、ile ( ij & Aj=itemif (idata;top=top-linkC. x=top;top=top-link；答案：AMAXSIZE (本題為 n),然后與 MAXSIZE (本題為 n)求,top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的B . top=top-link;x=top-linkD . x=top-link ；第3章棧和隊(duì)列i 選擇題(1)若讓元素 1 , 2 , 3 , 4, 5依次進(jìn)棧，則岀棧次序不可能岀現(xiàn)在()種情況。A.5, 4, 3, 2, 1 B 2, 1 , 5, 4, 3 C. 4, 3, 1, 2, 5 D . 2, 3, 5, 4, 1 答案：C

33、解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素 1比元素2先出棧，違背了棧的后進(jìn)先岀原則，所以不可能岀現(xiàn)(2)若已知一個棧的入棧序列是C選項(xiàng)所示的情況。1, 2 , 3， n,其輸岀序列為p1 , p2, p3，pn ,若 p1=n , Wpi 為()。A. iB.n-iC.n-i+1D不確定答案:C解釋:棧是后進(jìn)先出的線性表，一個棧的入棧序列是1 , 2, 3，,n,而輸岀序列的第一個元素為n,說明 1, 2, 3,-, n 次性全部進(jìn)棧，再進(jìn)行輸出，所以p1= n , p2=n-1 ,，pi=n-i+1(3)數(shù)組Q：n用來表示一個循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置

34、，假定隊(duì)列中元素的個數(shù)小于n,計(jì)算隊(duì)列中元素個數(shù)的公式為()。A. r-fB. (n+f-r)%nC. n+r-f D. ( n+r-f)%n答案：D解釋：對于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長度，而對于循環(huán)隊(duì)列,解釋：x=top-data將結(jié)點(diǎn)的值保存到x中，top=top-link 棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。(5) 設(shè)有一個遞歸算法如下? ? int fact(i nt n) ? /n大于等于 0? ? if(n =0) return 1;? ? else return n *fact( n-1);? ? 則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為()。？A. ?

35、n+1? ? B . ?n-1?C. n?D.n+2答案：A解釋：初始棧頂指針 存儲在向量空間V仁ntop為n+1，說明元素從數(shù)組向量的高端地址進(jìn)棧，又因?yàn)樵?中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚,之后將元素x存儲在Vn 解釋：特殊值法。設(shè)n=0,易知僅調(diào)用一次fact( n) 函數(shù)，故選 A。(6)棧在?()中有所應(yīng)用。A.遞歸調(diào)用B函數(shù)調(diào)用C表達(dá)式求值D前三個選項(xiàng)都有答案：D解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。(7)為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸岀的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取岀數(shù)據(jù)。該緩沖區(qū)

36、的邏 輯結(jié)構(gòu)應(yīng)該是()。A.隊(duì)列B 棧C. 線性表D有序表答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線 性表。(8)設(shè)棧 S和隊(duì)列 Q的初始狀態(tài)為空，元素 el、e2、e3、e4、e5和e6依次進(jìn)入棧 S， 一個元素岀棧后即進(jìn)入Q，若6個元素岀隊(duì)的序列是e2、e4、e3、e6、e5和el，則棧S的容量至少應(yīng)該是()A. 2B. 3C 4D 6答案：B解釋：元素岀隊(duì)的序列是e2、e4、e3、e6、e5和el，可知元素入隊(duì)的序列是e2、e4、e3、e6、e5和el，即元素岀棧的序列也是e2、e4、e3、e6、e5和el，而元素 el、e2、e3、e4、e5和e

37、6依次進(jìn)入棧，易知棧 S中最多同時(shí)存在 3個元素，故棧 S的容量至少為 3。存儲，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確B.Vtop=x; top+;D. Vtop=x; top-;(10)設(shè)計(jì)一個判別表達(dá)式中左，右括號是否配對岀現(xiàn)的算法，采用( 佳。A.線性表的順序存儲結(jié)構(gòu)B隊(duì)列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧答案：D解釋：利用棧的后進(jìn)先岀原則。(11 )用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)()。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改答案：D(9)若一個棧以向量V仁n操作是()A.top+; Vtop=x;C. top-; Vtop=x;答

38、案：C)數(shù)據(jù)結(jié)構(gòu)最針也丟失了，因此需對隊(duì)尾指針重新賦值。（12）循環(huán)隊(duì)列存儲在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（A. rear=rear+1C. rear=（rea 葉1）%m 答案：D 解釋：數(shù)組 AO.m（13）最大容量為B. rear=(rea r+1)%(m-1)D. rear=(rea r+1)%(m+1)中共含有 m+1個元素，故在求模運(yùn)算時(shí)應(yīng)除以 n的循環(huán)隊(duì)列，隊(duì)尾指針是 rear ，隊(duì)頭是frontm+1。，則隊(duì)空的條件是（）。A. (rea r+1)% n=frontC. rear+1=front 答案：B解釋：最大容量為rear=fro nt。B. rear=fro ntD

39、. (rear-l)% n=frontn的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n=front，隊(duì)空條件是（14）棧和隊(duì)列的共同點(diǎn)是（）。A.都是先進(jìn)先岀B.C.只允許在端點(diǎn)處插入和刪除元素D.答案：C都是先進(jìn)后出沒有共同點(diǎn)解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭 刪除元素。（15） 一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分答案：B2 算法設(shè)計(jì)題（1）將編號為 0和1的兩個棧存放于一個數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top0等于-1時(shí)該棧為空，當(dāng)?shù)?號棧的棧頂指針top1等于m時(shí)

40、該棧為空。兩個棧均從兩端向中間增長。試編寫雙棧初始化，判斷?？?、棧滿、進(jìn)棧和出棧 等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedef structi nt top2,bot2; SEIemType *V; int m;/棧頂和棧底指針/棧數(shù)組/棧最大可容納元素個數(shù)DbIStack題目分析兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時(shí)，左棧頂指針為 兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。算法描述-1，右棧頂為mo（1）?棧初始化解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個元素時(shí)，隊(duì)尾指int?ln it()?S.top0=-1;?S.top1=m

41、;?return?1;?初始化成功(2) ?入棧操作：in t?push(stk S?,i nt?i,i nt?x)II i為棧號，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回 1，失敗返回0if(i1) cout棧號輸入不對”e ndl;exit(0);if(S.top1-S.top0=1) cout棧已滿” e ndl;retur n(0);switch(i)?case?0: S.V+S.top0=x;?return(1);?break;case?1: S.V-S.top1=x;?retur n(1); II push(3) ?退棧操作ElemType pop(stk S,i

42、nt?i)/退棧。i代表?xiàng)Ｌ枺琲=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功時(shí)返回退棧元素/否則返回-1if(i1)cout“棧號輸入錯誤”endl ； exit(0);?switch(i)case?0:?if(S.top0=-1) cout?？铡?endl ； return ( -1 ) ； else?retur n(S.VS.top0-);case?1:?if(S.top1=m cout棧空”e ndl;?return(-1);else?retur n(S.VS.top1+);? / switch? /算法結(jié)束(4) ?判斷?？読n t?Empty();return?(S.top0=-1 & S

43、.top1=m);算法討論?請注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。左棧是通常意義下的棧，而右棧入棧操作時(shí)，其棧頂指針左移(減1)，退棧時(shí)，棧頂指針右移(加1)。(2)回文是指正讀反讀均相同的字符序列，如abba 和abdba 均是回文，但good不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)?題目分析將字符串前一半入棧，然后，棧中元素和字符串后一半進(jìn)行比較。即將第一個出棧元素 和后一半串中第一個字符比較，若相等，則再出棧一個元素與后一個字符比較，直至 棧空，結(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時(shí)，結(jié)論字符序列不是回文。算法描述#define

44、StackSize 100 /假定預(yù)分配的棧空間最多為100個元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwe n( char *t)/判斷t字符向量是否為回文，若是，返回1,否則返回0SeqStack s;int i , le n;char temp;In itStack( &s);le n=strle n(t); /求向量長度for ( i=0; ile n/2; i+)將一半字符入棧Push( &s, ti);while( !Emp

45、tyStack( &s)/每彈出一個字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si)? return 0 ;/不等則返回0else i+;?return 1 ; /比較完畢均相等則返回1(3)設(shè)從鍵盤輸入一整數(shù)的序列：a1, a 2, a 3，an，試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai工-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況(入棧滿等)給岀相應(yīng)的信息。算法描述#defi ne maxsize ?？臻g容量void In OutS(i nt smaxsize)/s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。int top=0;/t

46、op為棧頂指針，定義top=0時(shí)為棧空。for(i=1; i x); /從鍵盤讀入整數(shù)序列。if(x!=-1)/讀入的整數(shù)不等于-1時(shí)入棧。if(top=maxsize-1)cout棧滿” endl;exit(O);else s+top=x; x入棧。else /讀入的整數(shù)等于-1時(shí)退棧。if(top=0) cout?？铡?e ndl;exit(O);else cout岀棧元素是” stop- x;/x是字符型變量。while(x!= $)switchcase O v=x= O &xx;else /處理小數(shù)部分。scale=10.0; cin x; while(x= O &x x; /else

47、 push(OPND ,n um); n um=O.O;/數(shù)壓入棧，下個數(shù)初始化case x= :break; /遇空格，繼續(xù)讀下一個字符。case x= + :push(OPND,pop(OPND)+pop(OPND);break;稱可以操作的序列為合法序列,否則稱為非法序列若合法，返回true ，/判斷字符數(shù)組 A中的輸入輸岀序列是否是合法序列。如是，返回true，否則返回falsei=0;/ij=k=0;/j為下標(biāo)。和k分別為I和字母O的的個數(shù)while(Ai!=0 ) /當(dāng)未到字符數(shù)組尾就作。case x= - :x1=pop(OPND);x2=pop(OPND);push(OPND,

48、x2-x1);break;case x= *:push(OPND,pop(OPND)*pop(OPND);break;case x=/ :x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;default:/其它符號不作處理。/ 結(jié)束 switchcin x;讀入表達(dá)式中下一個字符。/ 結(jié)束 while (x! = $)coutvv “后綴表達(dá)式的值為”vvpop(OPND);/算法結(jié)束。算法討論假設(shè)輸入的后綴表達(dá)式是正確的，未作錯誤檢查。算法中拼數(shù)部分是核心。若遇到大于等于0 且小于等于9 的字符，認(rèn)為是數(shù)。這種字符的序號減去字符0 的序號得岀數(shù)

49、。對于整數(shù)，每讀入一個數(shù)字字符，前面得到的部分?jǐn)?shù)要乘上10再加新讀入的數(shù)得到新的部分?jǐn)?shù)。當(dāng)讀到小數(shù)點(diǎn)，認(rèn)為數(shù)的整數(shù)部分已完，要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10 (或10的幕數(shù))變成十分位，百分位，千分位數(shù)等等，與前面部分?jǐn)?shù)相加。在拼數(shù)過程中，若遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復(fù)為0，準(zhǔn)備下一個數(shù)。這時(shí)對新讀入的字符進(jìn)入+ 、 - 、 * 、/ 及空格的判斷，因此在結(jié)束處理數(shù)字字符的case后，不能加入break語句。(5) 假設(shè)以I和O分別表示入棧和岀棧操作。棧的初態(tài)和終態(tài)均為空，入棧和岀棧的操作序列可表示為僅由 I和O組成的序列,下面所示的序列中哪些是合法

50、的？A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO通過對的分析，寫岀一個算法，判定所給的操作序列是否合法。 否則返回false(假定被判定的操作序列已存入一維數(shù)組中)答案： A和D是合法序列， B和C是非法序列。 設(shè)被判定的操作序列已存入一維數(shù)組A中。int Judge(char A)switch(Ai)caseI : j+; break; /入棧次數(shù)增1。case O : k+; if(kj)cout 序列非法” ednl ； exit(0);i+; / 不論Ai是I 或O，指針i均后移。if(j!=k) cout“序列非法” endl ； r

51、eturn(false);，否則視為非法序列。并且只設(shè)一個指針指向隊(duì)尾元素站點(diǎn)、入隊(duì)和岀隊(duì)等算法。（注意不else cout序歹列合法” rear = Q-rear- next;/將隊(duì)尾指針指向頭結(jié)點(diǎn)while (Q-rear!=Q-rear- next)/當(dāng)隊(duì)列非空，將隊(duì)中元素逐個岀隊(duì)s=Q-rear- n ext;Q-rear- n ext=s-n ext;delete s;/回收結(jié)點(diǎn)空間判隊(duì)空？int EmptyQueue( Lin kQueue *Q) /判隊(duì)空。當(dāng)頭結(jié)點(diǎn)的next指針指向自己時(shí)為空隊(duì)retur n Q-rear- n ext- n ext=Q-rear- n ext;

52、(3) 入隊(duì)void En Queue( Lin kQueue *Q, Datatype x) /入隊(duì)。也就是在尾結(jié)點(diǎn)處插入元素QueueNode *p=new QueueNode;/ 申請新結(jié)點(diǎn)p-data=x; p-n ext=Q-rear- n ext;/初始化新結(jié)點(diǎn)并鏈入Q-rear- n ext=p;?Q-rear=p;/將尾指針移至新結(jié)點(diǎn)(4) 岀隊(duì)Datatype DeQueue( Lin kQueue *Q)/出隊(duì)，把頭結(jié)點(diǎn)之后的元素摘下Datatype t;QueueNode *p;if(EmptyQueue( Q )Error(Queue un derflow);p=Q-r

53、ear- next-next; /p指向?qū)⒁碌慕Y(jié)點(diǎn)x=p-data; /保存結(jié)點(diǎn)中數(shù)據(jù)if (p=Q-rear)/當(dāng)隊(duì)列中只有一個結(jié)點(diǎn)時(shí)，p結(jié)點(diǎn)岀隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn)Q-rear = Q-rear- n ext;Q-rear- n ext=p-n ext;else?Q-rear- n ext- n ext=p-n ext;/摘下結(jié)點(diǎn) pdelete p;/ 釋放被刪結(jié)點(diǎn)return x;(7)假設(shè)以數(shù)組Qn存放循環(huán)隊(duì)列中的元素，同時(shí)設(shè)置一個標(biāo)志tag，以tag = 0和tag =1來區(qū)別在隊(duì)頭指針(front )和隊(duì)尾指針(rear )相等時(shí)，隊(duì)列狀態(tài)為空還是滿”。試編寫與此結(jié)構(gòu)相

54、應(yīng)的插入(enqueue)和刪除(dlqueue )算法。算法描述(1) 初始化SeQueue Queuel nit(SeQueue Q)/初始化隊(duì)列Q.fro nt=Q.rear=0; Q.tag=0;return?Q;(2) 入隊(duì)SeQueue Queue ln( SeQueue Q,i nt e)入隊(duì)列if(Q.tag=1) & (Q.rear=Q.front) cout隊(duì)列已滿 endl;else?Q.rear=(Q.rea r+1) % m;Q.dataQ.rear=e;if(Q.tag=0) Q.tag=1; /隊(duì)列已不空return?Q;(3)岀隊(duì)ElemType QueueOu

55、t(SeQueue Q)/岀隊(duì)列if(Q.tag=0) cout隊(duì)列為空endl; exit(O);elseQ.front=(Q.front+1) % m;e=Q.dataQ.fro nt;if(Q.fro nt=Q.rear) Q.tag=0;?空隊(duì)列return(e);(8 )如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。要求：寫岀循環(huán)隊(duì)列的類型定義；寫岀“從隊(duì)尾刪除”和“從隊(duì)頭插入”的算法。題目分析用一維數(shù)組v0.M-1 實(shí)現(xiàn)循環(huán)隊(duì)列，其中 M是隊(duì)列長度。設(shè)隊(duì)頭指針front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義fron t=rear 時(shí)

56、為隊(duì)空，(rear+1)%m=fro nt為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。算法描述#define M隊(duì)列可能達(dá)到的最大長度typedef structelemtp dataM;int fron t,rear;cycqueue;elemtp delqueue ( cycqueue Q)Q是如上定義的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)從隊(duì)尾刪除，若刪除成功，返回被刪除元素,隊(duì)列空endl; exit(O);修改隊(duì)尾指針。返回出隊(duì)元素。因m0,n0而得因m0,n=0而得因m0,n0而得因 m0,n=0而得因m=0而得因m=0而得因m0,n0而得因m0,n0而得因m0,n0而

57、得因m0,n=0而得因m=0而得因m=0而得因n=0而得因n=0而得否則給出出錯信息if (Q.fro nt=Q.rear) coutQ.rear=(Q.rear-1+M)%M; /return(Q.data(Q.rea r+1+M)%M); /從隊(duì)尾刪除算法結(jié)束void en queue (cycqueue Q, elemtp x)/ Q 是順序存儲的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)“從隊(duì)頭插入”元素xif (Q.rear=(Q.front-1+M)%M) cout隊(duì)滿endl; exit(O);)Q.dataQ.fro nt=x; /x入隊(duì)列Q.fro nt=(Q.fro nt-1+M)%M; /修改

58、隊(duì)頭指針。/結(jié)束從隊(duì)頭插入算法。(9)已知 Ackermann函數(shù)定義如下：寫岀計(jì)算 Ack(m,n)的遞歸算法，并根據(jù)此算法給岀岀Ack(2,1)的計(jì)算過程。 寫岀計(jì)算Ack(m,n)的非遞歸算法。算法描述int Ack(i nt m,n)if (m=0) retur n(n+1);else if(m!=0&n=0) return(Ack(m-1,1);else return(Ack(m-1,Ack(m,m-1);/ 算法結(jié)束Ack(2,1)的計(jì)算過程Ack(2,1)= Ack(1,Ack(2,0)/=Ack(1,Ack(1,1)/=Ack(1,Ack(0,Ack(1,0)/=Ack(1,A

59、ck(0,Ack(0,1)/=Ack(1,Ack(0,2)/=Ack(1,3)/=Ack(0,Ack(1,2)/=Ack(0,Ack(0,Ack(1,1)/=Ack(0,Ack(0,Ack(0,Ack(1,0) /=Ack(0,Ack(0,Ack(0,Ack(0,1) /=Ack(0,Ack(0,Ack(0,2)/=Ack(0,Ack(0,3)/=Ack(0,4)/=5/int Ackerma n(i nt m, int n)int akmMN;int i,j;for(j=0;jN;j+) akm0j=j+1;for(i=1;im;i+)akmi0=akmi-11;for(j=1;jn ext

60、)return p-data;elseint max=GetMax(p-n ext);retur n p-data=max p-data:max;int GetLength(LinkList p)if(!p-n ext)return 1;elseretur n GetLe ngth(p-n ext)+1;double GetAverage(L in kList p , int n)if(!p-n ext)return p-data;else double ave=GetAverage(p-n ext ,n-1); return (ave*( n-1)+p-data)/n;第4章串、數(shù)組和廣義表