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

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)成都錦城學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的有序數(shù)組中，若要?jiǎng)h除一個(gè)特定元素，并且保持?jǐn)?shù)組的有序性，以下關(guān)于刪除操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)3、對(duì)于一個(gè)具有n個(gè)元素的有序鏈表，進(jìn)行折半查找，其時(shí)間復(fù)雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進(jìn)行折半查找4、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)中，若每個(gè)節(jié)點(diǎn)都有左右孩子，則葉子節(jié)點(diǎn)的數(shù)量與度為2的節(jié)點(diǎn)數(shù)量有什么關(guān)系？A.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量+1B.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量-1C.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量D.以上都不對(duì)5、已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA6、在一個(gè)有序的單鏈表中，若要?jiǎng)h除一個(gè)重復(fù)出現(xiàn)的元素，使得鏈表中不再有重復(fù)元素，應(yīng)如何操作？（）A.從頭遍歷，遇到重復(fù)元素就刪除B.從尾遍歷，遇到重復(fù)元素就刪除C.先排序，再刪除重復(fù)元素D.建立一個(gè)新鏈表，將不重復(fù)元素插入7、對(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+i8、在一個(gè)具有n個(gè)元素的有序數(shù)組中，采用插入排序進(jìn)行排序，在最好情況下，需要比較的次數(shù)為（）。A.n-1B.nC.0D.n(n-1)/29、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)無(wú)向圖中，使用普里姆算法構(gòu)造最小生成樹(shù)，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)10、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲(chǔ)方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以11、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)12、在一個(gè)字符串匹配算法中，BM算法相對(duì)于樸素的字符串匹配算法，其優(yōu)勢(shì)在于？（）A.平均性能更好B.代碼更簡(jiǎn)潔C.空間復(fù)雜度更低D.適用于短字符串匹配13、在一個(gè)有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，采用鄰接矩陣存儲(chǔ)，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)14、在一棵二叉搜索樹(shù)中，刪除一個(gè)只有左子樹(shù)的節(jié)點(diǎn)，其右子樹(shù)的節(jié)點(diǎn)需要（）A.替換被刪除節(jié)點(diǎn)B.保持不動(dòng)C.全部刪除D.移動(dòng)到左子樹(shù)15、在一個(gè)具有n個(gè)元素的有序單鏈表中，若要查找一個(gè)特定元素，以下關(guān)于查找操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)，若一個(gè)二叉樹(shù)的先序遍歷序列為ABC，中序遍歷序列為BAC，那么它的后序遍歷序列是什么？（）A.BCAB.CBAC.CABD.ACB17、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表存儲(chǔ)時(shí)，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)18、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖中，使用Prim算法生成最小生成樹(shù)。若采用鄰接矩陣存儲(chǔ)圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)19、以下關(guān)于樹(shù)的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是不正確的？（）A.孩子兄弟表示法可以方便地實(shí)現(xiàn)樹(shù)的遍歷B.雙親表示法便于查找一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)C.孩子鏈表表示法在處理多叉樹(shù)時(shí)空間利用率較高D.以上存儲(chǔ)結(jié)構(gòu)在時(shí)間復(fù)雜度上沒(méi)有明顯差異20、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的無(wú)向圖中，若采用鄰接表存儲(chǔ)，則存儲(chǔ)空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^2二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述在一個(gè)循環(huán)隊(duì)列中，如何判斷隊(duì)空和隊(duì)滿的條件，并解釋為什么需要這樣判斷，以及可能會(huì)出現(xiàn)的誤判情況和解決方法。2、（本題10分）數(shù)組的索引是如何確定的？在不同編程語(yǔ)言中索引的使用有哪些注意事項(xiàng)？3、（本題10分）詳細(xì)闡述B+樹(shù)的范圍查詢操作的實(shí)現(xiàn)過(guò)程和優(yōu)勢(shì)。4、（本題10分）對(duì)于一個(gè)用哈希表存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，解釋哈希函數(shù)的作用和選擇原則，以及如何處理哈希沖突，并分析其查找效率