數(shù)據(jù)結(jié)構(gòu)課后答案第3章

1、第 3 章 特殊線(xiàn)性表?xiàng)?、?duì)列和串2005-07-14第 3 章 特殊線(xiàn)性表?xiàng)?、?duì)列和串 課后習(xí)題講解 1. 填空 設(shè)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5， 經(jīng)過(guò)push，push，pop，push，pop，push，push后，輸出序列是（ ），棧頂指針為（ ）?！窘獯稹?3，1003H 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）；其判定?？盏臈l件分別是（ ），判定棧滿(mǎn)的條件分別是（ ）。【解答】順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= -1和top=NULL，棧頂指針top等于數(shù)組的長(zhǎng)度和內(nèi)存無(wú)可用空間（ ）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。【

2、解答】棧【分析】遞歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。 表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ ）?！窘獯稹縜bc+*d-【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫(xiě)下來(lái)，再將算符插在它的兩個(gè)操作數(shù)的后面。 棧和隊(duì)列是兩種特殊的線(xiàn)性表，棧的操作特性是（ ），隊(duì)列的操作特性是（ ），棧和隊(duì)列的主要區(qū)別在于（ ）?！窘獯稹亢筮M(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同 循環(huán)隊(duì)列的引入是為了克服（ ）?！窘獯稹考僖绯?數(shù)組Qn用來(lái)表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ ）?！窘獯稹浚╮ear-front+n）

3、% n【分析】也可以是（rear-front）% n，但rear-front的結(jié)果可能是負(fù)整數(shù)，而對(duì)一個(gè)負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會(huì)有所不同。 用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（ ）和（ ）?！窘獯稹?1)，(n)【分析】在帶頭指針的循環(huán)鏈表中，出隊(duì)即是刪除開(kāi)始結(jié)點(diǎn)，這只需修改相應(yīng)指針；入隊(duì)即是在終端結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭指針開(kāi)始查找終端結(jié)點(diǎn)的位置。 串是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在（ ）。【解答】數(shù)據(jù)元素的類(lèi)型是一個(gè)字符 兩個(gè)串相等的充分必要條件是（ ）?！窘獯稹块L(zhǎng)度相同且對(duì)應(yīng)位置的字符相等【分析】例如"ab

4、c""abc "，"abc""bca"。2. 選擇題 若一個(gè)棧的輸入序列是1，2，3，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是（ ）。A 不確定 B n-i C n-i-1 D n-i+1【解答】D【分析】此時(shí)，輸出序列一定是輸入序列的逆序。 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（ ）。A 6 B 4 C 3 D 2【解答】C【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此

5、題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、e1。 一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（ ）。A 54321 B 45321 C 43512 D 12345 【解答】C【分析】此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號(hào)）的兩個(gè)元素。 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳A 順序表 B 棧 C 隊(duì)列 D 鏈表【解答】B【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒(méi)有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該

6、是一個(gè)（ ）結(jié)構(gòu)。A 棧 B隊(duì)列 C 數(shù)組 D線(xiàn)性表【解答】B【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。 一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（ ）。A 4321 B 1234 C 1432 D 3241【解答】B【分析】隊(duì)列的入隊(duì)順序和出隊(duì)順序總是一致的。 棧和隊(duì)列的主要區(qū)別在于（ ）。A 它們的邏輯結(jié)構(gòu)不一樣 B 它們的存儲(chǔ)結(jié)構(gòu)不一樣C 所包含的運(yùn)算不一樣 D 插入、刪除運(yùn)算的限定不一樣【解答】D【分析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是線(xiàn)性的，都有順序存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問(wèn)題時(shí)包含的運(yùn)算都可能不同。 設(shè)數(shù)組

7、Sn作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)Sn全滿(mǎn)時(shí)才不能進(jìn)行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是（ ）。A S1的棧底位置為0，S2的棧底位置為n-1B S1的棧底位置為0，S2的棧底位置為n/2C S1的棧底位置為0，S2的棧底位置為nD S1的棧底位置為0，S2的棧底位置為1【解答】A【分析】?jī)蓷９蚕砜臻g首先兩個(gè)棧是相向增長(zhǎng)的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，并注意C+中的數(shù)組下標(biāo)是從0開(kāi)始的。 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作（ ）。A 連接 B 模式匹配 C 求子串 D 求串長(zhǎng)【解答】B3. 判斷題 有n個(gè)元素依次進(jìn)棧，則出棧序列有(n

8、-1)/2種?！窘獯稹垮e(cuò)。應(yīng)該有 種。 ?？梢宰鳛閷?shí)現(xiàn)過(guò)程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹繉?duì)。只要操作滿(mǎn)足后進(jìn)先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。 在棧滿(mǎn)的情況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉?duì)。 在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿(mǎn)的條件是front=rear。【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿(mǎn)的判定條件區(qū)別開(kāi)。 空串與空格串是相同的?！窘獯稹垮e(cuò)。空串的長(zhǎng)度為零，而空格串的長(zhǎng)度不為0，其長(zhǎng)度是串中空格的個(gè)數(shù)。4. 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，能否得到如下出棧序列，若能，請(qǐng)寫(xiě)出操作序列，若不

