資料結構試卷（一）
一、單選題（每題 2 分，共20分）
1. 棧和佇列的共同特點是( a )。
a.只允許在端點處插入和刪除元素
b.都是先進後出
c.都是先進先出
d.沒有共同點
2. 用鏈結方式儲存的佇列，在進行插入運算時( d ).
a. 僅修改頭指標b. 頭、尾指標都要修改
c. 僅修改尾指標d.頭、尾指標可能都要修改
3. 以下資料結構中哪乙個是非線性結構？( d )
a. 佇列 b. 棧 c. 線性表 d. 二叉樹
4. 設有乙個二維陣列a[m][n]，假設a[0][0]存放位置在644(10)，a[2][2]存放位置在676(10)，每個元素佔乙個空間，問a[3][3](10)存放在什麼位置？腳注(10)表示用10進製表示。
ca．688b．678 c．692 d．696
5. 樹最適合用來表示( c )。
a.有序資料元素b.無序資料元素
c.元素之間具有分支層次關係的資料 d.元素之間無聯絡的資料
6. 二叉樹的第k層的結點數最多為( d ).
a．2k-1 b.2k+1 c.2k-1 d. 2k-1
7. 若有18個元素的有序表存放在一維陣列a[19]中，第乙個元素放a[1]中，現進行二分查詢，則查詢a［3］的比較序列的下標依次為( c d )
a. 1，2，3b. 9，5，2，3
c. 9，5，3d. 9，4，2，3
8. 對n個記錄的檔案進行快速排序，所需要的輔助儲存空間大致為 c
a. o（1） b. o（n） c. o（1og2n） d. o（n2）
9. 對於線性表（7，34，55，25，64，46，20，10）進行雜湊儲存時，若選用h（k）=k %9作為雜湊函式，則雜湊位址為1的元素有（ c d ）個，
a．1 b．2c．3d．4
10. 設有6個結點的無向圖，該圖至少應有( a )條邊才能確保是乙個連通圖。
a.5 b.6 c.7 d.8
二、填空題（每空1分，共26分）
1. 通常從四個方面評價演算法的質量：____時間正確性占用記憶體_易讀性____、____複雜度__強壯性___和_____準確度_ 高效率___。
2. 乙個演算法的時間複雜度為(n3+n2log2n+14n)/n2，其數量級表示為___3 0（n）_____。
3. 假定一棵樹的廣義表表示為a（c，d（e，f，g），h（i，j）），則樹中所含的結點數為_____9_____個，樹的深度為_____3______，樹的度為____2_____。
4. 字尾算式9 2 3 +- 10 2 / -的值為____3__-1____。中綴算式（3+4x）-2y/3對應的字尾算式為______3 4x* + 2y
5. 若用鍊錶儲存一棵二叉樹時，每個結點除資料域外，還有指向左孩子和右孩子的兩個指標。在這種儲存結構中，n個結點的二叉樹共有____n_2n___個指標域，其中有_____n-1___個指標域是存放了位址，有________3__n+1______個指標是空指標。
6. 對於乙個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有___e+1_e___個和____e+1__2e__個。
7. aov網是一種________有向無迴路的圖。
8. 在乙個具有n個頂點的無向完全圖中，包含有____n-1_n(n-1)/2___條邊，在乙個具有n個頂點的有向完全圖中，包含有____n-1___n(n-1)_條邊。
9. 假定乙個線性表為(12,23,74,55,63,40)，若按key % 4條件進行劃分，使得同一餘數的元素成為乙個子表，則得到的四個子表分別為12,4023,63,5574和
10. 向一棵b_樹插入元素的過程中，若最終引起樹根結點的**，則新樹比原樹的高度______增加1____。
1. 在堆排序的過程中，對任一分支結點進行篩運算的時間複雜度為___0（n/2）___ o(log2n) __，整個堆排序過程的時間複雜度為__0（1）__ o(nlog2n)____。
11. 在快速排序、堆排序、歸併排序中，____堆排序__歸併排序___排序是穩定的。
三、計算題（每題 6 分，共24分）
1. 在如下陣列a中鏈結儲存了乙個線性表，表頭指標為a [0].next，試寫出該線性表。
a 0 1 2 3 4 5 6 7
a[0] a[3] a[2] a[7] a[1] a[5] a[4] a[0]
線性表為：（78，50，40，60，34，90）
2. 請畫出下圖的鄰接矩陣和鄰接表。
1. 鄰接矩陣：
3. 已知乙個圖的頂點集v和邊集e分別為：v=;
e=;用克魯斯卡爾演算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 畫出向小根堆中加入資料4, 2, 5, 8, 3時，每加入乙個資料後堆的變化。
四、閱讀演算法（每題7分，共14分）
1. linklist mynote(linklist l)
l是不帶頭結點的單鏈表的頭指標
if(l&&l->next){
資料結構試題及答案
2 二維陣列是陣列元素為一維陣列的線性表，因此它是線性結構。3 順序錶用一維陣列作為儲存結構，因此順序表是一維陣列。4 通常使用兩個類來協同表示單鏈表，即鍊錶的結點類和鍊錶類。5 棧和佇列都是順序訪問的的線性表，但它們對訪問位置的限制不同。6 在使用字尾表表示實現計算器時用到乙個棧的例項，其作用是暫...
資料結構試題及答案
資料結構 自考複習思考試題 一 單選題 從選擇的答案中選出正確的答案，將其字母編號填入下列敘述中的括號內。每小題 3分，共24分 1 向乙個有127個元素原順序表中插入乙個新元素並儲存原來順序不變，平均要移動 個元素。a 8 b 63.5 c 63 d 7 2 設有乙個二維數a m n 假設a 0 ...
資料結構試題及答案
24.快速排序的樞軸有多種選擇方法，取首尾節點是較簡單的做法。25.氣泡排序不但穩定，而且速度很快。二 名詞解釋與問答 26.線性結構 唯一的首節點，唯一的尾節點，除首尾外其它節點既有前驅也有後繼，首無前驅，尾無後繼。27.線性結構中端操作受限的含義是什麼？操作僅在指定的位置。棧在棧頂，佇列在隊頭和...