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

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

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