數(shù)據(jù)結構與算法第3章課后答案

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

2、遞歸函數(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ù)的公式為（）。page: 2The Home of jetmambo -第3 章

3、特殊線性表棧、隊列和串【解答】（rear-front+n） % n【分析】也可以是（rear-front ） % n，但rear-front的結果可能是負整數(shù)，而對一個負整數(shù)求模，其結果在不同的編譯器環(huán)境下可能會有所不同。用循環(huán)鏈表表示的隊列長度為n，若只設頭指針，則岀隊和入隊的時間復雜度分別是（）和（）。【解答】O ，O （n）【分析】在帶頭指針的循環(huán)鏈表中，岀隊即是刪除開始結點，這只需修改相應指針；入隊即是在終端結點的后面插入一個結點，這需要從頭指針開始查找終端結點的地址。【解答】數(shù)據(jù)元素的類型是一個字符 兩個串相等的充分必要條件是（）?！窘獯稹块L度相同且對應位置的字符相等【分析】例如&q

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

5、以，此題中隊列形同虛設，即岀棧的順序也是 e2、e4、e3、e6、e5、el。一個棧的入棧序列是 1, 2, 3 , 4, 5，則棧的不可能的輸岀序列是（）。A 54321 B 45321 C 43512 D 12345【解答】C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。page: 3The Home of jetmambo -第3 章 特殊線性表棧、隊列和串設計一個判別表達式中左右括號是否配對的算法，采用（）數(shù)據(jù)結構最佳A順序表B棧C隊列D鏈表【解答】B【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先岀

6、性。在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區(qū)，該緩沖區(qū)應該 是一個（）結構。A棧B隊列C數(shù)組D線性表【解答】B【分析】先進入打印緩沖區(qū)的文件先被打印，因此具有先進先岀性。一個隊列的入隊順序是 1, 2, 3 , 4,則隊列的輸岀順序是（）。A 4321 B 1234 C 1432 D 3241【解答】B【分析】隊列的入隊順序和岀隊順序總是一致的。 棧和隊列的主要區(qū)別在于（）。A它們的邏輯結構不一樣B它們的存儲結構不一樣C所包含的運算不一樣D插入、刪除運算的限定不一樣【解答】D別，任何數(shù)據(jù)結構在針對具體問題時包含的運算都可能不同。設數(shù)組Sn作為兩個棧S1和S2的存儲空間

7、，對任何一個棧只有當Sn全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（）。A S1的棧底位置為0, S2的棧底位置為n-1B S1的棧底位置為0，S2的棧底位置為n/2C S1的棧底位置為0，S2的棧底位置為nD S1的棧底位置為0，S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注意C+中的數(shù)組下標是從0開始的。 設有兩個串p和q，求q在P中首次岀現(xiàn)的位置的運算稱作（）。A連接B模式匹配C求子串D求串長【解答】Bpage: 4The Home of jetmambo -第3 章 特殊線性表棧、隊列和串3. 判斷

8、題 有n個元素依次進棧，則岀棧序列有（n-1）/2種。2【解答】錯。應該有 ' 種。棧可以作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)結構?！窘獯稹繉?。只要操作滿足后進先岀性，都可以采用棧作為輔助數(shù)據(jù)結構。 在棧滿的情況下不能做進棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉Α?在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是 fron t=rear 。【解答】錯。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開?？沾c空格串是相同的。【解答】錯?？沾拈L度為零，而空格串的長度不為0,其長度是串中空格的個數(shù)。4. 設有一個棧，元素進棧的次序為A，B，C，

9、D, E,能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。 C，E, A，B, D C , B, A, D, E【解答】不能，因為在 C、E出棧的情況下，A定在棧中，而且在 B的下面，不可能先于 B岀棧。 可以，設I為進棧操作，0為入棧操作，則其操作序列為HI000I0I0。5. 舉例說明順序隊列的“假溢岀”現(xiàn)象?！窘獯稹考僭O有一個順序隊列，如圖3-6所示，隊尾指針rear=4，隊頭指針front=1 ，如果再有元素入隊，就會產(chǎn)生“上溢”，此時的“上溢”又稱為“假溢岀”，因為隊列并不是真的溢岀了，存儲隊列的數(shù)組 中還有2個存儲單元空閑，其下標分別為 0和1。3-6順序嘰列的慚溢

10、岀page: 5The Home of jetmambo - 第3 章 特殊線性表棧、隊列和串6. 在操作序列 push、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧 底元素分別是什么？ ( push(k)表示整數(shù)k入棧，pop表示棧頂元素岀棧。)【解答】棧頂元素為 6,棧底元素為1。其執(zhí)行過程如圖3-7所示。出挨(a) push (1) > pushQ)(b)pop > push (5) t pushC?) (c) pep jg3-7棧的執(zhí)存過程示意圖7. 在操作序列 EnQueue(1)、EnQueue(3)、DeQueue、

11、EnQueue(5)、EnQueue7)、DeQueue EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？( EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素岀隊)【解答】隊頭元素為 5,隊尾元素為9。其執(zhí)行過程如圖3-8所示。(ai) EnQueue (1) jEnQu&iie G) (b) DeQueue jEnQueue (5) jEnQueue C7)(c) DeQueue jEnQueue(5)S3-3臥列的執(zhí)行過程示意圖8空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空

