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

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

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

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

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

5、1. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)潔類型，而鏈表的每個(gè)結(jié)點(diǎn)可以 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)潔類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)困難類型。 是一個(gè)困難類型。 錯(cuò)，線性表是邏輯構(gòu)造概念，可以依次存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú) 錯(cuò)，線性表是邏輯構(gòu)造概念，可以依次存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。 關(guān)。〔 × 〕2. 在表構(gòu)造中最常用的是線性表，棧和隊(duì)列不太常用。 在表構(gòu)造中最常用的是線性表，棧和隊(duì)列不太常用。

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

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

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

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

10、半句不對(duì)。 錯(cuò)，后半句不對(duì)?！?× 〕10. 一個(gè)棧的輸入序列是 一個(gè)棧的輸入序列是 12345，那么棧的輸出序列不行能是 ，那么棧的輸出序列不行能是 12345。 L=head 頭結(jié) 頭結(jié) 點(diǎn)R=head head細(xì)心整理?xiàng)Ｊ且环N線性表，它的特點(diǎn)是 棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組 。設(shè)用一維數(shù)組 A[1,…,n]來(lái)表示一個(gè) 來(lái)表示一個(gè)棧， 棧，A[n]為棧底，用整型變量 為棧底，用整型變量 T 指

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

12、后，從棧中彈出的元素的序列是 D ，變量 ，變量 T 的值 的值是 E 。 供選擇的答案： 供選擇的答案： A： ① 先進(jìn)先出 先進(jìn)先出 ②后進(jìn)先出 ②后進(jìn)先出③進(jìn)優(yōu)于出 ③進(jìn)優(yōu)于出④出優(yōu)于進(jìn) ④出優(yōu)于進(jìn) ⑤ 隨機(jī) 隨機(jī)進(jìn)出 進(jìn)出 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留意，向地址的高端生長(zhǎng)，稱為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆 留意，向地址的高端生長(zhǎng)，稱為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，此題中底部為 棧，此題中底部為 n，向地址的低端遞減生成，稱為向下生成堆棧。 ，向地址的低端遞減生成，稱為向下

14、生成堆棧。8. 【91 初程 初程 P77】 從供選擇的答案中，選出應(yīng)填入下面表達(dá) 從供選擇的答案中，選出應(yīng)填入下面表達(dá) ？ 內(nèi)的最精 內(nèi)的最精確的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。 確的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 A ；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是 ；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為 。當(dāng)棧中元素為 n 個(gè)，做進(jìn)棧運(yùn)算

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

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

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

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

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