嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)參考答案

《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)參考答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)參考答案（77頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第2版） 課后習(xí)題答案 李冬梅 2015.3 目 錄 第1章 緒論 1 第2章 線性表 5 第3章 棧和隊(duì)列 13 第4章 串、數(shù)組和廣義表 26 第5章 樹(shù)和二叉樹(shù) 33 第6章 圖 43 第7章 查找 54 第8章 排序 65 75 第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ù)類(lèi)型。 答案： 數(shù)據(jù)：是客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)

2、，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動(dòng)畫(huà)等通過(guò)特殊編碼定義后的數(shù)據(jù)。 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱(chēng)為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對(duì)象，如一個(gè)學(xué)生記錄，樹(shù)中棋盤(pán)的一個(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(chǎn)

3、’，‘b’，…，‘z’}，學(xué)生基本信息表也可是一個(gè)數(shù)據(jù)對(duì)象。 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說(shuō)，數(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ǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。 存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱(chēng)為物理結(jié)構(gòu)。 抽象數(shù)據(jù)類(lèi)型：由用戶(hù)定義的，表示應(yīng)用問(wèn)題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一組操作的總稱(chēng)。具體包括三部分：數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象上關(guān)系的集合和對(duì)數(shù)據(jù)對(duì)象的基本操作的集合。 2．試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的

4、例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。 答案： 例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號(hào)、姓名、性別、籍貫、專(zhuān)業(yè)等。每個(gè)學(xué)生基本信息記錄對(duì)應(yīng)一個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線性序列。對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)(它的前面無(wú)記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無(wú)記錄)，其他的結(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ù)組表示)來(lái)存放這些記錄，則稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)；如果存儲(chǔ)單元不連續(xù)，而是隨機(jī)存放各個(gè)記錄，然后用指針進(jìn)

5、行鏈接，則稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 即相同的邏輯結(jié)構(gòu)，可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。 3．簡(jiǎn)述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫(huà)出它們的關(guān)系圖。 答案： （1）集合結(jié)構(gòu) 數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無(wú)其他關(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）樹(shù)結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。例如，在班級(jí)的管理體系中，班長(zhǎng)管理多個(gè)組長(zhǎng)，每位組長(zhǎng)管理多名組員，從而構(gòu)成樹(shù)形結(jié)構(gòu)。 （4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系

6、。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。 其中樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。 四類(lèi)基本邏輯結(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ì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組類(lèi)型來(lái)描述。 （2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無(wú)需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)

7、言的指針類(lèi)型來(lái)描述。 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) 答案：C （2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(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．?dāng)?shù)據(jù)具有同一特點(diǎn) B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)

8、據(jù)項(xiàng)的類(lèi)型要一致 C．每個(gè)數(shù)據(jù)元素都一樣 D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等 答案：B （4）以下說(shuō)法正確的是（ ）。 A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位 B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合 D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) 答案：D 解釋?zhuān)簲?shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。 （5）算法的時(shí)間復(fù)雜度取決于（ ）。 A．問(wèn)題的規(guī)模 B．待處理數(shù)據(jù)的初態(tài) C．計(jì)算機(jī)的配置 D．A和B 答案：D 解釋?zhuān)核惴ǖ臅r(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模有關(guān)，還與問(wèn)題的其他

9、因素有關(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．樹(shù) B．字符串 C．隊(duì)列 D．棧 答案：A 6．試分析下面各程序段的時(shí)間復(fù)雜度。 （1）x=90; y=100;? while(y>0) if(x>100) {x=x-10;y--;} else x++; 答案：O(1) 解釋?zhuān)撼绦虻膱?zhí)行次數(shù)為常數(shù)階。 （2）for (i=0; i

10、[j]=0; 答案：O(m*n) 解釋?zhuān)赫Z(yǔ)句a[i][j]=0;的執(zhí)行次數(shù)為m*n。 （3）s=0; for i=0; i

11、; j++) x++; 答案：O(n2) 解釋?zhuān)赫Z(yǔ)句x++;的執(zhí)行次數(shù)為n-1+n-2+……＋1= n(n-1)/2。 （6）x=n; //n>1 y=0; while(x≥(y+1)* (y+1)) y++; 答案：O() 解釋?zhuān)赫Z(yǔ)句y++;的執(zhí)行次數(shù)為???。 第2章 線性表 1．選擇題 （1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ ）。 A．110 B．108 C．100 D．120 答案：B 解釋?zhuān)喉樞虮碇械臄?shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為

