數(shù)據(jù)結(jié)構(gòu)與算法課后答案

1、第 3 章 特殊線性表棧、隊列和串(2005-07-14) -第 3 章 特殊線性表棧、隊列和串 課后習(xí)題講解1. 填空 設(shè)有一個空棧，棧頂指針為1000H,現(xiàn)有輸入序列為1、2、3、4、5,經(jīng)過push , push , pop, push , pop, push , push后，輸岀序列是()，棧頂指針為()?！窘獯稹?23， 1003H 棧通常采用的兩種存儲結(jié)構(gòu)是( )；其判定?？盏臈l件分別是( ),判定棧滿的條件分別 是( )?！窘獯稹宽樞虼鎯Y(jié)構(gòu)和鏈接存儲結(jié)構(gòu)(或順序棧和鏈棧)，棧頂指針top= -1和top=NULL，棧頂指針 top 等于數(shù)組的長度和內(nèi)存無可用空間3()可作為實現(xiàn)

2、遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進先岀性。 表達式 a*(b+c)-d 的后綴表達式是( )?！窘獯稹?abc+*d-【分析】 將中綴表達式變?yōu)楹缶Y表達式有一個技巧： 將操作數(shù)依次寫下來, 再將算符插在它的兩個操作數(shù)的后面。 棧和隊列是兩種特殊的線性表,棧的操作特性是(),隊列的操作特性是( ),棧和隊列的主要區(qū)別在于()?！窘獯稹亢筮M先岀,先進先岀,對插入和刪除操作限定的位臵不同 循環(huán)隊列的引入是為了克服( )?！窘獯稹考僖鐚?數(shù)組 Qn 用來表示一個循環(huán)隊列, front 為隊頭元素的前一個位臵, rear 為隊尾元素的位臵, 計算隊列中元素個數(shù)

3、的公式為( )。page: 2The Home of jetmambo - 第 3 章 特殊線性表棧、隊列和串【解答】( rear-front+n ) % n【分析】也可以是(rear-front ) % n,但rear-front的結(jié)果可能是負整數(shù)，而對一個負整數(shù)求模,其結(jié)果在不同的編譯器環(huán)境下可能會有所不同。用循環(huán)鏈表表示的隊列長度為n,若只設(shè)頭指針，則岀隊和入隊的時間復(fù)雜度分別是()和( )?！窘獯稹縊 ,O (n)【分析】在帶頭指針的循環(huán)鏈表中,岀隊即是刪除開始結(jié)點,這只需修改相應(yīng)指針；入隊即是在終端結(jié)點的后面 插入一個結(jié)點,這需要從頭指針開始查找終端結(jié)點的地址。 串是一種特殊的線性表

4、,其特殊性體現(xiàn)在()。【解答】數(shù)據(jù)元素的類型是一個字符 兩個串相等的充分必要條件是（ ）。【解答】長度相同且對應(yīng)位臵的字符相等【分析】例如"abc"工"abc "，“abc"工"bca"。2. 選擇題若一個棧的輸入序列是1,2, 3,，n,輸岀序列的第一個元素是n,則第i個輸岀元素是（）。A 不確定 B n-i C n-i-1 D n-i+1【解答】 D【分析】此時,輸岀序列一定是輸入序列的逆序。 設(shè)棧S和隊列C的初始狀態(tài)為空，元素 el、e2、e3、e4、e5、e6依次通過棧S, 一個元素岀棧后 即進入隊列Q若6個元素岀隊

5、的順序是 e2、e4、e3、e6、e5、el,則棧S的容量至少應(yīng)該是（）。A 6B 4C 3D 2【解答】 C【分析】 由于隊列具有先進先岀性， 所以， 此題中隊列形同虛設(shè)， 即岀棧的順序也是 e2、 e4、 e3、e6、 e5、 e1 。 一個棧的入棧序列是 1 ，2，3，4，5，則棧的不可能的輸岀序列是（）。A 54321 B 45321 C 43512 D 12345【解答】 C【分析】 此題有一個技巧： 在輸岀序列中任意元素后面不能岀現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。page: 3The Home of jetmambo - 第 3 章 特殊線性表棧、隊列和串 設(shè)計

6、一個判別表達式中左右括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳A 順序表 B 棧 C 隊列 D 鏈表【解答】 B 【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先岀性。 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)臵一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。A棧B隊列C數(shù)組D線性表【解答】 B【分析】先進入打印緩沖區(qū)的文件先被打印，因此具有先進先岀性。 一個隊列的入隊順序是1，2，3，4，則隊列的輸岀順序是（）。A 4321 B 1234 C 1432 D 3241【解答】 B【分析】隊列的入隊順序和岀隊順序總是一致的。 棧和隊列的主要區(qū)別在于（ ）。A 它們的

