蝸牛**更多免費學習資料等待您的光臨！
資料結構期末考試試卷（ a ）
一、 選擇題（每小題2分，共24分）
1．計算機識別、儲存和加工處理的物件被統稱為( a )
a.資料b.資料元素
c.資料結構d.資料型別
2．棧和佇列都是（ a ）
a．限制訪問位置的線性結構b．順序儲存的線性結構
c．鏈式儲存的線性結構d．限制訪問位置的非線性結構
3．鏈棧與順序棧相比，比較明顯的優點是( d )
a.插入操作更加方便b.刪除操作更加方便
c.不會出現下溢的情況d.不會出現上溢的情況
4．採用兩類不同儲存結構的字串可分別簡稱為( b )
a.主串和子串b.順序串和鏈串
c.目標串和模式串d.變數串和常量串
5． 乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的位址是：b
a. 110 b .108
c. 100 d. 120
6．串是一種特殊的線性表，其特殊性體現在：b
a.可以順序儲存 b .資料元素是乙個字元
c. 可以鏈結儲存 d. 資料元素可以是多個字元
7．設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為： c
a. 2h b .2h-1
c. 2h+1 d. h+1
軟體開發網
8．樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這裡，我們把由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。下列結論哪個正確？ a
a. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同
b .樹的後根遍歷序列與其對應的二叉樹的後序遍歷序列相同
c. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同
d. 以上都不對
9．乙個有n個頂點的無向圖最多有多少邊？c
a. nb .n(n-1)
c. n(n-1)/2 d. 2n
10．在乙個圖中，所有頂點的度數之和等於所有邊數的多少倍?c
a. 1/2 b .1
c. 2d. 4
11．當在二叉排序樹中插入乙個新結點時，若樹中不存在與待插入結點的關鍵字相同的結點，且新結點的關鍵字小於根結點的關鍵字，則新結點將成為（ a ）
a．左子樹的葉子結點b．左子樹的分支結點
c．右子樹的葉子結點d．右子樹的分支結點
軟體開發網
12．對於雜湊函式h(key)=key%13,被稱為同義詞的關鍵字是( d )
a.35和41b.23和39
c.15和44d.25和51
二、已知某棵二叉樹的前序遍歷結果為a,b,d,e,g,c,f,h,i,j，其中中序遍歷的結果為d,b,g,e,a,h,f,i,j,c。請畫出二叉的具體結構。（注意要寫出具體步驟）（10分）
原理見課本128頁
三、有圖如下，請寫出從頂點c0出發的深度優先及寬度優先遍歷的結果。(10分
深度優先；c0-c1-c3-c4-c5-c2
寬度優先：c0-c1-c2-c3-c4-c5
四、有圖如下，按kruskal演算法求出其最小生成樹。要求寫出完整的步驟。（10分）
原理見課本250頁
五、給定線性表（12，23，45，66，76，88，93，103，166），試寫出在其上進行二分查詢關鍵字值12，93，166的過程。並寫出二分查詢的演算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
過程：mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
演算法：見課本84頁上
六、知單鏈表的結點結構為
data next
下列演算法對帶頭結點的單鏈表l進行簡單選擇排序，使得l中的元素按值從小到大排列。
請在空缺處填入合適的內容，使其成為完整的演算法。 (可用文字說明該演算法的基本思想及執行的過程，10分)
void selectsort(linkedlist l)
if( (3) )
(4) ;
}}本題不會。嘿嘿。。。。
七、乙個完整的演算法應該具有哪幾個基本性質？分別簡要說明每一性質的含意。(5分)
輸入：四個基本性質：1.輸入：有零個或多個有外部提供的量作為演算法的輸入
2：輸出：演算法產生至少乙個量作為輸出
3.：確定性：組成演算法的每條指令是清晰的，無歧異的。
4.：有限性：演算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的
八、何謂佇列的"假溢"現象？如何解決？（5分）
佇列的假溢現象是指數組實現的順序佇列中，隊尾指標已到達陣列的下表上界產生上溢而隊頭指標之前還有若干空間閒置的現象。解決的辦法之一是利用迴圈佇列技術使陣列空間的首尾相連。
九、說明並比較檔案的各種物理結構。（6分）
順序結構，鏈結結構，索引結構
資料結構》期末考試試卷 含答案
一 選擇題 每小題2分，共24分 1 計算機識別 儲存和加工處理的物件被統稱為 a a.資料b.資料元素 c.資料結構d.資料型別 2 棧和佇列都是 a a 限制訪問位置的線性結構b 順序儲存的線性結構 c 鏈式儲存的線性結構d 限制訪問位置的非線性結構 3 鏈棧與順序棧相比，比較明顯的優點是 d ...
2023年資料結構期末考試題及答案
一 選擇題 1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d 資料元素之間的關係 3 在資料結構中...
2023年資料結構期末考試題及答案
一 選擇題 1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d 資料元素之間的關係 3 在資料結構中...