成都大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁成都大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》

2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、平衡二叉樹是一種特殊的二叉搜索樹，其目的是為了保證查找效率。以下哪種操作可能會導(dǎo)致平衡二叉樹失去平衡？A.插入節(jié)點B.刪除節(jié)點C.查找節(jié)點D.以上都可能2、在一個有向無環(huán)圖中，進行拓撲排序的結(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對3、在一個具有n個頂點和e條邊的有向圖中，采用鄰接表存儲，求頂點的入度的時間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)4、對于一個具有n個節(jié)點的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結(jié)果都是唯一確定的，這個二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是5、對于一個具有n個元素的堆，進行刪除操作并調(diào)整堆的時間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、對于一個用數(shù)組實現(xiàn)的小根堆，進行刪除堆頂元素操作后，需要重新調(diào)整堆以保持堆的性質(zhì)。以下關(guān)于刪除操作的時間復(fù)雜度的描述，哪一個是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序8、對于一個用數(shù)組實現(xiàn)的循環(huán)隊列，若隊列已滿，此時front=10，rear=20，隊列的最大容量為50，那么下一個入隊元素應(yīng)該存儲在哪個位置？A.21B.0C.30D.無法確定9、在一個具有n個節(jié)點的帶權(quán)有向圖中，若存在負權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用10、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強連通圖D.弱連通圖11、在一個具有n個元素的鏈表中，訪問第i個元素的時間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、設(shè)有一個棧，元素進棧的次序為A、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE13、在一個具有n個節(jié)點的圖中，使用弗洛伊德算法求所有節(jié)點對之間的最短路徑，其時間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)14、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n/215、若一個隊列的入隊序列是1、2、3、4、5，在進行出隊操作時，第一個出隊的元素是：A.1B.2C.3D.416、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機位置D.以上都不對17、棧和隊列的實現(xiàn)可以使用數(shù)組或鏈表，以下關(guān)于它們的實現(xiàn)方式的說法中，錯誤的是？（）A.用數(shù)組實現(xiàn)棧和隊列時，需要考慮數(shù)組的大小和溢出問題。B.用鏈表實現(xiàn)棧和隊列時，插入和刪除操作的時間復(fù)雜度為O(1)。C.棧和隊列的實現(xiàn)方式只影響它們的性能，不影響它們的功能。D.棧和隊列可以同時使用數(shù)組和鏈表實現(xià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個元素的有序數(shù)組，若采用折半插入排序算法進行排序，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)20、設(shè)有一個具有n個節(jié)點的二叉搜索樹，若要查找一個值大于給定值的最小節(jié)點，以下關(guān)于查找操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）在一個二叉搜索樹中，如何查找值在給定范圍內(nèi)的所有元素？2、（本題10分）在一個具有n個元素的有序鏈表中，如何進行高效的插入操作，使得鏈表仍然保持有序，分析其時間復(fù)雜度。3、（本題10分）解釋如何在一個字符串中查找所有不重復(fù)的字符組合。4、（本題10分）論述在字符串匹配的模