幫你掌握數(shù)據(jù)結(jié)構(gòu)(第三章系列經(jīng)典試題及答案)

1、細心整理第 3 章 棧和隊列 棧和隊列 一、填空題〔每空 一、填空題〔每空 1 分，共 分，共 15 分〕 分〕1. 向量、棧和隊列都是 向量、棧和隊列都是 線性 線性 構(gòu)造，可以在向量的 構(gòu)造，可以在向量的 任何 任何 位置插入和刪 位置插入和刪除元素；對于棧只能在 除元素；對于棧只能在 棧頂 棧頂 插入和刪除元素；對于隊列只能在 插入和刪除元素；對于隊列只能在 隊尾 隊尾 插入

2、和 插入和 隊首 隊首 刪除元素。 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 棧頂 。不允 。不允許插入和刪除運算的一端稱為 許插入和刪除運算的一端稱為 棧底 棧底 。3. 隊列 隊列 是被限定為只能在表的一端進展插入運算，在表的另一端進展刪除 是被限定為只能在表的一端進展插入運算，在表的另一端進展刪除

3、運算的線性表。 運算的線性表。 4. 在一個循環(huán)隊列中，隊首指針指向隊首元素的 在一個循環(huán)隊列中，隊首指針指向隊首元素的 前一個 前一個 位置。 位置。5. 在具有 在具有 n 個單元的循環(huán)隊列中，隊滿時共有 個單元的循環(huán)隊列中，隊滿時共有 n-1 個元素。 個元素。6. 向棧中壓入元素的操作是先 向棧中壓入元素的操作是先 存入元素 存入元素 ，后 ，后 移動棧頂指針 移動棧頂指針。7. 從循環(huán)隊列中刪除一個元素時，

4、其操作是 從循環(huán)隊列中刪除一個元素時，其操作是 先 移動隊首指針 移動隊首指針 ，后 ，后 取出元 取出元素 。8. 〖00 年統(tǒng)考題〗 年統(tǒng)考題〗帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于 帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于 0 。解： 解：二、判定正誤〔判定以下概念的正確性，并作出簡要的說明。 二、判定正誤〔判定以下概念的正確性，并作出簡要的說明。 〕 〔每題 〔每題 1 分，共 分，共 10分〕 分〕〔 × 〕

5、1. 線性表的每個結(jié)點只能是一個簡潔類型，而鏈表的每個結(jié)點可以 線性表的每個結(jié)點只能是一個簡潔類型，而鏈表的每個結(jié)點可以是一個困難類型。 是一個困難類型。 錯，線性表是邏輯構(gòu)造概念，可以依次存儲或鏈式存儲，與元素數(shù)據(jù)類型無 錯，線性表是邏輯構(gòu)造概念，可以依次存儲或鏈式存儲，與元素數(shù)據(jù)類型無關。 關。〔 × 〕2. 在表構(gòu)造中最常用的是線性表，棧和隊列不太常用。 在表構(gòu)造中最常用的是線性表，棧和隊列不太常用。

6、錯，不必需吧？調(diào)用子程序或函數(shù)常用， 錯，不必需吧？調(diào)用子程序或函數(shù)常用，CPU 中也用隊列。 中也用隊列?！?√ 〕3. 棧是一種對全部插入、刪除操作限于在表的一端進展的線性表， 棧是一種對全部插入、刪除操作限于在表的一端進展的線性表，是一種后進先出型構(gòu)造。 是一種后進先出型構(gòu)造。〔 √ 〕4. 對于不同的運用者，一個表構(gòu)造既可以是棧，也可以是隊列，也 對于不同的運用者，一個表構(gòu)造既可以是棧，也可以是隊列，也可以是線性表

7、。 可以是線性表。 正確，都是線性邏輯構(gòu)造，棧和隊列其實是特殊的線性表，對運算的定 正確，都是線性邏輯構(gòu)造，棧和隊列其實是特殊的線性表，對運算的定 義略有不同而已。 義略有不同而已?！?× 〕5. 棧和鏈表是兩種不同的數(shù)據(jù)構(gòu)造。 棧和鏈表是兩種不同的數(shù)據(jù)構(gòu)造。 錯，棧是邏輯構(gòu)造的概念，是特殊殊線性表，而鏈表是存儲構(gòu)造概念， 錯，棧是邏輯構(gòu)造的概念，是特殊殊線性表，而鏈表是存儲構(gòu)造概念， 二者不是同類項。 二者不是同類項。

8、〔 × 〕6. 棧和隊列是一種非線性數(shù)據(jù)構(gòu)造。 棧和隊列是一種非線性數(shù)據(jù)構(gòu)造。 錯，他們都是線性邏輯構(gòu)造，棧和隊列其實是特殊的線性表，對運算的 錯，他們都是線性邏輯構(gòu)造，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。 定義略有不同而已?！?√ 〕7. 棧和隊列的存儲方式既可是依次方式，也可是鏈接方式。 棧和隊列的存儲方式既可是依次方式，也可是鏈接方式。 〔 √ 〕8. 兩個棧共享一片連續(xù)內(nèi)存空間

9、時，為提高內(nèi)存利用率，削減溢出 兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，削減溢出時機，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。 時機，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。 〔 × 〕9. 隊是一種插入與刪除操作分別在表的兩端進展的線性表，是一種先 隊是一種插入與刪除操作分別在表的兩端進展的線性表，是一種先進后出型構(gòu)造。 進后出型構(gòu)造。錯，后

