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

1、 數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版） 課后習(xí)題答案 李冬梅 2015.3 目錄 第 1 章 緒論 1 第 2 章 線性表 5 第 3 章 棧和隊(duì)列 14 第 4 章 串、數(shù)組和廣義表 27 第 5 章 樹和二叉樹 34 第 6 章 圖 44 第 7 章 查找 55 第 8 章 排序 66 II 第1章緒論 1 簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié) 構(gòu)、抽象數(shù)據(jù)類型。 答案： 數(shù)據(jù)：是客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的 總稱。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、 圖像、聲音、動(dòng)畫等通過特殊

2、編碼定義后的數(shù)據(jù)。 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。在有些 情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對(duì)象，如一個(gè) 學(xué)生記錄，樹中棋盤的一個(gè)格局（狀態(tài)）、圖中的一個(gè)頂點(diǎn)等。 數(shù)據(jù)項(xiàng)：是組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。例如，學(xué)生基本信 息表中的學(xué)號(hào)、姓名、性別等都是數(shù)據(jù)項(xiàng)。 數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是 集合N=0，士 1， 2,，字母字符數(shù)據(jù)對(duì)象是集合C= A, B,，Z, a, b ， z ，學(xué)生基本信息表也可是一個(gè)數(shù)據(jù)對(duì)象。 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特

3、定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié) 構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。 邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此， 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。 存儲(chǔ)結(jié)構(gòu)： 數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱為物理結(jié)構(gòu)。 抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一 組操作的總稱。具體包括三部分：數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象上關(guān)系的集合和對(duì)數(shù)據(jù)對(duì)象的基本操 作的集合。 2 試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。 答案： 例如有一張學(xué)生基本信息表，包括學(xué)生

4、的學(xué)號(hào)、姓名、性別、籍貫、專業(yè)等。每個(gè)學(xué)生 基本信息記錄對(duì)應(yīng)一個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線性 序列。對(duì)于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)（它的前面無記錄 ）和一個(gè)終端結(jié)點(diǎn) （它的后面無記 錄），其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確 定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。 這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。如果用連續(xù)的存儲(chǔ)單元（如用數(shù)組表 示）來存放這些記錄，則稱為順序存儲(chǔ)結(jié)構(gòu)；如果存儲(chǔ)單元不連續(xù)，而是隨機(jī)存放各個(gè)記錄， 然后用指針進(jìn)行鏈接，則稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 即相同的邏輯結(jié)構(gòu)，可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。 3 簡(jiǎn)述邏輯結(jié)

5、構(gòu)的四種基本關(guān)系并畫岀它們的關(guān)系圖。 答案： (1 )集合結(jié)構(gòu) 數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無其他關(guān)系。例如，確定一名學(xué)生是 否為班級(jí)成員，只需將班級(jí)看做一個(gè)集合結(jié)構(gòu)。 (2) 線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報(bào)到的時(shí)間先后順 序進(jìn)行排列，將組成一個(gè)線性結(jié)構(gòu)。 (3) 樹結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。例如，在班級(jí)的管理體系中，班長(zhǎng)管理多個(gè)組長(zhǎng)，每 位組長(zhǎng)管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。 (4) 圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可 以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。 其中樹

6、結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。 四類基本邏輯結(jié)構(gòu)關(guān)系圖 4 存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？ 答案： (1) 順序存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常 借助程序設(shè)計(jì)語言的數(shù)組類型來描述。 (2) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無 需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于 存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言的指針類型來描述。 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

7、 緊湊結(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)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（）。 A. 存儲(chǔ)結(jié)構(gòu)B存儲(chǔ)實(shí)現(xiàn) C.邏輯結(jié)構(gòu)D運(yùn)算實(shí)現(xiàn) 答案： C （ 3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。 A .數(shù)據(jù)具有同一特點(diǎn) B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致 C. 每個(gè)數(shù)據(jù)元素都一樣 D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(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ù)

8、項(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 解釋：算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些 排序的算法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對(duì)算法有最好、最壞 以及平均時(shí)間復(fù)雜度的評(píng)價(jià)。 （ 6）以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu) A.樹 B字符串C 隊(duì)列D棧 答案： A 6.試分析下面各程序段的時(shí)間復(fù)雜度。

