2024年4月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

　　課程代碼：02142

　　1.請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。

　　2.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號用黑色字跡的簽字筆或鋼筆 填寫在答題紙規(guī)定的位置上。

　　選擇題部分

　　注意事項：

　　每小題選出答案后，用2B 鉛筆把答題紙上對應(yīng)題目的答案標(biāo)號涂黑。如需改動，用橡皮 擦干凈后，再選涂其他答案標(biāo)號。不能答在試題卷上。

　　一 、單項選擇題：本大題共15小題，每小題2分，共30分。在每小題列出的備選項中只

　　有一項是最符合題目要求的，請將其選出。

　　1. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是

　　A. 數(shù)據(jù)項 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. 對長度為n 的順序表實現(xiàn)給定操作的算法中，平均時間復(fù)雜度為 O(1) 的是

　　A. 查找包含指定值元素的算法

　　B. 獲取第i(1≤i≤n) 個元素的算法

　　C. 在第i(1≤i≤n+1) 個元素之前插入一個新元素x 的算法

　　D. 刪除第i(1≤i≤n) 個元素的算法

　　4. 在單鏈表中，指針域為next,在 p 指向的結(jié)點之后插入結(jié)點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)隊列的敘述，正確的是

　　A. 隊列屬于非線性表 B. 隊列在隊尾刪除數(shù)據(jù)

　　C. 隊列在隊首插入數(shù)據(jù) D. 隊列按“先進(jìn)先出”原則組織數(shù)據(jù)

　　浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第1頁(共4頁)

　　6. 按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是

　　A. 隊列 B. 棧

　　C. 雙向鏈表 D. 二叉樹

　　7. 設(shè)初始棧為空，s 表示入棧操作，x 表示出棧操作，則合法的操作序列是

　　A.sssxxxsx B.Ssxsxxxs

　　C.ssxxxssx D.sxxssxxs

　　8. 二叉樹中第5層(根的層號為1)上的結(jié)點個數(shù)最多為

　　A.8 個 B.15 個

　　C.16 個 D.32 個

　　9. 二叉樹若采用二叉鏈表存儲結(jié)構(gòu)，則對于n 個結(jié)點的二叉樹一定有

　　A.2n-1 個指針域，其中n 個指針域為NULL

　　B.2n-1 個指針域，其中n+1 個指針域為NULL

　　C.2n 個指針域，其中n 個指針域為NULL

　　D.2n 個指針域，其中n+1個指針域為NULL

　　10.n 個頂點的強連通圖中至少含有

　　A.n-1 條弧 B.n 條弧

　　C.n(n-1)/2 條弧 D.n(n-1) 條弧

　　11.n 個頂點的連通圖用鄰接矩陣表示時，該矩陣中的非零元素至少有

　　A.n-1 個 B.n 個

　　C.2(n-1) 個 D.n(n-1)/2 個

　　12. 若構(gòu)造一棵具有n 個結(jié)點的二叉排序樹，最壞的情況下其深度不會超過

　　A.n/2 B.(n+1)/2

　　C.n-1 D.n

　　13. 對含有64個數(shù)據(jù)元素的有序表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為

　　A.6 次 B.7 次

　　C.63 次 D.64 次

　　14. 歸并排序算法的時間復(fù)雜度是

　　A.O(log?n) B.O(n)

　　C.O(nlog?n) D.O(n2)

　　15. 采用冒泡排序方法對7個記錄進(jìn)行排序，需要進(jìn)行的鍵值比較次數(shù)是

　　A.7 次 B.14 次

　　C.21 次 D.49 次

　　浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第2頁(共4頁)

　　非選擇題部分

　　注意事項：

　　用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。

　　二 、填空題：本大題共13小題，每小題2分，共26分。

　　16. 一個算法通常可從正確性、易讀性、健壯性和 等四個方面評價和分析。

　　17. 在長度為n 的順序表中刪除一個元素需移動元素的平均次數(shù)為 次。

　　18,設(shè)帶頭結(jié)點的單向循環(huán)鏈表的頭指針為head, 則空循環(huán)鏈表的判定條件是

　　19. 設(shè)某循環(huán)隊列CQ 的容量maxsize 為50,隊列首指針CQ.front=5 (指向隊首元素的前一

　　位置),隊列尾指針 CQ.rear=29 (指向隊尾元素),則該循環(huán)隊列中共有 個元素。

　　20. 設(shè)有二維數(shù)組int a[10][20], 每個數(shù)組元素占4個存儲單元，數(shù)組元素 a[0][0]的存儲位 置為2000,則數(shù)組元素 a[5][10]的存儲位置為

