西安電子科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)和算法應(yīng)用》2022-2023學(xué)年期末試卷

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記?！堋狻€…………第1頁(yè)，共1頁(yè)西安電子科技大學(xué)

《數(shù)據(jù)結(jié)構(gòu)和算法應(yīng)用》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、已知一個(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,52、若要對(duì)一個(gè)具有n個(gè)元素的無(wú)序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序3、設(shè)有一個(gè)循環(huán)隊(duì)列，存儲(chǔ)空間為Q[0..m-1]，初始時(shí)front=rear=m?，F(xiàn)經(jīng)過(guò)一系列入隊(duì)與退隊(duì)操作后，front=20，rear=15，則此時(shí)隊(duì)列中的元素個(gè)數(shù)為（）。A.5B.6C.m-5D.m+54、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素，需要移動(dòng)的元素個(gè)數(shù)為？（）A.n-iB.iC.n-i+1D.n-i-16、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？A.鏈表B.隊(duì)列C.棧D.堆7、在一個(gè)具有n個(gè)元素的最小堆中，若要將堆頂元素與堆底元素交換，然后調(diào)整堆的結(jié)構(gòu)，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線性表中，要在第i個(gè)位置插入一個(gè)新元素（1<=i<=n+1），需要移動(dòng)的元素個(gè)數(shù)約為？A.n-iB.iC.n-i+1D.n-i-19、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若其邊的集合為{(1,2),(1,3),(2,3),(2,4),(3,4)}，則該圖的鄰接表存儲(chǔ)中，頂點(diǎn)2的鏈表中包含的頂點(diǎn)有：A.1,3,4B.1,3C.3,4D.1,410、已知一棵二叉樹(shù)的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹(shù)的右子樹(shù)為空的條件是？（）A.A為根節(jié)點(diǎn)B.B為根節(jié)點(diǎn)C.C為根節(jié)點(diǎn)D.無(wú)法確定11、對(duì)于一個(gè)具有n個(gè)元素的小根堆，若要?jiǎng)h除堆頂元素并重新調(diào)整堆，以下關(guān)于操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、在一個(gè)字符串中，要查找某個(gè)子串首次出現(xiàn)的位置，通常可以使用哪種算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找13、若一個(gè)隊(duì)列的入隊(duì)序列是1、2、3、4、5，在進(jìn)行出隊(duì)操作時(shí)，第一個(gè)出隊(duì)的元素是：A.1B.2C.3D.414、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，使用快速排序算法進(jìn)行排序，在平均情況下的空間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、一棵哈夫曼樹(shù)共有215個(gè)節(jié)點(diǎn)，對(duì)其進(jìn)行編碼，共能得到（）種不同的編碼。A.107B.108C.214D.21516、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?huì)？A.正常排序B.無(wú)法排序C.部分排序D.排序結(jié)果不確定17、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，其鄰接矩陣中非零元素的個(gè)數(shù)最多為？（）A.eB.2eC.n^2D.n(n-1)18、在一個(gè)順序存儲(chǔ)的隊(duì)列中，若要在隊(duì)尾插入一個(gè)元素，需要移動(dòng)元素的平均次數(shù)為（）A.0B.n/2C.nD.n-119、對(duì)于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲(chǔ)到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無(wú)序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對(duì)20、若一棵二叉樹(shù)的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）鏈表的選擇排序有哪些步驟？請(qǐng)?jiān)敿?xì)描述其實(shí)現(xiàn)過(guò)程。2、（本題10分）詳細(xì)說(shuō)明如何在一個(gè)具有n個(gè)元素的無(wú)序數(shù)組中，使用選擇排序算法進(jìn)行排序，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題10分）闡述后綴數(shù)組與后綴樹(shù)的關(guān)系，以及它們?cè)谧址幚碇械牟煌瑧?yīng)用場(chǎng)景。4、（本題10分）論述跳表在數(shù)據(jù)動(dòng)態(tài)更新頻繁情況下的性能優(yōu)化策略。三、設(shè)計(jì)題（本大題共