《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集第3章 棧和隊(duì)列

1、數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題練習(xí)題第3章棧和隊(duì)列15北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程組編制201131第3章棧和隊(duì)列棧和隊(duì)列一、一、選擇題選擇題1.1.棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（A）。）。A、順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)B、散列和索引方式、散列和索引方式C、鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組、鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D、線性鏈表結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)、線性鏈表結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)2.2.設(shè)

2、棧設(shè)棧ST用順序存儲(chǔ)結(jié)構(gòu)表示，則棧用順序存儲(chǔ)結(jié)構(gòu)表示，則棧ST為空的條件是（為空的條件是（B）A、ST.topST.basenD、ST.topST.base==n3.3.向一個(gè)棧頂指針為向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，則執(zhí)行（結(jié)點(diǎn)時(shí)，則執(zhí)行（C）（注：當(dāng)有頭結(jié)點(diǎn)選B）A、HSnext=sB、snext=HSnext；HSnext=sC、snext=HS；HS=sD、snext=HS；HS=HSnext4.4

3、.從一個(gè)棧頂指針為從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（C）（應(yīng)無(wú)頭結(jié)點(diǎn)）A、x=HS；HS=HSnextB、HS=HSnext；x=HSdataC、x=HSdata；HS=HSnextD、snext=Hs；Hs=HSnext5.5.表達(dá)式表達(dá)式a(bc)d的后綴表達(dá)式為（的后綴表達(dá)式為（B）A、abcddB、abcdC、abcdD、abcd6.6.

4、中綴表達(dá)式中綴表達(dá)式A（BCD）E的后綴形式是（的后綴形式是（D）A、ABCDEB、ABCDEC、ABCDED、ABCDE7.7.一個(gè)隊(duì)列的入列序列是一個(gè)隊(duì)列的入列序列是1，2，3，4，則隊(duì)列的輸出序列是（則隊(duì)列的輸出序列是（C）A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18.8.循環(huán)隊(duì)列循環(huán)隊(duì)列SQ采用數(shù)組空間采用數(shù)組空間SQ.base[0n1]存放其元素值，已知其頭尾指針分別是存放其元素值，已知其頭尾指針

5、分別是front和rear，則判定此循環(huán)，則判定此循環(huán)隊(duì)列為空的條件是（隊(duì)列為空的條件是（C）A、Q.rearQ.front==nB、Q.rearQ.front1==nC、Q.front==Q.rearD、Q.front==Q.rear19.9.循環(huán)隊(duì)列循環(huán)隊(duì)列SQ采用數(shù)組空間采用數(shù)組空間SQ.base[0n1]存放其元素值，已知其頭尾指針分別是存放其元素值，已知其頭尾指針分別是front和rear，則判定此循環(huán)，則判定此循環(huán)隊(duì)列為滿的

6、條件是（隊(duì)列為滿的條件是（C）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear1)%nD、Q.front!=(Q.rear1)%n10.10.若在一個(gè)大小為若在一個(gè)大小為6的數(shù)組上實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前的數(shù)組上實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，再加入兩個(gè)元素后，rear和front的

7、值分別為（的值分別為（B）A、1，5B、24C、4，2D、5，111.11.用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（A）位置）位置A、鏈頭、鏈頭B、鏈尾、鏈尾C、鏈中、鏈中12.12.判定一個(gè)鏈隊(duì)列判定一個(gè)鏈隊(duì)列Q（最多元素為（最多元素為n個(gè)）為空的條件是（個(gè)）為空的條件是（A）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear1)%nD、Q.fr

8、ont!=(Q.rear1)%n13.13.在鏈隊(duì)列在鏈隊(duì)列Q中，插入中，插入s所指結(jié)點(diǎn)需順序執(zhí)行的指令是（所指結(jié)點(diǎn)需順序執(zhí)行的指令是（B）A、Q.frontnext=s；f=sB、Q.rearnext=s；Q.rear=sC、snext=Q.rear；Q.rear=sD、snext=Q.front；Q.front=s14.14.在一個(gè)鏈隊(duì)列在一個(gè)鏈隊(duì)列Q中，刪除一個(gè)結(jié)點(diǎn)需要執(zhí)行的指令是（中，刪除一個(gè)結(jié)點(diǎn)需要執(zhí)行的指令是（C）數(shù)據(jù)數(shù)據(jù)結(jié)

