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

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

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