　　21. 某二叉樹有5個度為2的結(jié)點，3個度為1的結(jié)點，則該二叉樹中共有 _個結(jié)點。

　　22. 已知某完全二叉樹的第6層(設(shè)根為第1層)有8個葉結(jié)點，則該完全二叉樹的結(jié)點

　　個數(shù)最多是

　　23. 在有n 個頂點的有向圖中，每個頂點的度最大可達(dá) 。

　　24. 已知有向圖 G=(V,A), 其中 V={a,b,c,d,e,f,g},A={,,,,

　　,,,}, 則該有向圖可以排出 種不同的拓?fù)湫蛄小?/e,f>

　　25. 在有序表(7,12,15,18,27,32,41,92)中用二分查找法查找和鍵值32相等的數(shù)據(jù)元素，

　　在查找過程中依次和鍵值32比較的鍵值為

　　26. 已知某長度為11的散列表，其散列函數(shù)為H(key)=key mod 11,在表中已填入鍵值分別 為15、27、39的元素，其余地址為空，若采用線性探測法處理沖突，則鍵值為60 的 元素保存的地址是 _。

　　27.對初始關(guān)鍵字序列{45,39,72,98,24}的記錄，按關(guān)鍵字升序的方式進(jìn)行直接選擇排序， 第一次選擇后的結(jié)果是

　　28. 對初始關(guān)鍵字序列{45,39,72,98,24}的記錄，按關(guān)鍵字升序的方式進(jìn)行快速排序，以 第一個記錄關(guān)鍵字45為基準(zhǔn)得到的一次劃分結(jié)果為 _。

　　三、應(yīng)用題：本大題共5小題，每小題6分，共30分。

　　29. 有5個元素，其入棧次序為：A、B、C、D、E, 寫出以元素 C、D 最先出棧(即C 第

　　一個且D 第二個出棧)的各種可能的出棧次序。

　　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é)點的左孩子結(jié)點的權(quán)值不小于其右孩子結(jié)點的權(quán)值),并按左分支為0和

　　右分支為1的規(guī)則分別寫出與每個字符對應(yīng)的哈夫曼編碼。

　　浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第3頁(共4頁)

　　31. 某有向圖G 如題31 圖所示，試畫出圖 G 的鄰接表存儲結(jié)構(gòu)。

　　題31圖

　　32. 已知一棵二叉排序樹(結(jié)點值大小按字母順序)的先序遍歷序列為 FBADCEGH, 試畫

　　出此二叉排序樹，并且寫出此二叉排序樹的后序遍歷序列。

　　33. 對關(guān)鍵字序列{72,87,61,23,94,16,5,58}進(jìn)行堆排序，使之按關(guān)鍵字遞減次序排列。

　　寫出排序過程中得到的初始堆和前兩趟排序后的序列狀態(tài)。

　　四 、算法設(shè)計題：本大題共2小題，每小題7分，共14分。

　　34. 已知單鏈表的類型定義如下：

　　typedef int DataType;

　　typedef struct node {

　　DataType data;

　　struct node*next;

　　}LinkNode,*LinkList;

　　編寫一個函數(shù) DataType minValue(LinkList L), 求非空的帶頭結(jié)點單鏈表L 中各結(jié)點

　　data 域的最小值。

　　35. 已知二叉樹的存儲結(jié)構(gòu)類型定義如下：

　　Typedef struct btnode

　　DataType data:

　　Struct btnode *lchild,*rchild;

　　}*BinTree;

　　編寫遞歸算法 int CountD2Node(BinTree bt),求二叉樹 bt 中所有度為2的結(jié)點的個

　　數(shù)。

浙江自考助學(xué)報名預(yù)約

請選擇您的報考層次 大專 本科 專本套讀

提交報名信息 重置信息

我已閱讀并同意《用戶隱私條款》

個人信息授權(quán)與保護(hù)聲明

關(guān)閉

鑒于網(wǎng)絡(luò)的特性，本網(wǎng)站將無可避免地與您產(chǎn)生直接或間接的互動關(guān)系，故特此說明本網(wǎng)站對用戶個人信息所采取的收集、使用和保護(hù)政策，請您務(wù)必仔細(xì)閱讀：

信息收集范圍

我們根據(jù)合法、正當(dāng)、必要的原則，僅收集為您提供服務(wù)所必要的信息。包括：

1、您在使用我們服務(wù)時主動提供的信息

