2024年4月安徽自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題 課程代碼：02142

絕密★考試結(jié)束前2024年4月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：021421.請(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.SsxsxxxsC.ssxxxssx D.sxxssxxs8. 二叉樹中第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)镹ULLB.2n-1個(gè)指針域，其中n+1 個(gè)指針域?yàn)镹ULLC.2n個(gè)指針域，其中n個(gè)指針域?yàn)镹ULLD.2n 個(gè)指針域，其中n+1個(gè)指針域?yàn)镹ULL10.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ì)超過(guò)A.n/2 B.(n+1)/2C.n-1D.n13.對(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ù)組inta[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={,,,,,,,},則該有向圖可以排出種不同的拓?fù)湫蛄小?5.在有序表(7,12,15,18,27,32,41,92)中用二分查找法查找和鍵值32相等的數(shù)據(jù)元素，在查找過(guò)程中依次和鍵值32比較的鍵值為26.已知某長(zhǎng)度為11的散列表，其散列函數(shù)為H(key)=keymod11,在表中已填入鍵值分別為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)鍵字遞減次序排列。寫出排序過(guò)程中得到的初始堆和前兩趟排序后的序列狀態(tài)。四、算法設(shè)計(jì)題：本大題共2小題，每小題7分，共14分。34. 已知單鏈表的類型定義如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;編寫一個(gè)函數(shù) DataTypeminValue(LinkListL), 求非空的帶頭結(jié)點(diǎn)單鏈表L中各結(jié)點(diǎn)data域的最小值。35. 已知二叉樹的存儲(chǔ)結(jié)構(gòu)類型定義如下：TypedefstructbtnodeDataTypedata:Structbtnode*lchild,*rchild;}*BinTree;編寫遞歸算法intCountD2Node(BinTreebt),求二叉樹 bt中所有度為2的結(jié)點(diǎn)的個(gè)數(shù)。02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第4頁(yè)(共4頁(yè))