成都錦城學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁成都錦城學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個鏈隊列中，假設(shè)隊頭指針為front，隊尾指針為rear，刪除隊頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL2、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結(jié)構(gòu)，則插入和刪除操作的時間復(fù)雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)3、若要對100個元素進(jìn)行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.選擇排序C.插入排序D.歸并排序4、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同5、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB6、在一個帶權(quán)的有向圖中，使用迪杰斯特拉算法求從源點到其他頂點的最短路徑，每次選擇的頂點是？（）A.距離源點最近的頂點B.距離源點最遠(yuǎn)的頂點C.未確定最短路徑的頂點中權(quán)值最小的頂點D.未確定最短路徑的頂點中權(quán)值最大的頂點7、對于一個用鏈表實現(xiàn)的棧，若要在棧頂插入一個元素，時間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)8、鏈表是另一種常見的數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點組成，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的指針。以下關(guān)于鏈表的說法中，錯誤的是？（）A.鏈表的插入和刪除操作比較方便，只需要修改指針即可。B.鏈表可以動態(tài)地增長和縮小，不像數(shù)組那樣受固定長度的限制。C.鏈表的訪問速度比數(shù)組慢，因為需要遍歷鏈表才能找到特定的元素。D.鏈表只能存儲整數(shù)類型的數(shù)據(jù)元素。9、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，若采用Prim算法生成最小生成樹，其時間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)10、以下關(guān)于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項是正確的？（）A.深度優(yōu)先搜索使用隊列實現(xiàn)B.廣度優(yōu)先搜索使用棧實現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑11、在一個用鏈表實現(xiàn)的棧中，若要獲取棧底元素的值，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、已知一個帶權(quán)無向圖的鄰接矩陣表示，若要計算圖中兩個頂點之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法13、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB14、在一個平衡二叉搜索樹中，插入一個新節(jié)點后，可能需要進(jìn)行的調(diào)整操作次數(shù)最多為（）A.1B.lognC.nD.nlogn15、設(shè)有一個廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)16、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)17、在一個用順序存儲結(jié)構(gòu)實現(xiàn)的棧中，若棧頂指針top指向棧頂元素的上一個位置，當(dāng)棧為空時，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）18、對于一個m行n列的二維數(shù)組，按行優(yōu)先存儲時，元素a[i][j]（0<=i<m,0<=j<n）的地址計算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i19、在一個具有n個節(jié)點的二叉排序樹中，刪除一個節(jié)點后，為了保持二叉排序樹的性質(zhì)，可能需要進(jìn)行哪些操作？A.僅調(diào)整刪除節(jié)點的子樹B.從根節(jié)點開始重新調(diào)整C.調(diào)整整個樹的結(jié)構(gòu)D.以上都有可能20、數(shù)組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何使用二分查找在一個旋轉(zhuǎn)有序數(shù)組中查找目標(biāo)值。2、（本題10分）詳細(xì)闡述圖的拓?fù)渑判虻母拍詈蛻?yīng)用場景，給出拓?fù)渑判虻乃惴ú襟E，并分析其時間復(fù)雜度。3、（本題10分）論述跳表在插入和刪除元素時，如何維護(hù)其結(jié)構(gòu)的平衡性和查找效率。4、（本題10分）詳細(xì)說明在二叉樹的平衡調(diào)整中，除了旋轉(zhuǎn)操作，還有