鄭州航空工業(yè)管理學(xué)院《數(shù)據(jù)結(jié)構(gòu)中俄》2023-2024學(xué)年期末試卷

站名：站名：年級(jí)專(zhuān)業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專(zhuān)業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記?！堋狻€(xiàn)…………第1頁(yè)，共1頁(yè)鄭州航空工業(yè)管理學(xué)院《數(shù)據(jù)結(jié)構(gòu)中俄》

2023-2024學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)2、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)3、在一個(gè)具有n個(gè)節(jié)點(diǎn)的有向圖中，若存在多個(gè)入度為0的節(jié)點(diǎn)，進(jìn)行拓?fù)渑判驎r(shí)，應(yīng)該選擇哪個(gè)節(jié)點(diǎn)作為起始節(jié)點(diǎn)？A.任意一個(gè)入度為0的節(jié)點(diǎn)B.編號(hào)最小的入度為0的節(jié)點(diǎn)C.編號(hào)最大的入度為0的節(jié)點(diǎn)D.以上都不對(duì)4、以下關(guān)于樹(shù)的遍歷算法的描述，哪一項(xiàng)是不正確的？（）A.先序遍歷先訪(fǎng)問(wèn)根節(jié)點(diǎn)B.中序遍歷先訪(fǎng)問(wèn)左子樹(shù)C.后序遍歷先訪(fǎng)問(wèn)右子樹(shù)D.三種遍歷算法都可以用遞歸或非遞歸方式實(shí)現(xiàn)5、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表中，若要?jiǎng)h除第i個(gè)元素（1<=i<=n），需要找到其前驅(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表存儲(chǔ)，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)7、在一個(gè)具有n個(gè)元素的有序單鏈表中，要查找一個(gè)特定元素，平均時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)8、在哈夫曼編碼中，對(duì)于出現(xiàn)頻率較高的字符，其編碼長(zhǎng)度通常怎樣？（）A.較長(zhǎng)B.較短C.固定不變D.隨機(jī)確定9、對(duì)于一個(gè)具有n個(gè)元素的有序鏈表，進(jìn)行二分查找的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.不能進(jìn)行二分查找10、在一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列中，若隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針front指向隊(duì)頭元素，則隊(duì)列中元素的個(gè)數(shù)為？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+111、在數(shù)據(jù)結(jié)構(gòu)中，AVL樹(shù)的刪除操作比插入操作更復(fù)雜，以下關(guān)于刪除操作的描述，錯(cuò)誤的是（）A.可能需要進(jìn)行多次旋轉(zhuǎn)來(lái)保持平衡B.首先找到要?jiǎng)h除的節(jié)點(diǎn)C.刪除后不需要調(diào)整樹(shù)的結(jié)構(gòu)D.要考慮刪除節(jié)點(diǎn)的子樹(shù)情況12、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，若每個(gè)節(jié)點(diǎn)都有左子樹(shù)和右子樹(shù)，則其葉子節(jié)點(diǎn)的個(gè)數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn13、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)14、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，使用深度優(yōu)先搜索算法進(jìn)行遍歷。以下關(guān)于算法中使用的標(biāo)記數(shù)組的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)15、在一個(gè)容量為10的順序存儲(chǔ)的循環(huán)隊(duì)列中，若front=4，rear=8，則此時(shí)隊(duì)列中元素的個(gè)數(shù)為：A.4B.5C.6D.716、以下關(guān)于字符串匹配算法的描述，哪一項(xiàng)是不正確的？（）A.BF算法的時(shí)間復(fù)雜度在最壞情況下較高B.KMP算法通過(guò)利用已匹配的部分信息來(lái)提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時(shí)間復(fù)雜度都與模式串的長(zhǎng)度成正比17、已知一個(gè)完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)為100，其葉子節(jié)點(diǎn)的個(gè)數(shù)為（）。A.49B.50C.51D.不確定18、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.1543219、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用20、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖，其生成樹(shù)中邊的條數(shù)為（）。A.nB.n-1C.eD.e-1二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋在平衡二叉搜索樹(shù)中，如何通過(guò)平衡調(diào)整操作減少節(jié)點(diǎn)的移動(dòng)次數(shù)。2、（本題10分）詳細(xì)闡述AVL樹(shù)的旋轉(zhuǎn)操作，包括單旋轉(zhuǎn)和雙旋轉(zhuǎn)，以及在插入節(jié)點(diǎn)時(shí)如何進(jìn)行平衡調(diào)整。3、（本題10分）闡述后綴樹(shù)的空間優(yōu)化方法和實(shí)際應(yīng)用中的考慮因素。4、（本題10分）論述在圖的存儲(chǔ)結(jié)構(gòu)中，鄰接多重表的特點(diǎn)和適用場(chǎng)景，與鄰接表的區(qū)別。三、設(shè)計(jì)題（本大題