12、格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符?？勺鳛槿我獯淖哟?.算法設計 假設以不帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和岀隊的算法?！窘獯稹繉珀牪僮魇窃谘h(huán)鏈表的頭部進行，相當于刪除開始結點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結點之后插入一個結點。由于循環(huán)鏈表不帶頭結點，需要處理空表的特殊情況。 入隊算法如下：碼環(huán)隊刪入隊算法Enqueuetemplate <c3ass T>void Enqueue(Node<T> 嚀ear, T

13、 盟)if Crear- gJLL) "處理空表的特殊情況rear=s, rear->nesi=s;dse "處理除空表以外的一般情況s - >next=rcar- >nesrt;rear->next=s;rearms,)岀隊算法如下:循環(huán)隊列出 隊算法 Dequeue template <class T>T Dequeue (Node<T> *rear)if (rcar= =NULL) throw underflow", 舞!|斷表空 dse if Cs=rear)rcar-NULLr熾表中只有一平結點else r

14、ear->nezt=s->n毗delete s;) 設順序棧S中有2n個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，al，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，a2，a2n-1，a2n-3，al,請設計算法實現(xiàn)該操作，要求空間復雜度和時間復雜度均為0(n)?！窘獯稹坎僮鞑襟E為： 將所有元素岀棧并入隊； 依次將隊列元素岀隊，如果是偶數(shù)結點，則再入隊，如果是奇數(shù)結點，則入棧； 將奇數(shù)結點岀棧并入隊； 將偶數(shù)結點岀隊并入棧； 將所有元素岀棧并入隊； 將所有元素岀隊并入棧即為所求。用順序存儲結構存儲串 S,編寫算法刪除S中第i個字符開始

15、的連續(xù)j個字符?！窘獯稹肯扰袛啻甋中要刪除的內(nèi)容是否存在，若存在，則將第 i+j-1之后的字符前移j個位置 算法如下：串刪除算法Delvoid DeKchar S, tnt ； int j)償?俎0號單元存放串的底度 if (i+j<SO) fa- (k-i;k<S0;k+)$疔陰；嗣刑OJ-j;ei鷄慘數(shù)非法"； 對于采用順序存儲結構的串S,編寫一個函數(shù)刪除其值等于ch的所有字符?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下：申刪徐void Del (char STcharch) 熾姐的0

16、號單元存戲串的長度for (i=S0I;i>0J)if (Si=wch) for(j+lj<=S0J+)刪一;)對串的模式匹配KM算法設計求模式滑動位置的next函數(shù)。【解答】參見325學習自測及答案1 在一個具有n個單元的順序棧中，假定以地址低端(即下標為0的單元)作為棧底，以top作為棧頂指針，當出棧時，top的變化為()。page: 7The Home of jetmambo - 第3 章 特殊線性表棧、隊列和串A 不變 B top=0; C top=top-1; D top=top+1;2.個棧的入棧序列是 a, b, c, d, e，則棧的不可能的岀棧序列是（）。A ed

17、cba B cdeba C debca D abcde【解答】C3從棧頂指針為top的鏈棧中刪除一個結點，用x保存被刪除結點的值，則執(zhí)行（ ）。A x=top; top=top->n ext; B x=top->data;C top=top->n ext; x=top->data; D x=top->data; top=top->n ext;【解答】D4設元素1, 2, 3, P, A 依次經(jīng)過一個棧，進棧次序為 123PA在棧的輸岀序列中，有哪些序列 可作為C+程序設計語言的變量名。【解答】PA321, P3A21, P32A1, P321A, AP321

18、5.設 S="l_ am_ a_ teacther"，其長度為（）?！窘獯稹?56 對于棧和隊列，無論它們采用順序存儲結構還是鏈接存儲結構，進行插入和刪除操作的時間 復雜度都是（）°【解答】O7 如果進棧序列為 A、B、C、D,則可能的岀棧序列是什么？答：共14種，分別是:ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA8 簡述隊列和棧這兩種數(shù)據(jù)結構的相同點和不同點?！窘獯稹肯嗤c：它們都是插入和刪除操作的位置受限制的線性表。不同點：棧是限定僅在表尾進行插入和刪除的線性表，是

19、后進先岀的線性表，而隊列是限定在表的一端進行插入，在另一端進行刪除的線性表，是先進先出的線性表。9. 利用兩個棧S俐S2模擬一個隊列，如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算 法思想?！窘獯稹坷脙蓚€棧S1和 S2模擬一個隊列，當需要向隊列中插入一個元素時，用S1來存放已輸入的元素，即通過page: 8The Home of jetmambo - 第3 章 特殊線性表棧、隊列和串向棧S1執(zhí)行入棧操作來實現(xiàn)；當需要從隊列中刪除元素時，則將S1中元素全部送入到S2中,再從S2中刪除棧頂元素，最后再將S2中元素全部送入到 S1中；判斷隊空的條件是：棧S俐S2同時為空。10. 設計算法把一個

20、十進制整數(shù)轉(zhuǎn)換為二至九進制之間的任一進制數(shù)輸出?！窘獯稹克惴ɑ谠恚篘=（N div d） x d + N mod d （div為整除運算，moc為求余運算）。11 假設一個算術表達式中可以包含三種括號：圓括號“(”和“)”，方括號“”和“”以及花括號“ ”和“ ”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達式中所含括號是否配對 出現(xiàn)。【解答】假設表達式已存入字符數(shù)組An中，具體算法如下：括號匹配算法Prmlvoid ProoKchar A tnt n)topl;i=0; flag 1,while (i<n && flag)(if(AH=riiAi=ris

21、+u)p戶州i+；else switchAi(case')1 if(top=*l 11 Stop !=' C) flag MJ; break;caseif (top=-1 | | Stap-'-!-) fla=0; break; case1)1 if (topi | Stop !=f) flag-0, break;)i+；Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the

22、 soft lookYour eyes had once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you.And loved the sorrows of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how