9、（ 1 ） x=90; y=100; while（y0） if（x100） x=x-10;y-; else x+; 答案： O（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) s=0; for i=0; in; i+) for(j=0; jn; j+) s+=Bij sum=s; 2 答案：0(n ) 解釋：語句 s+=Bij;的執(zhí)行次數(shù)為n2c (4) i=1； while(i=n) i=i*3; 答案：O(log 3n) 解釋：語

10、句i=i*3;的執(zhí)行次數(shù)為lllog 3n。 (5) x=0; for(i=1; i1 y=0; while(x (y+1)* (y+1) y +； 答案：0( .n ) 解釋：語句 y+;的執(zhí)行次數(shù)為IL ：n 。 10 第2章線性表 i 選擇題 (1) 順序表中 第一個(gè) 元素的存儲(chǔ) 地址是100 ,每個(gè)元素的 長(zhǎng)度為2，則第5個(gè)元素的 地址是()。 A 110B 108C 100D 120 答案：B 解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。 (2) 在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0(1)的操作是()。 A .訪問第i個(gè)結(jié)點(diǎn)(1 i n)和求第

11、i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2 i n) B .在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1 i n) C 刪除第i個(gè)結(jié)點(diǎn)(K i n) D將n個(gè)結(jié)點(diǎn)從小到大排序 答案：A 解釋：在順序表中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是0(n2)，排序的時(shí)間復(fù)雜度為0(n2) 或0(nlog 2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都可 以直接通過數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是0(1)。 (3) 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移 動(dòng)的元素個(gè)數(shù)為()。 A 8B 63.5C 63D . 7 答案：B 解釋：平均要移動(dòng)的元素個(gè)數(shù)為：n/2。 (4) 鏈接存儲(chǔ)的存

12、儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間( A 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B 只有一部分，存放結(jié)點(diǎn)值 C 只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針 D 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù) 答案：A (5) 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址( A .必須是連續(xù)的 C 一定是不連續(xù)的 答案：D (6)線性表1在( B部分地址必須是連續(xù)的 D連續(xù)或不連續(xù)都可以 )情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 A需經(jīng)常修改L中的結(jié)點(diǎn)值 CL中含有大量的結(jié)點(diǎn) 答案：B E. 需不斷對(duì)L進(jìn)行刪除插入 D. L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要

13、移動(dòng)數(shù)據(jù)，直接修改指針即可。 ( 7 )單鏈表的存儲(chǔ)密度()。 A 大于1B 等于1C 小于1D 不能確定 答案： C 解釋：存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空 間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密 度為： D/(D+N) ，一定小于 1。 ( 8 )將兩個(gè)各有 n 個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是()。 A nB 2n-1C. 2nD . n-1 答案： A 解釋：當(dāng)?shù)谝粋€(gè)有序表中所有的元素都小于(或大于)第二個(gè)表中的元素，只需 要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n 次。 (9)

14、 在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素(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) 在雙向鏈表存儲(chǔ)結(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-next-prior=p; C p-prior-next=p; p-prior=p-prior-

15、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; D q-prior=p; q-next=p-next; p-n

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

17、一個(gè)表到達(dá)表尾結(jié) 點(diǎn)，為空時(shí)，將非空表的剩余元素直接鏈接在 Lc 表的最后。 算法描述 void MergeList(LinkList pb=Lb-next; /pa 和 pb 分別是鏈表 La 和 Lb 的工作指針 , 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) Lc=pc=La; / 用 La 的頭結(jié)點(diǎn)作為 Lc 的頭結(jié)點(diǎn) while(pa pc=pa;pa=pa-next; / 取較小者 La 中的元素，將 pa 鏈接在 pc 的后面， pa 指針后移 else if(pa-datapb-data) pc-next=pb; pc=pb; pb=pb-next; / 取較小者 Lb 中的元素，將 pb

18、鏈接在 pc 的后面， pb 指針后移 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è)鏈表的存儲(chǔ)空間 , 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。 題目分析 合并后的新表使用頭指針 Lc 指向， pa 和 pb 分別是鏈表 La 和 Lb 的工作指針 , 初始化為 相應(yīng)鏈表

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

20、b ) / 只要存在一個(gè)非空表，用 q 指向待摘取的元素 if(!pa) q=pb; pb=pb-next; /La 表為空，用 q 指向 pb， pb 指針后移 else if(!pb) q=pa; pa=pa-next; /Lb 表為空，用 q 指向 pa， pa 指針后移 else if(pa-datadata) q=pa; pa=pa-next; / 取較小者(包括相等) La 中的元素，用 q 指向 pa， pa 指針后移 else q=pb; pb=pb-next; / 取較小者 Lb 中的元素，用 q 指向 pb， pb 指針后移 q-next = Lc-next; Lc-nex

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

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

23、delete u; u; / 釋放結(jié)點(diǎn)空間 u; /釋放結(jié)點(diǎn)空間 while(pa) u=pa; pa=pa-next; delete while(pb) u=pb; pb=pb-next; delete pc- next=null; /置鏈表尾標(biāo)記。 delete Lb; / 釋放 Lb 的頭結(jié)點(diǎn) ( 4 )已知兩個(gè)鏈表A 和 B 分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出兩個(gè)集 合A和B的差集(即僅由在A中岀現(xiàn)而不在B中岀現(xiàn)的元素所構(gòu)成的集合)，并以同樣的形 式存儲(chǔ)，同時(shí)返回該集合的元素個(gè)數(shù)。 題目分析 求兩個(gè)集合 A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)

