成都錦城學院《數據結構與算法基礎》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁成都錦城學院

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