(2)您通過電話咨詢方式提供的姓名、電話、住址、微信/QQ、備注等信息。

(3)您在使用網(wǎng)上咨詢服務(wù)所提供的姓名、電話、住址、微信/QQ、備注等信息。

(4)您參與我們線上活動時填寫的調(diào)查問卷中可能包含您的姓名、電話、地址等信息。

我們的部分服務(wù)可能需要您提供特定的個人敏感信息來實現(xiàn)特定功能。

若您選擇不提供該類信息，則可能無法正常使用服務(wù)中的特定功能，但不影響您使用服務(wù)中的其他功能。

若您主動提供您的個人敏感信息，即表示您同意我們按本政策所述目的和方式來處理您的個人敏感信息。

本次報名數(shù)據(jù)服務(wù)由本網(wǎng)站提供，本網(wǎng)站不承擔(dān)由于內(nèi)容的不一致性所引起的一切爭議和法律責(zé)任，報名結(jié)果以最終輔導(dǎo)報名系統(tǒng)為準(zhǔn)。

信息使用用途

我們嚴(yán)格遵守法律法規(guī)的規(guī)定及與用戶的約定，將收集的信息用于以下用途。若我們超出以下用途使用您的信息，我們將再次向您進(jìn)行說明，并征得您的同意。

1、通過微信、電話形式建立溝通，向您提供學(xué)歷咨詢服務(wù)。

2、滿足您的個性化需求。例如，學(xué)歷途徑規(guī)劃、學(xué)歷評估等。

3、項目開發(fā)和服務(wù)優(yōu)化。例如，通過您的咨詢問題及服務(wù)過程中您的建議等，優(yōu)化我們的服務(wù)。

4、向您推薦您可能感興趣的學(xué)校、資訊等。

5、學(xué)校推薦。例如，我們會根據(jù)您的具體要求以您所具備的條件向您推薦合適的院校。

為了讓您有更好的體驗、改善我們的服務(wù)或經(jīng)您同意的其他用途，在符合相關(guān)法律法規(guī)的前提下，我們可能將通過某些服務(wù)所收集的信息用于我們的其他服務(wù)。例如，將您在使用我們某項服務(wù)時的信息，用于另一項服務(wù)中向您展示個性化的內(nèi)容或廣告、用于用戶研究分析與統(tǒng)計等服務(wù)。

信息保護(hù)

我們僅在本《隱私政策》所述目的所必需的期間和法律法規(guī)要求的時限內(nèi)保留您的個人信息。

本網(wǎng)站將對您所提供的資料進(jìn)行嚴(yán)格的管理及保護(hù)，本網(wǎng)站將使用相應(yīng)的技術(shù)，防止您的個人資料丟失、被盜用或遭篡改。

當(dāng)政府機關(guān)依照法定程序要求本網(wǎng)站披露個人資料時，本網(wǎng)站將根據(jù)執(zhí)法單位之要求或為公共安全之目的提供個人資料。在此情況下之任何披露，本網(wǎng)站均得免責(zé)。

由于您將用戶密碼告知他人或與他人共享注冊帳戶，由此導(dǎo)致的任何個人資料泄露。任何由于計算機問題、黑客政擊、計算機病毒侵入或發(fā)作、因政府管制而造成的暫時性關(guān)閉等影響網(wǎng)絡(luò)正常經(jīng)營之不可抗力而造成的個人資料泄露、丟失、被盜用或被篡改情況時本網(wǎng)站亦毋需承擔(dān)任何責(zé)任。

未成年人保護(hù)

本網(wǎng)站將建立和維持一合理的程序，以保護(hù)未成年人個人資料的保密性及安全性。本網(wǎng)站鄭重聲明：任何16歲以下的未成年人參加網(wǎng)上活動應(yīng)事先得到家長或其法定監(jiān)護(hù)人的可經(jīng)查證的同意。若您是未成年人的監(jiān)護(hù)人，當(dāng)您對您所監(jiān)護(hù)的未成年人的個人信息有相關(guān)疑問時，請通過與我們聯(lián)系。

適用范圍

我們的所有服務(wù)均適用本政策。但某些服務(wù)有其特定的隱私指引/聲明，該特定隱私指引/聲明更具體地說明我們在該服務(wù)中如何處理您的信息。如本政策與特定服務(wù)的隱私指引/聲明有不一致之處，請以該特定隱私指引/聲明為準(zhǔn)。

您必須完全同意以上協(xié)議才能使用本網(wǎng)站的在線報名服務(wù)。