24、點(diǎn),所以要保存待刪除結(jié)點(diǎn)的前驅(qū)，使用指針pre 指向前驅(qū)結(jié)點(diǎn)。 pa 和 pb 分別是鏈表 La 和 Lb 的工作指針 , 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表 La 和 Lb 均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果 La 表中的元素小于 Lb 表中的元素， pre 置為 La 表的工 作指針 pa 刪除 Lb 表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的元素， 此表的工作指針后移。 當(dāng)鏈表 La 和 Lb 有一個(gè)為空時(shí)， 依次刪除另一個(gè)非空表中的所有元素。 算法描述 void Difference ( LinkList pb=Lb-next; / pa 和 pb

25、 分別是鏈表 La 和 Lb 的工作指針 , 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) pre=La;/ pre 為 La 中 pa 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針 while ( papa=pa-next;*n+; / A 鏈表中當(dāng)前結(jié)點(diǎn)指針后移 else if ( pa-dataq-data ) q=q-next;/ B 鏈表中當(dāng)前結(jié)點(diǎn)指針后移 else pre-next=pa-next;/處理 A， B 中元素值相同的結(jié)點(diǎn)，應(yīng)刪除 u=pa; pa=pa-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表中值小于零

26、的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈表 A中的元 素為非零整數(shù)，要求 B、 C 表利用 A 表的結(jié)點(diǎn)) 。 題目分析 B表的頭結(jié)點(diǎn)使用原來A表的頭結(jié)點(diǎn)，為 C表新申請(qǐng)一個(gè)頭結(jié)點(diǎn)。從A表的第一個(gè)結(jié)點(diǎn) 開始，依次取其每個(gè)結(jié)點(diǎn)p，判斷結(jié)點(diǎn) p的值是否小于 0,利用前插法，將小于 0的結(jié)點(diǎn)插入 B表，大于等于0的結(jié)點(diǎn)插入 C表。 算法描述 void DisCompose(LinkedList A) / B表初始化 C 申請(qǐng)結(jié)點(diǎn)空間 / C初始化為空表 / p為工作指針 B=A; B-next= NULL; C=new LNode; / 為 C-next=NULL; p=A-next; whi

