課程**：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1.下述檔案中適合於磁帶儲存的是（ ）
a.順序檔案 b.索引檔案
c.雜湊檔案 d.多關鍵字檔案
2.某二叉樹的後根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為（ ）
3.含有n個結點的二叉樹用二叉鍊錶表示時，空指標域個數為( )
4.在乙個圖中，所有頂點的度數之和與圖的邊數的比是( )
a.1∶2 b.1∶1
c.2∶1 d.4∶1
5.長度為n的鏈佇列用單迴圈鍊錶表示，若只設頭指標，則出隊操作的時間複雜度為( )
6.下述幾種排序方法中，要求記憶體量最大的是( )
a.插入排序 b.快速排序
c.歸併排序 d.選擇排序
7.對n個不同值進行氣泡排序，在元素無序的情況下比較的次數為( )
8.對線性表進行二分查詢時，要求線性表必須( )
a.以順序方式儲存
b.以鏈式方式儲存
c.以順序方式儲存，且結點按關鍵字有序排列
d.以鏈結方式儲存，且結點按關鍵字有序排列
9.在表長為n的順序表上做刪除運算，其平均時間複雜度為( )
10.當利用大小為n的陣列順序儲存乙個佇列時，該佇列的最大容量為( )
11.有關插入排序的敘述，錯誤的是( )
a.插入排序在最壞情況下需要o(n2)時間
b.插入排序在最佳情況可在o(n)時間內完成
c.插入排序平均需要o(nlog2n)時間
d.插入排序的空間複雜度為o(1)
12.有關樹的敘述正確的是( )
a.每乙個內部結點至少有乙個兄弟
b.每乙個葉結點均有父結點
c.有的樹沒有子樹
d.每個樹至少有乙個根結點與乙個葉結點。
13.迴圈佇列儲存在陣列元素a[0]至a[m]中，則入隊時的操作為( )
14.關於串的的敘述，不正確的是( )
a.串是字元的有限序列
b.空串是由空格構成的串
c.替換是串的一種重要運算
d.串既可以採用順序儲存，也可以採用鏈式儲存
15.對稱矩陣a[n][n]，a[1][1]為首元素，將下三角(包括對角線)元素以行優先順序儲存到一維陣列元素t[1]至t[n(n+1)／2]中，則任一上三角元素a[i][j]存於t[k]中，下標k為( )
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.下列程式段的時間複雜度為
for(i=1；i<=n；i++)
for(j=1；j<=n；j++)
for(k=1；k<=n；k++)
s=i+j+k；
17.在資料結構中，各個結點按邏輯關係互相纏繞，任意兩個結點可以鄰接的結構稱為
18.在單鏈表中，儲存每個結點有兩個域，乙個是資料域，另乙個是指標域，指標域指向該結點的。
19.在棧結構中，允許插入的一端稱為
20.從乙個長度為n的順序表中刪除第i個元素(1≤i≤n)時，需向前移動個元素。
21.乙個棧的輸入序列是1，2，3，…，n，輸出序列的第乙個元素是n，則第i個輸出元素為
22.迴圈佇列被定義為結構型別，含有三個域：data、front和rear，則迴圈佇列sq為空的條件是
23.乙個10階對稱矩陣a，採用行優先順序壓縮儲存上三角元素，a00為第乙個元素，其儲存位址為0，每個元素占有1個儲存位址空間，則a45的位址為
24.對於一棵滿二叉樹，若有m個葉子，則樹中結點數為
25.含有n個頂點和n-1條邊的連通圖g採用儲存結構較省空間。
26.在圖中，第乙個頂點和最後乙個頂點相同的路徑稱為
27.動態查詢中兩個元素x，y存入同乙個雜湊表時，x、y鍵值相同，則這種情況稱為
28.堆排序需個記錄大小的輔助儲存空間。
三、應用題(本大題共5小題，每小題6分，共30分)
29.有一字串的次序為-3*y+a／y！2，試利用棧將輸出次序改變為3y*-ay！2／+，試寫出進棧和退棧的操作步驟。(用push(x)表示x進棧，pop(x)表示x退棧)
30.已知一棵二叉樹的先根遍歷序列為abcdeghf，中根遍歷序列為cbedagfh，畫出該
二叉樹。
31.題31圖中二叉排序樹的各結點的值為32～40，標出各結點的值。
題31圖
32.下述矩陣表示乙個無向網，畫出該無向網，並構造出其最小生成樹。
33.什麼是堆?寫出對應於序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆頂元素取最小值)。
四、演算法設計題(本大題共2小題，每小題7分，共14分)
34.二叉樹按二叉鍊錶形式儲存，編寫乙個演算法判別給定的二叉樹是否為完全二叉樹。
35.試寫出直接插入排序演算法。
自考資料結構真題
絕密 考試結束前 全國2013年10月高等教育自學考試 資料結構試題 課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把...
自考資料結構試題真題
全國2012年1月高等教育自學考試 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.每個結點有且僅有乙個直接前趨和多個 或無 直接後繼 第乙個結點除外 的資料結構稱為...
資料結構導論自考試題
全國2008年10月高等教育自學考試 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.從邏輯上可以把資料結構分為 a.動態結構 靜態結構 b.順序結構 鏈式結構 c....