《c語言數(shù)據(jù)結(jié)構(gòu)》第3章棧和隊(duì)列自測(cè)卷答案_第1頁
《c語言數(shù)據(jù)結(jié)構(gòu)》第3章棧和隊(duì)列自測(cè)卷答案_第2頁
《c語言數(shù)據(jù)結(jié)構(gòu)》第3章棧和隊(duì)列自測(cè)卷答案_第3頁
免費(fèi)預(yù)覽已結(jié)束,剩余4頁可下載查看

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、題號(hào)一二三四五A總分題分151020202015100得分第3章棧和隊(duì)列自測(cè)卷答案姓名班級(jí)一、填空(每空1分,共15分)1. 【李春葆】向量、棧和隊(duì)列都是 線性 結(jié)構(gòu),可以在向量的 任何位置插入和刪除元素;對(duì)于棧只能在 棧頂 插入和刪除元素:對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首刪除元素。2. 棧是一種特殊的線性表,允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為棧底 。3. 隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算,在表的另一端進(jìn)行刪除運(yùn)算的線性表。4. 在一個(gè)循壞隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的前一個(gè) 位置。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中,隊(duì)滿時(shí)共有ml個(gè)元素。6. 向棧中

2、壓入元素的操作是先 移動(dòng)棧頂指針,后 存入元素 ,7. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí),其操作是先移動(dòng)隊(duì)首指針,后取出元素8. K00年統(tǒng)考題帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長度等于 0°解:head | L=head | 頭結(jié)點(diǎn) I R=hcad|二、判斷正誤(判斷下列概念的正確性,并作出簡要的說明。)(每小題1分,共10分) ( X ) 1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型,而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜 類型。借,線性表繪邏輯結(jié)構(gòu)概念,可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ),與元素?cái)?shù)據(jù)類型無關(guān)。(X ) 2.在表結(jié)構(gòu)中最常用的是線性表,棧和隊(duì)列不太常用。借,不一定吧?調(diào)用子程序或函數(shù)常用,CPU中也

3、用隊(duì)列。(V ) 3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表,是一種后進(jìn) 先出型結(jié)構(gòu)。(V ) 4.對(duì)于不同的使用者,一個(gè)表結(jié)構(gòu)既可以是棧,也可以是隊(duì)列,也可以是線性 表。正確,都是線性邏輯結(jié)構(gòu),棧和隊(duì)列其實(shí)是特殊的線性表,對(duì)運(yùn)算的定義略有不同而已。(X ) 5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。借,棧是邏輯結(jié)構(gòu)的概念,是特殊殊線性表,而鏈表是存儲(chǔ)結(jié)構(gòu)概念,二者不是同類項(xiàng)。(X ) 6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。借,他們都是線性邏輯結(jié)構(gòu),棧和隊(duì)列其實(shí)是特殊的線性表,對(duì)運(yùn)算的定義略有不同而已。(V ) 7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式,也可是鏈接方式。(V ) 8.兩個(gè)棧共享

4、一片連續(xù)內(nèi)存空間時(shí),為提高內(nèi)存利用率,減少溢出機(jī)會(huì),應(yīng)把 兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。(X ) 9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表,是一種先進(jìn)后出型結(jié) 構(gòu)。借,后半句不對(duì)。(X ) 10. 一個(gè)棧的輸入序列是12345,則棧的輸出序列不可能是12345c 錯(cuò),有可能。三、單項(xiàng)選擇題(每小題1分,共20分)(B ) 1. K00年元月統(tǒng)考題棧中元素的進(jìn)出原則是A.先進(jìn)先出 B.后進(jìn)先出 C.??談t進(jìn)D.棧滿則出(C ) 2. K李春葆若已知一個(gè)棧的入棧序列是1, 2, 3,,11,其輸出序列為pl, p2, p3,,pn,若 pl=n,則 pi 為A. i B. n

5、=i C. n-i+1D.不確定解釋:當(dāng)pl=n,即n是最先出棧的,根據(jù)棧的原理,n必定是最后入棧的,那么輸入順序 必定是1, 2, 3,,n,則出棧的序列是n,,3, 2, 1。(B ) 3. K李春葆判定一個(gè)棧ST (最多元素為mO)為空的條件是A . ST->top<>0B . ST->top=0C . ST->top<>mOD. ST->top=mO(B ) 4. K李春葆判定一個(gè)隊(duì)列QU (最多元素為mO)為滿隊(duì)列的條件是A . QU->iear QU->fiont = = mO B . QU->rear QU->

6、;fiont 1= mOC . QU->fiont = = QU->rearD . QU->fiont = = QU->rear+l(D ) 5.數(shù)組Q n 用來表示一個(gè)循環(huán)隊(duì)列,f為當(dāng)前隊(duì)列頭元素的前一位置,r為隊(duì)尾元素的位置,假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素的公 式為(A ) 1f;( B ) (n+f-i ) % n; ( C ) n+if;( D ) (n+r-f) %n6. 【98初程P71 從供選擇的答案中,選出應(yīng)填入下面敘述_內(nèi)的最確切的解答, 把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素al、a2、a3和a4,對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在

