課程**：02331
請考生按規定用筆將所有試題的答案塗、寫在答題紙上。
選擇題部分
注意事項：
1. 答題前，考生務必將自己的考試課程名稱、姓名、准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。
2. 每小題選出答案後，用2b鉛筆把答題紙上對應題目的答案標號塗黑。如需改動，用橡皮擦乾淨後，再選塗其他答案標號。不能答在試題卷上。
一、單項選擇題(本大題共l5小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其選出並將「答題
紙」的相應**塗黑。錯塗、多塗或未塗均無分。
1．乙個演算法的時間耗費的數量級稱為該演算法的
a．效率 b．難度
c．可實現性 d．時間複雜度
2．順序表便於
a．插入結點 b．刪除結點
c．按值查詢結點 d．按序號查詢結點
3．設帶頭結點的單迴圈鍊錶的頭指標為head，指標變數p指向尾結點的條件是
a．p->next->next==head b．p->next==head
c．p->next->next==null d．p->next==null
4．設以陣列a[0..m-1]存放迴圈佇列，front指向隊頭元素，rear指向隊尾元素的下乙個位置，則當前佇列中的元素個數為
a．(rear-front+m)％m b．rear-front+1
c．(front-rear+m)％m d．(rear-front)％m
5．下列關於順序棧的敘述中，正確的是
a．入棧操作需要判斷棧滿，出棧操作需要判斷棧空
b．入棧操作不需要判斷棧滿，出棧操作需要判斷棧空
c．入棧操作需要判斷棧滿，出棧操作不需要判斷棧空
d．入棧操作不需要判斷棧滿，出棧操作不需要判斷棧空
6．a是乙個10×10的對稱矩陣，若採用行優先的下三角壓縮儲存，第乙個元素a0,0的儲存位址為1，每個元素佔乙個儲存單元，則a7,5的位址為
a．25 b．26
c．33 d．34
7．樹的後序遍歷等價於該樹對應二叉樹的
a．層次遍歷 b．前序遍歷
c．中序遍歷 d．後序遍歷
8．使用二叉線索樹的目的是便於
a．二叉樹中結點的插入與刪除 b．在二叉樹中查詢雙親
c．確定二叉樹的高度 d．查詢乙個結點的前趨和後繼
9．設無向圖的頂點個數為n，則該圖邊的數目最多為
a．n-l b．n(n-1)／2
c．n(n+1)／2 d．n2
10．可進行拓撲排序的圖只能是
a．有向圖 b．無向圖
c．有向無環圖 d．無向連通圖
11．下列排序方法中穩定的是
a．直接插入排序 b．直接選擇排序
c．堆排序 d．快速排序
12．下列序列不為堆的是
a．75,45,65,30,15,25 b．75,65,45,30,25,15
c．75,65,30,l5,25,45 d．75,45,65,25,30,15
13．對線性表進行二分查詢時，要求線性表必須是
a．順序儲存 b．鏈式儲存
c．順序儲存且按關鍵字有序 d．鏈式儲存且按關鍵字有序
14．分別用以下序列生成二叉排序樹，其中三個序列生成的二叉排序樹是相同的，不同
的序列是
a．(4,1,2,3,5) b．(4,2,3,l,5)
c．(4,5,2,1,3) d．(4,2,1,5,3)
15．下列關於m階b樹的敘述中，錯誤的是
a．每個結點至多有m個關鍵字
b．每個結點至多有m棵子樹
c．插入關鍵字時，通過結點**使樹高增加
d．刪除關鍵字時通過結點合併使樹高降低
非選擇題部分
注意事項：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。
二、填空題(本大題共10小題，每小題2分，共20分)
16．資料元素之間的邏輯關係稱為資料的______結構。
17．**性表中，表的長度定義為______。
18．用s表示入棧操作，x表示出棧操作，若元素入棧的順序為1、2、3、4，為了得到
1、3、4、2的出棧順序，相應的s和x的操作序列為______。
19．在二叉樹中，帶權路徑長度最短的樹稱為______。
20．已知廣義表g，head(g)與tail(g)的深度分別為4和6，則g的深度是______。
21．一組字元(a,b,c,d)在文中出現的次數分別為(7，6，3，5)，字元＇d＇的哈夫曼編碼的長度為______。
22．在乙個具有n個頂點的無向圖中，要連通全部頂點至少需要______條邊。
23．直接選擇排序演算法的時間複雜度是______。
24．對於長度為81的表，若採用分塊查詢，每塊的最佳長度為______。
25．用二叉鍊錶儲存有n個結點的二叉樹，則結點中有______個空指標域。
三、解答題(本大題共4小題，每小題5分，共20分)
26．假設q是乙個具有11個元素儲存空間的迴圈佇列(隊尾指標指向隊尾元素的下一
個位置，隊頭指標指向隊頭元素)，初始狀態q.front=q.rear=0；寫出依次執行
下列操作後頭、尾指標的當前值。
a,b,c,d,e,f入隊，a,b,c,d出隊； (1) q.front=______；q.rear=______。
g,h,i,j,k,l入隊，e,f,g,h出隊； (2) q.front=______；q.rear=______。
m,n,o,p入隊， i,j,k,l,m出隊； (3) q.front=______；q.rear=______。
27．已知乙個無向圖如題27圖所示，以①為起點，用普里姆(prim)演算法求其最小生成樹，畫出最小生成樹的構造過程。
28．用歸併排序法對序列 (98,36,-9,0,47,23,1,8)進行排序，問：
(1)一共需要幾趟歸併可完成排序。
(2)寫出第一趟歸併後資料的排列次序。
29．一組記錄關鍵字(55,76,44,32,64,82,20,16,43)，用雜湊函式h(key)=key％11將記錄
雜湊到雜湊表ht[0..12]中去，用線性探測法解決衝突。
(1)畫出存入所有記錄後的雜湊表。
(2)求在等概率情況下，查詢成功的平均查詢長度。
四、演算法閱讀題(本大題共4小題，每小題5分，共20分)
30．順序表型別定義如下：
# define listsize 100
typedef struct seqlist；
閱讀下列演算法，並回答問題：
void f30(seqlist *l)
l->data[j-1]=l->data[j];
l->length--;
}else i++
}（1）若l->data 中的資料為（22,4,63,0,15,29,34,42,3）,則執行上述演算法後l->data中的資料以及l->length的值各是什麼？
（2）該演算法的功能是什麼？
31.有向圖的鄰接矩陣型別定義如下：
#define mvn 100最大頂點數
typedef int etype邊上權值型別
typedef struct
}(1)stepl到step2之間的二重迴圈語句的功能是什麼?
(2)step2之後的二重迴圈語句的功能是什麼?
32．閱讀下列演算法，並回答問題：
void f32(int r， int n)
} (1)這是哪一種插入排序演算法?該演算法是否穩定?
(2)設定r[0]的作用是什麼?
33．順序表型別定義如下：
typedef int seqlist[100]；
void f33(seqlist r， int n)
{ int a, b，i；
if (r[0] { a=r[0]；b=r[1]； >
全國自學考試資料結構試題
課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.每個結點有且僅有乙個直接前趨和多個 或無 直接後繼 第乙個結點除外 的資料結構稱為 a.樹狀結構 b.網狀結構 c.線...
自學考試資料結構導論試題
全國2007年1月高等教育自學考試 資料結構導論試題 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1 關於棧和佇列的說法中正確的是 a 棧和佇列都是線性結構 b.棧是...
自學考試《資料結構》複習指導
第一章 緒論 一 概念 資料結構 是一門研究程式設計中計算機操作的物件以及它們之間的關係和運算的一門學科。資料 是描述額觀事物的數 字元以及所有能輸入到計算機中被電腦程式加工處理的資訊的集合。資料元素 資料元素是資料的基本單位。乙個資料項或多個資料項 域 資料項是資料的最小單位。結點 頂點 記錄。資...