【文章內(nèi)容簡介】 進棧，則出棧次序不可能出現(xiàn)在（ ）種情況。A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解釋：棧是后進先出的線性表，不難發(fā)現(xiàn)C選項中元素1比元素2先出棧，違背了棧的后進先出原則，所以不可能出現(xiàn)C選項所示的情況。（2）若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（ ）。A．i B．ni C．ni+1 D．不確定答案：C解釋：棧是后進先出的線性表，一個棧的入棧序列是1，2，3，…，n，而輸出序列的第一個元素為n，說明1，2，3，…，n一次性全部進棧，再進行輸出，所以p1=n，p2=n1，…，pi=ni+1。（3）數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素個數(shù)的公式為（ ）。A．rf B．(n+fr)%n C．n+rf D．（n+rf)%n答案：D解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+rf)%n。（4）鏈式棧結(jié)點為：(data,link)，并將刪除結(jié)點的值保存到x中,則應(yīng)執(zhí)行操作（ ）。A．x=topdata。top=toplink； B．top=toplink。x=toplink； C．x=top。top=toplink； D．x=toplink；答案：A解釋：x=topdata將結(jié)點的值保存到x中，top=toplink棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。（5）設(shè)有一個遞歸算法如下 int fact(int n) { //n大于等于0 if(n=0) return 1。 else return n*fact(n1)。 }則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。A．n+1 B．n1 C． n D． n+2答案：A解釋：特殊值法。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。（6）棧在（ ）中有所應(yīng)用。A．遞歸調(diào)用 B．函數(shù)調(diào)用 C．表達式求值 D．前三個選項都有答案：D解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達式求值均用到了棧的后進先出性質(zhì)。（7）為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ ）。A．隊列 B．棧 C． 線性表 D．有序表答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進先出的線性表，而隊列正是一種先進先出的線性表。（8）設(shè)棧S和隊列Q的初始狀態(tài)為空，元素eeeee5和e6依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是eeeee5和e1，則棧S的容量至少應(yīng)該是（?。?。A．2 B．3 C．4 D． 6答案：B解釋：元素出隊的序列是eeeee5和e1，可知元素入隊的序列是eeeee5和e1，即元素出棧的序列也是eeeee5和e1，而元素eeeee5和e6依次進入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少為3。（9）若一個棧以向量V[1..n]存儲，初始棧頂指針top設(shè)為n+1，則元素x進棧的正確操作是( )。A．top++。 V[top]=x。 B．V[top]=x。 top++。C．top。 V[top]=x。 D．V[top]=x。 top。答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進棧，又因為元素存儲在向量空間V[1..n]中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在V[n]。（10）設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（　）數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲結(jié)構(gòu) B．隊列 C. 線性表的鏈式存儲結(jié)構(gòu) D. 棧答案：D解釋：利用棧的后進先出原則。（11）用鏈接方式存儲的隊列，在進行刪除運算時（?。?。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。（12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（　）。A. rear=rear+1 B. rear=(rear+1)%(m1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解釋：數(shù)組A[0..m]中共含有m+1個元素，故在求模運算時應(yīng)除以m+1。（13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（?。?。 A. (rear+1)%n==front B. rear==front C．rear+1==front D. (rearl)%n==front答案：B解釋：最大容量為n的循環(huán)隊列，隊滿條件是(rear+1)%n==front，隊空條件是rear==front。（14）棧和隊列的共同點是（?。?。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點答案：C解釋：棧只允許在棧頂處進行插入和刪除元素，隊列只允許在隊尾插入元素和在隊頭刪除元素。（15）一個遞歸算法必須包括（　）。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分答案：B2．算法設(shè)計題（1）將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當?shù)?號棧的棧頂指針top[0]等于1時該棧為空，當?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長。試編寫雙棧初始化，判斷棧空、棧滿、進棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedef struct{int top[2],bot[2]。 //棧頂和棧底指針 SElemType *V。 //棧數(shù)組 int m。 //棧最大可容納元素個數(shù)}DblStack[題目分析]兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時，左棧頂指針為1，右棧頂為m。兩棧頂指針相鄰時為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。[算法描述](1)棧初始化intInit(){[0]=1。[1]=m。return1。//初始化成功}(2)入棧操作：intpush(stk S,inti,intx)∥i為棧號，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，失敗返回0{if(i0||i1){ cout“棧號輸入不對”endl。exit(0)。}if([1][0]==1) {cout“棧已滿”endl。return(0)。}switch(i){case0: [++[0]]=x。return(1)。break。case1: [[1]]=x。return(1)。}}∥push(3)退棧操作ElemType pop(stk S,inti)∥退棧。i代表棧號，i=0時為左棧，i=1時為右棧。退棧成功時返回退棧元素∥否則返回1{if(i0 || i1){cout“棧號輸入錯誤”endl；exit(0)。}switch(i){case0:if([0]==1) {cout“棧空”endl；return（1）；}elsereturn([[0]])。case1:if([1]==m { cout“?？铡眅ndl。return(1)。}elsereturn([[1]++])。}∥switch }∥算法結(jié)束(4)判斷?？読ntEmpty()。{return([0]==1 amp。amp。 [1]==m)。}[算法討論]請注意算法中兩棧入棧和退棧時的棧頂指針的計算。左棧是通常意義下的棧，而右棧入棧操作時，其棧頂指針左移（減1），退棧時，棧頂指針右移（加1）。（2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)[題目分析]將字符串前一半入棧，然后，棧中元素和字符串后一半進行比較。即將第一個出棧元素和后一半串中第一個字符比較，若相等，則再出棧一個元素與后一個字符比較，……，直至?？眨Y(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時，結(jié)論字符序列不是回文。[算法描述]define StackSize 100 //假定預(yù)分配的?？臻g最多為100個元素typedef char DataType。//假定棧元素的數(shù)據(jù)類型為字符typedef struct{DataType data[StackSize]。int top。}SeqStack。int IsHuiwen( char *t){//判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s。int i , len。char temp。InitStack( amp。s)。len=strlen(t)。 //求向量長度for ( i=0。 ilen/2。 i++)//將一半字符入棧Push( amp。s, t[i])。while( !EmptyStack( amp。s)){// 每彈出一個字符與相應(yīng)字符比較temp=Pop (amp。s)。if( temp!=S[i]) return 0 。// 不等則返回0else i++。}return 1 。 // 比較完畢均相等則返回 1}（3）設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，…，an，試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai≠1時，將ai進棧；當ai=1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。[算法描述]define maxsize ?？臻g容量void InOutS(int s[maxsize])//s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。{int top=0。 //top為棧頂指針，定義top=0時為?？?。 for(i=1。 i=n。 i++) //n個整數(shù)序列作處理。 {cinx)。 //從鍵盤讀入整數(shù)序列。 if(x!=1) // 讀入的整數(shù)不等于1時入棧。 ｛if(top==maxsize1){cout“棧滿”endl。exit(0)。}else s[++top]=x。 //x入棧。｝ else //讀入的整數(shù)等于1時退棧。 {if(top==0){ cout“?？铡眅ndl。exit(0)。} else cout“出棧元素是” s[top]endl。} }}//算法結(jié)束。（4）從鍵盤上輸入一個后綴表達式，試編寫算法計算表達式的值。規(guī)定：逆波蘭表達式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、*、/四種運算。例如：234 34+2*$。[題目分析]逆波蘭表達式(即后綴表達式)求值規(guī)則如下：設(shè)立運算數(shù)棧OPND,對表達式從左到右掃描(讀入)，當表達式中掃描到數(shù)時，壓入OPND棧。當掃描到運算符時，從OPND退出兩個數(shù)，進行相應(yīng)運算，結(jié)果再壓入OPND棧。這個過程一直進行到讀出表達式結(jié)束符$，這時OPND棧中只有一個數(shù)，就是結(jié)果。[算法描述]