第4章棧與隊(duì)列自測(cè)卷答案

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁(yè)眉頁(yè)腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請(qǐng)聯(lián)系刪除，謝謝！一、填空題（每空1分，共15分）棧頂。n。先。0。L=headR=head頭結(jié)點(diǎn)（每小題1分，共10分）（×錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類(lèi)型無(wú)關(guān)。（×錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。（√（√正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。（×錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類(lèi)項(xiàng)。（×錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。（√（√（×錯(cuò)，后半句不對(duì)。（×。錯(cuò)，有可能。（每小題1分，共20分）為inn1－====－===1A==%%n？4和、ABCDEA：12③③3④02？A量TTBTC，DTE。A：①B：①加11④出優(yōu)于進(jìn)⑤0⑤加2⑥2DE⑤⑤③n④4n稱(chēng)為向下生成堆棧。ABnC？。DEAC：D：①②滿②n③③④④③④E3四、簡(jiǎn)答題（每小題4分，共20分）2限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。4劉答：至少有14種。①全進(jìn)之后再出情況，只有1種：4，3，21②進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3’’采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三：①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；②浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。③我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲兀硪粋€(gè)指