7、進(jìn)?;蜻M(jìn)隊(duì)操作時(shí),按al、a2、a3. a4次序每次進(jìn)入一個(gè)元素。假設(shè)?;蜿?duì)的初始狀態(tài)都是空。現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次,出棧一次,再進(jìn)棧兩次,出棧一次;這時(shí),第一次出棧得到的元素是一 A ,第二次出棧得到的元素是一 B 是:類似地,考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次,出隊(duì)一次,再進(jìn)隊(duì)兩次,出隊(duì)一次;這時(shí),第一次出隊(duì)得到的元素是 C ,第二次出隊(duì)得到的元素是 D 。經(jīng)操作后,最后在棧中或隊(duì)中的元素還有 E 個(gè)。供選擇的答案:AD: ©al a2 a3a4E: ®1230答:ABCDE = 2,4. 1, 2.27. 【94初程P75 從供選擇的答案中,選出應(yīng)填入下面

8、敘述?內(nèi)的最確切的解答,把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表,它的特點(diǎn)是 A 。設(shè)用一維數(shù)組Al,11來表示一個(gè)棧,An為 棧底,用整型變量T指示當(dāng)前棧頂位置,AT為棧頂元素。往棧中推入(PUSH) 一個(gè)新元 素時(shí),變量T的值E :從棧中彈出(POP) 一個(gè)元素時(shí),變量T的值C 。設(shè)???時(shí),有輸入序列a, b, c,經(jīng)過PUSH, POP, PUSH, PUSH, POP操作后,從棧中彈出的 元素的序列是_ D ,變量T的值是_ E °供選擇的答案:A:先進(jìn)先出后進(jìn)先出進(jìn)優(yōu)于出出優(yōu)于進(jìn)隨機(jī)進(jìn)出B, C:加1減1不變清0加2減2D: a,bb,cc,ab,ac,ba,cE:n

9、+1n+2n 11-1n-2答案:ABCDE=2. 2,1. 6. 4注總,向地址的高端生長,稱為向上生成堆棧;向地址低端生長叫向下生成堆棧,木題中底部為n,向地 址的低端遞減生成,稱為向下生成堆棧。8. 【91初程P77 從供選擇的答案中,選出應(yīng)填入下面敘述 ?內(nèi)的最確切的解答,把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否 A :在做退棧運(yùn)算時(shí),應(yīng)先判別棧是否 。 當(dāng)棧中元素為n個(gè),做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說明該棧的最大容量為C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的D分別設(shè)在這片內(nèi)存空間的兩端,供選擇的答案:A,B:空滿上

10、溢C:®n-lnn+1D:長度深度棧頂E:兩個(gè)棧的棧頂同時(shí)到達(dá)??胀闹行狞c(diǎn)點(diǎn)兩個(gè)棧的棧頂在達(dá)??臻g的某一位置相遇 一個(gè)棧的棧底答案:ABCDE=2, 1, 2, 4, 3這樣,只有當(dāng)E時(shí),才產(chǎn)生上溢。下溢n/2棧底其中一個(gè)棧的棧頂?shù)竭_(dá)??臻g的中心兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另四、簡答題(每小題4分,共20分)1. 【嚴(yán)題集3.2和3.11】說明線性表、棧與隊(duì)的異同點(diǎn)。劉答,相同點(diǎn):都是線性結(jié)構(gòu),都是邏輯結(jié)構(gòu)的概念.都可以用順序存儲(chǔ)或鏈表存儲(chǔ);棧和隊(duì)列是兩種特 殊的線性表,即受限的線性表,只是對(duì)插入、刪除運(yùn)算加以限制.不同點(diǎn):運(yùn)算規(guī)則不同,線性表為隨機(jī)存取,而棧是只允許在一瑞進(jìn)行

11、插入、刪除運(yùn)算,因而是后進(jìn)先 出表LIFO;隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算,因而是先進(jìn)先出表FIFO。 用途不同,堆棧用于子程調(diào)用和保護(hù)現(xiàn)場,隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。2. 【統(tǒng)考書P60 4-11,難于嚴(yán)題集3.1®設(shè)有編號(hào)為1, 2, 3, 4的四輛列車,順序進(jìn)入 一個(gè)棧式結(jié)構(gòu)的車站,具體寫出這四輛列車開出車站的所有可能的順序。劉答:至少有14種。 全進(jìn)之后再出情況,只有1種:4, 3, 2, 1 進(jìn)3個(gè)之后再出的情況,有3種,3,42,1 3,2,4,1 3,2,1,4 進(jìn)2個(gè)之后再出的情況,有5種,2,4,32,3.42,1, 3,4 2,

