資料結構試卷（一）
一、單選題
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進製表示。（ c ）
a、688b、678 c、692d、696
5、樹最適合用來表示( c )。
a.有序資料元素 b.無序資料元素c.元素之間具有分支層次關係的資料 d.元素之間無聯絡的資料
6、 二叉樹的第k層的結點數最多為( d ).
a、2k-1 b、2k+1c、2k-1 +1 d、 2k-1
7、若有18個元素的有序表存放在一維陣列a[19]中，第乙個元素放a[1]中，現進行二分查詢，則查詢a［3］的比較序列的下標依次為( d )
a、 1，2，3 b、 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的元素有（ d ）個，
a、1b、2c、3d、4
10、設有6個結點的無向圖，該圖至少應有( a )條邊才能確保是乙個連通圖。
a、5b、6c、7d、8
二、填空題
1. 通常從四個方面評價演算法的質量：（正確性）、（可讀性）、（健壯性）和（效率與低儲存量）。
2. 乙個演算法的時間複雜度為(n3+n2log2n+14n)/n2，其數量級表示為（ o(n) ）。
3. 假定一棵樹的廣義表表示為a（c，d（e，f，g），h（i，j）），則樹中所含的結點數為（ 9 ）個，樹的深度為（ 3 ），樹的度為（ 3 ）。
4. 字尾算式9 2 3 + - 10 2 / -的值為（-1）。中綴算式（3+4x）-2y/3對應的字尾算式為（3 4 x * + 2 y * 3 / -）。
5. 若用鍊錶儲存一棵二叉樹時，每個結點除資料域外，還有指向左孩子和右孩子的兩個指標。在這種儲存結構中，n個結點的二叉樹共有（2n ）個指標域，其中有（n-1）個指標域是存放了位址，有（ n+1）個指標是空指標。
6. 對於乙個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有（e）個和（2e）個。
7. aov網是一種（有向無迴路）的圖。
8. 在乙個具有n個頂點的無向完全圖中，包含有（ n(n-1)/2）條邊，在乙個具有n個頂點的有向完全圖中，包含有（ n(n-1)）條邊。
9. 假定乙個線性表為(12,23,74,55,63,40)，若按key % 4條件進行劃分，使得同一餘數的元素成為乙個子表，則得到的四個子表分別為 （12，40）、（74）、（23,55，63）和（ ）。
10. 向一棵b_樹插入元素的過程中，若最終引起樹根結點的**，則新樹比原樹的高度（增加1）。
11. 在堆排序的過程中，對任一分支結點進行篩選運算的時間複雜度為（ o(log2n)），整個堆排序過程的時間複雜度為（ o(nlog2n)）。
12. 在快速排序、堆排序、歸併排序中，（歸併）排序是穩定的。
三、計算題
1. 在如下陣列a中鏈結儲存了乙個線性表，表頭指標為a[0].next，試寫出該線性表。
a 0 1 2 3 4 5 6 7
參***：線性表為：（78，50，40，60，34，90）
2、請畫出下圖的鄰接矩陣和鄰接表
參***：
鄰接矩陣：
鄰接表：
3、已知乙個圖的頂點集v和邊集e分別為：v=;
e=;用克魯斯卡爾演算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。
參***：用克魯斯卡爾演算法得到的最小生成樹為：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
5、 畫出向小根堆中加入資料4, 2, 5, 8, 3時，每加入乙個資料後堆的變化。
參***：
四、閱讀演算法
1、linklist mynote(linklist l)
l是不帶頭結點的單鏈表的頭指標
if(l&&l->next)
} 該演算法的功能是：
參***：遞迴地後序遍歷鏈式儲存的二叉樹
五、演算法填空
二叉搜尋樹的查詢——遞迴演算法:
bool find(btreenode* bst,elemtype& item)
else if(itemdata)
return find( bst->left ,item);
else return find( bst->right ,item);if}
六、編寫演算法
統計出單鏈表hl中結點的值等於給定值x的結點數。
int countx(lnode* hl,elemtype x)
參***：
int countx(lnode* hl,elemtype x)
//countx
資料結構試卷（二）
一、選擇題
1．下面關於線性表的敘述錯誤的是（ d ）。
a、 線性表採用順序儲存必須占用一片連續的儲存空間
b、 線性表採用鏈式儲存不必占用一片連續的儲存空間
c、 線性表採用鏈式儲存便於插入和刪除操作的實現
d、 線性表採用順序儲存便於插入和刪除操作的實現
2．設哈夫曼樹中的葉子結點總數為m，若用二叉鍊錶作為儲存結構，則該哈夫曼樹中總共有（ b ）個空指標域。
a、 2m-1 b、 2m c、 2m+1 d、 4m
3．設順序迴圈佇列q[0：m-1]的頭指標和尾指標分別為f和r，頭指標f總是指向隊頭元素的前一位置，尾指標r總是指向隊尾元素的當前位置，則該迴圈佇列中的元素個數為（ c ）。
a、 r-f b、 f-r c、(r-f+m)％m d、(f-r+m)％m
4．設某棵二叉樹的中序遍歷序列為abcd，前序遍歷序列為cabd，則後序遍歷該二叉樹得到序列為（a）。
a、 badc b、 bcda c、 cdab d、cbda
5．設某完全無向圖中有n個頂點，則該完全無向圖中有（ a ）條邊。
a、 n(n-1)/2 b、 n(n-1) c、 n2 d、 n2-1
6．設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（ c ）。
a、 9 b、 10 c、 11 d、 12
7．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（b ）個表頭結點。
a、 n-1 b、 n c、n+1 d、2n-1
8．設一組初始記錄關鍵字序列(5，2，6，3，8)，以第乙個記錄關鍵字5為基準進行一趟快速排序的結果為（c）。
a、 2，3，5，8，6 b、 3，2，5，8，6
c、 3，2，5，6，8 d、 2，3，6，5，8
二、填空題
1. 為了能有效地應用hash查詢技術，必須解決的兩個問題是（構造乙個好的hash函式）和（確定解決衝突的方法）。
2. 下面程式段的功能實現資料x進棧，要求在括號處填上正確的語句。
歷年資料結構試題答案
中國自考人 門自考課程永久免費 完整 學習快快加入我們吧！課程 02331 一 2001.10單項選擇題 本大題共15小題，每小題2分，共30分 1 d1011 12 13 14 15 二 填空題 本大題共10小題，每小題2分，共20分 16 儲存 或儲存結構 進棧和退棧19 1220 a4,821...
東北大學2023年資料結構試題
1 20分 簡要回答下列問題 注意 請將答案寫在答題紙上，並註明題號 3分 記憶體中一片連續空間 不妨假設位址從1到m 提供給兩個棧s1和s2使用，怎樣分配這部分儲存空間，使得對任乙個棧，僅當這部分空間全滿時才發生上溢。5分 假設字元a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12...
東北大學2023年資料結構試題
1 20分 簡要回答下列問題 注意 請將答案寫在答題紙上，並註明題號 3分 記憶體中一片連續空間 不妨假設位址從1到m 提供給兩個棧s1和s2使用，怎樣分配這部分儲存空間，使得對任乙個棧，僅當這部分空間全滿時才發生上溢。5分 假設字元a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12...