9、能，請(qǐng)說(shuō)明原因。 C，E，A，B，D C，B，A，D，E【解答】不能，因?yàn)樵贑、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B出棧?？梢裕O(shè)為進(jìn)棧操作，為入棧操作，則其操作序列為IIIOOOIOIO。5. 舉例說(shuō)明順序隊(duì)列的“假溢出”現(xiàn)象。【解答】假設(shè)有一個(gè)順序隊(duì)列，如圖3-6所示，隊(duì)尾指針rear=4，隊(duì)頭指針front=1，如果再有元素入隊(duì)，就會(huì)產(chǎn)生“上溢”，此時(shí)的“上溢”又稱(chēng)為“假溢出”，因?yàn)殛?duì)列并不是真的溢出了，存儲(chǔ)隊(duì)列的數(shù)組中還有2個(gè)存儲(chǔ)單元空閑，其下標(biāo)分別為0和1。6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(

10、6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。）【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過(guò)程如圖3-7所示。7 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊(duì)頭元素和隊(duì)尾元素分別是什么？（EnQueue(k)表示整數(shù)k入隊(duì)，DeQueue表示隊(duì)頭元素出隊(duì)）?！窘獯稹筷?duì)頭元素為5，隊(duì)尾元素為9。其執(zhí)行過(guò)程如圖3-8所示。8空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱(chēng)為空串，其長(zhǎng)度為

11、零。僅含空格的串稱(chēng)為空格串，它的長(zhǎng)度為串中空格符的個(gè)數(shù)。串中的空格符可用來(lái)分隔一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長(zhǎng)時(shí)應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?。9. 算法設(shè)計(jì) 假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針。試設(shè)計(jì)相應(yīng)的入隊(duì)和出隊(duì)的算法?！窘獯稹砍鲫?duì)操作是在循環(huán)鏈表的頭部進(jìn)行，相當(dāng)于刪除開(kāi)始結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部進(jìn)行，相當(dāng)于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。由于循環(huán)鏈表不帶頭結(jié)點(diǎn)，需要處理空表的特殊情況。入隊(duì)算法如下：出隊(duì)算法如下： 設(shè)順序棧S中有2n個(gè)元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，a1，要求通過(guò)一個(gè)循環(huán)隊(duì)

12、列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，a2，a2n-1，a2n-3，a1，請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)間復(fù)雜度均為O(n)?！窘獯稹坎僮鞑襟E為： 將所有元素出棧并入隊(duì)； 依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn)，則再入隊(duì)，如果是奇數(shù)結(jié)點(diǎn)，則入棧； 將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)； 將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧； 將所有元素出棧并入隊(duì)； 將所有元素出隊(duì)并入棧即為所求。 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串S，編寫(xiě)算法刪除S中第 i個(gè)字符開(kāi)始的連續(xù)j個(gè)字符?！窘獯稹肯扰袛啻甋中要?jiǎng)h除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個(gè)位置。算法如下： 對(duì)于采用順序存儲(chǔ)結(jié)構(gòu)的串S，編寫(xiě)一個(gè)函

13、數(shù)刪除其值等于ch的所有字符?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有移動(dòng)的元素中沒(méi)有值為ch的元素，能減少移動(dòng)元素的次數(shù)，提高算法的效率。算法如下： 對(duì)串的模式匹配KMP算法設(shè)計(jì)求模式滑動(dòng)位置的next函數(shù)?！窘獯稹繀⒁?jiàn)3.2.5學(xué)習(xí)自測(cè)及答案 1在一個(gè)具有n個(gè)單元的順序棧中，假定以位置低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為（ ）。A 不變 B top=0; C top=top-1; D top=top+1;【解答】C2一個(gè)棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。A edcba B cdeba C debca

14、 D abcde 【解答】C3從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（ ）。A x=top; top=top->next; B x=top->data;C top=top->next; x=top->data; D x=top->data; top=top->next;【解答】D4設(shè)元素1, 2, 3, P, A依次經(jīng)過(guò)一個(gè)棧，進(jìn)棧次序?yàn)?23PA，在棧的輸出序列中，有哪些序列可作為C+程序設(shè)計(jì)語(yǔ)言的變量名。【解答】PA321, P3A21, P32A1, P321A, AP3215.設(shè)S="I_ am_ a_ te

15、acther"，其長(zhǎng)度為（ ）?！窘獯稹?56對(duì)于棧和隊(duì)列，無(wú)論它們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是（ ）?！窘獯稹?1)7如果進(jìn)棧序列為A、B、C、D，則可能的出棧序列是什么？答：共14種，分別是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA8簡(jiǎn)述隊(duì)列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)?！窘獯稹肯嗤c(diǎn)：它們都是插入和刪除操作的位置受限制的線(xiàn)性表。不同點(diǎn)：棧是限定僅在表尾進(jìn)行插入和刪除的線(xiàn)性表，是后進(jìn)先出的線(xiàn)性表，而隊(duì)列是限定在表的一端進(jìn)行插入，在另一端進(jìn)行刪除的線(xiàn)性表，是先進(jìn)先出的線(xiàn)性表。9. 利用兩個(gè)棧S1和S2模擬一個(gè)隊(duì)列，如何利用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入和刪除操作，請(qǐng)簡(jiǎn)述算法思想?！窘獯稹坷脙蓚€(gè)棧S1和S2模擬一個(gè)隊(duì)列，當(dāng)需要向隊(duì)列中插入一個(gè)元素時(shí)，用S1來(lái)存放已輸入的元素，即通過(guò)向棧S1執(zhí)行入棧操作來(lái)實(shí)現(xiàn)；當(dāng)需要從隊(duì)列中刪除元素時(shí)，則將S1中元素全部送入到S2中，再?gòu)腟2中刪除棧頂元素，最后再將S2中元素全部送入到S1中；判斷隊(duì)空的條件是：棧S1和S2同時(shí)為空。10. 設(shè)計(jì)算法把一個(gè)十進(jìn)