27、le(p!= NULL) 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ì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。 題目分析 假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個(gè)元素比較，若其小于下一個(gè)元素，則 設(shè)其下一個(gè)元素為最大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。 算法描述 ElemType Max (Li nkList L ) if(L- next=NULL

28、) return NULL; pmax=L- next; /假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值 p=L-n ext-n ext; while(p != NULL )/如果下一個(gè)結(jié)點(diǎn)存在 if(p-data pmax-data) pmax=p;/如果 p的值大于 pmax的值，則重新賦值 p=p- next;/遍歷鏈表 retur n pmax-data; (7) 設(shè)計(jì)一個(gè)算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表 存儲(chǔ)空間。 題目分析 從首元結(jié)點(diǎn)開始，逐個(gè)地把鏈表 算法描述 void in verse(L in kList L- next=NULL; while ( p) q=

29、p-n ext; / q p-n ext=L-n ext; L-n ext=p;/ *p L的當(dāng)前結(jié)點(diǎn) p插入新的鏈表頭部。 指向*p的后繼 插入在頭結(jié)點(diǎn)之后 ii p = q; ( 8 )設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink 且小于 maxk 的所有元素( mink 和 maxk 是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同 )。 題目分析 分別查找第一個(gè)值 mink的結(jié)點(diǎn)和第一個(gè)值 maxk的結(jié)點(diǎn)，再修改指針，刪除值大于 mink 且小于 maxk 的所有元素。 算法描述 void delete(LinkList / 首元結(jié)點(diǎn) while (p /查找第一個(gè)值 mink

30、 的結(jié)點(diǎn) if (p) while (p 查找第一個(gè)值 maxk的結(jié)點(diǎn) 修改指針 釋放結(jié)點(diǎn)空間 / q=pre-next; pre-next=p; / while (q!=p) s=q-next; delete q; q=s; / /if ( 9)已知 p 指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為 data 、prior 、next 三個(gè)域， 寫出算法 change(p), 交換 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 (Linke

31、dList p ) II p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。 q=p-llink； q-llink-rlink=p 5 I p 的前驅(qū)的前驅(qū)之后繼為p p-llink=q-llink 5 I p 的前驅(qū)指向其前驅(qū)的前驅(qū)。 q-rlink=p-rlink 5 I p 的前驅(qū)的后繼為p 的后繼。 q-llink=p； I p 與其前驅(qū)交換 p-rlink-llink=q 5 I p 的后繼的前驅(qū)指向原p 的前驅(qū) p-rlink=q； I p 的后繼指向其原來的前驅(qū) I 算法 exchange 結(jié)束。 ( 10 )已知長(zhǎng)度為 n 的線性表 A 采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一

32、時(shí)間復(fù)雜度為 O(n) 、空間復(fù) 雜度為 O(1) 的算法，該算法刪除線性表中所有值為item 的數(shù)據(jù)元素 題目分析 在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)(刪第 i+1 至第 n 個(gè)元素要依次前移） 。本題要求刪除線性表中所有值為 item 的數(shù)據(jù)元素，并未要 求元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針（i=1 ，j=n ），從兩端向中間移動(dòng)， 凡遇到值 item 的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item 的數(shù)據(jù)元素位置。 算法描述 void Delete （ ElemType A ， int n ） II A是有n個(gè)元素的一維數(shù)組，本算法刪除 i=1 ;

33、j=n ；/設(shè)置數(shù)組低、高端指針（下標(biāo)） while （ ij ） while （ ij top=top-link； C x=top;top=top-link； 答案： A 解釋： x=top-data 將結(jié)點(diǎn)的值保存到 即摘除棧頂結(jié)點(diǎn)。 ( 5)設(shè)有一個(gè)遞歸算法如下 int fact(int n) /n 大于等于 0 if(nlink;x=top-link； D x=top-link ； x 中， top=top-link 棧頂指針指向棧頂下一結(jié)點(diǎn)， )。 C nD n+2 解釋：特殊值法。設(shè)n=0 ，易知僅調(diào)用一次fact(n) 函數(shù)，故選 A 。 ( 6 )棧在 ( )中有所應(yīng)用。 A.

34、遞歸調(diào)用B 函數(shù)調(diào)用C.表達(dá)式求值D.前三個(gè)選項(xiàng)都有 答案： D 解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。 ( 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.有序表 答案： 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, 一個(gè)元素出棧后即進(jìn)入 Q ，若 6 個(gè)元素出隊(duì)的序列是

35、 e2、 e4、 e3、 e6、 e5 和 e1 ，則棧 S 的容 量至少應(yīng)該是( )。 A. 2B. 3C. 4D. 6 答案： B 解釋：元素出隊(duì)的序列是 e2、 e4、 e3、 e6、 e5 和 e1 ，可知元素入隊(duì)的序列是e2、 e4、 e3、 e6、 e5 和 e1 ，即元素出棧的序列也是 e2 、 e4、 e3 、 e6、 e5 和 e1 ，而元素 e1 、 e2、 e3、 e4、 e5 和 e6 依次進(jìn)入棧，易知棧S 中最多同時(shí)存在 3 個(gè)元素，故棧 S 的容量至少為3。 ( 9 ) 若一個(gè)棧以向量V1.n 存儲(chǔ)， 初始棧頂指針 top 設(shè)為 n+1 ，則元素 x 進(jìn)棧的正確操

36、作是 ( )。 A. top+; Vtop=x; B. Vtop=x; top+; C. top-; Vtop=x; D. Vtop=x; top-; 答案： C 解釋：初始棧頂指針 top 為 n+1 ，說明元素從數(shù)組向量的高端地址進(jìn)棧，又因?yàn)樵?存儲(chǔ)在向量空間 V1.n中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚,之后將元素x存儲(chǔ)在 Vn ( 10)設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最 佳。 A.線性表的順序存儲(chǔ)結(jié)構(gòu)B隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D. 棧 答案： D 解釋：利用棧的后進(jìn)先出原則。 ( 11)用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)()。 A. 僅

37、修改頭指針B.僅修改尾指針 C. 頭、尾指針都要修改D.頭、尾指針可能都要修改 答案： D 解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指 針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值 12 ）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m 中，則入隊(duì)時(shí)的操作為（ ） A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m 答案： D D. rear=(rear+1)%(m+1) 解釋：數(shù)組 A0.m 中共含有 m+1 個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以 m+1 35 A. (rear+1)%n=front B. rear=front C r

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

39、歸部分 C. 迭代部分D.終止條件和迭代部分 答案： B 2算法設(shè)計(jì)題 （ 1）將編號(hào)為 0 和 1 的兩個(gè)棧存放于一個(gè)數(shù)組空間 Vm 中， 棧底分別處于數(shù)組的兩端。 當(dāng)?shù)?0 號(hào)棧的棧頂指針 top0 等于 -1 時(shí)該棧為空，當(dāng)?shù)?1 號(hào)棧的棧頂指針 top1 等于 m 時(shí)該 棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。試編寫雙棧初始化，判斷?？?、棧滿、進(jìn)棧和出棧等 算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下： Typedef struct int top2,bot2;/ 棧頂和棧底指針 SElemType *V;/ 棧數(shù)組 int m;/ 棧最大可容納元素個(gè)數(shù) DblStack 題目分析 兩棧共享向量空間，

40、將兩棧棧底設(shè)在向量?jī)啥?，初始時(shí)，左棧頂指針為 -1 ，右棧頂為 m。 兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長(zhǎng)，棧頂指針指向棧頂元素。 算法描述 int Init() S.top0=-1; S.top1=m; return 1; / 初始化成功 (2) 入棧操作： int push(stk S ,int i,int x) II i為棧號(hào)，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1,失敗返回 if(i1) cout “棧號(hào)輸入不對(duì)”endl;exit(0); if(S.top1-S.top0=1) cout “棧已滿 ”endl;return(0); switch(i) ca