12、：100+2*4=108。 （2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（ ）。 A．訪問(wèn)第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第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)（1≤i≤n） D．將n個(gè)結(jié)點(diǎn)從小到大排序 答案：A 解釋?zhuān)涸陧樞虮碇胁迦胍粋€(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(n2)，排序的時(shí)間復(fù)雜度為O(n2)或O(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問(wèn)第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都可以直接通過(guò)數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是O(1)。 （3） 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持

13、原來(lái)順序不變，平均要移動(dòng) 的元素個(gè)數(shù)為（ ）。 A．8 B．63.5 C．63 D．7 答案：B 解釋?zhuān)浩骄苿?dòng)的元素個(gè)數(shù)為：n/2。 （4）鏈接存儲(chǔ)的存儲(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ù)的 B．部分地址必須是連續(xù)的 C．一定

14、是不連續(xù)的 D．連續(xù)或不連續(xù)都可以 答案：D （6）線性表Ｌ在（ ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 A．需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值 Ｂ．需不斷對(duì)Ｌ進(jìn)行刪除插入 C．Ｌ中含有大量的結(jié)點(diǎn) Ｄ．Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 答案：B 解釋?zhuān)烘湵碜畲蟮膬?yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。 （7）單鏈表的存儲(chǔ)密度（ ）。 A．大于1 B．等于1 C．小于1 D．不能確定 答案：C 解釋?zhuān)捍鎯?chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占

15、的空間為N，則存儲(chǔ)密度為：D/(D+N)，一定小于1。 （8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（ ）。 A．n B．2n-1 C．2n D．n-1 答案：A 解釋?zhuān)寒?dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）第二個(gè)表中的元素，只需要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。 （9）在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（ ）個(gè)元素。 A．n-i B．n-i+1 C．n-i-1 D．I

16、答案：B (10) 線性表L=(a1，a2,……an)，下列說(shuō)法正確的是（ ）。 A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B．線性表中至少有一個(gè)元素 C．表中諸元素的排列必須是由小到大或由大到小 D．除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。 答案：D (11) 創(chuàng)建一個(gè)包括n個(gè)結(jié)點(diǎn)的有序單鏈表的時(shí)間復(fù)雜度是（ ）。 A．O(1) B．O(n) C．O(n2) D．O(nlog2n) 答案：C 解釋?zhuān)簡(jiǎn)捂湵韯?chuàng)建的時(shí)間復(fù)雜度是O(n)，而要建立一個(gè)有序的單鏈表，則每生成一

17、個(gè)新結(jié)點(diǎn)時(shí)需要和已有的結(jié)點(diǎn)進(jìn)行比較，確定合適的插入位置，所以時(shí)間復(fù)雜度是O(n2)。 (12) 以下說(shuō)法錯(cuò)誤的是（ ）。 A．求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低 B．順序存儲(chǔ)的線性表可以隨機(jī)存取 C．由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活 D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu) 答案：D 解釋?zhuān)烘準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場(chǎng)合。 (13) 在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為（ ）。 A．s->next=p+1; p->next=s; B．(*p)

18、.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->prior; D．p->prior=

19、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-

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

21、，為空時(shí)，將非空表的剩余元素直接鏈接在Lc表的最后。 [算法描述] void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) Lc=pc=La; //用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) while(pa && pb) {if(pa->datadata){pc->next=pa;pc=pa;pa=pa->n

22、ext;} //取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} //取較小者Lb中的元素，將pb鏈接在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; //插入剩余段

23、 delete Lb; //釋放Lb的頭結(jié)點(diǎn) } （2）將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。 [題目分析] 合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(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í)，將非空表的剩余元素依次摘取，鏈接在

24、Lc表的表頭結(jié)點(diǎn)之后。 [算法描述] void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) Lc=pc=La; //用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) Lc->next=NULL; while(pa||pb ) {//只要存在一個(gè)非空表，用q指向待摘取的元素 if(!pa) {q=pb; pb=p

25、b->next;} //La表為空，用q指向pb，pb指針后移 else if(!pb) {q=pa; pa=pa->next;} //Lb表為空，用q指向pa，pa指針后移 else if(pa->data<=pb->data) {q=pa; pa=pa->next;} //取較小者（包括相等）La中的元素，用q指向pa，pa指針后移 else {q=pb; pb=pb->next;} //取較小者Lb中的元素，用q指向pb，pb指針后移 q->next = Lc->next; Lc->next = q; //將q指向的

