2010級夜大資料結構期末考試試題 （a卷）
姓名學號序號： 成績：
注意事項：本試卷滿分100分，考試時間120分鐘；
一. 單項選擇題，每題有乙個正確選擇。（每題2分，共20分）
1. 下列資料結構中是線性結構。
a二叉樹 b 樹 c佇列 d 圖
2. 以下關於演算法的說法不正確的是
a 乙個演算法應包含有限個步驟 b 演算法越簡單越好
c 演算法中的每個步驟都能在有限時間內完成
d 演算法中的所有操作都可以通過已經實現的基本操作運算有限次實現之
3. 下列有關線性表的敘述中，正確的是
a 乙個線性表是 n 個資料元素的有限序列
b 線性表中任何乙個元素有且僅有乙個直接前驅
c 線性表中任何乙個元素有且僅有乙個直接後繼
d 以上說法都不正確
4. 若線性表採用順序儲存結構，假設每個資料元素占用4個儲存單元，並且已知第乙個元素的儲存位置為100，則第12個資料元素的儲存位址為
a 148b 112c 111d 144
5. 在乙個鏈棧中，已知s為棧頂指標（直接指向棧頂元素結點，無頭結點），t為棧底指標，直接指向棧底元素，則插入r結點的操作為
a t->next=r;t=r; b r->next=s;s=r; c s->next=r;s=r; d r->next=t;
6. 迴圈佇列用陣列a[0..m-1]存放其元素值，已知其頭尾指標分別是front和rear，則當前佇列中的元素個數是
a (rear-front+m)%m b rear-front+1 c rear-front-1 d rear-front
7. 設樹t的度為4，其中度為1、2、3和4的結點個數分別是4、2、1和1，則t中葉結點的個數是______ 。
a 6 b 7 c 8 d 9
8. 根據使用頻率為5個字元設計的哈夫曼編碼不可能是
a 111，110，10，01，00b 000，001，010，011，1
c 100，11，10，1，0d 001，000，01，11，10
9. 對線性表進行二分查詢，要求線性表必須
a 以順序方式儲存b 以順序方式儲存，且結點按關鍵字有序排序
c 以鏈結方式儲存d以鏈結方式儲存，且結點按關鍵字有序排序
10. 對於長度為n的線性表,在最壞情況下,下列各種排序所對應的比較次數中正確的是
a 冒泡順序為n/2 b 冒泡順序為n
c 快速排列為nd 快速排序為n(n+1)/2
二. 填空題，請將正確答案填在____上。（每空2分，共30分）
1. 對資料進行檢索、插入、刪除、合併、拆分、排序、統計、簡單計算、轉換、輸入、輸出等的操作過程叫做
2. 鏈式儲存結構用一組位址任意的儲存單元依次存放資料元素，資料元素之間的邏輯關係通過間接地反映。
3. 廣義表((a),(((b),c)),(d))的長度是深度是
4. 棧的特點是與之對應，佇列的特點是先進先出。在棧頂進行插入刪除乙個元素的時間複雜度是
5. 在順序儲存的二叉樹中,編號為i和j的兩個結點處在同一層的條件是______ 。
6. 在乙個無向圖中，所有頂點的度數之和等於所有邊的數目的_________倍。
7. 將資料元素2,4,6,8,10,12,14,16,18,20依次存放於一維陣列a[0..9]中，然後採用二分查詢方法查詢元素12，被比較過的陣列元素的下標依次為
8. 外排序是指在排序前後，資料在________上，排序時資料調入記憶體進行的排序方法。
9.深度為k的完全二叉樹至少有個結點，至多有個結點，若按從上到下，從左到右的次序給結點編號（從1開始），則編號最小的葉子結點的編號是
10. 每趟排序從未排序的子串行中依次取出元素與已經排好序的序列中元素進行比較，然後將其放在已經排好序的序列的合適位置。這種排序法稱為_________排序法。
11.已知乙個圖的鄰接矩陣表示，計算第i個結點的入度的方法是
三. 判斷題，正確者在（）中打√，錯誤者在（）中打×。（每小題2分，共20分）
1. 棧和佇列都是操作受限的線性表。
（ ）
2. 判斷乙個環形佇列qu（最多元素為maxsize）為空的條件為qu->front==qu->rear+1。
（ ）
3.從乙個棧頂指標為hs的鏈棧中刪除乙個結點時，用x儲存被刪結點的值，則執行x=hs;hs=hs->next的操作。
（ ）
4. 外排序是指在外存上進行的排序方法。
（ ）
5.樹形結構中，每個結點的前驅結點和後續結點可以任意多個。
（ ）
6.乙個演算法可以永無止境的運算下去。
（ ）
7.樹中結點的最大度數沒有限制，而二叉樹的最大度數為2.
（ ）
8. 結點最少的樹為只有乙個結點的樹。
（ ）
9.快速排序的時間複雜度為o(log2n)
（ ）
10. 在n個頂點的無向圖中，若邊數》n-1，則該圖必是連通圖。
（ ）
四. 問答題。（每小題5分，共30分）
1. 設長度為n的鏈隊用單迴圈鍊錶表示，若只設頭指標，則入隊出隊操作的時間複雜度為多少？ 若只設尾指標呢？請分別說明詳細理由。
2.根據二叉樹的定義，具有3個結點的二叉樹有多少種不同的形態？請分別畫出。
l=((a),(((b),c)),(d))
4.已知下圖二叉排序樹的各結點數值依次為12-20，請標出結點的數值。
5. 一棵二叉樹的結點資料採用順序儲存結構，儲存於陣列t中，入下圖，請畫出該二叉樹的鏈式儲存圖。結點形式：
6. 對如下的圖，用prim演算法從頂點1開始求最小生成樹，寫出按次序產生的邊。採用 kruscal演算法產生的邊次序是哪些？畫出最小生成樹。
資料結構期末考試題及答案
2012年資料結構期末考試題及答案 一 選擇題 1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d ...
資料結構》期末考試試卷 含答案
一 選擇題 每小題2分，共24分 1 計算機識別 儲存和加工處理的物件被統稱為 a a.資料b.資料元素 c.資料結構d.資料型別 2 棧和佇列都是 a a 限制訪問位置的線性結構b 順序儲存的線性結構 c 鏈式儲存的線性結構d 限制訪問位置的非線性結構 3 鏈棧與順序棧相比，比較明顯的優點是 d ...
資料結構及演算法期末考試複習試題
資料結構與演算法 複習題 一 選擇題。1 在資料結構中，從邏輯上可以把資料結構分為 c a 動態結構和靜態結構 b 緊湊結構和非緊湊結構 c 線性結構和非線性結構 d 內部結構和外部結構 2 資料結構在計算機記憶體中的表示是指 a a 資料的儲存結構 b 資料結構 c 資料的邏輯結構 d 資料元素之...