數(shù)據(jù)結(jié)構(gòu)試題精選（3）-應(yīng)用題_跨考網(wǎng)

應(yīng)用題

　　1. 名詞解釋：棧。【燕山大學(xué) 1999 一、1（2分）】【吉林工業(yè)大學(xué) 1999 一、3（2分）】

　　2. 名詞解釋：隊(duì)列【大連海事大學(xué)? 1996? 一、6 ( 1分 )】

　　3. 什么是循環(huán)隊(duì)列？【哈爾濱工業(yè)大學(xué) 2001 三、2（3分）】【河南大學(xué) 1998 一、4（3分）】

　　4. 假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。

　?。?）試指出判別給定序列是否合法的一般規(guī)則。

　?。?）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說明。

　　【東南大學(xué) 1992 二（10分）】

　　5. 有5 個(gè)元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有哪幾個(gè)？【西南交通大學(xué) 2000 】

　　6. 如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)序列:4 3 5 6 1 2和1 3 5 4 2 6;請(qǐng)說明為什么不能或如何才能得到?！疚錆h交通科技大學(xué) 1996 】

　　7. 若元素的進(jìn)棧序列為：A、B、C、D、E，運(yùn)用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E？為什么？【北京科技大學(xué) 1998? 一、2】

　　8. 設(shè)輸入序列為a,b,c,d,試寫出借助一個(gè)棧可得到的兩個(gè)輸出序列和兩個(gè)不能得到的輸出序列。

　　【北京科技大學(xué) 2001 一、4（2分）】

　　9. 設(shè)輸入序列為2，3，4，5，6，利用一個(gè)棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺?shí)現(xiàn)嗎？

　　【山東師范大學(xué) 1996 五、4（2分）】

　　10. 試證明：若借助棧由輸入序列1,2,…,n得到輸出序列為P1,P2,…,Pn（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使Pj<Pk<Pi。【上海交通大學(xué) 1998 二（15分）】

　　11. 設(shè)一數(shù)列的輸入順序?yàn)?23456，若采用堆棧結(jié)構(gòu)，并以A和D分別表示入棧和出棧操作，試問通過入出棧操作的合法序列。

　?。?） 能否得到輸出順序?yàn)?25641的序列。（5分）

　?。?） 能否得到輸出順序?yàn)?54623的序列。（5分） 【北方交通大學(xué) 1995? 一（10分）】

　　12.（1） 什么是遞歸程序？

　?。?） 遞歸程序的優(yōu)、缺點(diǎn)是什么？

　?。?） 遞歸程序在執(zhí)行時(shí)，應(yīng)借助于什么來完成？

　　（4） 遞歸程序的入口語句、出口語句一般用什么語句實(shí)現(xiàn)？【大連海事大學(xué) 1996二、4(4分)】

　　13. 設(shè)有下列遞歸算法:

　　FUNCTION? vol(n:integer):integer;

　　VAR??? x :integer:

　　BEGIN IF n=0 THEN? vol:=0

　　ELSE?? BEGIN read(x)；vol:=vol(n-1)+x；END；

　　END；

　　如該函數(shù)被調(diào)用時(shí)，參數(shù)n值為4,讀入的x值依次為5,3,4,2，函數(shù)調(diào)用結(jié)束時(shí)返回值vol為多少?用圖示描述函數(shù)執(zhí)行過程中，遞歸工作棧的變化過程?！?a target="_blank">北京工業(yè)大學(xué) 1998 四 (10分)】

　　14. 當(dāng)過程P遞歸調(diào)用自身時(shí)，過程P內(nèi)部定義的局部變量在P的2次調(diào)用期間是否占用同一數(shù)據(jù)區(qū)？為什么？【山東師范大學(xué) 1999 一、4 （4分）】

　　15. 試推導(dǎo)出當(dāng)總盤數(shù)為n的Hanoi塔的移動(dòng)次數(shù)。 【北京郵電大學(xué) 2001 四、3 （5分）】

　　16. 對(duì)下面過程寫出調(diào)用P(3)的運(yùn)行結(jié)果。

　　PROCEDURE p（w：integer）;

　　BEGIN

　　IF w>0 THEN

　　BEGIN

　　p(w-1);

　　writeln(w);{輸出W}

　　p(w-1）

　　END；

　　END；

　　【西北大學(xué) 2001 三、7】