26、結(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)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個(gè)表中相等的元素時(shí)，摘取La表中的元素，刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的元素，

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

28、 u=pb;pb=pb->next; delete u;} else if(pa->datadata) {u=pa;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; //釋放Lb的頭結(jié)點(diǎn) } （4）已知兩個(gè)鏈表A和B分別表示

29、兩個(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é)點(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)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果La表中的元素小于Lb表中的元素，pre置為L(zhǎng)a表的工作指針pa刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的元素，此表

30、的工作指針后移。當(dāng)鏈表La和Lb有一個(gè)為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。 [算法描述] void Difference（LinkList& La, LinkList& Lb,int *n） {∥差集的結(jié)果存儲(chǔ)于單鏈表La中，*n是結(jié)果集合中元素個(gè)數(shù)，調(diào)用時(shí)為0 pa=La->next; pb=Lb->next; ∥pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) pre=La; ∥pre為L(zhǎng)a中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針 while（pa&&pb） {if（pa->datadata）{pre=pa;p

31、a=pa->next;*n++;} ∥ A鏈表中當(dāng)前結(jié)點(diǎn)指針后移 else if（pa->data>q->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表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A中的元素為非零整數(shù)，要求B、C表利用A表的

32、結(jié)點(diǎn)）。 [題目分析] B表的頭結(jié)點(diǎn)使用原來(lái)A表的頭結(jié)點(diǎn)，為C表新申請(qǐng)一個(gè)頭結(jié)點(diǎn)。從A表的第一個(gè)結(jié)點(diǎn)開(kāi)始，依次取其每個(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=A; B->next= NULL; ∥B表初始化 C=new LNode;∥為C申請(qǐng)結(jié)點(diǎn)空間 C->next=NULL; ∥C初始化為空表 p=A->next; ∥p為工作指針 while(p!= NULL)

33、 { r=p->next; ∥暫存p的后繼 if(p->data<0) {p->next=B->next; B->next=p; }∥將小于0的結(jié)點(diǎn)鏈入B表,前插法 else {p->next=C->next; C->next=p; }∥將大于等于0的結(jié)點(diǎn)鏈入C表,前插法 p=r;∥p指向新的待處理結(jié)點(diǎn)。 } } （6）設(shè)計(jì)一個(gè)算法，通過(guò)一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。 [題目分析] 假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個(gè)元素比較，若其小于下一個(gè)元素，則設(shè)其下一個(gè)元素為最大值

34、，反復(fù)進(jì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(p->data > pmax->data) pmax=p;//如果p的值大于pmax的值，則重新賦值 p=p->next;//遍歷鏈表 } return pmax->data; （7）設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟，將鏈表中所有結(jié)

35、點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲(chǔ)空間。 [題目分析] 從首元結(jié)點(diǎn)開(kāi)始，逐個(gè)地把鏈表L的當(dāng)前結(jié)點(diǎn)p插入新的鏈表頭部。 [算法描述] 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è)

36、算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同 ）。 [題目分析] 分別查找第一個(gè)值>mink的結(jié)點(diǎn)和第一個(gè)值 ≥maxk的結(jié)點(diǎn)，再修改指針，刪除值大于mink且小于maxk的所有元素。 [算法描述] void delete(LinkList &L, int mink, int maxk) { p=L->next; //首元結(jié)點(diǎn) while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一個(gè)值>mink的結(jié)點(diǎn)

37、 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è)域，寫(xiě)出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順

38、序。 [題目分析] 知道雙向循環(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ū)交換

39、 p->rlink->llink=q； ∥p的后繼的前驅(qū)指向原p的前驅(qū) p->rlink=q； ∥p的后繼指向其原來(lái)的前驅(qū) }∥算法exchange結(jié)束。 （10）已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫(xiě)一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。 [題目分析] 在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)（刪第i個(gè)元素，第i+1至第n個(gè)元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針（i=1，j=n），從兩端向

40、中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。 [算法描述] void Delete（ElemType A[ ]，int n） ∥A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。 {i=1；j=n；∥設(shè)置數(shù)組低、高端指針（下標(biāo)）。 while（i

41、j--]；} 第3章 棧和隊(duì)列 1．選擇題 （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 解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的情況。 （2）若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（ ）。 A．i B．n-i C．n-i+

42、1 D．不確定 答案：C 解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，…，n，而輸出序列的第一個(gè)元素為n，說(shuō)明1，2，3，…，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，…，pi=n-i+1。 （3）數(shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ ）。 A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n 答案：D 解釋?zhuān)簩?duì)于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是

