湖南工商大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》2022-2023學(xué)年期末試卷

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁(yè)，共1頁(yè)湖南工商大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法分析》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)元素的哈希表，負(fù)載因子越大，發(fā)生沖突的可能性如何變化？（）A.越大B.越小C.不變D.不確定2、在一個(gè)字符串匹配算法中，BM算法相對(duì)于樸素的字符串匹配算法，其優(yōu)勢(shì)在于？（）A.平均性能更好B.代碼更簡(jiǎn)潔C.空間復(fù)雜度更低D.適用于短字符串匹配3、在一個(gè)用鄰接矩陣存儲(chǔ)的圖中，若要判斷兩個(gè)節(jié)點(diǎn)是否相鄰，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)4、對(duì)于一個(gè)具有n個(gè)元素的雙向循環(huán)鏈表，若要?jiǎng)h除第i個(gè)節(jié)點(diǎn)（1<=i<=n），平均需要修改多少個(gè)指針？（）A.2B.3C.4D.55、圖的存儲(chǔ)方式和遍歷方式可以用于解決很多實(shí)際問(wèn)題，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。B.圖的鄰接表可以用于表示稀疏圖，如地圖、電路圖等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問(wèn)題和最小生成樹(shù)問(wèn)題等。D.圖的存儲(chǔ)方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。6、深度為5的滿二叉樹(shù)的結(jié)點(diǎn)數(shù)為：A.16B.31C.32D.157、在一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表中，若要在p所指結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)q，需要修改幾個(gè)指針？（）A.2B.4C.6D.88、以下關(guān)于紅黑樹(shù)的性質(zhì)，錯(cuò)誤的是：A.每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)是黑色的C.每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色的D.紅色節(jié)點(diǎn)的子節(jié)點(diǎn)一定是紅色的9、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)其下三角部分，第一個(gè)元素A[1,1]存儲(chǔ)在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲(chǔ)位置為k，則A[7,5]在數(shù)組B中的存儲(chǔ)位置為（）。A.k-13B.k-12C.k-11D.k-1010、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序11、若一個(gè)鏈表的每個(gè)節(jié)點(diǎn)只包含數(shù)據(jù)域和指針域，且指針域只指向其后繼節(jié)點(diǎn)，這種鏈表稱為：A.單向鏈表B.雙向鏈表C.循環(huán)鏈表D.靜態(tài)鏈表12、在一個(gè)順序存儲(chǔ)的隊(duì)列中，若要在隊(duì)尾插入一個(gè)元素，需要移動(dòng)元素的平均次數(shù)為（）A.0B.n/2C.nD.n-113、以下關(guān)于字符串壓縮算法的描述，哪一項(xiàng)是不正確的？（）A.哈夫曼編碼可以根據(jù)字符出現(xiàn)頻率進(jìn)行壓縮B.LZW壓縮算法基于字典進(jìn)行壓縮C.壓縮算法一定能減小字符串的存儲(chǔ)空間D.不同的壓縮算法適用于不同類型的字符串14、在一個(gè)具有n個(gè)元素的最大堆中，插入一個(gè)新元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、在一個(gè)具有n個(gè)元素的堆中，查找最大元素的時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)16、在圖的遍歷算法中，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是兩種常見(jiàn)的方法。以下關(guān)于它們的描述，錯(cuò)誤的是（）A.DFS使用棧來(lái)保存未訪問(wèn)的節(jié)點(diǎn)B.BFS使用隊(duì)列來(lái)保存未訪問(wèn)的節(jié)點(diǎn)C.DFS可能會(huì)陷入死循環(huán)D.BFS一定能找到最短路徑17、對(duì)于一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front18、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲(chǔ)方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以19、對(duì)于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲(chǔ)到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無(wú)序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對(duì)20、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用弗洛伊德算法求所有節(jié)點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）比較快速排序和插入排序在對(duì)重復(fù)元素較多的數(shù)據(jù)處理情況。2、（本題10分）詳細(xì)闡述在圖的廣度優(yōu)先遍歷算法中，如何使用隊(duì)列來(lái)實(shí)現(xiàn)，并說(shuō)明其應(yīng)用場(chǎng)景。3、（本題10分）詳細(xì)闡述在具有n個(gè)頂點(diǎn)的無(wú)向圖中，如何使用廣度優(yōu)先搜索算法判斷兩個(gè)頂點(diǎn)是否連通，并給出具體的算法步驟和代碼實(shí)現(xiàn)。4、（本題10分）詳細(xì)闡述如何在一個(gè)字符串中查找所有由相同字符組成的子串。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（本題10分）設(shè)計(jì)一個(gè)程