數(shù)據(jù)結(jié)構(gòu)單元練習(xí)3

單元練習(xí)一.判斷題(下列各題，正確的請在前面的括號內(nèi)打V；錯誤的打X)(J)()棧是運算受限制的線性表。(V)(2)在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢出。(X)(3)棧一定是順序存儲的線性結(jié)構(gòu)。(J)()棧的特點是“后進先出”。(X)(5)空棧就是所有元素都為0的棧。(X)⑹在C或者C++語言中設(shè)順序棧的長度為MAXLEN,則top=MAXLEN時表示隊滿。(V)(7)鏈棧與順序棧相比，其特點之一是通常不會浮現(xiàn)棧滿的情況。(X)(J)一個棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,Do(X)()遞歸定義就是循環(huán)定義。(7)()將十進制數(shù)轉(zhuǎn)換為二進制數(shù)是棧的典型應(yīng)用之一。二.填空題()對、棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂。()在順序棧中，當(dāng)棧頂指針top時，表示?？?。()在有個元素的棧中，進棧操作的時間復(fù)雜度為一()O()在棧中，出棧操作的時間復(fù)雜度為： 。 ()已知表達式，求它的后綴表達式是棧的典型應(yīng)用。()在一個鏈棧中，若棧頂指針等于 ，則表示棧空。()向一個棧頂指針為top的鏈棧插入一個新結(jié)點P時，應(yīng)執(zhí)行p->next=top； 和top=p；操作。()順序棧存儲在數(shù)組 中，進棧操作時要執(zhí)行的語句有：topo (或者top+1)()鏈棧，指向棧頂元素的指針是 。(10)從一個棧刪除元素時，首先取出棧頂元素，然后再挪移棧頂指針。(11)由于鏈棧的操作只在鏈表的頭部進行，所以沒有必要設(shè)置 頭幺吉點002)°已知順序棧S,在對S進行進棧操作之前首先要判斷棧是否滿o L13)已知順序棧S,在對S進行出棧操作之前首先要判斷棧是否試寫出把十進數(shù)轉(zhuǎn)換為?鏈棧的存儲結(jié)構(gòu)和棧頂指針定義如下,二進制數(shù)的程序。試寫出把十進數(shù)轉(zhuǎn)換為儲結(jié)構(gòu)定義棧的存定義棧頂?shù)闹付x棧頂?shù)闹笚５膽?yīng)用：針解：二一十進制轉(zhuǎn)換占八、、指針置棧取余數(shù)取新的商申請新結(jié)余數(shù)入棧轉(zhuǎn)換后的二進制數(shù)值為:轉(zhuǎn)換后的二進制數(shù)值為：出棧處理出棧一個余數(shù)，收回一個結(jié)-L-O(14)若內(nèi)存空間充足， 鏈 ?？梢圆欢x棧滿運算。()鏈棧是空的條件是 o()鏈棧的棧頂元素是鏈表的 首元素。()同一棧的各元素的類型相同。(18)若進棧的次序是A、B、C、D、E,執(zhí)行三次出棧操作以后，棧頂元素為Bo(19)A+B/C-D*E的后綴表達式是： ABC/+DE*-。()四個元素按、、、順序進棧，執(zhí)行兩次(， )運算后，的值是o三.選擇題()插入和刪除只能在一端進行的線性表，稱為 。.隊列 .循環(huán)隊列 .棧 .循環(huán)棧()設(shè)有編號為，，，的四輛列車，順序進入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序為則出棧操作時( ).則出棧操作時( ).必須判別棧是否空.隊?？刹蛔鋈魏闻袆e.必須判別棧是否滿.必須判別棧元素類型()元素挨次進棧以后，棧頂元素是(()元素挨次進棧以后，棧頂元素是(()順序棧存儲空間的實現(xiàn)使用( )存儲棧元素。.鏈表.數(shù)組 .循環(huán)鏈表.變量()在或者語言中，一個順序棧一旦被聲明，其占用空間的大小( )O.已固定.不固定 .可以改變.動態(tài)變化()帶頭結(jié)點的鏈棧的示意圖如下，棧頂元素是( )()鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是(.插入操作更加方便.插入操作更加方便.通常不會浮現(xiàn)棧滿的情況。.不會浮現(xiàn)?？盏那闆r（）從一個棧頂指針為

被刪除的結(jié)點，應(yīng)執(zhí)行下列.況。.不會浮現(xiàn)?？盏那闆r（）從一個棧頂指針為

被刪除的結(jié)點，應(yīng)執(zhí)行下列.刪除操作根加方便

的鏈棧中刪除一個結(jié)點時，用保存

命令。（）在一個棧頂指針為入棧，應(yīng)執(zhí)行下列的鏈棧中，將一個指針?biāo)傅慕Y(jié)點命令。TOC\o"1-5"\h\z（）四個元素按、、、順序進棧，執(zhí)行兩次 （， ）運算后，棧頂元素的值是（）o（）元素 挨.進棧以后，棧焉元素是（ ）O（）經(jīng)過下列棧的運算后，再執(zhí)行.的值是（.）。（初始化棧）（）經(jīng)過下列棧的運算后，的值是（. ）0 .（初始化棧）（）經(jīng)過下列棧的運算后， 的值是（ ）0（ 初 始 化棧）（）經(jīng)過下列棧的運算后， .的值是（ ）。.（初始化棧）（）向順序棧中壓入元素時，（ ）O.先存入元素，后挪移棧頂指針 .先挪移棧頂指針,后存入元素.誰先誰后無關(guān)緊要（）初始化一個空間大小為的順序棧后， 的值是（ ）o.再也不改變.動態(tài)變化7）一個棧的入棧次序，則棧的不可能的輸出序列是挨次進棧：如果六則棧的容量至少應(yīng)是（）設(shè)有一個順序棧：元素個元素出棧的順序是，，，挨次進棧：如果六則棧的容量至少應(yīng)是四.設(shè)有一個棧，元素進棧的次序為：，，，，，用表示進棧操作，表示出棧操作，寫出下列出棧的操作序列。（）,,,,（）,,,,解：（）（）五.求后綴表達式（）（）（）（）六.算法設(shè)計題.設(shè)用一維數(shù)組 表示一個堆棧，若堆棧中每一個元素需占用個數(shù)組單元（）,（）試寫出其入棧操作的算法。（）試寫出其出棧操作的算法。.設(shè)計一個算法，要求判別一個算術(shù)表達式中的圓括號配對是否正確。.解：用一整型變量top表示棧頂指針，top為0時表示棧為空。棧中元素從S[1]開始存放元素。(1)入棧算法：voidpush(charx)(if((top+M)>MAXLEN-1)printf("堆棧溢出!”)；else(if(top==0)(top++;S[top]=x;)else(top=top+M;S[top]=x;)(2)出棧算法:voidpop(charx)(if(top==0)printf("堆棧為空棧！”)；else(if(top==1)(X=[top];top--;)else(X=[top];top=top-M;))).解：設(shè)表達式在字符數(shù)組a口中，使用一堆棧S來匡助判斷。intcorrect(chara[])stacks;InitStack(s);for(i=0;i<strlen(a);i++)if(a[i]=='(')Push(s,'(');elseif(a[i]==')')(ifStackEmpty(s)return0;棧elsePop(s);)if(StackEmpty(s))printf(“配對正確！”);并返回1//調(diào)用初始化棧函數(shù)//調(diào)用判?？蘸瘮?shù)//若棧為空返回0；否則出//調(diào)用判棧空函數(shù)//若?？?，說明配對正確,elseprintf("配對錯誤！”);//配對錯誤返回0摹擬考題求后綴表達式.求下列表達式： A 的后綴表達式。解：ABCA