7、邏輯結(jié)構(gòu)不一樣 B 它們的存儲結(jié)構(gòu)不一樣C 所包含的運算不一樣 D 插入、刪除運算的限定不一樣【解答】 D【分析】 棧和隊列的邏輯結(jié)構(gòu)都是線性的， 都有順序存儲和鏈接存儲， 有可能包含的運算不一樣， 但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含的運算都可能不同。設(shè)數(shù)組Sn作為兩個棧S1和S2的存儲空間，對任何一個棧只有當Sn全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（）。A S1的棧底位臵為0, S2的棧底位臵為n-1B S1的棧底位臵為0, S2的棧底位臵為n/2C S1的棧底位臵為0，S2的棧底位臵為nD S1的棧底位臵為0，S2的棧底位臵為1【解答】A【分析】兩棧共享空

8、間首先兩個棧是相向增長的，棧底應(yīng)該分別指向兩個棧中的第一個元素的位臵，并注意C+沖的數(shù)組下標是從0開始的。 設(shè)有兩個串p和q，求q在p中首次岀現(xiàn)的位臵的運算稱作（）。A連接B模式匹配C求子串D求串長【解答】Bpage: 4The Home of jetmambo - 第3 章 特殊線性表棧、隊列和串3. 判斷題 有n個元素依次進棧，則岀棧序列有（n-1）/2種。2【解答】錯。應(yīng)該有 -' 種。棧可以作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹繉?。只要操作滿足后進先岀性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。 在棧滿的情況下不能做進棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉?。 在循環(huán)隊列中，front指

9、向隊頭元素的前一個位臵，rear指向隊尾元素的位臵，則隊滿的條件是 fron t=rear 。【解答】錯。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開?？沾c空格串是相同的?！窘獯稹垮e。空串的長度為零，而空格串的長度不為0,其長度是串中空格的個數(shù)。4. 設(shè)有一個棧，元素進棧的次序為A，B，C，D, E,能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。 C , E, A, B, D C , B, A, D, E【解答】不能，因為在 C、E出棧的情況下，A定在棧中，而且在 B的下面，不可能先于 B岀棧 可以，設(shè)I為進棧操作，0為入棧操作，則其操作序列為HI000I

10、0I0。5. 舉例說明順序隊列的“假溢岀”現(xiàn)象?！窘獯稹考僭O(shè)有一個順序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1 ，如果再有元素入隊，就會產(chǎn)生“上溢”，此時的“上溢”又稱為“假溢岀”，因為隊列并不是真的溢岀了，存儲隊列的數(shù)組 中還有2個存儲單元空閑，其下標分別為 0和13-6順序肚列的同溢岀page: 5The Home of jetmambo - 第3 章 特殊線性表棧、隊列和串6.在操作序列 push、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧 底元素分別是什么？ ( push(k)表示整數(shù)k入棧，pop表示棧頂

11、元素岀棧。)【解答】棧頂元素為 6,棧底元素為1。其執(zhí)行過程如圖3-7所示。入棧f7625511I(a) push (1 r push (2)fb) pop r> pushC?)何 pop j push 棧的執(zhí)行過程示意團7.在操作序列 EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue7)、DeQueue EnQueue(9)之后,隊頭元素和隊尾元素分別是什么？( EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素岀隊)【解答】隊頭元素為 5,隊尾元素為9。其執(zhí)行過程如圖3-8所示。(ai) EnQueue (1) jEnQue

12、ne Gi(b) DeQueue *EnQueuie C5) jEnQueue 0)(c) DeQueue jEnQueue (?)®3-3趴列的執(zhí)行過程示意圖8空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應(yīng)包括這些空格符。空串在串處理中可作為任意串的子串。9. 算法設(shè)計 假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針。試設(shè)計相應(yīng)的入隊和岀隊的算法?！窘獯稹繉珀牪僮魇?/p>

13、在循環(huán)鏈表的頭部進行，相當于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結(jié)點之后插入一個結(jié)點。由于循環(huán)鏈表不帶頭結(jié)點，需要處理空表的特殊情況。 入隊算法如下：縉環(huán)隊別入隊算法Enqueuetemplate <c3ass T>void Enqueue(Node<T> 嚀ear, T 盟)s=new NddxTn,S">daU=xJif Create FULL) 誡t理空表的特殊情況rear=s, rear->nesi=s;dse "處理除空表以外的一般情況s - >next=rcar- >nesrt;rear-&