12、1.43 2,1,3,4 進(jìn)1個(gè)之后再出的情況,有5種,1,43,21,3,2,41,3421,2,3,41,2,4,33. 【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回文”,例如,'abba,和,abcba,是 回文,勺bcde'和ababab*則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī),請(qǐng)分析用線性 表、堆棧和隊(duì)列等方式正確輸出其回文的可能性?答:線性表是隨機(jī)存儲(chǔ),可以實(shí)現(xiàn),靠循環(huán)變量(J-)從表尾開始打印輸出:堆棧是后進(jìn)先出,也可以實(shí)現(xiàn),靠正序入棧、逆序出棧即可;隊(duì)列是先進(jìn)先出,不易實(shí)現(xiàn)。哪種方式最好,要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲(chǔ),則直接用線性表從 后往前讀

13、取即町,或?qū)⒍褩m旈_到數(shù)組末尾,然后直接用POP動(dòng)作實(shí)現(xiàn)。(但堆棧是先減 后壓還是)若正文是單鏈表形式存儲(chǔ),則等同于隊(duì)列,需開輔助空間,可以從鏈?zhǔn)组_始入棧,全部 壓入后再依次輸出。4. 【統(tǒng)考書P60 4-13】順序隊(duì)的“假溢出”是怎樣產(chǎn)生的?如何知道循環(huán)隊(duì)列是空還是滿? 答:一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界,不能再有入隊(duì)操作,但其實(shí)數(shù)組中還有空位擔(dān), 這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。窮外,解決隊(duì)滿隊(duì)空的辦法有三: 設(shè)擔(dān)一個(gè)布爾變呈以區(qū)別隊(duì)滿還是隊(duì)空: 浪費(fèi)一個(gè)元素的空間,用于區(qū)別隊(duì)滿還是隊(duì)空。 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)(即隊(duì)列長度)。我們常釆用法,即隊(duì)

14、頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?,而列一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志繪:f-rear隊(duì)滿標(biāo)志是:f-(r+l)%N5. 【統(tǒng)考書P60 4-14設(shè)循環(huán)隊(duì)列的容量為40 (序號(hào)從0到39),現(xiàn)經(jīng)過一系列的入隊(duì)和 出隊(duì)運(yùn)算后,有fiont=ll, rear=19; fiont=19, rear=ll;問在這兩種情況下,循環(huán)隊(duì)列中各有元素 多少個(gè)?答:用隊(duì)列長度計(jì)算公式:(N+rf)%N L= (40+19-11) % 40=8 L= (40+11-19) % 40=32五、閱讀理解(每小題5分,共20分。至少要寫出思路)1. 【嚴(yán)題集3.7®按照四則運(yùn)算加、減、乘、除和幕運(yùn)算(

15、t )優(yōu)先關(guān)系的慣例,并仿 照教材例32的格式,畫出對(duì)卞列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程:AEXC/D+E t F序號(hào)()PTR 棧OPND 棧當(dāng)前字符備注AB#c/D+EAFn(操作)1push(OPND/A,)2#Apush(OPTR/-f)3# Apush(OPND/Br)4n-ABpush(OPTR/ *z)5ABpushCOPND/CO6# 一類ABC歸約令T> = B*C7# -AT,pushCOPTR/f)8#-AT.push(OPND/Df)9«-/ATiD歸約令T: = T./D10»-/AT2歸約,令Tj = A-Tz11t2push

16、(OPTR/4-r)12« +t3push(OPND/E#)13# +t3epush()PTR/ f F)14# + *t3epush (OPND/D15# +豐t3ef歸約令T4=Ef F16# +t3t4歸約令t5=t,+t417#Tsreturn(T$)2. 【嚴(yán)題集3.3】寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為chai)。 void main()Stack S;Clw x,y;IiutStack(S);X=C;y=上;Push(S,x); Push(S,W); Push(S,y);Pop(S,x); Push(S;f); Push(S?x);Pop(S,x

17、); Push(S,s,);wlule(? StackEniptv(S) Pop(S、y);pnntf(y); ;Printf(x);答:輸出為“stack”。3. 【嚴(yán)題集3.12】寫出卞列程序段的輸出結(jié)果(隊(duì)列中的元素類型QElemType為char)。 void main()Queue Q; Init Queue (Q);Char x='e'y='c:EnQueue (Q/1V); EnQueue (Q/r5); EnQueue (Q,y);lf(sttop= ='C ) top;else tag=0;if (expi= =5 y )/*遇到訂,若棧頂是十

18、,則繼續(xù)處理,否則以不配對(duì)返回*/if(sttop= = top;else tag=0;if(expi=>)9/*遇到),若棧頂是則繼續(xù)處理,否則以不配對(duì)返回*/if(sttop= =cc top-;else tag=0;1+;if(top>0)tag=0; /*若棧不空,則不配對(duì)*/嚴(yán)題集對(duì)應(yīng)答案:3.19Status AllBrackets_Test(cliar *str)判別表達(dá)式中三種括號(hào)是否匹配LutStack(s);for(p=str;*p;p-H-)if(*P='(1l*P=''H*P='') push(s,*p);else if(*p=,)1|*p=T|*p=T)if(StackEmptv(s) retiim ERROR;pop(s,c);&c!=() return ERROR;if(*p=T&&c!=T) return ERROR;if(*p=丁&&c!=) r

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論