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

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

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