43、隊(duì)列的長(zhǎng)度，而對(duì)于循環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+r-f)%n。 （4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（ ）。 A．x=top->data;top=top->link； B．top=top->link;x=top->link； C．x=top;top=top->link； D．x=top->link； 答案：A 解釋?zhuān)簒=top->data將結(jié)點(diǎn)的值保存到x中，top=top->lin

44、k棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。 （5）設(shè)有一個(gè)遞歸算法如下 ??? ??? int fact(int n) {? //n大于等于0 ??? ???????? if(n<=0) return 1; ??? ???????? else return n*fact(n-1);??? ??? } 則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。? A．?n+1??? ?? B．?n-1????? C． n????? D． n+2 答案：A 解釋?zhuān)禾厥庵捣?。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。 （6

45、）棧在?（ ）中有所應(yīng)用。 A．遞歸調(diào)用 B．函數(shù)調(diào)用 C．表達(dá)式求值 D．前三個(gè)選項(xiàng)都有 答案：D 解釋?zhuān)哼f歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。 （7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ ）。 A．隊(duì)列 B．棧 C． 線性表 D．有序表 答案：A 解釋?zhuān)航鉀Q緩沖區(qū)問(wèn)題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線性表。

46、（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)該是（　）。 A．2 B．3 C．4 D． 6 答案：B 解釋?zhuān)涸爻鲫?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的容量

47、至少為3。 （9）若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是( )。 A．top++; V[top]=x; B．V[top]=x; top++; C．top--; V[top]=x; D．V[top]=x; top--; 答案：C 解釋?zhuān)撼跏紬ｍ斨羔榯op為n+1，說(shuō)明元素從數(shù)組向量的高端地址進(jìn)棧，又因?yàn)樵卮鎯?chǔ)在向量空間V[1..n]中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在V[n]。 （10）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（?。?shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲(chǔ)結(jié)構(gòu)

48、 B．隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧 答案：D 解釋?zhuān)豪脳５暮筮M(jìn)先出原則。 （11）用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（?。? A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 答案：D 解釋?zhuān)阂话闱闆r下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。 （12）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（?。?。 A. rear

49、=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D 解釋?zhuān)簲?shù)組A[0..m]中共含有m+1個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。 （13）最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（?。?。 A. (rear+1)%n==front B. rear==front

50、 C．rear+1==front D. (rear-l)%n==front 答案：B 解釋?zhuān)鹤畲笕萘繛閚的循環(huán)隊(duì)列，隊(duì)滿(mǎn)條件是(rear+1)%n==front，隊(duì)空條件是rear==front。 （14）棧和隊(duì)列的共同點(diǎn)是（?。?。 A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn) 答案：C 解釋?zhuān)簵Ｖ辉试S在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭刪除元素。 （15）