41、se 0: S.V+S.top0=x; return(1); break; case 1: S.V-S.top1=x; return(1); I push (3) 退棧操作 ElemType pop(stk S,int i) I退棧。i代表?xiàng)Ｌ?hào)，i=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功時(shí)返回退棧元素 I否則返回-1 if(i1)cout “棧號(hào)輸入錯(cuò)誤”endl ；exit(0); switch(i) case 0: if(S.top0=-1) cout “?？?”endl ； return ( -1 )； else return(S.VS.top0-); case 1: if(S.top1=

42、m cout “?？?”endl; return(-1); else return(S.VS.top1+); I switch I算法結(jié)束 (4) 判斷棧空 int Empty(); return (S.top0=-1 算法討論 請(qǐng)注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。左棧是通常意義下的棧，而右棧入 棧操作時(shí)，其棧頂指針左移(減1 )，退棧時(shí)，棧頂指針右移(加1 )。 good (2) 回文是指正讀反讀均相同的字符序列，如abba和abdba均是回文，但 不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧) 題目分析 將字符串前一半入棧，然后，棧中元素和字符串后一

43、半進(jìn)行比較。即將第一個(gè)出棧元素 和后一半串中第一個(gè)字符比較，若相等，則再岀棧一個(gè)元素與后一個(gè)字符比較，直至 ?？?，結(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時(shí)，結(jié)論字符序列不是回文。 算法描述 #define StackSize 100 /假定預(yù)分配的?？臻g最多為100 個(gè)元素 typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符 typedef struct DataType dataStackSize; int top; SeqStack; int IsHuiwen( char *t) / 判斷 t 字符向量是否為回文，若是，返回1，否則返回 0 SeqStac

44、k s; int i , len; char temp; InitStack( len=strlen(t); / 求向量長(zhǎng)度 for ( i=0; ilen/2; i+)/將一半字符入棧 Push( while( !EmptyStack( if( temp!=Si)return 0 ;/不等則返回 0 else i+; return 1 ; /比較完畢均相等則返回 1 (3) 設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an，試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ) 輸入的整數(shù)，當(dāng)q豐-1時(shí)，將q進(jìn)棧；當(dāng) ai=-i時(shí)，輸岀棧頂整數(shù)并岀棧。算法應(yīng)對(duì)異常情 況(入棧滿等)給岀相應(yīng)的信息。 算法描述 #d

45、efine maxsize 棧空間容量 void InOutS(int smaxsize) /s 是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。 int top=0; /top為棧頂指針，定義 top=0 時(shí)為?？?。 for(i=1; ix); / 從鍵盤讀入整數(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“?？铡?endl;exit(0); else cout “出棧元素是” stop-x

46、;/x 是字符型變量。 while(x!= $) switch case0=x= 0 else /處理小數(shù)部分。 scale=10.0; cinx; while(x= 0 /else push(OPND,num); num=0.0;/ 數(shù)壓入棧，下個(gè)數(shù)初始化 case x= :break; / 遇空格，繼續(xù)讀下一個(gè)字符。 case x= + :push(OPND,pop(OPND)+pop(OPND);break; case x= - :x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=* :push(OPND,pop(OPND)

47、*pop(OPND);break; case x= / :x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: / 其它符號(hào)不作處理。 / 結(jié)束 switch cinx;/ 讀入表達(dá)式中下一個(gè)字符。 / 結(jié)束 while ( x ！ = $) cout “后綴表達(dá)式的值為” j)cout “序列非法” ednl ； exit(0); / 判斷字符數(shù)組 A 中的輸入輸岀序列是否是合法序列。如是，返回 i+； / 不論Ai是I 或O,指針i均后移。 if(j!=k) cout“序列非法” endl ； return(false); e

48、lse cout “序列合法” 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; delete s; / 回收結(jié)點(diǎn)空間 (2) 判隊(duì)空 int EmptyQueue( LinkQueue *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) / 入

49、隊(duì)。也就是在尾結(jié)點(diǎn)處插入元素 QueueNode *p=new QueueNode;/ 申請(qǐng)新結(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)之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q ) Error(Queue underflow); p=Q-rear-next-next; /p 指向?qū)⒁碌慕Y(jié)點(diǎn) x=p-data; / 保

50、存結(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; else Q-rear-next-next=p-next;/ 摘下結(jié)點(diǎn) p delete p;/ 釋放被刪結(jié)點(diǎn) return x; (7)假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素，同時(shí)設(shè)置一個(gè)標(biāo)志tag ,以tag = 0和tag = 1 來區(qū)別在隊(duì)頭指針 (front )和隊(duì)尾指針 (rear )相等時(shí)，隊(duì)列狀態(tài)為 “空 ”還是 “滿”。試編寫與 此結(jié)構(gòu)相應(yīng)的插入 (enqueue )和刪除 (dlque

51、ue ) 算法。 算法描述 (1) 初始化 SeQueue QueueInit(SeQueue Q) / 初始化隊(duì)列 Q.front=Q.rear=0; Q.tag=0; return Q; (2) 入隊(duì) SeQueue QueueIn(SeQueue Q,int e) / 入隊(duì)列 if(Q.tag=1) else Q.rear=(Q.rear+1) % m; Q.dataQ.rear=e; if(Q.tag=0) Q.tag=1; / 隊(duì)列已不空 return Q; (3) 出隊(duì) ElemType QueueOut(SeQueue Q) / 出隊(duì)列 if(Q.tag=0) cout隊(duì)列為空

52、endl; exit(0); else Q.front=(Q.front+1) % m; e=Q.dataQ.front; if(Q.front=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ì)列長(zhǎng)度。設(shè)隊(duì)頭指針 front 和隊(duì)尾指針 rear ，約定 front 指向隊(duì)頭元素的前一位置， rear 指向隊(duì)尾元素。定義 front=rear 時(shí)為隊(duì)空， (rear+1)%m=f

53、ront 為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展， 隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。 算法描述 #defi ne M隊(duì)列可能達(dá)到的最大長(zhǎng)度 typedef struct elemtp dataM; int fron t,rear; cycqueue; elemtp delqueue ( cycqueue Q) Q是如上定義的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)從隊(duì)尾刪除，若刪除成功，返回被刪除元素, 否則給出出錯(cuò)信息。 if (Q.fro nt=Q.rear) cout Q.rear=(Q.rear-1+M)%M; / return(Q.data(Q.rea r+1+M)%M); / /從隊(duì)尾刪除算法結(jié)束 隊(duì)

54、列空endl; exit(O); 修改隊(duì)尾指針。 返回出隊(duì)元素。 void en queue (cycqueue Q, elemtp x) / Q 是順序存儲(chǔ)的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)“從隊(duì)頭插入”元素x if (Q.rear=(Q.front-1+M)%M) cout隊(duì)滿 ,Ack(mliAqk 1) 寫岀計(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 else return(Ack(m-1,Ack(m,m

55、-1); /算法結(jié)束 Ack(2,1)的計(jì)算過程 Ack(2,1)= Ack(1,Ack(2,0)/ =Ack(1,Ack(1,1) / 因m0,n0而得 因m0,n=0而得 因 m0,n0 而得 因 m0,n=0 而得 因 m=0 而得 因 m=0 而得 因 m0,n0 而得 因 m0,n0 而得 因 m0,n0 而得 因 m0,n=0 而得 因 m=0 而得 因 m=0 而得 因 n=0 而得 因 n=0 而得 = Ack(1,Ack(0,Ack(1,0) / = Ack(1,Ack(0,Ack(0,1) / = Ack(1,Ack(0,2)/ = Ack(1,3) / = Ack(0,A

56、ck(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 Ackerman(int 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;jnext) return p-data; else int m

57、ax=GetMax(p-next); return p-data=max ? p-data:max; int GetLength(LinkList p) if(!p-next) return 1; else return GetLength(p-next)+1; double GetAverage(LinkList p , int n) if(!p-next) return p-data; else double ave=GetAverage(p-next,n-1); return (ave*(n-1)+p-data)/n; 第 4 章 串、數(shù)組和廣義表 1 選擇題 （ 1 ）串是一種特殊的線

58、性表，其特殊性體現(xiàn)在（ A 可以順序存儲(chǔ) C 可以鏈?zhǔn)酱鎯?chǔ) 答案： B （ 2）串下面關(guān)于串的的敘述中， A 串是字符的有限序列 C.模式匹配是串的一種重要運(yùn)算 答案： B 解釋：空格常常是串的字符集合中的一個(gè)元素， 串，零個(gè)字符的串成為空串，其長(zhǎng)度為零。 （ 3）串“ ababaaababaa ”的 next 數(shù)組為（ ）。 B 數(shù)據(jù)元素是一個(gè)字符 D 數(shù)據(jù)元素可以是多個(gè)字符若 ）是不正確的？ B空串是由空格構(gòu)成的串 串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ) D 有一個(gè)或多個(gè)空格組成的串成為空格 ）。 A 012345678999 答案： C 4)串“ ababaabab ” B 01212

59、1111212 C 011234223456 D 0123012322345 的 nextval 為( A 010104101 答案： A （ 5）串的長(zhǎng)度是指（ A 串中所含不同字母的個(gè)數(shù) C 串中所含不同字符的個(gè)數(shù) 答案： B 解釋：串中字符的數(shù)目稱為串的長(zhǎng)度 （ 6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組 儲(chǔ)單元，基地址為 10 ，則 LOC5,5= B 010102101 C 010100011 D 010101011 ）。 B 串中所含字符的個(gè)數(shù) D 串中所含非空格字符的個(gè)數(shù) A=array1.100,1.100，設(shè)每個(gè)數(shù)據(jù)元素占 ）。 A 808 答案： B 解釋：以行序?yàn)橹鳎瑒t LOC5,

60、5= （ 7）設(shè)有數(shù)組 Ai,j ，數(shù)組的每個(gè)元素長(zhǎng)度為 B 818 C 1010 D 1020 2 個(gè)存 5-1) 數(shù)組從內(nèi)存首地址 BA 開始順序存放， 當(dāng)用以列為主存放時(shí)， *100+ （5-1 ） *2+1 0=81 8 。 3 字節(jié)， i 的值為 1 到 8，j 的值為 元素 A5,8 的存儲(chǔ)首地址為 到 10， （ ）。 A BA+141 答案： B 解釋：以列序?yàn)橹?，則 LOC5,8= （8-1 ）*8+ （5-1 ）*3+BA=BA+180。 （8）設(shè)有一個(gè) 10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a為第一元 素，其存儲(chǔ)地址為 1，每個(gè)元素占一個(gè)地址空間，則a85