【文章內(nèi)容簡介】 位置的字符相等 【分析】例如abc≠abc ，abc≠bca。 2. 選擇題 ⑴ 若一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素是（ ）。 A 不確定 B ni C ni1 D ni+1 【解答】D 【分析】此時，輸出序列一定是輸入序列的逆序。 ⑵ 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素eeeeee6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是eeeeee1，則棧S的容量至少應該是（ ）。 A 6 B 4 C 3 D 2 【解答】C 【分析】由于隊列具有先進先出性，所以，此題中隊列形同虛設(shè)，即出棧的順序也是eeeeee1。 ⑶ 一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（ ）。 A 54321 B 45321 C 43512 D 12345 【解答】C 【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。 ⑷ 設(shè)計一個判別表達式中左右括號是否配對的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳 A 順序表 B 棧 C 隊列 D 鏈表 【解答】B 【分析】每個右括號與它前面的最后一個沒有匹配的左括號配對，因此具有后進先出性。 ⑸ 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應該是一個（ ）結(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 它們的邏輯結(jié)構(gòu)不一樣 B 它們的存儲結(jié)構(gòu)不一樣 C 所包含的運算不一樣 D 插入、刪除運算的限定不一樣 【解答】D 【分析】棧和隊列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含的運算都可能不同。 ⑻ 設(shè)數(shù)組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當S[n]全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（ ）。 A S1的棧底位置為0，S2的棧底位置為n1 B S1的棧底位置為0，S2的棧底位置為n/2 C S1的棧底位置為0，S2的棧底位置為n D S1的棧底位置為0，S2的棧底位置為1 【解答】A 【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注意C++中的數(shù)組下標是從0開始的。 ⑼ 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（ ）。 A 連接 B 模式匹配 C 求子串 D 求串長 【解答】B 3. 判斷題 ⑴ 有n個元素依次進棧，則出棧序列有(n1)/2種。 【解答】錯。應該有 種。 ⑵ 棧可以作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 【解答】對。只要操作滿足后進先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。 ⑶ 在棧滿的情況下不能做進棧操作，否則將產(chǎn)生“上溢”。 【解答】對。 ⑷ 在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear。 【解答】錯。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。 ⑸ 空串與空格串是相同的。 【解答】錯。空串的長度為零，而空格串的長度不為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è)Ｉ為進棧操作，Ｏ為入棧操作，則其操作序列為IIIOOOIOIO。 5. 舉例說明順序隊列的“假溢出”現(xiàn)象。 【解答】假設(shè)有一個順序隊列，如圖36所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊，就會產(chǎn)生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數(shù)組中還有2個存儲單元空閑，其下標分別為0和1。 6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。） 【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過程如圖37所示。 7． 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？（EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊）。 【解答】隊頭元素為5，隊尾元素為9。其執(zhí)行過程如圖38所示。 8．空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？ 【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?9. 算法設(shè)計 ⑴ 假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針。試設(shè)計相應的入隊和出隊的算法。 【解答】出隊操作是在循環(huán)鏈表的頭部進行，相當于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結(jié)點之后插入一個結(jié)點。由于循環(huán)鏈表不帶頭結(jié)點，需要處理空表的特殊情況。 入隊算法如下： 出隊算法如下： ⑵ 設(shè)順序棧S中有2n個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n1，…，a1，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n2，…，a2，a2n1，a2n3，…，a1，請設(shè)計算法實現(xiàn)該操作，要求空間復雜度和時間復雜度均為O(n)。 【解答】操作步驟為： ① 將所有元素出棧并入隊； ② 依次將隊列元素出隊，如果是偶數(shù)結(jié)點，則再入隊，如果是奇數(shù)結(jié)點，則入棧； ③ 將奇數(shù)結(jié)點出棧并入隊； ④ 將偶數(shù)結(jié)點出隊并入棧； ⑤ 將所有元素出棧并入隊； ⑥ 將所有元素出隊并入棧即為所求。 ⑶ 用順序存儲結(jié)構(gòu)存儲串S，編寫算法刪除S中第 i個字符開始的連續(xù)j個字符。 【解答】先判斷串S中要刪除的內(nèi)容是否存在，若存在，則將第i+j1之后的字符前移j個位置。算法如下： ⑷ 對于采用順序存儲結(jié)構(gòu)的串S，編寫一個函數(shù)刪除其值等于ch的所有字符。 【解答】從后向前刪除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下： ⑸ 對串的模式匹配KMP算法設(shè)計求模式滑動位置的next函數(shù)。 【解答】 學習自測及答案 1．在一個具有n個單元的順序棧中，假定以地址低端（即下標為0的單元）作為棧底，以top作為棧頂指針，當出棧時，top的變化為（ ）。 A 不變 B top=0。 C top=top1。 D top=top+1。 【解答】C 2．一個棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。 A edcba B cdeba C debca D abcde 【解答】C 3．從棧頂指針為top的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行（ ）。 A x=top。 top=topnext。 B x=topdata。 C top=topnext。 x=topdata。 D x=topdata。 top=topnext。 【解答】D 4．設(shè)元素1, 2, 3, P, A依次經(jīng)過一個棧，進棧次序為123PA，在棧的輸出序列中，有哪些序列可作為C++程序設(shè)計語言的變量名。 【解答】PA321, P3A21, P32A1, P321A, AP321 =I_ am_ a_ teacther，其長度為（ ）。 【解答】15 6．對于棧和隊列，無論它們采用順序存儲結(jié)構(gòu)還是鏈接存儲結(jié)構(gòu)，進行插入和刪除操作的時間復雜度都是（ ）。 【解答】Ｏ(1) 7．如果進棧序列為A、B、C、D，則可能的出棧序列是什么？ 答：共14種，分別是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA 8．簡述隊列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點和不同點。 【解答】相同點：它們都是插入和刪除操作的位置受限制的線性表。 不同點：棧是限定僅在表尾進行插入和刪除的線性表，是后進先出的線性表，而隊列是限定在表的一端進行插入，在另一端進行刪除的線性表，是先進先出的線性表。 9. 利用兩個棧S1和S2模擬一個隊列，如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算法思想。 【解答】利用兩個棧S1和S2模擬一個隊列，當需要向隊列中插入一個元素時，用S1來存放已輸入的元素，即通過向棧S1執(zhí)行入棧操作來實現(xiàn)；當需要從隊列中刪除元素時，則將S1中元素全部送入到S2中，再從S2中刪除棧頂元素，最后再將S2中元素全部送入到S1中；判斷隊空的條件是：棧S1和S2同時為空。 10. 設(shè)計算法把一個十進制整數(shù)轉(zhuǎn)換為二至九進制之間的任一進制數(shù)輸出。 【解答】算法基于原理：N=(N div d)d + N mod d （div為整除運算，mod為求余運算）。  11．假設(shè)一個算術(shù)表達式中可以包含三種括號：圓括號“（”和“）”，方括號“[”和“]”以及花括號“{”和“}”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達式中所含括號是否配對出現(xiàn)。 【解答】假設(shè)表達式已存入字符數(shù)組A[n]中，具體算法如下： 第 4 章 廣義線性表——多維數(shù)組和廣義表 課后習題講解 1. 填空 ⑴ 數(shù)組通常只有兩種運算：（ ）和（ ），這決定了數(shù)組通常采用（ ）結(jié)構(gòu)來實現(xiàn)存儲。 【解答】存取，修改，順序存儲 【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。 ⑵ 二維數(shù)組A中行下標從10到20，列下標從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是1000，則元素A[15][10]的存儲地址是（ ）。 【解答】1140 【分析】數(shù)組A中每行共有6個元素，元素A[15][10]的前面共存儲了(1510)6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。 ⑶ 設(shè)有一個10階的對稱矩陣A采用壓縮存儲，A[0][0]為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A[8][5]的存儲地址為（ ）。 【解答】d+41 【分析】元素A[8][5]的前面共存儲了(1+2+…+8)+5=41個元素。 ⑷ 稀疏矩陣一般壓縮存儲方法有兩種，分別是（ ）和（ ）。 【解答】三元組順序表，十字鏈表 ⑸ 廣義表((a), (((b),c)),(d))的長度是（ ），深度是（ ），表頭是（ ），表尾是（ ）。 【解答】3，4，(a)，((((b),c)),(d)) ⑹ 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是（ ）。 【解答】Head(Head(Tail(LS))) 2. 選擇題 ⑴ 二維數(shù)組A的每個元素是由6個字符組成的串，行下標的范圍從0~8，列下標的范圍是從0~9，則存放A至少需要（ ）個字節(jié)，A的第8列和第5行共占（ ）個字節(jié)，若A按行優(yōu)先方式存儲，元素A[8][5]的起始地址與當A按列優(yōu)先方式存儲時的（ ）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要906=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A[8][5]按行優(yōu)先存儲的起始地址為d+810+5=d+85，設(shè)元素A[i][j]按列優(yōu)先存儲的起始地址與之相同，則d+j9+i=d+85，解此方程，得i=4，j=9。 ⑵ 將數(shù)組稱為隨機存取結(jié)構(gòu)是因為（ ） A 數(shù)組元素是隨機的 B 對數(shù)組任一元素的存取時間是相等的 C 隨時可以對數(shù)組進行訪問 D 數(shù)組的存儲結(jié)構(gòu)是不定 【解答】B ⑶ 下面的說法中，不正確的是（ ） A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長的線性結(jié)構(gòu) C 除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等 D 數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操 【解答】C 【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)