51、一個(gè)遞歸算法必須包括（?。? A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 D. 終止條件和迭代部分 答案：B 2．算法設(shè)計(jì)題 （1）將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。試編寫(xiě)雙棧初始化，判斷棧空、棧滿(mǎn)、進(jìn)棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下： Typedef struct {int to

52、p[2],bot[2]; //棧頂和棧底指針 SElemType *V; //棧數(shù)組 int m; //棧最大可容納元素個(gè)數(shù) }DblStack [題目分析] 兩棧共享向量空間，將兩棧棧底設(shè)在向量?jī)啥?，初始時(shí)，左棧頂指針為-1，右棧頂為m。兩棧頂指針相鄰時(shí)為棧滿(mǎn)。兩棧頂相向、迎面增長(zhǎng)，棧頂指針指向棧頂元素。 [算法描述] (1)?棧初始化 int?Init() ?{S.top[0]=-1; ??S.top[1]=m; ??return?1;?//初始化成功 } (2)?入棧操作： int?push(stk S?,int?i,int?x) ∥i為

53、棧號(hào)，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，失敗返回0 {if(i<0||i>1){ cout<<“棧號(hào)輸入不對(duì)”<

54、i=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功時(shí)返回退棧元素 ∥否則返回-1 {if(i<0 || i>1){cout<<“棧號(hào)輸入錯(cuò)誤”<

55、 (4)?判斷棧空 int?Empty(); {return?(S.top[0]==-1 && S.top[1]==m); } [算法討論]? 請(qǐng)注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。左棧是通常意義下的棧，而右棧入棧操作時(shí)，其棧頂指針左移（減1），退棧時(shí)，棧頂指針右移（加1）。 （2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)? [題目分析] 將字符串前一半入棧，然后，棧中元素和字符串后一半進(jìn)行比較。即將第一個(gè)出棧元素和后一半串中第一個(gè)字符比較，

56、若相等，則再出棧一個(gè)元素與后一個(gè)字符比較，……，直至?？?，結(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時(shí)，結(jié)論字符序列不是回文。 [算法描述] #define StackSize 100 //假定預(yù)分配的?？臻g最多為100個(gè)元素 typedef char DataType;//假定棧元素的數(shù)據(jù)類(lèi)型為字符 typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判斷t字符向量是否為回文，若是，返回1，否則返回0 SeqStack s; int i

57、 , len; char temp; InitStack( &s); len=strlen(t); //求向量長(zhǎng)度 for ( i=0; i

58、：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù)，當(dāng)ai≠-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對(duì)異常情況（入棧滿(mǎn)等）給出相應(yīng)的信息。 [算法描述] #define maxsize 棧空間容量 void InOutS(int s[maxsize]) //s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。 {int top=0; //top為棧頂指針，定義top=0時(shí)為棧空。 for(i=1; i<=n; i++) //n個(gè)整數(shù)序列作處理。 {cin>>x); //從鍵盤(pán)讀入整數(shù)序列。 if(x!=-1) //

59、讀入的整數(shù)不等于-1時(shí)入棧。 ｛if(top==maxsize-1){cout<<“棧滿(mǎn)”<

60、可能有+、-、*、/四種運(yùn)算。例如：234 34+2*$。 [題目分析] 逆波蘭表達(dá)式(即后綴表達(dá)式)求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND,對(duì)表達(dá)式從左到右掃描(讀入)，當(dāng)表達(dá)式中掃描到數(shù)時(shí)，壓入OPND棧。當(dāng)掃描到運(yùn)算符時(shí)，從OPND退出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果再壓入OPND棧。這個(gè)過(guò)程一直進(jìn)行到讀出表達(dá)式結(jié)束符$，這時(shí)OPND棧中只有一個(gè)數(shù)，就是結(jié)果。 [算法描述] float expr( ) //從鍵盤(pán)輸入逆波蘭表達(dá)式，以‘$’表示輸入結(jié)束，本算法求逆波蘭式表達(dá)式的值。 ｛float OPND[30]; // OPND是操作數(shù)棧。 init(OPND); /

61、/兩棧初始化。 float num=0.0; //數(shù)字初始化。 cin>>x;//x是字符型變量。 while(x!=’$’) {switch {case‘0’<=x<=’9’: while((x>=’0’&&x<=’9’)||x==’.’) //拼數(shù) if(x!=’.’) //處理整數(shù) {num=num*10+（ord(x)-ord(‘0’)）; cin>>x;} else //處理小數(shù)部分。 {scale=10.0; cin>>x; while(x>=’0’&&x<=’9’) {num=num+(ord(x)-ord(

62、‘0’)/scale; scale=scale*10; cin>>x; } }//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)*pop(

63、OPND));break; case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符號(hào)不作處理。 }//結(jié)束switch cin>>x;//讀入表達(dá)式中下一個(gè)字符。 }//結(jié)束while（x！=‘$’） cout<<“后綴表達(dá)式的值為”<

64、號(hào)減去字符‘0’的序號(hào)得出數(shù)。對(duì)于整數(shù)，每讀入一個(gè)數(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ù)過(guò)程中，若遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復(fù)為0，準(zhǔn)備下一個(gè)數(shù)。這時(shí)對(duì)新讀入的字符進(jìn)入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在結(jié)束處理數(shù)字字符的case后，不能加入break語(yǔ)句。 （5）假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成

65、的序列，稱(chēng)可以操作的序列為合法序列，否則稱(chēng)為非法序列。 ①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通過(guò)對(duì)①的分析，寫(xiě)出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。 答案： ①A和D是合法序列，B和C 是非法序列。 ②設(shè)被判定的操作序列已存入一維數(shù)組A中。 int Judge(char A[]) //判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否則

66、返回false。 {i=0; //i為下標(biāo)。 j=k=0; //j和k分別為I和字母O的的個(gè)數(shù)。 while(A[i]!=‘\0’) //當(dāng)未到字符數(shù)組尾就作。 {switch(A[i]) {case‘I’: j++; break; //入棧次數(shù)增1。 case‘O’: k++; if(k>j){cout<<“序列非法”<