全國2023年10月高等教育自學考試
資料結構試題
課程**：02331
請考生按規定用筆將所有試題的答案塗、寫在答題紙上。
選擇題部分
注意事項：
1. 答題前，考生務必將自己的考試課程名稱、姓名、准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。
2. 每小題選出答案後，用2b鉛筆把答題紙上對應題目的答案標號塗黑。如需改動，用橡皮擦乾淨後，再選塗其他答案標號。不能答在試題卷上。
一、單項選擇題(本大題共15小題，每小題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．迪傑斯特拉(dijkstra)演算法的功能是
a．求圖中某頂點到其他頂點的最短路徑 b．求圖中所有頂點之間的最短路徑
c．求圖的最小生成樹 d．求圖的拓撲排序序列
5．若棧的進棧序列為1，2，3，4，5，則經過出入棧操作不可能獲得的出棧序列是
a．4，5，3，2，1 b．4，3，5，1，2
c．1，2，3，4，5 d．5，4，3，2，1
6．a是7×4的二維陣列，按行優先方式順序儲存，元素a[0][0]的儲存位址為1 000，若每個元素佔2個位元組，則元素a[3][3]的儲存位址為
a．1015 b．1016
c．1028 d．1030
7．深度為4的完全二叉樹的結點數至少為
a．4 b．8
c．13 d．15
8．若採用鄰接矩陣a儲存有向圖g，則結點k的入度等於a中
a．結點k對應行元素之和 b．結點k對應列元素之和
c．結點k對應行和列元素之和 d．非零元素之和
9．無向圖g的鄰接矩陣一定是
a．對稱矩陣 b．對角矩陣
c．三角矩陣 d．單位矩陣
10．下列關於有向帶權圖g的敘述中，錯誤的是
a．圖g的任何一棵生成樹都不含有迴路
b．圖g生成樹所含的邊數等於頂點數減1
c．圖g含有迴路時無法得到拓撲序列
d．圖g的最小生成樹總是唯一的
11．在下列排序演算法中，關鍵字比較次數與初始排列次序無關的是
a．氣泡排序 b．希爾排序
c．直接插入排序 d．直接選擇排序
1 2．對下圖進行拓撲排序，可以得到的拓撲序列是
a．a b c d e b．b a c d e
c．b c a d e d．a b d c e
13．下列線性表中，能使用二分查詢的是
a．順序儲存(2,12,5,6,9,3,89,34,25) b．鏈式儲存(2,12,5,6,9,3,89,34,25)
c．順序儲存(2,3,5,6,9,12,25,34,89) d．鏈式儲存(2,3,5,6,9,12,25,34,89)
14．在下列查詢方法中，平均查詢長度與結點數量無直接關係的是
a．順序查詢 b．分塊查詢
c．雜湊查詢 d．基於b樹的查詢
15．下列排序演算法中，時間複雜度為o(nlog2 n)的演算法是
a．快速排序 b．氣泡排序
c．直接選擇排序 d．直接插入排序
非選擇題部分
注意事項：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。
二、填空題(本大題共10小題，每小題2分，共20分)
1 6．資料的同一種邏輯結構，可以對應多種不同的
17．若在長度為n的順序表第i個元素之前插入乙個元素，則需要向後移動的元素個數是
18．順序棧存放在s[m]中，s[0]為棧底，棧頂指標top初始值為-1，則棧滿的條件是top
19．佇列只能在隊尾進行插入操作，在隊首進行操作。
20．廣義表a=(x，((y，z)，a，b))，則函式head(head(tail(a)))的值是
21．以權值分別為4，3，2，1的四個葉子結點構成的哈夫曼樹，其帶權路徑長度wpl是_______。
22．圖的遍歷方法有兩種，一種是深度優先遍歷，另一種是
23．如果排序演算法是穩定的，則關鍵字相同的兩個記錄排序前後相對次序
24．己知雜湊表表長m=11，雜湊函式h(key)=key％11，表中存有三個關鍵字15，27，39，其餘位址為空，若採用線性探查法處理衝突，則關鍵字為60的結點儲存的位址是
25．己知圖g的鄰接表如題25圖所示。
從頂點v1出發進行深度優先搜尋，得到的深度優先搜尋序列是
三、解答題(本大題共4小題，每小題5分，共20分)
26．設q[m]是有m個元素儲存空間的迴圈佇列，若front指向隊首元素，rear指向隊尾
元素的下一位置，請分別用c語言描述下列操作：
(1)將元素x入隊；
(2)將隊首元素出隊，並儲存到變數y中；
(3)計算當前佇列中元素個數。
27．己知帶權圖g=(ve)，其中v=(a，b，c，d，e)，鄰接矩陣如下
(1)畫出對應的圖g
(2)畫出圖g的最小生成樹
28．已知一組待排記錄的關鍵字序列為(15，11，17，59，14，35，13，17，24，84)，請給出對應的小根堆序列。
29．已知二叉樹如題29圖，請畫出該二叉樹的前序線索。
四、演算法閱讀題(本大題共4小題，每小題5分，共20分)
30．閱讀下列函式並回答問題
typedef struct nodelinknode；
typedef linknode*linklist；
void delex(linklist head，datatype x)
else
}(1)執行該函式後，單鏈表head中data值為x的結點數是多少?
(2)該函式的功能是什麼?
31．閱讀下列函式並回答問題
typedef struct nodebintnode；
typedef b intnode *bintree；
void inorder(bintree bt)
}(1)給出對如題3 1圖所示的二叉樹執行函式inorder後得到的輸出序列。
(2)該函式的功能是什麼?
32．下列函式實現直接插入排序，請填寫適當內容，使其功能完整。
void f32(int r，int n)
r[j+l]= r[0]； }}
33．函式binsearch實現二分查詢，請回答下列問題。
(1)在空白處填寫適當內容，使函式功能完整。
(2)查詢成功時函式的返回值是什麼?
(3)查詢失敗時函式的返回值是什麼?
int binsearch(seqlist r，keytype k，int n)
return-1；
}五、演算法設計題(本題10分)
34．已知：
typedef struct node linknode；
typedef linknode *linklist；
請編寫原型為int listisequal(linklist a，linklist b)的函式，指標a、b分別指向兩個帶頭結點的單鏈表。函式功能是：若單鏈表a、b中全部對應結點的data值相等，則返回1，否則返回0。
全國高等教育自學考試資料結構
全國2012年10月高等教育自學考試 資料結構導論試題及答案 課程 02142 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上...
全國高等教育自學考試資料結構試題
全國2007年10月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下面程式段的時間複雜度為 s 0 for i 1 i for j ...
全國高等教育自學考試資料結構試題
資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1 按值可否分解，資料型別通常可分為兩類，它們是 a 靜態型別和動態型別 b 原子型別和表型別 c 原子型別...