9、構(gòu)課后練習(xí)題練習(xí)題第3章棧和隊(duì)列35北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程組編制2011316.循環(huán)隊(duì)列中元素個(gè)數(shù)為循環(huán)隊(duì)列中元素個(gè)數(shù)為rearfront。X7.一個(gè)棧的輸入序列是一個(gè)棧的輸入序列是1234，則在棧的輸出序列中可以得到，則在棧的輸出序列中可以得到4312。X8.一個(gè)棧的輸入序列是一個(gè)棧的輸入序列是1234，則在棧的輸出序列中可以得到，則在棧的輸出序列中可以得到1234。V9.若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則進(jìn)棧需要判

10、斷棧是否滿。若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則進(jìn)棧需要判斷棧是否滿。X10.若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧需要判斷棧是否空。若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧需要判斷棧是否空。V三、三、填空題填空題1.棧的特點(diǎn)是（棧的特點(diǎn)是（后進(jìn)先出后進(jìn)先出），隊(duì)列的特點(diǎn)是（），隊(duì)列的特點(diǎn)是（先進(jìn)先出先進(jìn)先出）。）。2.線性表、棧、隊(duì)列都是（線性）結(jié)構(gòu)，可以在線性表的（線性表、棧、隊(duì)列都是（線性）結(jié)構(gòu)，可以在線性表的（任意任意）位置插入和刪除元素；對(duì)于棧只能

11、在（）位置插入和刪除元素；對(duì)于棧只能在（棧頂）插入和刪除元素；對(duì)于隊(duì)列只能在（）插入和刪除元素；對(duì)于隊(duì)列只能在（隊(duì)尾隊(duì)尾）插入元素和在（隊(duì)首）位置刪除元素。）插入元素和在（隊(duì)首）位置刪除元素。3.有程序如下，則此程序的輸出結(jié)果（棧的元素類型是有程序如下，則此程序的輸出結(jié)果（棧的元素類型是SelemType為）是（）是（Stact）。）。voidmain()stacksxyinitstack(s)x=’c’y=’k’push(sx)pus

12、h(s’a’)push(sy)pop(sx)push(s’t’)push(sx)pop(sx)push(s’s’)while(!stackempty(s))pop(sy)printf(y)printf(x)4.在棧頂指針為在棧頂指針為HS的鏈棧中，判定棧空的條件是（的鏈棧中，判定棧空的條件是（HS==NULL）。）。5.向棧中壓入元素的操作是先（向棧中壓入元素的操作是先（存入元素存入元素）后（）后（移動(dòng)棧頂指針）。移動(dòng)棧頂指針）。6.對(duì)

13、棧進(jìn)行退棧操作是先（對(duì)棧進(jìn)行退棧操作是先（移動(dòng)棧頂指針移動(dòng)棧頂指針）后（）后（取出元素取出元素）。）。7.用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（O(1)）和（）和（O(n)）；若）；若只設(shè)尾指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（只設(shè)尾指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（O(1)）和（）和（O(1)）。）。8.從循環(huán)隊(duì)列中刪除

14、一個(gè)元素時(shí)，其操作是（從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是（先取出元素，再移動(dòng)頭指針先取出元素，再移動(dòng)頭指針）。）。9.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（當(dāng)前位置當(dāng)前位置）。）。10.在具有在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有（個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有（n1）個(gè)元素。）個(gè)元素。11.在HQ的鏈隊(duì)列中，判斷只有一個(gè)結(jié)點(diǎn)的條件是（的鏈隊(duì)列中，判斷只有一個(gè)結(jié)點(diǎn)的條件是（HQ.front

15、next=HQ.rear）。）。12.設(shè)棧設(shè)棧S和隊(duì)列和隊(duì)列Q的初始狀態(tài)為空，元素的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q。若這若這6個(gè)元素出隊(duì)列的順序是個(gè)元素出隊(duì)列的順序是b、d、c、f、e、a則棧則棧S的容量至少應(yīng)該是（的容量至少應(yīng)該是（3）。）。13.有程序如下，則此程序的輸出結(jié)果（隊(duì)列的元素類型是有程序如下，則此程序的輸出結(jié)果（隊(duì)列的元素類型是QSel