安徽科技學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程實訓(xùn)》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁安徽科技學(xué)院

《數(shù)據(jù)結(jié)構(gòu)課程實訓(xùn)》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一棵二叉搜索樹中，刪除一個只有左子樹的節(jié)點，其右子樹的節(jié)點需要（）A.替換被刪除節(jié)點B.保持不動C.全部刪除D.移動到左子樹2、在一個有n個頂點和e條邊的無向圖中，采用鄰接矩陣存儲，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)3、對于一個具有n個元素的快速排序，在最好情況下，其時間復(fù)雜度為？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)4、已知一個帶權(quán)有向圖G=(V,E)，頂點集合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）算法求從頂點1到頂點5的最短路徑，經(jīng)過的中間頂點依次為？（）A.2,4B.3,4C.2,3D.3,55、在一個具有n個元素的最小堆中，插入一個新元素并調(diào)整為最小堆，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、若一棵二叉樹的先序遍歷序列和后序遍歷序列分別為ABC和CBA，則其中序遍歷序列為：A.BCAB.CABC.ABCD.無法確定7、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)8、在一個具有n個節(jié)點的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用9、在圖的最短路徑算法中，Dijkstra算法適用于帶權(quán)有向圖，以下關(guān)于Dijkstra算法的描述，錯誤的是（）A.以起始節(jié)點為中心向外層層擴(kuò)展B.每次選擇距離起始節(jié)點最近的未訪問節(jié)點C.可以處理負(fù)權(quán)邊D.時間復(fù)雜度為O(n^2)10、在數(shù)據(jù)結(jié)構(gòu)中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復(fù)訪問11、設(shè)有一個具有n個節(jié)點的二叉平衡樹，若要插入一個新節(jié)點并保持平衡，以下關(guān)于插入操作的平均時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、隊列是一種先進(jìn)先出的線性表，若用一個數(shù)組實現(xiàn)循環(huán)隊列，隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素，隊列最大容量為MAX_SIZE，那么判斷隊滿的條件是什么？（）A.(rear+1)%MAX_SIZE==frontB.rear==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-113、以下關(guān)于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)14、在一個字符串中，要查找某個子串首次出現(xiàn)的位置，通?？梢允褂媚姆N算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找15、在一個具有n個元素的雙向鏈表中，要在指定節(jié)點之后插入一個新節(jié)點，需要修改幾個指針？A.2B.3C.4D.516、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)文件系統(tǒng)的目錄結(jié)構(gòu)？A.二叉樹B.多叉樹C.鏈表D.棧17、在一個長度為n的有序數(shù)組中進(jìn)行二分查找，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)18、已知一個有序表為{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值為35的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.419、在一棵AVL樹中，進(jìn)行插入操作后，可能導(dǎo)致樹失去平衡，此時需要進(jìn)行的旋轉(zhuǎn)操作最多為（）A.1次B.2次C.logn次D.n次20、一棵完全二叉樹的第5層（根為第1層）有16個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最少為（）。A.47B.55C.63D.64二、簡答題（本大題共4個小題，共40分)1、（本題10分）在二叉樹中，解釋如何判斷一棵二叉樹是否為平衡二叉樹，給出相應(yīng)的算法步驟和實現(xiàn)代碼。2、（本題10分）詳細(xì)闡述哈希表的基本原理，包括哈希函數(shù)的設(shè)計和沖突解決方法（開放定址法、鏈地址法等）。3、（本題10分）詳細(xì)說明選擇排序算法中選擇最小元素的過程和時間復(fù)雜度。4、（本題10分）詳細(xì)說明在并查集的優(yōu)化中，如何使用路徑分裂或按秩合并進(jìn)一