北京理工大學資料結構10年期末試題
資料結構試卷(一)
一、單選題(每題 2 分,共20分)
1. 棧和佇列的共同特點是( )。
a.只允許在端點處插入和刪除元素
b.都是先進後出
c.都是先進先出
d.沒有共同點
2. 用鏈結方式儲存的佇列,在進行插入運算時( ).
a. 僅修改頭指標b. 頭、尾指標都要修改
c. 僅修改尾指標d.頭、尾指標可能都要修改
3. 以下資料結構中哪乙個是非線性結構?( )
a. 佇列 b. 棧 c. 線性表 d. 二叉樹
4. 設有乙個二維陣列a[m][n],假設a[0][0]存放位置在644(10),a[2][2]存放位置在676(10),每個元素佔乙個空間,問a[3][3](10)存放在什麼位置?腳注(10)表示用10進製表示。
a.688b.678 c.692 d.696
5. 樹最適合用來表示( )。
a.有序資料元素b.無序資料元素
c.元素之間具有分支層次關係的資料 d.元素之間無聯絡的資料
6. 二叉樹的第k層的結點數最多為( ).
a.2k-1 b.2k+1 c.2k-1 d. 2k-1
7. 若有18個元素的有序表存放在一維陣列a[19]中,第乙個元素放a[1]中,現進行二分查詢,則查詢a[3]的比較序列的下標依次為( )
a. 1,2,3b. 9,5,2,3
c. 9,5,3d. 9,4,2,3
8. 對n個記錄的檔案進行快速排序,所需要的輔助儲存空間大致為
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的元素有( )個,
a.1 b.2c.3d.4
10. 設有6個結點的無向圖,該圖至少應有( )條邊才能確保是乙個連通圖。
a.5 b.6 c.7 d.8
二、填空題(每空1分,共26分)
1. 通常從四個方面評價演算法的質量和
2. 乙個演算法的時間複雜度為(n3+n2log2n+14n)/n2,其數量級表示為________。
3. 假定一棵樹的廣義表表示為a(c,d(e,f,g),h(i,j)),則樹中所含的結點數為個,樹的深度為樹的度為
4. 字尾算式9 2 3 +- 10 2 / -的值為中綴算式(3+4x)-2y/3對應的字尾算式為
5. 若用鍊錶儲存一棵二叉樹時,每個結點除資料域外,還有指向左孩子和右孩子的兩個指標。在這種儲存結構中,n個結點的二叉樹共有________個指標域,其中有________個指標域是存放了位址,有個指標是空指標。
6. 對於乙個具有n個頂點和e條邊的有向圖和無向圖,在其對應的鄰接表中,所含邊結點分別有_______個和________個。
7. aov網是一種的圖。
8. 在乙個具有n個頂點的無向完全圖中,包含有________條邊,在乙個具有n個頂點的有向完全圖中,包含有________條邊。
9. 假定乙個線性表為(12,23,74,55,63,40),若按key % 4條件進行劃分,使得同一餘數的元素成為乙個子表,則得到的四個子表分別為和
10. 向一棵b_樹插入元素的過程中,若最終引起樹根結點的**,則新樹比原樹的高度
11. 在堆排序的過程中,對任一分支結點進行篩運算的時間複雜度為________,整個堆排序過程的時間複雜度為________。
12. 在快速排序、堆排序、歸併排序中排序是穩定的。
三、計算題(每題 6 分,共24分)
1. 在如下陣列a中鏈結儲存了乙個線性表,表頭指標為a [0].next,試寫出該線性表。
a 0 1 2 3 4 5 6 7
2. 請畫出下圖的鄰接矩陣和鄰接表。
3. 已知乙個圖的頂點集v和邊集e分別為:v=;
e=;用克魯斯卡爾演算法得到最小生成樹,試寫出在最小生成樹中依次得到的各條邊。
4. 畫出向小根堆中加入資料4, 2, 5, 8, 3時,每加入乙個資料後堆的變化。
四、閱讀演算法(每題7分,共14分)
1. linklist mynote(linklist l)
l是不帶頭結點的單鏈表的頭指標
if(l&&l->next)
該演算法的功能是:
五、演算法填空(共8分)
二叉搜尋樹的查詢——遞迴演算法:
bool find(btreenode* bst,elemtype& item)
六、編寫演算法(共8分)
統計出單鏈表hl中結點的值等於給定值x的結點數。
int countx(lnode* hl,elemtype x)
資料結構試卷(二)
一、選擇題(24分)
1.下面關於線性表的敘述錯誤的是( )。
(a) 線性表採用順序儲存必須占用一片連續的儲存空間
(b) 線性表採用鏈式儲存不必占用一片連續的儲存空間
(c) 線性表採用鏈式儲存便於插入和刪除操作的實現
(d) 線性表採用順序儲存便於插入和刪除操作的實現
2.設哈夫曼樹中的葉子結點總數為m,若用二叉鍊錶作為儲存結構,則該哈夫曼樹中總共有( )個空指標域。
(a) 2m-1 (b) 2m (c) 2m+1 (d) 4m
3.設順序迴圈佇列q[0:m-1]的頭指標和尾指標分別為f和r,頭指標f總是指向隊頭元素的前一位置,尾指標r總是指向隊尾元素的當前位置,則該迴圈佇列中的元素個數為( )。
(a) r-f (b) f-r (c) (r-f+m)%m (d) (f-r+m)%m
4.設某棵二叉樹的中序遍歷序列為abcd,前序遍歷序列為cabd,則後序遍歷該二叉樹得到序列為( )。
(a) badc (b) bcda (c) cdab (d) cbda
5.設某完全無向圖中有n個頂點,則該完全無向圖中有( )條邊。
(a) n(n-1)/2 (b) n(n-1) (c) n2 (d) n2-1
6.設某棵二叉樹中有2000個結點,則該二叉樹的最小高度為( )。
(a) 9 (b) 10 (c) 11 (d) 12
7.設某有向圖中有n個頂點,則該有向圖對應的鄰接表中有( )個表頭結點。
(a) n-1 (b) n (c) n+1 (d) 2n-1
8.設一組初始記錄關鍵字序列(5,2,6,3,8),以第乙個記錄關鍵字5為基準進行一趟快速排序的結果為( )。
(a) 2,3,5,8,6 (b) 3,2,5,8,6
(c) 3,2,5,6,8 (d) 2,3,6,5,8
二、填空題(24分)
1. 為了能有效地應用hash查詢技術,必須解決的兩個問題是和
2. 下面程式段的功能實現資料x進棧,要求在下劃線處填上正確的語句。
typedef struct sqstack;
void push(sqstack &stack,int x)
十套資料結構試題及答案
發布時間 2014 09 25石寒康 資料結構試卷 一 一 單選題 每題 2 分,共20分 1.棧和佇列的共同特點是 a.只允許在端點處插入和刪除元素 b.都是先進後出 c.都是先進先出 d.沒有共同點 2.用鏈結方式儲存的佇列,在進行插入運算時 a.僅修改頭指標 b.頭 尾指標都要修改 c.僅修改...
十套資料結構試題及答案
資料結構試卷 一 1 資料結構試卷 二 4 資料結構試卷 三 6 資料結構試卷 四 8 資料結構試卷 五 11 資料結構試卷 六 14 資料結構試卷 七 16 資料結構試卷 八 18 資料結構試卷 九 20 資料結構試卷 十 23 資料結構試卷 一 參 26 資料結構試卷 二 參 27 資料結構試卷...
北京理工大學珠海學院計算機專業資料結構培訓A卷
資料結構試卷a 一 單選題 每小題 2 分,共 8 分 1 在乙個長度為 n 的順序線性表中順序查詢值為 x 的元素時,查詢成功時的平均查詢長度 即 x 與元素的平均比較次數,假定查詢每個元素的概率都相等 為 a n b n 2 c n 1 2 d n 1 2 2 在乙個單鏈表中 若 q 所指結點是...