2024年4月安徽自學考試數據結構導論試題 課程代碼：02142

絕密★考試結束前2024年4月高等教育自學考試數據結構導論試題課程代碼：021421.請考生按規定用筆將所有試題的答案涂、寫在答題紙上。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.SsxsxxxsC.ssxxxssx D.sxxssxxs8. 二叉樹中第5層(根的層號為1)上的結點個數最多為A.8個B.15個C.16個 D.32個9. 二叉樹若采用二叉鏈表存儲結構，則對于n 個結點的二叉樹一定有A.2n-1 個指針域，其中n 個指針域為NULLB.2n-1個指針域，其中n+1 個指針域為NULLC.2n個指針域，其中n個指針域為NULLD.2n 個指針域，其中n+1個指針域為NULL10.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)/2C.n-1D.n13.對含有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.設有二維數組inta[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)=keymod11,在表中已填入鍵值分別為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. 已知單鏈表的類型定義如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;編寫一個函數 DataTypeminValue(LinkListL), 求非空的帶頭結點單鏈表L中各結點data域的最小值。35. 已知二叉樹的存儲結構類型定義如下：TypedefstructbtnodeDataTypedata:Structbtnode*lchild,*rchild;}*BinTree;編寫遞歸算法intCountD2Node(BinTreebt),求二叉樹 bt中所有度為2的結點的個數。02142#數據結構導論試題第4頁(共4頁)