10、半句不對。 錯，后半句不對?！?× 〕10. 一個棧的輸入序列是 一個棧的輸入序列是 12345，那么棧的輸出序列不行能是 ，那么棧的輸出序列不行能是 12345。 L=head 頭結(jié) 頭結(jié) 點R=head head細心整理棧是一種線性表，它的特點是 棧是一種線性表，它的特點是 A 。設用一維數(shù)組 。設用一維數(shù)組 A[1,…,n]來表示一個 來表示一個棧， 棧，A[n]為棧底，用整型變量 為棧底，用整型變量 T 指

11、示當前棧頂位置， 指示當前棧頂位置，A[T]為棧頂元素。往棧中推 為棧頂元素。往棧中推入〔 入〔PUSH〕一個新元素時，變量 〕一個新元素時，變量 T 的值 的值 B ；從棧中彈出〔 ；從棧中彈出〔POP〕一個元素 〕一個元素時，變量 時，變量 T 的值 的值 C 。設?？諘r，有輸入序列 。設?？諘r，有輸入序列 a，b，c，經(jīng)過 ，經(jīng)過 PUSH，POP，PUSH，PUSH，POP 操作后，從棧中彈出的元素的序列是 操作

12、后，從棧中彈出的元素的序列是 D ，變量 ，變量 T 的值 的值是 E 。 供選擇的答案： 供選擇的答案： A： ① 先進先出 先進先出 ②后進先出 ②后進先出③進優(yōu)于出 ③進優(yōu)于出④出優(yōu)于進 ④出優(yōu)于進 ⑤ 隨機 隨機進出 進出 B，C： ① 加 1 ②減 ②減 1 ③不變 ③不變 ④清 ④清 0 ⑤ 加 2 ⑥減 2D：① ：① a,b ②b,c ③c,a ④b,a

13、 ⑤ c,b ⑥ a,cE：① ：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2答案： 答案：ABCDE=2, 2, 1, 6, 4留意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆 留意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，此題中底部為 棧，此題中底部為 n，向地址的低端遞減生成，稱為向下生成堆棧。 ，向地址的低端遞減生成，稱為向下

14、生成堆棧。8. 【91 初程 初程 P77】 從供選擇的答案中，選出應填入下面表達 從供選擇的答案中，選出應填入下面表達 ？ 內(nèi)的最精 內(nèi)的最精確的解答，把相應編號寫在答卷的對應欄內(nèi)。 確的解答，把相應編號寫在答卷的對應欄內(nèi)。在做進棧運算時，應先判別棧是否 在做進棧運算時，應先判別棧是否 A ；在做退棧運算時，應先判別棧是 ；在做退棧運算時，應先判別棧是否 B 。當棧中元素為 。當棧中元素為 n 個，做進棧運算

15、時發(fā)生上溢，那么說明該棧的最大容 個，做進棧運算時發(fā)生上溢，那么說明該棧的最大容量為 量為 C 。為了增加內(nèi)存空間的利用率和削減溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存 為了增加內(nèi)存空間的利用率和削減溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應將兩棧的 空間時，應將兩棧的 D 分別設在這片內(nèi)存空間的兩端，這樣，只有當 分別設在這片內(nèi)存空間的兩端，這樣，只有當 E 時，才產(chǎn)生上溢。 時，才產(chǎn)生上溢。 供選擇的答

16、案： 供選擇的答案：A，B：①空 ：①空 ② 滿 ③ 上溢 上溢 ④ 下溢 下溢C： ①n-1 ② n ③ n+1 ④ n/2D： ① 長度 長度 ②深度 ②深度 ③ 棧頂 棧頂 ④ 棧底 棧底E：①兩個棧的棧頂同時到達?？臻g的中心點 ：①兩個棧的棧頂同時到達?？臻g的中心點 ②其中一個棧的棧頂?shù)竭_?？?②其

17、中一個棧的棧頂?shù)竭_?？臻g的中心點 間的中心點 ③兩個棧的棧頂在達棧空間的某一位置相遇 ③兩個棧的棧頂在達?？臻g的某一位置相遇 ④兩個棧均不空，且一個棧的 ④兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底 棧頂?shù)竭_另一個棧的棧底答案： 答案：ABCDE＝2, 1, 2, 4, 3四、簡答題〔每題 四、簡答題〔每題 4 分，共 分，共 20 分〕 分〕1. 【嚴題集 【嚴題集 3.2①和 ①和 3.11①】

18、 ①】說明線性表、棧與隊的異同點。 說明線性表、棧與隊的異同點。答：一樣點：都是線性構(gòu)造，都是邏輯構(gòu)造的概念。都可以用依次存儲或鏈表存 答：一樣點：都是線性構(gòu)造，都是邏輯構(gòu)造的概念。都可以用依次存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加 儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加 以限制。 以限制。 不同點：①運算規(guī)那么不同，線性表為隨機存取，而棧是只允許在一端進展插

19、不同點：①運算規(guī)那么不同，線性表為隨機存取，而棧是只允許在一端進展插 入、刪除運算，因而是后進先出表 入、刪除運算，因而是后進先出表 LIFO；隊列是只允許在一端進展插入、另一 ；隊列是只允許在一端進展插入、另一端進展刪除運算，因而是先進先出表 端進展刪除運算，因而是先進先出表 FIFO。 ② 用途不同，堆棧用于子程調(diào)用和愛惜現(xiàn)場，隊列用于 用途不同，堆棧用于子程調(diào)用和愛惜現(xiàn)場，隊列用于多道作業(yè)處理 多道作業(yè)處理、指令存 、指令存放及