習題3 棧和佇列
一、基本內容
棧和佇列的結構特點;在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。
二、學習要點
1. 掌握棧和佇列的特點。
2.熟練掌握棧型別的兩種實現方法,即兩種儲存結構表示時的基本操作實現演算法,特別應注意棧滿和棧空的條件以及它們的描述方法。
3.熟練掌握迴圈佇列的基本操作實現演算法.持別注意隊滿和隊空的描述方法。
4.理解遞迴演算法執行過程中棧的狀態變化過程。
3.1 單項選擇題
1. 乙個棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是____。
a. edcba b. decba d. abcde
2. 若已知乙個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為____。
a. i b. n=i d. 不確定
3. 棧結構通常採用的兩種儲存結構是____。
[, ] b.雜湊方式和索引方式
c.鍊錶儲存結構和陣列d.線性儲存結構和非線性儲存結構
4. 判定乙個順序棧st(最多元素為m0)為空的條件是____。
a. top !=0 [, ] c. top !=m0 d. top= =m0-1
5. 判定乙個順序棧st(最多元素為m0)為棧滿的條件是____。
a. top!=0 b. top= =0 c. top!=m0
6. 棧的特點是_b__,佇列的特點是_a__。
a. 先進先出 b. 先進後出
7. 向乙個棧頂指標為hs的鏈棧中插入乙個s所指結點時,則執行__ __。(不帶空的頭結點)
a. hs—>next=s;
b. s—>next= hs—>next; hs—>next=s;
[, ]
d. s—>next= hs; hs= hs—>next;
8. 從乙個棧頂指標為hs的鏈棧中刪除乙個結點時,用x儲存被刪結點的值,則執行__ __。(不帶空的頭結點)
a. x=hs; hs= hs—>nextt': 'span', 'c': ' b. x=hs'}, ]
c. hs= hs—>next; x=hs—>data; d. x=hs—>data; hs= hs—>next;
9. 乙個佇列的資料入列序列是1,2,3,4,則佇列的出隊時輸出序列是____ 。
a. 4,3,2,1t': 'span', 'ct': 'span', 'c': 'b. 1', 'r': 'r_32'}, , , , , , ]
c. 1,4,3,2d. 3,2,4,1
10. 判定乙個迴圈佇列qu(最多元素為m)為空的條件是____。
a. rear - front= =m b. rear-front-1= =m
[, , ]
b. rear-front-1= =m c. front= =rear d. front= = rear+1
12. 迴圈佇列用陣列a[0,m-1]存放其元素值,已知其頭尾指標分別是front和rear,則當前佇列中的元素個數是____。
[, }
出隊演算法:
int dl_cycque(int sq,int start,int end,int *q)
}佇列某個時刻的初始狀態如圖所示。
1).在初始狀態上,畫出a7、a8和a9入隊後的狀態圖,
2).在初始狀態上,畫出a4、a5和a6出隊後的狀態圖。
資料結構練習題
習題5 陣列和廣義表 一 基本內容 陣列定義及表示方式 特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現 廣義表的邏輯結構和儲存結構。二 學習要點 1.了解陣列的兩種儲存表示方法,並掌握陣列在以行為主的儲存結構中的位址計算方法。2 掌握對特殊矩陣進行壓縮儲存時的下標變換公式。3 了解稀疏矩陣的兩種壓縮儲...
資料結構練習題
a.n b.n 1 2 c.n 1 9 對於乙個具有n個頂點和e條邊的無向圖,若採用鄰接表表示,則表頭向量的大小為 所有鄰接表中的接點總數是 b.n 1 c.n 1 d.n e a.e 2 b.e d.n e 10 已知乙個圖如圖7.1所示,若從頂點a出發按深度搜尋法進行遍歷,則可能得到的一種頂點序...
資料結構練習題
1 3個結點可構成棵不同形態的樹。2 利用直接選擇排序演算法對n個記錄進行排序,最壞的情況下,記錄交換的次數為 3 乙個圖的 表示法是唯一的,而 表示法是不唯一的。4 一棵深度為h的滿二叉樹上的結點總數為 一棵深度為h的完全二叉樹上的結點總數的最小值為 最大值為 5 在一棵完全二叉樹中有n個結點,對...