數(shù)據(jù)結(jié)構(gòu)第3章自測卷

1、第3章 棧和隊列 自測卷 姓名 袁忠楊 班級 09計算機1班 題號一二三四五六總分題分151020202015100得分一、填空題（每空1分，共15分）1. 向量、棧和隊列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 。不允許插入和刪除運算的一端稱為 棧底 。3. 隊列 是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。4. 在一個循環(huán)隊列中，隊首指針指向隊首元素的 前一個 位置。5. 在具有n個單元的循環(huán)隊列中，隊

2、滿時共有 n-1 個元素。6. 向棧中壓入元素的操作是先 移動棧頂指針 ，后 存入元素 。7. 從循環(huán)隊列中刪除一個元素時，其操作是 先 移動隊首指針 ，后 取出元素 。8. 帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于 0 。L=head頭結(jié)點R=headhead解：二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）（ ）1. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。 錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈?zhǔn)酱鎯?，與元素數(shù)據(jù)類型無關(guān)。（ ）2. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。 錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU

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

4、連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 （ ）9. 隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。 錯，后半句不對。（ ）10. 一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。 錯，有可能。三、單項選擇題（每小題1分，共20分）（ B ）1. 棧中元素的進出原則是 先進先出 后進先出 ?？談t進 棧滿則出（ C ）2. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為 i n=i n-i+1 不確定解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必

5、定是最后入棧的（事實上題目已經(jīng)表明了），那么輸入順序必定是1，2，3，n，則出棧的序列是n，3，2，1。（若不要求順序出棧，則輸出序列不確定）（ B ）3. 判定一個棧ST（最多元素為m0）為空的條件是 ST-top0 ST-top=0 ST-topm0 ST-top=m0（ A ）4. 判定一個隊列QU（最多元素為m0）為滿隊列的條件是 QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1解：隊滿條件是元素個數(shù)為m0。由于約定滿隊時隊首指針與隊尾指針相差1，所以

6、不必再減1了，應(yīng)當(dāng)選A。當(dāng)然，更正確的答案應(yīng)該取模，即：QU-front = = (QU-rear+1)% m0（ D ）5數(shù)組用來表示一個循環(huán)隊列，為當(dāng)前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個數(shù)據(jù)元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進?；蜻M隊操作時，按a1、a2、a3、a4次序每次進入一個元素。假設(shè)?；蜿牭某跏紶顟B(tài)都是空。現(xiàn)要進行的棧操作是進棧兩次

7、，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是 C ，第二次出隊得到的元素是 D 。經(jīng)操作后，最后在棧中或隊中的元素還有 E 個。供選擇的答案：AD：a1 a2 a3 a4E： 1 2 3 0答：ABCDE2, 4, 1, 2, 27. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。棧是一種線性表，它的特點是 A 。設(shè)用一維數(shù)組A1,n來表示一個棧，An為棧底，用整型變量T指示當(dāng)前棧頂

8、位置，AT為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值 B ；從棧中彈出（POP）一個元素時，變量T的值 C 。設(shè)?？諘r，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進先出 后進先出 進優(yōu)于出 出優(yōu)于進 隨機進出B，C： 加1 減1 不變 清0 加2 減2D： a,b b,c c,ab,a c,b a,cE： n+1 n+2 n n-1 n-2答案：ABCDE=2, 2, 1, 6, 4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，

9、向地址的低端遞減生成，稱為向下生成堆棧。8. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在做進棧運算時，應(yīng)先判別棧是否 A ；在做退棧運算時，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時，才產(chǎn)生上溢。供選擇的答案：A，B：空 滿 上溢 下溢C： n-1 n n+1 n/2D： 長度 深度 棧頂 棧底E：兩個棧的棧頂同時到達棧空間的中心點 其中一個棧的棧頂?shù)竭_棧

10、空間的中心點 兩個棧的棧頂在達棧空間的某一位置相遇 兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底答案：ABCDE2, 1, 2, 4, 3四、簡答題（每小題4分，共20分）1. 說明線性表、棧與隊的異同點。劉答：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。 用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場，隊列用于多道作業(yè)處理、指

