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

1、單元練習(xí)3一判斷題（下列各題，正確的請?jiān)谇懊娴睦ㄌ杻?nèi)打；錯誤的打 ）（ ）（1）棧是運(yùn)算受限制的線性表。（ ）（2）在?？盏那闆r下，不能作出棧操作，否則產(chǎn)生下溢出。（ ）（3）棧一定是順序存儲的線性結(jié)構(gòu)。（ ）（4）棧的特點(diǎn)是“后進(jìn)先出”。（ ）（5）空棧就是所有元素都為0的棧。（ ）（6）在C或C+語言中設(shè)順序棧的長度為MAXLEN，則top=MAXLEN時表示隊(duì)滿。（ ）（7）鏈棧與順序棧相比，其特點(diǎn)之一是通常不會出現(xiàn)棧滿的情況。（ ）（8）一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。二填空題（1）在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為 。（2）在順序棧中，當(dāng)棧頂指

2、針top=-1時，表示 。（3）在有n個元素的棧中，進(jìn)棧操作的時間復(fù)雜度為 。（4）在棧中，出棧操作的時間復(fù)雜度為： 。（5）在一個鏈棧中，若棧頂指針等于NULL，則表示 。（6）向一個棧頂指針為top的鏈棧插入一個新結(jié)點(diǎn)*p時，應(yīng)執(zhí)行 和top=p； 操作。（7）順序棧S存儲在數(shù)組 S-data0.MAXLEN-1中，進(jìn)棧操作時要執(zhí)行的語句有：S-top 。 （8）鏈棧LS，指向棧頂元素的指針是 。（9）從一個棧刪除元素時，首先取出 ，然后再移動棧頂指針。（10）由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒有必要設(shè)置 結(jié)點(diǎn)。（11）已知順序棧S，在對S進(jìn)行進(jìn)棧操作之前首先要判斷 。（12）已知順

3、序棧S，在對S進(jìn)行出棧操作之前首先要判斷 。（13）若內(nèi)存空間充足， ?？梢圆欢x棧滿運(yùn)算。（14）鏈棧LS是空的條件是 。（15）鏈棧LS的棧頂元素是鏈表的 元素。（16）同一棧的各元素的類型 。（17）若進(jìn)棧的次序是A、B、C、D、E，執(zhí)行三次出棧操作以后，棧頂元素為 。（18）四個元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop（S，x）運(yùn)算后，x的值是 。三選擇題（1）插入和刪除只能在一端進(jìn)行的線性表，稱為( )。 A隊(duì)列 B循環(huán)隊(duì)列 C棧 D循環(huán)棧 （2）設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序?yàn)?( ) A1234 B1243 C1324 D

4、1423（3）如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（ ） A必須判別棧是否滿 B必須判別棧是否空 C必須判別棧元素類型 D隊(duì)棧可不做任何判別（4）元素A,B,C,D依次進(jìn)棧以后，棧頂元素是（ ） AA BB CC DD（5）順序棧存儲空間的實(shí)現(xiàn)使用（ ）存儲棧元素。 A鏈表 B數(shù)組 C循環(huán)鏈表 D變量（6）在C或C+語言中，一個順序棧一旦被聲明，其占用空間的大?。?）。 A已固定 B不固定 C可以改變 D動態(tài)變化（7）帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是（ ） LSHABCD AA BB CC DD（8）鏈棧與順序棧相比，有一個比較明顯的優(yōu)點(diǎn)是（ ）。A插入操作更加方便 B通常不會出

5、現(xiàn)棧滿的情況。C不會出現(xiàn)?？盏那闆r D刪除操作根加方便（9）從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列 ( )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;top=top-next;（10）在一個棧頂指針為HS的鏈棧中，將一個S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列 ( )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next;（11）四個元素按

6、A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop（S，x）運(yùn)算后，棧頂元素的值是（ ）。 AA BB CC DD（12）元素A,B,C,D依次進(jìn)棧以后，棧底元素是（ ）。 AA BB CC DD（13）經(jīng)過下列棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是（ ）。 InitStack(s) （初始化棧）;Push(s,a);Push(s,b); Pop(s)Aa Bb C1 D0（14）經(jīng)過下列棧的運(yùn)算后，x的值是（ ）。 InitStack(s) （初始化棧）;Push(s,a);Push(s,b); ReadTop(s);Pop(s,x);Aa Bb C1 D0（15）經(jīng)過下列棧的運(yùn)算后，x的值是（

7、 ）。 InitStack(s) （初始化棧）;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);Aa Bb C1 D0（16）經(jīng)過下列棧的運(yùn)算后，SEmpty(s)的值是（ ）。 InitStack(s) （初始化棧）; Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);Aa Bb C1 D0（17）向順序棧中壓入元素時，（ ）。A 先存入元素，后移動棧頂指針 B先移動棧頂指針，后存入元素C誰先誰后無關(guān)緊要 D同時進(jìn)行（18）初始化一個空間大小為5的順序棧S后，S-top的值是（ ）。 A0 B-1 C不再改變 D動態(tài)變化（19）一個棧的入棧次序ABCDE，則棧的不可能的輸出序列是 ( )。 AEDCBA BDECBA CDCEAB DABCDE（20）設(shè)有一個順序棧S，元素A,B,C,D,E,F,依次進(jìn)棧，如果六個元素出棧的順序是B，D，C，F(xiàn)，E，A，則棧的容量至少應(yīng)是 ( )。 A3 B4 C5 D 6四設(shè)有一個棧，元素進(jìn)棧的次序?yàn)椋篈，B，C，D，E，用I表示進(jìn)棧操作，O表示出棧操作，寫出下列出棧的操作序列。（1）C，B，A，D，E