(完整word版)第3章習(xí)題(帶答案)

1、1. 鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是 （） 。 A.插入操作更加方便 B.通常不會(huì)出現(xiàn)棧滿的情況 C.不會(huì)出現(xiàn)?？盏那闆r D.刪除操作更加方便 2. 在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的 （）。 A.前一個(gè)位置 B.后一個(gè)位置 C.隊(duì)頭元素位置 D.隊(duì)尾元素的前一位置 3. 設(shè) S 表示進(jìn)棧，X 表示出棧，則將 CABDB 執(zhí)行操作序列 SSXXSSXXS 后得到 ACDBBo 4. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是 0 至 m-1,其頭尾指針分別為 f 和 r,則其元素 個(gè)數(shù)為 _ 。 A. r-f B. r-f+1 C. （r-f）%m+1 D. （r-f+m）%m 5

2、. 判定一個(gè)循環(huán)隊(duì)列 Q （數(shù)組元素為 m 個(gè)）隊(duì)滿的條件為 _ 。 A . Q.front=Q.rear B. Q.front!=Q.rear C. Q.fro nt=（Q.rea 葉 1）%m 0 D. Q.fro nt!=（Q.rea 葉 1）%m 0 6. 長度為 m 的循環(huán)隊(duì)列 q 的隊(duì)滿條件為q.front=（q.rear+1）%m _，隊(duì)空條件為 q.fron t=q.rear 。 7. 隊(duì)列是一種特殊的線性表，它的特點(diǎn)是后進(jìn)先出。 （錯(cuò)） 8. 棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健?（對(duì)） 9. 循環(huán)隊(duì)列采用的存儲(chǔ)結(jié)構(gòu)為 順序存儲(chǔ)結(jié)構(gòu) ，其引入的目的是為了克

3、服_ 假溢出的現(xiàn)象 _ 。 10. 有六個(gè)元素 6, 5, 4, 3, 2，1 的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧 序列？（ ） A. 543612 B. 453126 C.346521 D. 234156 11. 棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。 （對(duì)） 12.鏈棧通常不會(huì)出現(xiàn)滿的情況。 （對(duì)） 13.往順序棧中插入一個(gè)元素時(shí)， 棧頂扌曰針疋（） 。 A)加 1 B) 減 1 C)不變 D清 0 14.棧和隊(duì)列的共同點(diǎn)是（） 。 A）都是先進(jìn)后出 B) 都是先進(jìn)先出 C）只允許在端點(diǎn)處插入和刪除兀素 D） 沒有共同點(diǎn) 15. 為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問

4、題， 通常設(shè)置一個(gè)打印緩沖區(qū)， 主機(jī)將要打印的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù) 據(jù)，該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是： A.棧 B. 圖 C.樹 D.隊(duì)列 16. 線性表、棧和隊(duì)列都是（線性）結(jié)構(gòu)，可以在線性表的（ 任意）位置插 入和刪除元素；對(duì)于棧只能在 （ 棧頂）插入和刪除元素；對(duì)于隊(duì)列只能在 （隊(duì)尾）插入和（ 隊(duì)頭）刪除元素。 17. 設(shè)棧 S 和隊(duì)列 Q 的初始狀態(tài)均為空，元素 a,b,c,d,e,f,g 依次進(jìn)入棧 S。若 每個(gè)元素出棧后立即進(jìn)入隊(duì)列，且 7 個(gè)元素出隊(duì)的順序是 b,d,c,f,e,a,g ，則棧 S 的容量至少是（）。 A.1 B.2 C.3 D.4

5、18. 在具有 n 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有（n-1 ）個(gè)元素。 19若一個(gè)棧的輸入序列為 1, 2,，100，則其輸出序列的第 2 個(gè)元素為 100 的輸出序列的種數(shù)是 _ 99 _ 。 20. 個(gè)棧的輸入序列為 123n，若輸出序列的第一個(gè)元素是 n，輸出第 i （1=i=n）個(gè)元素是（ ）。 A.不確定 B. n-i+1 C. i D. n-i 21. 若在一個(gè)大小為 6 的數(shù)組上實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear 和 front 的值分別 為 0 和 3,當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear 和 front 的值分 別為（ ） A 1，5 B、2, 4 C 、4，2 D

6、 、5，1 22. _ 棧的特點(diǎn)是先進(jìn)后出 _，隊(duì)列的特點(diǎn)是先進(jìn)先出 _ 。 23. 引起循環(huán)隊(duì)列隊(duì)尾位置發(fā)生變化的操作是（）。 A.入隊(duì)列 B. 出隊(duì)列 C.取隊(duì)尾元素 D.取隊(duì)頭元素 24. _ 設(shè)循環(huán)隊(duì)列 Q 采用順序存儲(chǔ)結(jié)構(gòu)，其最大存儲(chǔ)容量為 MAX 其頭指針和尾指 針分別為 Q.front 和 Q.rear， 則隊(duì)列 Q 為空的條件為 _ Q.front=Q.rear ，隊(duì) 列為滿的條件為 _ Q.front=（Q.rea 葉 1）%MAX _ 。 25. 在棧中，出棧操作的時(shí)間復(fù)雜度為（）。 A.O（log 2n） B.O（1） C.O（n） D.O（n 2） 26. 引起循環(huán)隊(duì)列

7、隊(duì)頭位置發(fā)生變化的操作是（） A. 出隊(duì)列 B. 入隊(duì)列 C. 取隊(duì)頭元素 D. 取隊(duì)尾元素 27在棧中，入棧操作的時(shí)間復(fù)雜度為 （ ） 。 A.O（n） B.O（n 2） C.O（log 2n） D.O（1） 28、棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）。 A、順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu) B 、散列和索引方式 C 、鏈表存儲(chǔ) 結(jié)構(gòu)和數(shù)組 D 、線性鏈表結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu) 29、 設(shè)棧 ST 用順序存儲(chǔ)結(jié)構(gòu)表示，則棧 ST 為空的條件是（ ） A、 ST.top-ST.base0 B、 ST.top-ST.base=0 C、 ST.top-ST.basen D 、 ST.top-ST.base

8、=n 30、 向一個(gè)棧頂指針為 HS 的鏈棧中插入一個(gè) s 結(jié)點(diǎn)時(shí)，則執(zhí)行（ ） A、 HS-next=s; B 、 s-next=HS-next;HS-next=s; C、 s-next=HS;HS=s; D、 s-next=HS;HS=HS-next; 31、 從一個(gè)棧頂指針為 HS 的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用 x 保存被刪除結(jié)點(diǎn)的值， 則執(zhí)行（ ） A、 x=HS;HS=HS-next; B 、 HS=HS-next;x=HS-data; C、 x=HS-data;HS=HS-next; D、 s-next=Hs;Hs=HS-next; 32、 消除遞歸（ ）需要使用棧。 A、一定 B、不

9、一定 33、 用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（ ）位置 A、鏈頭 B、鏈尾 C、鏈中 34、 判定一個(gè)鏈隊(duì)列 Q （最多元素為 n 個(gè)）為空的條件是（ ） A、 Q.front=Q.rear B、 Q.front!=Q.rear C 、 Q.front=（Q.rear+1）%n D、 Q.front!=（Q.rear+1）%n 35、 在鏈隊(duì)列 Q 中，插入 s 所指結(jié)點(diǎn)需順序執(zhí)行的指令是（ ） A、 Q.front-next=s;f=s; B、 Q.rear-next=s;Q.rear=s; C、 s-next=Q.rear;Q.rear=s; D 、 s-next=Q.front;Q.front=s; 36、 在一個(gè)