14、gt;next=s;rearms,)岀隊算法如下：循環(huán)隊列出 隊算法 Dequeue template <class T>T Dequeue (Node<T> *reai)if (rear= =NULL) throw unclerflow", 妙|斷表空 dse if Cs=rear)rcar-NULLr熾表中只有一平結(jié)點else rear->nezt=s->n毗delete s; 設(shè)順序棧S中有2n個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，al，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，a2，

15、a2n-1，a2n-3，al,請設(shè)計算法實現(xiàn)該操作，要求空間復(fù)雜度和時間復(fù)雜度均為0(n)?！窘獯稹坎僮鞑襟E為： 將所有元素岀棧并入隊； 依次將隊列元素岀隊，如果是偶數(shù)結(jié)點，則再入隊，如果是奇數(shù)結(jié)點，則入棧； 將奇數(shù)結(jié)點岀棧并入隊； 將偶數(shù)結(jié)點岀隊并入棧； 將所有元素岀棧并入隊； 將所有元素岀隊并入棧即為所求。用順序存儲結(jié)構(gòu)存儲串 S,編寫算法刪除S中第i個字符開始的連續(xù)j個字符?！窘獯稹肯扰袛啻甋中要刪除的內(nèi)容是否存在，若存在，則將第 i+j-1之后的字符前移j個位臵 算法如下：串刪除算法Delvoid Del (char S, int i, intj)傲組0號單元存放串的長度(if G+j

16、<SO)(for (kM；k<S0,k+) 購=S圈dsecout<<" 數(shù)非法"， 對于采用順序存儲結(jié)構(gòu)的串S，編寫一個函數(shù)刪除其值等于ch的所有字符?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下：申刪徐站Ed*void Del (char STctach) 熾姐的0號單元存戲串的長屋for (i=S0I;i>0J)if (Si=三ch) for(j+lj<=S0;j+)SD'1-SDL級葉；)對串的模式匹配KM算法設(shè)計求模式滑動位臵的next函數(shù)

17、?！窘獯稹繀⒁?25學(xué)習(xí)自測及答案1 在一個具有n個單元的順序棧中，假定以地址低端(即下標為0的單元)作為棧底，以top作為棧頂指針，當出棧時，top的變化為()。page: 7The Home of jetmambo - 第3 章 特殊線性表棧、隊列和串A 不變 B top=0; C top=top-1; D top=top+1;【解答】C2.個棧的入棧序列是a, b, c, d, e，則棧的不可能的岀棧序列是()。A edcba B cdeba C debca D abcde【解答】C3從棧頂指針為top的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行()。A x=top; top=t

18、op->n ext; B x=top->data;C top=top->n ext; x=top->data; D x=top->data; top=top->n ext;【解答】D4 設(shè)元素1, 2, 3, P, A依次經(jīng)過一個棧，進棧次序為123PA在棧的輸岀序列中，有哪些序列可作為C+程序設(shè)計語言的變量名?！窘獯稹縋A321, P3A21, P32A1, P321A, AP3215.設(shè) S="l_ am_ a_ teacther"，其長度為()?！窘獯稹?56 對于棧和隊列，無論它們采用順序存儲結(jié)構(gòu)還是鏈接存儲結(jié)構(gòu)，進行插入和刪除操

19、作的時間 復(fù)雜度都是()°【解答】O7 如果進棧序列為 A、B、C、D,則可能的岀棧序列是什么？答：共14種，分別是:ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA8 簡述隊列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點和不同點?！窘獯稹肯嗤c：它們都是插入和刪除操作的位臵受限制的線性表。不同點：棧是限定僅在表尾進行插入和刪除的線性表，是后進先岀的線性表，而隊列是限定在表的一端進行插入，在另一端進行刪除的線性表，是先進先出的線性表。9. 利用兩個棧S俐S2模擬一個隊列，如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算 法思想。【解答】利用兩個棧S1和 S2模擬一個隊列，當需要向隊列中插入一個元素時，用S1來存放已輸入的元素，即通過page: 8The Home of jetmambo - 第3 章 特殊線性表棧、隊列和串向棧S1執(zhí)行入棧操作來實現(xiàn)；當需要從隊列中刪除元素時，則將S1中元素全部送入到S