2024年4月高等教育自學考試數據結構導論試題

　　課程代碼：02142

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

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

　　選擇題部分

　　注意事項：

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

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

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

　　1. 在數據結構中，數據的基本單位是

　　A. 數據項 B. 數據元素

　　C. 數據類型 D. 數據變量

　　2. 在下列數據的邏輯結構中，結構最復雜的是

　　A. 圖結構 B. 集合

　　C. 線性結構 D. 樹形結構

　　3. 對長度為n 的順序表實現給定操作的算法中，平均時間復雜度為 O(1) 的是

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

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

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

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

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

　　A. 隊列屬于非線性表 B. 隊列在隊尾刪除數據

　　C. 隊列在隊首插入數據 D. 隊列按“先進先出”原則組織數據

　　浙02142#數據結構導論試題第1頁(共4頁)

　　6. 按照“后進先出”原則組織數據的數據結構是

　　A. 隊列 B. 棧

　　C. 雙向鏈表 D. 二叉樹

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

　　A.sssxxxsx B.Ssxsxxxs

　　C.ssxxxssx D.sxxssxxs

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

　　A.8 個 B.15 個

　　C.16 個 D.32 個

　　9. 二叉樹若采用二叉鏈表存儲結構，則對于n 個結點的二叉樹一定有

　　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. 若構造一棵具有n 個結點的二叉排序樹，最壞的情況下其深度不會超過

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

　　C.n-1 D.n

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

　　A.6 次 B.7 次

　　C.63 次 D.64 次

　　14. 歸并排序算法的時間復雜度是

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

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

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

　　A.7 次 B.14 次

　　C.21 次 D.49 次

　　浙02142#數據結構導論試題第2頁(共4頁)

　　非選擇題部分

　　注意事項：

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

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

　　16. 一個算法通?？蓮恼_性、易讀性、健壯性和 等四個方面評價和分析。

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

　　18,設帶頭結點的單向循環鏈表的頭指針為head, 則空循環鏈表的判定條件是

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

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

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

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

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

　　個數最多是

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

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

　　,,,}, 則該有向圖可以排出 種不同的拓撲序列。

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

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

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

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

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

　　三、應用題：本大題共5小題，每小題6分，共30分。

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

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

　　30. 假設某通信系統中電文使用的字符集為{A,B,C,D,E,F,G,H}, 各字符在電文中出現的 頻率分別為：0.07,0.19,0.02,0.06,0.32,0.03,0.21和0.10。試畫出哈夫曼樹(要 求樹中任一結點的左孩子結點的權值不小于其右孩子結點的權值),并按左分支為0和

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

　　浙02142#數據結構導論試題第3頁(共4頁)

　　31. 某有向圖G 如題31 圖所示，試畫出圖 G 的鄰接表存儲結構。

　　題31圖

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

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

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

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

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

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

　　typedef int DataType;

　　typedef struct node {

　　DataType data;

　　struct node*next;

　　}LinkNode,*LinkList;

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

　　data 域的最小值。

　　35. 已知二叉樹的存儲結構類型定義如下：

　　Typedef struct btnode

　　DataType data:

　　Struct btnode *lchild,*rchild;

　　}*BinTree;

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

　　數。

浙江自考助學報名預約

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

提交報名信息 重置信息

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

個人信息授權與保護聲明

關閉

鑒于網絡的特性，本網站將無可避免地與您產生直接或間接的互動關系，故特此說明本網站對用戶個人信息所采取的收集、使用和保護政策，請您務必仔細閱讀：

信息收集范圍

我們根據合法、正當、必要的原則，僅收集為您提供服務所必要的信息。包括：

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

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

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

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

我們的部分服務可能需要您提供特定的個人敏感信息來實現特定功能。

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

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

本次報名數據服務由本網站提供，本網站不承擔由于內容的不一致性所引起的一切爭議和法律責任，報名結果以最終輔導報名系統為準。

信息使用用途

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

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

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

3、項目開發和服務優化。例如，通過您的咨詢問題及服務過程中您的建議等，優化我們的服務。

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

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

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

信息保護

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

本網站將對您所提供的資料進行嚴格的管理及保護，本網站將使用相應的技術，防止您的個人資料丟失、被盜用或遭篡改。

當政府機關依照法定程序要求本網站披露個人資料時，本網站將根據執法單位之要求或為公共安全之目的提供個人資料。在此情況下之任何披露，本網站均得免責。

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

未成年人保護

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

適用范圍

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

您必須完全同意以上協議才能使用本網站的在線報名服務。