PTA第三章棧與隊(duì)列練習(xí)題

1-1通過對堆棧S操作:Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。輸出得序列為:123。(2分)T

F作者:DS課程組單位:浙江大學(xué)1-2在用數(shù)組表示得循環(huán)隊(duì)列中,front值一定小于等于rear值。(1分)T

F作者:DS課程組單位:浙江大學(xué)1-3若一個(gè)棧得輸入序列為{1,2,3,4,5},則不可能得到{3,4,1,2,5}這樣得出棧序列。(2分)T

F作者:徐鏡春單位:浙江大學(xué)1-4Ifkeysarepushedontoastackintheorder{1,2,3,4,5},thenitisimpossibletoobtaintheoutputsequence{3,4,1,2,5}、(2分)T

F作者:徐鏡春單位:浙江大學(xué)1-5所謂“循環(huán)隊(duì)列”就是指用單向循環(huán)鏈表或者循環(huán)數(shù)組表示得隊(duì)列。(1分)T

F作者:DS課程組單位:浙江大學(xué)1-6Analgorithmtocheckforbalancingsymbolsinanexpressionusesastacktostorethesymbols、(1分)T

F2-1設(shè)棧S與隊(duì)列Q得初始狀態(tài)均為空,元素a、b、c、d、e、f、g依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,且7個(gè)元素出隊(duì)得順序就是b、d、c、f、e、a、g,則棧S得容量至少就是:(2分)1234作者:DS課程組單位:浙江大學(xué)2-2若元素a、b、c、d、e、f依次進(jìn)棧,允許進(jìn)棧、退棧操作交替進(jìn)行,但不允許連續(xù)三次進(jìn)行退棧工作,則不可能得到得出棧序列就是？(2分)bcaefdcbdaefdcebfaafedcb作者:DS課程組單位:浙江大學(xué)2-3設(shè)一個(gè)棧得輸入序列就是1、2、3、4、5,則下列序列中,就是棧得合法輸出序列得就是？(2分)32154512344513243125作者:DS課程組單位:浙江大學(xué)2-4令P代表入棧,O代表出棧。則將一個(gè)字符串3*a+b/c變?yōu)?a*bc/+得堆棧操作序列就是哪個(gè)？(例如將ABC變成BCA得操作序列就是PPOPOO。)(2分)PPPOOOPPOPPOOOPOPOPOPPOPPOOOPOPPOOPPOPOOPOPOPPOOPPOPPOOO作者:DS課程組單位:浙江大學(xué)2-5設(shè)一個(gè)堆棧得入棧順序就是1、2、3、4、5。若第一個(gè)出棧得元素就是4,則最后一個(gè)出棧得元素必定就是:(2分)1351或者5作者:DS課程組單位:浙江大學(xué)2-6為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題,通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出得數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)得邏輯結(jié)構(gòu)應(yīng)該就是？(1分)堆棧隊(duì)列樹圖作者:DS課程組單位:浙江大學(xué)2-7某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作,但僅允許在一端進(jìn)行出隊(duì)操作。若元素a、b、c、d、e依次入此隊(duì)列后再進(jìn)行出隊(duì)操作,則不可能得到得出隊(duì)序列就是:(2分)bacdedbaceecbaddbcae作者:DS課程組單位:浙江大學(xué)2-8若用大小為6得數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前front與rear得值分別為0與4。當(dāng)從隊(duì)列中刪除兩個(gè)元素,再加入兩個(gè)元素后,front與rear得值分別為多少？(2分)2與02與22與42與6作者:DS課程組單位:浙江大學(xué)2-10以下不就是棧得基本運(yùn)算得就是()。(2分)刪除棧頂元素刪除棧底元素判斷棧就是否為空將棧置為空棧作者:嚴(yán)冰單位:浙江大學(xué)城市學(xué)院2-11在一個(gè)鏈隊(duì)列中,front與rear分別為頭指針與尾指針,則插入一個(gè)結(jié)點(diǎn)s得操作為()。(2分)front=front->nexts->next=rear;rear=srear->next=s;rear=s;s->next=front;front=s;作者:楊斌單位:棗莊學(xué)院2-12依次在初始為空得隊(duì)列中插入元素a,b,c,d以后,緊接著做了兩次刪除操作,此時(shí)得隊(duì)頭元素就是()。(2分)abcd作者:楊斌單位:棗莊學(xué)院2-13當(dāng)用大小為N得數(shù)組存儲(chǔ)順序循環(huán)隊(duì)列時(shí),該隊(duì)列得最大長度為()。(2分)NN-1N+1N+2作者:楊斌單位:棗莊學(xué)院2-14判斷一個(gè)循環(huán)隊(duì)列QU(最多元素為MaxSize)為空得條件就是()。(2分)QU、front==QU、rearQU、front!=QU、rearQU、front==(QU、rear+1)%MaxSizeQU、front!=(QU、rear+1)%MaxSize作者:嚴(yán)冰單位:浙江大學(xué)城市學(xué)院2-15(neuDS)在隊(duì)列中存取數(shù)據(jù)元素得原則就是()。(2分)先進(jìn)先出先進(jìn)后出后進(jìn)先出沒有限制作者:徐婉珍單位:浙江大學(xué)2-16循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放其元素值,已知其頭尾指針分別就是front與rear,則當(dāng)前隊(duì)列中得元素個(gè)數(shù)就是()。(2分)(rear-front+m)%mrear-frontrear-front-1rear-front作者:楊斌單位:棗莊學(xué)院2-17若以1234作為雙端隊(duì)列得輸入序列,則既不能由輸入受限得雙端隊(duì)列得到,也不能由輸出受限得雙端隊(duì)列得到得就是()。(2分)1234413242314213作者:楊斌單位:棗莊學(xué)院2-18(neuDS)在鏈棧中,進(jìn)行出棧操作時(shí)()。(2分)需要判斷棧就是否滿需要判斷棧就是否為空需要判斷棧元素得類型無需對棧作任何操作作者:徐婉珍單位:廣東東軟學(xué)院2-19(neuDS)在棧中存取數(shù)據(jù)得原則就是()。(2分)先進(jìn)先出先進(jìn)后出后進(jìn)后出沒有限制作者:徐婉珍單位:廣東東軟學(xué)院2-20鏈?zhǔn)綏Ｅc順序棧相比,一個(gè)比較明顯得優(yōu)點(diǎn)就是()。(2分)插入操作更加方便通常不會(huì)出現(xiàn)棧滿得情況不會(huì)出現(xiàn)棧空得情況刪除操作更加方便作者:嚴(yán)冰單位:浙江大學(xué)城市學(xué)院2-21若(a-b)*(c+d)就是中序表達(dá)式,則其后序表達(dá)式就是()。(2分)abcd+*-ab-cd+*ab-*cd+a-bcd+*作者:嚴(yán)冰單位:浙江大學(xué)城市學(xué)院2-21LetPstandsforpushandOforpop、Whenusingastacktoconverttheinfixexpression3*2+8/4intoapostfixexpression,thestackoperationsequenceis:(3分)PPPOOOPOPOPOPOPPOOPPOOPO作者:DS課程組單位:浙江大學(xué)2-22Thepostfixexpressionofa*(b+c)-dis:(2分)abc+*d-abcd*+-abc*+d--+*abcd作者:DS課程組單位:浙江大學(xué)2-23現(xiàn)有隊(duì)列Q與棧S,初始時(shí)Q中得元素依次就是{1,2,3,4,5,6}(1在隊(duì)頭),S為空。若允許下列3種操作:(1)出隊(duì)并輸出出隊(duì)元素;(2)出隊(duì)并將出隊(duì)元素入棧;(3)出棧并輸出出棧元素,則不能得到得輸出序列就是:(2分)1,2,5,6,4,32,3,4,5,6,13,4,5,6,1,26,5,4,3,2,1作者:考研真題單位:浙江大學(xué)2-24Supposedthata,b,c,d,eandfarepushedontoastackinthegivenorder、Assumethatpushingandpoppingcanbedonealternatively,butnoconsecutivethreepoppingsareallowed、Thenamongthefollowing,theimpossiblepoppingsequenceis:(2分)bcaefdcbdaefdcebfaafedcb作者:DS課程組單位:浙江大學(xué)2-25GivenanemptystackSandanemptyqueueQ、Pushelements{1,2,3,4,5,6,7}onebyoneontoS、IfeachelementthatispoppedfromSisenqueuedontoQimmediately,andifthedequeuesequenceis{4,5,7,6,3,2,1},thentheminimumsizeofSmustbe:(2分)2345作者:MartinEster單位:浙江大學(xué)2-26Giventhepushingsequenceofastackas{6,5,4,3,2,1}、Amongthefollowing,theimpossiblepoppingsequenceis:(2分)234156346521543612453126作者:DS課程組單位:浙江大學(xué)2-27下列關(guān)于棧得敘述中,錯(cuò)誤得就是:(2分)采用非遞歸方式重寫遞歸程序時(shí)必須使用棧函數(shù)調(diào)用時(shí),系統(tǒng)要用棧保存必要得信息只要確定了入棧次序,即可確定出棧次序棧就是一種受限得線性表,允許在其兩端進(jìn)行操作僅1僅1、2、3僅1、3、4僅2、3、42 李文超 61、0 F(2、0