- 歡迎訪問重慶自考網(wǎng)！本站為考生提供重慶自考信息服務，網(wǎng)站信息供學習交流使用，非政府官方網(wǎng)站，官方信息以重慶教育考試院www.cqksy.cn為準。
絕密 ★ 考試結(jié)束前
2023年 4月高等教育自學考試
數(shù)據(jù)結(jié)構(gòu)導論試題
課程代碼 :02142
1. 請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。
2. 答題前 ,考生務必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆 填寫在答題紙規(guī)定的位置上。
選擇題部分
注意事項 :
每小題選出答案后 ,用 2B鉛筆把答題紙上對應題目的答案標號涂黑 。如需改動 ,用橡皮 擦干凈后 ,再選涂其他答案標號 。不能答在試題卷上 。
一、單項選擇題 :本大題共 15小題 ,每小題 2 分 ,共 30分。在每小題列出的備選項中只有一項 是最符合題目要求的 ,請將其選出。
1. 與數(shù)據(jù)元素本身的形式 、內(nèi)容 、相對位置 、個數(shù)無關的是數(shù)據(jù)的
A. 存儲結(jié)構(gòu) B. 邏輯結(jié)構(gòu)
C. 類型 D. 運算實現(xiàn)
2. 在單鏈表中 ,釋放已移出結(jié)點 p 的空間使用語句
A. maloc(p) B. sizeof(p) C. fre(p) D. p=NULL
3. 在表長為 n 的順序表上做插入運算 ,平均要移動的結(jié)點數(shù)為
A. n/4 B. n/3 C. n/2 D. n
4. 線性表實現(xiàn)順序存儲使用
A. 棧 B. 隊列 C. 鏈表 D. 數(shù)組
5. 棧可以實現(xiàn)
A. 函數(shù)的嵌套調(diào)用和操作系統(tǒng)中進程調(diào)度
B. 函數(shù)的嵌套調(diào)用和程序遞歸的處理
C. 程序遞歸的處理和操作系統(tǒng)中進程調(diào)度
D. 操作系統(tǒng)中進程調(diào)度和網(wǎng)絡管理中的打印服務
6. 順序隊列結(jié)構(gòu)類型中 ,data為
A. 一維數(shù)組 B. 二維數(shù)組
C. 單鏈表 D. 循環(huán)鏈表
浙 02142# 數(shù)據(jù)結(jié)構(gòu)導論試題 第 1 頁(共 4 頁)
7. 下列關于樹的描述 ,正確的是
A. 樹形結(jié)構(gòu)不可以表示具有層次結(jié)構(gòu)的數(shù)據(jù)
B. 樹是 n(n≥0) 個結(jié)點的有限集合
C. 任何只含一個結(jié)點的集合不是一棵樹
D. 樹形結(jié)構(gòu)的定義是非遞歸的
8. 葉子的度為
A. - 1 B. 0 C. 1 D. 2
9. 樹的遍歷有三種 ,為
A. 先序 、中序和后序遍歷 B. 先序 、中序和層次遍歷
C. 先序 、后序和層次遍歷 D. 中序 、后序和層次遍歷
10. 二叉樹的中序序列中 ,結(jié)點 P排在結(jié)點 Q之前的條件是 :在二叉樹中
A. P 在 Q 的左邊 B. P 在 Q 的右邊
C. P是 Q 的祖先 D. P是 Q 的子孫
11. 無向圖中一個頂點的度是指圖中
A. 通過該頂點的簡單路徑數(shù) B. 與該頂點連通的頂點數(shù)
C. 通過該頂點的回路數(shù) D. 與該頂點相鄰接的頂點數(shù)
12. 下列序列中 ,符合堆定義的是
A. (100,80,55,60,50,40,58,35,20) B. (100,80,55,60,50,40,35,58,20)
C. (100,80,55,58,50,40,60,35,20) D. (100,70,55,60,50,40,58,35,20)
13. 下列有關解決沖突的幾種方法 ,描述正確的是
A. 線性探測法生成后繼散列地址計算復雜
B. 二次探測法生成的后繼散列地址是連續(xù)的
C. 鏈地址法是挑選部分同義詞建單鏈表來解決沖突
D. 多重散列法不易產(chǎn)生“堆積”
14. 雙向循環(huán)鏈表的對稱性可以表示為
A. p p->prior->next p->next->prior
B. p p->next p->prior
C. p p->next->next p->prior->prior
D. p p->next->next p->next
15. 待排序記錄的數(shù)量很大時 ,排序方法效果較好的是
A. 堆排序和快速排序 B. 堆排序和直接插入排序
C. 直接插入排序和直接選擇排序 D. 直接選擇排序和快速排序
浙 02142# 數(shù)據(jù)結(jié)構(gòu)導論試題 第 2 頁(共 4 頁 )
非選擇題部分
注意事項 :
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上 ,不能答在試題卷上 。
二、填空題 :本大題共 13小題 ,每小題 2 分 ,共 26分。
16. 表示數(shù)據(jù)元素之間的關聯(lián)方式主要有順序存儲方式和 ▲ 存儲方式 。
17. 在單鏈表中 ,如果讓最后一個結(jié)點的指針域指向第一個結(jié)點可以構(gòu)成 ▲ 鏈表 。
18. 棧的插入運算稱為 ▲ 。
19. 隊列的鏈接實現(xiàn)實際上是使用一個帶有 ▲ 的單鏈表來表示隊列 。
20. 以 ▲ 為界的上(下) 半部分是一個固定的值 c或零 ,這樣的矩陣叫做下(上) 三角矩陣 。
21. 循環(huán)隊列結(jié)構(gòu)類型中含有三個域 :data、front和 rear,循環(huán)隊列 SQ為空的條件是 ▲ 。
22. 對于任何完全二叉樹來說 , 可以采用以 ▲ 作為數(shù)組的下標的方法將結(jié)點存入 一 維數(shù) 組中 。
23. 如果一棵二叉樹中度數(shù)為 0 的結(jié)點有 6個 ,那么度數(shù)為 2 的結(jié)點有 ▲ 個 。
24. 如果 G是一個有向圖 ,則把以頂點 v為終點的弧的數(shù)目稱為 v 的 ▲ 。
25. 一個圖的最小生成樹是指該圖的所有生成樹中 ▲ 的生成樹 。
26. 若圖的頂點個數(shù)為 n, 圖的弧的數(shù)目為 e,則拓撲排序算法的時間復雜度為 ▲ 。
27. 靜態(tài)查找表最簡單的實現(xiàn)方法是以 ▲ 作為存儲結(jié)構(gòu) 。
28. 歸并排序要求待排序列是由若干個 ▲ 子序列組成 。
三、應用題 :本大題共 5 小題 ,每小題 6 分 ,共 30分。
29. 題 29圖給出了矩陣 A,請將矩陣 A表示成三元組表 。
(0 2 0 0 0 0)
0 0 0 0 0 0
A= 0 0 0 5 0 9
0 6 0 0 0 0
(0 0 0 0 4 0J
題 29圖
30. 根據(jù)有向圖的鄰接表回答下列問題 :
(1) 如何判斷圖中有多少條弧?
(2) 如何判斷圖中是否存在從頂點 i到頂點 j的弧?
(3) 如何求頂點 i的出度?
31. 設某通 信 系 統(tǒng) 中 一 個 待 傳 輸 的 文 本 有 6 個 不 同 字 符 , 它 們 的 出 現(xiàn) 頻 率 分 別 是 0. 5, 0. 8, 1. 4,2. 2,2. 3,2. 8,試設計哈夫曼編碼 。
浙 02142# 數(shù)據(jù)結(jié)構(gòu)導論試題 第 3 頁(共 4 頁)
32. 如題 32圖所示長度為 13的散列表 ,其散列函數(shù)為 H(key) =key mod 13,在表中已填入鍵
值分別為 16,30,54的元素 。
(1) 現(xiàn)要插入鍵值為 29的元素 ,應用二次探測法 ,計算填入散列表中單元的序號 。 (要求給 出求解過程)
(2) 二次探測法有什么缺點?
0 1 2 3 4 5 6 7 8 9 10 11 12
54
16
30
題 32圖
33. 給定表(19,14,22,01,66,21,83,27,56,13,10) ,試按元素在表中的次序?qū)⑺鼈円来尾迦胍?nbsp;棵初始時為空的二叉排序樹 ,畫出插入完成后的二叉排序樹 。
四、算法設計題 :本大題共 2 小題 ,每小題 7 分 ,共 14分。
34. 寫出計算方陣 A[n][n] 與 B[n][n] 的乘積 C[n][n] 的算法 。
35. 已知循環(huán)隊列的結(jié)構(gòu)類型如下 :
typedef struct cycqueue
{
DataType data maxsize
int front rear
}CycQue
CycQueCQ
設計出隊列的算法 。
重慶自考助學報名預約
我已閱讀并同意《用戶隱私條款》
加入重慶自考公眾號
重慶自考網(wǎng)微信公眾號
(掃一掃加入)
加入重慶自考交流群
掃一掃加入微信交流群
與考生自由互動、并且能直接與資深老師進行交流、解答。
