北京聯(lián)合大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2023-2024學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁北京聯(lián)合大學(xué)

《數(shù)據(jù)結(jié)構(gòu)》2023-2024學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)文件系統(tǒng)的目錄結(jié)構(gòu)？A.二叉樹B.多叉樹C.鏈表D.棧2、對于一個具有n個節(jié)點(diǎn)的二叉樹，若每個節(jié)點(diǎn)都有左子樹和右子樹，則其葉子節(jié)點(diǎn)的個數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn3、對于一個具有n個元素的順序存儲的循環(huán)隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+14、在數(shù)據(jù)結(jié)構(gòu)中，對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素，其平均時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、對于一個具有n個節(jié)點(diǎn)的完全二叉樹，若按照層次遍歷的順序?qū)⒐?jié)點(diǎn)編號為1到n，已知編號為i的節(jié)點(diǎn)有左孩子，則其左孩子的編號為？A.2iB.2i+1C.i*2D.i/26、對于一個循環(huán)隊列，若隊列的最大容量為m，當(dāng)前front指針為5，rear指針為2，則隊列中的元素個數(shù)為（）A.7B.3C.m-3D.m-77、對于一個具有n個元素的有序數(shù)組，若采用折半插入排序算法進(jìn)行排序，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)8、對于一個用數(shù)組實現(xiàn)的小根堆，進(jìn)行刪除堆頂元素操作后，需要重新調(diào)整堆以保持堆的性質(zhì)。以下關(guān)于刪除操作的時間復(fù)雜度的描述，哪一個是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、在一個有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.410、在一個帶頭結(jié)點(diǎn)的循環(huán)鏈表中，若要判斷鏈表是否為空，應(yīng)檢查？（）A.頭結(jié)點(diǎn)的指針是否為空B.頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)C.尾結(jié)點(diǎn)的指針是否為空D.尾結(jié)點(diǎn)的下一個結(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)11、對于一個采用鏈表存儲的棧，若要獲取棧的大?。ㄔ財?shù)量），以下關(guān)于操作的時間復(fù)雜度的描述，哪一個是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、在一棵二叉搜索樹中，刪除一個有兩個子節(jié)點(diǎn)的節(jié)點(diǎn)時，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點(diǎn)B.用右子樹的最小值替代該節(jié)點(diǎn)C.隨機(jī)選擇左子樹或右子樹的節(jié)點(diǎn)替代D.不進(jìn)行替代，直接刪除13、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB14、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點(diǎn)（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.515、以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序16、對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素。以下關(guān)于二分查找的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、已知一個帶權(quán)有向圖G=(V,E)，頂點(diǎn)集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點(diǎn)1到頂點(diǎn)5的最短路徑，經(jīng)過的中間頂點(diǎn)依次為？（）A.2,4B.3,4C.2,3D.3,518、對于一個具有n個頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)19、對于一個具有n個元素的無序鏈表，若要對其進(jìn)行排序，以下哪種排序算法較為合適？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序20、在一個用數(shù)組實現(xiàn)的循環(huán)隊列中，若front=rear，則隊列的狀態(tài)可能為（）A.隊空B.隊滿C.既不空也不滿D.以上都有可能二、簡答題（本大題共4個小題，共40分)1、（本題10分）對于一個用鄰接表存儲的圖，說明如何判斷圖是否為哈密頓圖，給出一種有效的算法并分析其時間復(fù)雜度。2、（本題10分）比較插入排序和希爾排序在初始有序程度不同的情況下的性能差異。3、（本題10分）對于一個用哈希表存儲的自定義類對象，解釋如何設(shè)計合適的哈希函數(shù)和處理沖突，給出具體的示例和代碼。4、（本題10分）解釋如何在一個循環(huán)鏈表中找到環(huán)的起點(diǎn)，給出算法步驟和實現(xiàn)代碼，并分析其時間復(fù)雜度。三、設(shè)計題（本大題共2個小題