2007～2008學年第二學期資料結構科目考試試題 a卷
使用班級（教師填寫）：網路專07-1、2
一、單項選擇題（ 每小題2分，共20分）
1． 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨元素，則採用（ ）儲存方式最節省時間。
①單鏈表 ②雙鏈表 ③單向迴圈 ④順序表
2． 串是任意有限個（ ）
①符號構成的序列 ②符號構成的集合
③字元構成的序列 ④字元構成的集合
3． 設矩陣a（aij ，l≤i,j≤ 10）的元素滿足：
aij≠0(i≥j, l≤i, j≤ 10)
aij=0 (i現將a的所有非0元素以行序為主序存放在首位址為2000的儲存區域中，每個元素占有4個單元，則元素a[9][5]的首址為
①2340 ②2336 ③2164 ④2160
4． 如果以鍊錶作為棧的儲存結構，則退棧操作時（ ）
1 必須判別棧是否滿
2 對棧不作任何判別
3 必須判別棧是否空
4 判別棧元素的型別
5． 設陣列data[0..m]作為迴圈佇列sq的儲存空間，front為隊頭指標，rear為隊尾指標，則執行出隊操作的語句為（ ）
①front=front+1front=(front+1)% m
③rear=(rear+1)%m ④front=(front+1)%(m+1)
6． 深度為6（根的層次為1）的二叉樹至多有（ ）結點。
1 64 ②32 ③31 ④63
7． 將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1。編號為49的結點x的雙親編號為（ ）
①24 ②25 ③23 ④無法確定
8． 當初始序列已經按鍵值有序，用直接插入演算法對其進行排序，需要迴圈的次數為（ ）
①n2nlog2n ③log2nn-1
9． 堆是乙個鍵值序列,對i=1,2,…,|_n/2_|,滿足( )
①ki≤k2i≤k2i+1ki③ki≤k2i且ki≤k2i+1(2i+1≤n) ④ki≤k2i 或ki≤k2i+1(2i+1≤n)
10． 二分查詢要求被查詢的表是（ ）
1 鍵值有序的鏈結表 ②鏈結表但鍵值不一定有序
③ 鍵值有序的順序表 ④順序表但鍵值不一定有序
二、 判斷題（判斷下列各題是否正確，正確在括號內打「v」，錯的 「x」。每小題1分，共10分）
1． 單鏈表中頭指標總是指著第乙個結點。（ ）
2． 在迴圈佇列中，front指向佇列中第乙個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件是front=rear。（ ）
3． 對鍊錶進行插入和刪除操作時，不必移動結點。（ ）
4． 棧可以作為實現程式語言過程呼叫時的一種資料結構。（ ）
5． 在乙個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧。( )i
6． 對有向圖g，如果從任一頂點出發進行一次深度優先或廣度優先搜尋就能訪問每個頂點，則該圖一定是完全圖。( )
7． 「順序查詢法」是指在順序表上進行查詢的方法。（ ）
8． 向二叉排序樹插入乙個新結點時，新結點一定成為二叉排序樹的乙個葉子結點。（）
9． 鍵值序列是乙個堆。
10 二路歸併時，被歸併的兩個子串行中的關鍵字個數一定要相等。（）
三、 綜合題（本題共45分）
1． 對下圖所示的樹，用後根遍歷方法進行遍歷，請寫出遍歷所得到的結點訪問序列。（5分）
2. 將上圖的樹轉換為二叉樹。（5分）
3. 下圖表示乙個地區的交通網，頂點表示城市，邊表示鏈結城市間的公路，邊上的權表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案。（5分）
4．已知乙個無向圖的鄰接表如下圖所示。（10分
(1) 畫出這個圖。
(2) 以v1為出發點，對圖進行廣度優先搜尋，寫出所有可能的訪問序列。
5. 給定資料表（jan,feb,mar,apr,may,jun,jun,aug,sep,oct,nov,dec）.設取雜湊函式h(x)= i mod 13 ,其中i為鍵值中第乙個字母的ascii值，要求：
（1） 畫出相應的雜湊列表，以線性探測法處理衝突；
（2） 求在等概率情況下查詢成功時的平均查詢長度。（10分 ）
6. 有一組鍵值25，84，21，47，15，27，68，35，24，採用快速排序方法由小到大進行排序，請寫出每趟的結果，並標明在第一趟排序過程中鍵值的移動情況。（10分）
四、設計題（共25分）
1． 二叉樹以二叉鍊錶為儲存結構，結點結構為[, ] 。設計乙個演算法，編寫按層次順序遍歷二叉樹的演算法。 （15分）
2． 設n個元素的有序表為ｒ，ｋ為乙個給定的值，二分查詢演算法如下：（10分）
int binsearch(sqlist r, keytype k)
}if (suc) return(mid); else return(0);
}將上述演算法中劃線語句改為：k（1） 改動後，演算法能否正常工作？請說明原因。
（2）若演算法不能正常工作，給出乙個查詢序列和乙個出錯情況的查詢鍵值；若能正常工作，請給出乙個查詢序列和查詢某個鍵值的比較次數。
資料結構試題及答案
資料結構試卷 一 一 單選題 每題 2 分，共20分 1.棧和佇列的共同特點是 a a.只允許在端點處插入和刪除元素 b.都是先進後出 c.都是先進先出 d.沒有共同點 2.用鏈結方式儲存的佇列，在進行插入運算時 d a.僅修改頭指標b.頭 尾指標都要修改 c.僅修改尾指標d.頭 尾指標可能都要修改...
資料結構試題及答案
2 二維陣列是陣列元素為一維陣列的線性表，因此它是線性結構。3 順序錶用一維陣列作為儲存結構，因此順序表是一維陣列。4 通常使用兩個類來協同表示單鏈表，即鍊錶的結點類和鍊錶類。5 棧和佇列都是順序訪問的的線性表，但它們對訪問位置的限制不同。6 在使用字尾表表示實現計算器時用到乙個棧的例項，其作用是暫...
資料結構試題及答案
資料結構 自考複習思考試題 一 單選題 從選擇的答案中選出正確的答案，將其字母編號填入下列敘述中的括號內。每小題 3分，共24分 1 向乙個有127個元素原順序表中插入乙個新元素並儲存原來順序不變，平均要移動 個元素。a 8 b 63.5 c 63 d 7 2 設有乙個二維數a m n 假設a 0 ...