1. 對於棧,運算元據的原則是()。
a.先進先出 b.後進先出 c.後進後出 d.不分順序
2. 一般情況下,將遞迴演算法轉換成非遞迴應通過設定()實現。
a.陣列 b.線性表 c.佇列d.棧
3. 棧和佇列的共同點是()。
a.都是先進後出b.都是先進先出
c.只允許在端點處插入和刪除元素 d.沒有共同點
4. 若元素a,b,c,d,e,f依次進棧,允許進棧、退棧操作交替進行,但不允許連續3次進行退棧操作,則不可能得到的順序是()。
a.dcebfa b.cbdaef c.bcaefd d.afedcb
5.某佇列允許在兩端進行入隊操作,但僅允許在一端進行出隊操作,若入隊順序為abcde,則不可能得到的順序是()。
a.bcade b.dbace c.dbcae d.ecbad
6.在對棧的操作中,能改變棧的結構是()。
a.stacklength(s) b.stackempty(s) c. gettop(s) d.clearstack(s)
7.在乙個棧頂指標為hs的鏈棧中將乙個s指標所指的結點入棧,應執行()。
a.hs->next=s;
b.s->next=hs->next;hs->next=s;
c.s->next=hs;hs=s;
d.s->next=hs;hs=hs->next;
8.若已知乙個棧的入棧序列是1,2,3,…n,其輸出序列是p1,p2,p3,…pn,若p1=n,
則pi=()。
a.ib.n-ic.n-i+1 d.不確定
9.若用乙個大小為6的陣列來實現迴圈佇列,且當前尾指標rear和頭指標front的值分別為0和3,當從佇列中刪除乙個元素,再加入兩個元素後,尾指標rear和頭指標front的值分別是()。
a.1和5 b.2和4c.4和2 d.5和1
10.要使輸入序列為abc變為序列bac,使用的棧操作序列為()
a.push,pop,push,pop,push,pop b.push,push,push,pop,pop,pop
c.push,push,pop,pop,push,pop d.push,pop,push,push,pop,pop
11.設用乙個大小為m=60的順序表a[m]表示乙個迴圈佇列,如果當前的尾指標
rear=32,頭指標front=15,則當前迴圈佇列的元素個數是()
a.42 b.16 c. 17 d.41
12.設用順序表a[n]表示迴圈佇列,頭,尾指標分別為front和rear,則判斷隊列為空的條件是(),判斷佇列滿的條件是()
(1)a.a.front+1==a.rearb.a.front==a.rear+1
c.a.front==0d.a.front==a.rear
(2)a.(a.rear-1)%n=a.front b(a.rear+1)%n=a.front
c.a.rear=(a.front-1)%n da.rear=(a.front+1)%n
13.設迴圈佇列儲存在陣列a[0..m]中,則入隊時的操作為()
a.rear=rear+1 b.rear=(rear+1)mod(m-1)
c,.rear=(rear+1)mod m d.rear=(rear+1)mod(m+1)
14在解決計算機主機與印表機之間速度不匹配問題時通常設定乙個列印資料緩衝區,主機將要輸出的資料依次寫入該緩衝區,而印表機則從該緩衝區中取出資料列印,該緩衝區應該是乙個()結構
a 棧b佇列c陣列d線性表
15.設棧用向量v[1.…n]儲存,初始棧頂指標top為n+1,則下面將x進棧的正確操作是
()a v[++top]=x b v[top++]=x
c v[--top]=x d v[top--]=x
16.若棧採用順序儲存方式儲存,現在倆個共享空間v[1……m],top[i]代表第i個棧(i=1,2)的棧頂,棧1的底在v[1],棧2的底在v[m],則棧滿的條件是()
a|top[2]-top[1]|=0 b top[1]+1=top[2]
c top[1]+top[2]=m d t op[1]=top[2]
17.表示式a*(b+c)-d的字尾表示式是()
a. abcdb abc+*d-
c abc*+dd-+*abcd
18乙個棧的輸入序列為123……n若輸出序列的第乙個元素是n,則輸出第i(1<=i<=n)
個元素是()
a 不確定 bn-i+1 c i d n-i
二題1.在棧中,可進行插入和刪除操作的一端稱為()。
2.在作進棧運算時,應先判別棧是否(),在作退棧運算時應先判別棧是否()。當棧中元素為n個時,作進棧運算時發生上溢,則說明該棧的最大容量為()。
3.棧的特點是(),佇列的特點是。4.
4.由於鏈棧的操作只在鍊錶頭部進行,所以沒有必要設定()結點。
5.帶頭結點的單鏈表l是空表的條件是();順序棧s是空棧的條件是();順序棧s滿的條件是();不帶頭結點的鏈棧l是空棧的條件是();迴圈佇列q是空佇列的條件是();迴圈佇列q是滿佇列的條件是()。
6.用陣列q(其下標在0到n—1之間,共有n個元素)表示乙個迴圈佇列,front為當前對頭元素的前乙個位置,rear為對尾元素的位置,假設佇列中的元素個數總小於n,則求佇列中元素個數的公式是()。
7.設元素入棧的順序是1,2,3,.....,n,則所有可能的出棧序列共有()種
8.在具有n個單元的迴圈佇列中,隊滿時共有()個元素。
9.設有乙個空棧,棧頂指標為1000h(十六進製制),現有輸入序列為1,2,3,4,5,經過push,
push,pop,push,pop,push,push之後,輸出序列是(),而棧頂指標值是()h。
(設棧為順序棧,每個元素佔4個位元組)
10.用push表示入站操作,pup表示出棧操作,如元素入棧的順序為1234,為了的到1342的出棧的順序,相應的push和pop的操作串為()。
3、問答題與演算法題
1.設將整數1,2,3,4依次進棧,若入、出棧次序為push(s,1),pop(s,x1),push(s,2),push(s,3),pop(s,x2),pop(s,x3),push(s,4),pop(s,x4),則出棧的數字序列為何?
2.設用不帶頭結點的單鏈表表示棧,請分別寫出入棧和出棧的演算法。
(1)int push_l(linkstack &s selemtype e)
(2)int pop_l(linkstack &s selemtype &e)
3.假設用帶頭節點的單迴圈鍊錶表示佇列,並設定乙個指向尾結點的指標(無頭指標),請分別寫出佇列的入隊和出隊演算法。
(1)int enqueue_l(queueptr &ql qelemtype e)
(2)int dequeue_l(queueptr &ql qelemtype &e)
4.指出下述程式段的功能是什麼。
(1)void abc1(stack &s)
;for(i=0,i}
(2)void abc2(stack s1,stack &s2)
}(3)void abc3(stack &s,int m)
while (!stackempty(t))
}(4)void abc4(queue &q)
while (!stackempty(s))
}(5) void invert1(linklist &l)
p=l利用原來的鍊錶只修改資料域的值(反序)
while(!stackempty(s))
return ok;
}5.回文是指正讀反讀均相同的字串行,如「abba」和「abdba」均是回文,但「good」不是回文。試寫乙個演算法判定給定的用帶頭節點的單鏈表表示的字串是否為回文。
int hw1(linklist l)
6.寫乙個將不帶頭節點的鏈棧s中所有節點均刪去的演算法。
void clearstack(linkstack &s)
7.寫乙個返回不帶頭結點的鏈棧s中結點個數的演算法。
int stacksize(linkstack s)
8.利用棧操作,寫乙個演算法把乙個不帶頭結點的鍊錶的元素反序存放。
void invert2(linklist &l)
9.試將下列地櫃過程改寫為非遞迴過程
void test(int &sum)
printf(sum);
資料結構課後習題及解析第三章
第三章習題 1.按圖3.1 b 所示鐵道 兩側鐵道均為單向行駛道 進行車廂排程,回答 如進站的車廂序列為123,則可能得到的出站車廂序列是什麼?如進站的車廂序列為123456,能否得到435612和135426的出站序列,並說明原因。即寫出以 s 表示進棧 以 x 表示出棧的棧操作序列 2.設佇列中...
資料結構第三章課後習題及總結
資料結構第三章 t1223 3 28朱俊傑 1 原理討論題 1 順序儲存的三個優點 1思路和實現都比較簡單,容易理解。2不用為表示結點間的邏輯關係而增加額外的儲存空間。3順序表具有按元素序號隨機訪問的特點。順序比鏈式節約空間。是因為鏈式結構每乙個節點都有乙個指標儲存域。順序支援隨機訪問,方便操作 鏈...
資料結構1800題第三章
第3章棧和佇列 一選擇題 1.對於棧運算元據的原則是 青島大學 2001 五 2 2分 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.在作進棧運算時,應先判別棧是否 在作退棧運算時應先判別棧是否 當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為 為了增加記憶體空間的利用率...