站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁西安電子科技大學

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