- 歡迎訪問浙江自考網(wǎng)！本站為考生提供浙江自考信息服務(wù)，網(wǎng)站信息供學(xué)習(xí)交流使用，非政府官方網(wǎng)站，官方信息以浙江教育考試院www.zjzs.net為準(zhǔn)。
網(wǎng)站服務(wù)
2024年4月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題
課程代碼：02142
1.請(qǐng)考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。
2.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆 填寫在答題紙規(guī)定的位置上。
選擇題部分
注意事項(xiàng)：
每小題選出答案后，用2B 鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng)，用橡皮 擦干凈后，再選涂其他答案標(biāo)號(hào)。不能答在試題卷上。
一 、單項(xiàng)選擇題：本大題共15小題，每小題2分，共30分。在每小題列出的備選項(xiàng)中只
有一項(xiàng)是最符合題目要求的，請(qǐng)將其選出。
1. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是
A. 數(shù)據(jù)項(xiàng) B. 數(shù)據(jù)元素
C. 數(shù)據(jù)類型 D. 數(shù)據(jù)變量
2. 在下列數(shù)據(jù)的邏輯結(jié)構(gòu)中，結(jié)構(gòu)最復(fù)雜的是
A. 圖結(jié)構(gòu) B. 集合
C. 線性結(jié)構(gòu) D. 樹形結(jié)構(gòu)
3. 對(duì)長(zhǎng)度為n 的順序表實(shí)現(xiàn)給定操作的算法中，平均時(shí)間復(fù)雜度為 O(1) 的是
A. 查找包含指定值元素的算法
B. 獲取第i(1≤i≤n) 個(gè)元素的算法
C. 在第i(1≤i≤n+1) 個(gè)元素之前插入一個(gè)新元素x 的算法
D. 刪除第i(1≤i≤n) 個(gè)元素的算法
4. 在單鏈表中，指針域?yàn)閚ext,在 p 指向的結(jié)點(diǎn)之后插入結(jié)點(diǎn)q 的代碼是
A.q->next=p->next;p->next=q; B.p->next=q;q->next=p->next;
C.q->next=p;p->next=q; D.p->next=q;q->next=p;
5. 下列有關(guān)隊(duì)列的敘述，正確的是
A. 隊(duì)列屬于非線性表 B. 隊(duì)列在隊(duì)尾刪除數(shù)據(jù)
C. 隊(duì)列在隊(duì)首插入數(shù)據(jù) D. 隊(duì)列按“先進(jìn)先出”原則組織數(shù)據(jù)
浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第1頁(yè)(共4頁(yè))
6. 按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是
A. 隊(duì)列 B. 棧
C. 雙向鏈表 D. 二叉樹
7. 設(shè)初始棧為空，s 表示入棧操作，x 表示出棧操作，則合法的操作序列是
A.sssxxxsx B.Ssxsxxxs
C.ssxxxssx D.sxxssxxs
8. 二叉樹中第5層(根的層號(hào)為1)上的結(jié)點(diǎn)個(gè)數(shù)最多為
A.8 個(gè) B.15 個(gè)
C.16 個(gè) D.32 個(gè)
9. 二叉樹若采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，則對(duì)于n 個(gè)結(jié)點(diǎn)的二叉樹一定有
A.2n-1 個(gè)指針域，其中n 個(gè)指針域?yàn)镹ULL
B.2n-1 個(gè)指針域，其中n+1 個(gè)指針域?yàn)镹ULL
C.2n 個(gè)指針域，其中n 個(gè)指針域?yàn)镹ULL
D.2n 個(gè)指針域，其中n+1個(gè)指針域?yàn)镹ULL
10.n 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有
A.n-1 條弧 B.n 條弧
C.n(n-1)/2 條弧 D.n(n-1) 條弧
11.n 個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣中的非零元素至少有
A.n-1 個(gè) B.n 個(gè)
C.2(n-1) 個(gè) D.n(n-1)/2 個(gè)
12. 若構(gòu)造一棵具有n 個(gè)結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不會(huì)超過
A.n/2 B.(n+1)/2
C.n-1 D.n
13. 對(duì)含有64個(gè)數(shù)據(jù)元素的有序表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為
A.6 次 B.7 次
C.63 次 D.64 次
14. 歸并排序算法的時(shí)間復(fù)雜度是
A.O(log?n) B.O(n)
C.O(nlog?n) D.O(n2)
15. 采用冒泡排序方法對(duì)7個(gè)記錄進(jìn)行排序，需要進(jìn)行的鍵值比較次數(shù)是
A.7 次 B.14 次
C.21 次 D.49 次
浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第2頁(yè)(共4頁(yè))
非選擇題部分
注意事項(xiàng)：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。
二 、填空題：本大題共13小題，每小題2分，共26分。
16. 一個(gè)算法通常可從正確性、易讀性、健壯性和 等四個(gè)方面評(píng)價(jià)和分析。
17. 在長(zhǎng)度為n 的順序表中刪除一個(gè)元素需移動(dòng)元素的平均次數(shù)為 次。
18,設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為head, 則空循環(huán)鏈表的判定條件是
19. 設(shè)某循環(huán)隊(duì)列CQ 的容量maxsize 為50,隊(duì)列首指針CQ.front=5 (指向隊(duì)首元素的前一
位置),隊(duì)列尾指針 CQ.rear=29 (指向隊(duì)尾元素),則該循環(huán)隊(duì)列中共有 個(gè)元素。
20. 設(shè)有二維數(shù)組int a[10][20], 每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，數(shù)組元素 a[0][0]的存儲(chǔ)位 置為2000,則數(shù)組元素 a[5][10]的存儲(chǔ)位置為
21. 某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，3個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中共有 _個(gè)結(jié)點(diǎn)。
22. 已知某完全二叉樹的第6層(設(shè)根為第1層)有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)
個(gè)數(shù)最多是
23. 在有n 個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 。
24. 已知有向圖 G=(V,A), 其中 V={a,b,c,d,e,f,g},A={
25. 在有序表(7,12,15,18,27,32,41,92)中用二分查找法查找和鍵值32相等的數(shù)據(jù)元素，
在查找過程中依次和鍵值32比較的鍵值為
26. 已知某長(zhǎng)度為11的散列表，其散列函數(shù)為H(key)=key mod 11,在表中已填入鍵值分別 為15、27、39的元素，其余地址為空，若采用線性探測(cè)法處理沖突，則鍵值為60 的 元素保存的地址是 _。
27.對(duì)初始關(guān)鍵字序列{45,39,72,98,24}的記錄，按關(guān)鍵字升序的方式進(jìn)行直接選擇排序， 第一次選擇后的結(jié)果是
28. 對(duì)初始關(guān)鍵字序列{45,39,72,98,24}的記錄，按關(guān)鍵字升序的方式進(jìn)行快速排序，以 第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)得到的一次劃分結(jié)果為 _。
三、應(yīng)用題：本大題共5小題，每小題6分，共30分。
29. 有5個(gè)元素，其入棧次序?yàn)椋篈、B、C、D、E, 寫出以元素 C、D 最先出棧(即C 第
一個(gè)且D 第二個(gè)出棧)的各種可能的出棧次序。
30. 假設(shè)某通信系統(tǒng)中電文使用的字符集為{A,B,C,D,E,F,G,H}, 各字符在電文中出現(xiàn)的 頻率分別為：0.07,0.19,0.02,0.06,0.32,0.03,0.21和0.10。試畫出哈夫曼樹(要 求樹中任一結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的權(quán)值不小于其右孩子結(jié)點(diǎn)的權(quán)值),并按左分支為0和
右分支為1的規(guī)則分別寫出與每個(gè)字符對(duì)應(yīng)的哈夫曼編碼。
浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第3頁(yè)(共4頁(yè))
31. 某有向圖G 如題31 圖所示，試畫出圖 G 的鄰接表存儲(chǔ)結(jié)構(gòu)。
題31圖
32. 已知一棵二叉排序樹(結(jié)點(diǎn)值大小按字母順序)的先序遍歷序列為 FBADCEGH, 試畫
出此二叉排序樹，并且寫出此二叉排序樹的后序遍歷序列。
33. 對(duì)關(guān)鍵字序列{72,87,61,23,94,16,5,58}進(jìn)行堆排序，使之按關(guān)鍵字遞減次序排列。
寫出排序過程中得到的初始堆和前兩趟排序后的序列狀態(tài)。
四 、算法設(shè)計(jì)題：本大題共2小題，每小題7分，共14分。
34. 已知單鏈表的類型定義如下：
typedef int DataType;
typedef struct node {
DataType data;
struct node*next;
}LinkNode,*LinkList;
編寫一個(gè)函數(shù) DataType minValue(LinkList L), 求非空的帶頭結(jié)點(diǎn)單鏈表L 中各結(jié)點(diǎn)
data 域的最小值。
35. 已知二叉樹的存儲(chǔ)結(jié)構(gòu)類型定義如下：
Typedef struct btnode
DataType data:
Struct btnode *lchild,*rchild;
}*BinTree;
編寫遞歸算法 int CountD2Node(BinTree bt),求二叉樹 bt 中所有度為2的結(jié)點(diǎn)的個(gè)
數(shù)。
浙江自考助學(xué)報(bào)名預(yù)約
上一篇：2024年4月浙江自考02141計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)試題
下一篇：2024年4月浙江自考02323操作系統(tǒng)概論試題
浙江自考網(wǎng)
掃一掃加入微信交流群
與考生自由互動(dòng)、并且能直接與資深老師進(jìn)行交流、解答。
掃碼小程序選擇報(bào)考專業(yè)
進(jìn)入在線做題學(xué)習(xí)
查看了解自考專業(yè)
查詢政策公告
進(jìn)入歷年真題學(xué)習(xí)
本站部分文字及圖片均來(lái)自于網(wǎng)絡(luò)，如侵犯到您的權(quán)益，請(qǐng)及時(shí)發(fā)送郵件到[email protected]，我們會(huì)盡快處理投訴中心
? 法律顧問：文律師