11、令寄存及其他運算等等。2. 設(shè)有編號為1，2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。 全進之后再出情況，只有1種：4，3，2，1 進3個之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和a

12、babab則不是回文。假設(shè)一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j-）從表尾開始打印輸出；堆棧是后進先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實現(xiàn)。（但堆棧是先減后壓還是）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。4. 順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)

13、組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三： 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空； 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法，即隊頭指針、隊尾指針中有一個指向?qū)嵲?，而另一個指向空閑元素。判斷循環(huán)隊列隊空標(biāo)志是： f=rear 隊滿標(biāo)志是：f=(r+1)%N5. 設(shè)循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 front=11，rear=19; front=19，rear=11；問在這兩種情

14、況下，循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=32五、閱讀理解（每小題5分，共20分。至少要寫出思路）1. 按照四則運算加、減、乘、除和冪運算（）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：ABC/D+EF答：2. 寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。void main( )Stack S;Char x,y;InitStack(S);X=c;y=k;Push(S,x); Push(S,a); Push(S,y);

15、Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y);printf(y); ;Printf(x);答：輸出為“stack”。3. 寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElem Type為char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQ

16、ueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);答：輸出為“char”。4. 簡述以下算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進行逆置。六、算法設(shè)計（每小題5分，共15分。

17、至少要寫出思路）1. 假設(shè)一個算術(shù)表達式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個判別表達式中括弧是否正確配對的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量（可理解為每個字符占用一個數(shù)組元素），表示被判別的表達式，tag為布爾型變量。答：用堆棧st進行判定，將 ( 、 或 入棧，當(dāng)遇到 、 或 ) 時，檢查當(dāng)前棧頂元素是否是對應(yīng)的( 、 或 ，若是則退棧，否則返回表示不配對。當(dāng)整個算術(shù)表達式檢查完畢時，若棧為空表示括號正確配對，否則不配對。編程后的整個函數(shù)如下#define m0 100 /*m0為算術(shù)表達式中最多字符個數(shù)*/correct(exp,tag)c

18、har expm0;int tag;char stm0;int top=0, i=1;tag=1;while (i0)tag=0; /*若棧不空，則不配對*/3.19 Status AllBrackets_Test(char *str)/判別表達式中三種括號是否匹配 InitStack(s); for(p=str;*p;p+) if(*p=(|*p=|*p=) push(s,*p); else if(*p=)|*p=|*p=) if(StackEmpty(s) return ERROR; pop(s,c); if(*p=)&c!=() return ERROR; if(*p=&c!=) ret

19、urn ERROR; if(*p=&c!=) return ERROR; /必須與當(dāng)前棧頂括號匹配 /for if(!StackEmpty(s) return ERROR; return OK; /AllBrackets_Test 2001級通信6班張沐同學(xué)答案（已上機通過）#include#includevoid push(char x);void pop();void correct(enum Boolean &tag);/原來的定義是void correct(struct Stack* head,enum Boolean &tag);typedef struct Stackchar da

20、ta;struct Stack *next;struct Stack *head,*p;enum BooleanFALSE,TRUEtag;void main()head=(struct Stack*)malloc(sizeof(struct Stack);head-data=S;head-next=NULL;/ heads data has not been initialized! correct(tag);if(tag)printf(Right!);elseprintf(Wrong!);void push(char x)p=(struct Stack*)malloc(sizeof(str

21、uct Stack);if(!p)printf(Theres no space.n);elsep-data=x;p-next=head;head=p;/ if you define the Correct function like that/Debug will show that the Push action doesnt take effectionvoid pop()if(head-next=NULL)printf(The stack is empty.n);elsep=head;head=head-next;free(p);/void correct(struct Stack* head,enum Boolean &tag)void correct(enum Boolean &tag)int i;char y;printf(Please enter a bds:);for(i=0;y!=n;i+)scanf(%c,&y);if(y=)&head-data=()|(y=&head-data=)|(y=&head-data=)pop();else if(y=()|(y=)|(y=)push(y);/*調(diào)試程序顯示