數據結構c版王紅梅版課后答案khdaw(編輯修改稿)

　

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