數學科學學院2013－2014學年第一學期期末考試試題
考試科目：資料結構年級：11 適用專業：資訊與計算科學
時間：120分鐘考試方式：閉卷試卷類別：a卷試題滿分：100分
一、單項選擇題（每小題 3 分，共30分）
1. 以下資料結構中哪乙個是線性結構？（ ）
（a）有向圖 （b）佇列 （c）線索二叉樹 （d）b樹
2. 在乙個單鏈表hl中，若要在當前由指標p指向的結點後面插入乙個由q指向的結點，則執行如下（ ）語句序列。
（a）p=q; p->next=qb）p->next=q; q->next=p;
（c）p->next=q->next; p=qd）q->next=p->next; p->next=q;
3. （ ）不是佇列的基本運算。
（a）在佇列第i個元素之後插入乙個元素 （b）從隊頭刪除乙個元素
（c）判斷乙個佇列是否為空d）讀取隊頭元素的值
4. 將乙個a[1..100,1..100]的三對角矩陣，按行優先存入一維陣列b[298]中，a中元素a66,65在b陣列中的位置k為（ ）（假設b[0]的位置是1）。
（a）195b）196c）197d）198
5. 設二叉樹中有n2個度為2的結點，n1個度為1的結點，n0個葉子結點，則此二叉樹採用二叉鍊錶儲存時空指標域個數為（ ）。
（a）n0+n1+n2 （b）n2+n1+2n0 （c）2n2+n1 （d）2n0+n1
6. 下面（ ）可以判斷出乙個有向圖中是否有環（迴路）？
（a）求關鍵路徑 （b）拓撲排序 （c）求最短路徑 （d）前面都不正確
7. 對線性表進行二分法查詢，其前提條件是（ ）。
（a）線性表以順序方式儲存，並且按關鍵字值排好序
（b）線性表以順序方式儲存，並且按關鍵字值的檢索頻率排好序
（c）線性表以鏈結方式儲存，並且按關鍵字值排好序
（d）線性表以鏈結方式儲存，並且按關鍵字值的檢索頻率排好序
8. 哈夫曼樹中一定不存在（ ）。
（a）度為0的結點 （b）度為1的結點 （c）度為2的結點 （d）帶權的結點
9. 用某種排序方法對關鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下：
30，15，25，21，47，27，68，35，84（初使列）
15，30，25，21，35，27，47，68，84（第一趟）
15，21，25，30，35，27，47，68，84（第二趟）
則所採用的排序方法是（ ）
（a）歸併排序 （b）希爾排序 （c）選擇排序 （d）快速排序
10. 若需在o(nlogn)的時間內完成對陣列的排序，且要求排序是穩定的，則可選擇（ ）。
（a）快速排序 （b）堆排序 （c）歸併排序 （d）直接插入排序
二、應用題、（每小題8分，共40分）
1. 試畫出表示式(a+b/c)*(d-e*f)的二叉樹表示，並寫出此表示式的波蘭式，中綴式及逆波蘭式。
2.對於圖2.2所示的有向圖若儲存它採用鄰接表，並且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈結的，給出鄰接表並寫出：
（1）從頂點v1出發進行深度優先搜尋所得到的頂點序列；
（2）從頂點v2出發進行廣度優先搜尋所得到的頂點序列。
圖2.2
3.一棵二叉樹的先序、中序和後序序列分別如下，其中有一部分未顯示出來。試求出空格處的內容並畫出這棵樹。
先序序列：_b_f_iceh_g
中序序列：d_kfia_ejc_
後序序列：_k_fbhj_g_a
4.設有序子串行：w=，試給出對應的：
（1）二叉排序樹； （2）哈夫曼樹；（3）平衡二叉樹；
5.已知雜湊表位址空間為0..8，雜湊函式為h(key)=key%7，採用線性探測再雜湊處理衝突，將資料序列依次存入此雜湊表中，列出插入時的比較次數，並求出在等概率下查詢成功時的平均查詢長度。
三、完成填空（每空2分，共10分）
1.如下為二分查詢的非遞迴演算法，試將其填寫完整。
int binsch(elemtype a[ ],int n,keytype k)
2. 下面是直接插入排序的演算法，請根據題意完成程式是點r[j+1] = l.r[0
void insertionsort ( sqlist &l ) } // insertsort
四、演算法題（每題10分，共20分）
1. 將兩個非遞減有序的有序表la、lb歸併為非遞增的有序表lc（有序表儲存方式為帶頭結點的單
鍊錶，利用原表結點）。
2. 編寫乙個演算法求二叉樹的深度。
A 第2學期資料結構期末考卷答案
誠信應考考出水平考出風格 浙江大學城市學院 2013 2014 學年第 2 學期期末考試答題卷 資料結構 開課單位 計算分院 考試形式 閉卷 考試時間 2014 年 06 月 29日 所需時間 120 分鐘 注 試卷答案必須寫在答卷上，寫在試卷上不得分。一 判斷題 有5條是正確的，將正確的編號寫在答...
資料結構第1章概論
二 單項選擇題 1.非線性結構是資料元素之間存在一種 a 一對多關係 b 多對多關係 c 多對一關係 d 一對一關係 2.資料結構中，與所使用的計算機無關的是資料的結構 a 儲存 b 物理 c 邏輯d 物理和儲存 3.演算法分析的目的是 a 找出資料結構的合理性 b 研究演算法中的輸入和輸出的關係 ...
資料結構習題 第1章
第一章概論自測題姓名班級 一 填空題 每空1分，共33分 1.乙個計算機系統包括和兩大部分。2.一台計算機中全部程式的集合，稱為這台計算機的 3.計算機軟體可以分為軟體和軟體兩大類。科學計算程式包屬於診斷程式屬於 4.一種用助憶符號來表示機器指令的操作符和運算元的語言是 5.資料結構是一門研究非數值...