站名：站名：年級(jí)專(zhuān)業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專(zhuān)業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁(yè)，共1頁(yè)西安電子科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)和算法應(yīng)用》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序2、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，若要在其中查找一個(gè)特定元素，平均需要比較的次數(shù)為？（）A.n/2B.nC.lognD.nlogn3、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若其所有頂點(diǎn)的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.204、在一棵完全二叉樹(shù)中，若節(jié)點(diǎn)個(gè)數(shù)為n，那么其葉子節(jié)點(diǎn)的個(gè)數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/35、在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n6、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的連通圖，其生成樹(shù)中邊的數(shù)量為：A.n-1B.nC.n+1D.不確定7、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速判斷一個(gè)元素是否在集合中？A.鏈表B.二叉搜索樹(shù)C.哈希表D.棧8、對(duì)于一個(gè)有向圖進(jìn)行深度優(yōu)先遍歷，若從頂點(diǎn)v開(kāi)始，訪問(wèn)完v的鄰接點(diǎn)后，接著應(yīng)該訪問(wèn)哪個(gè)頂點(diǎn)？（）A.按照頂點(diǎn)編號(hào)順序的下一個(gè)未訪問(wèn)頂點(diǎn)B.v的第一個(gè)鄰接點(diǎn)C.任意一個(gè)未訪問(wèn)的鄰接點(diǎn)D.以上都不對(duì)9、紅黑樹(shù)是一種自平衡的二叉搜索樹(shù)，具有嚴(yán)格的性質(zhì)。以下關(guān)于紅黑樹(shù)的描述，不正確的是（）A.節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)一定是黑色C.從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量相同D.紅黑樹(shù)的插入和刪除操作比平衡二叉樹(shù)簡(jiǎn)單10、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，若每個(gè)節(jié)點(diǎn)都有左右子樹(shù)，則該二叉樹(shù)的葉子節(jié)點(diǎn)數(shù)量與度為2的節(jié)點(diǎn)數(shù)量之間存在特定關(guān)系。以下關(guān)于這種關(guān)系的描述，哪一項(xiàng)是正確的？A.葉子節(jié)點(diǎn)數(shù)量等于度為2的節(jié)點(diǎn)數(shù)量B.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量多1C.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量少1D.兩者之間沒(méi)有固定關(guān)系11、對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，若要查找某個(gè)元素是否存在，以下哪種查找算法效率最高？（）A.順序查找B.二分查找C.分塊查找D.以上算法效率相同12、對(duì)于一個(gè)具有n個(gè)元素的有序雙向鏈表，查找中間元素的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,514、對(duì)于一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆，若要將堆頂元素與最后一個(gè)元素交換，然后重新調(diào)整堆，以下關(guān)于調(diào)整的方向，哪一項(xiàng)是正確的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先從堆頂向下調(diào)整，再?gòu)亩训紫蛏险{(diào)整D.以上都不對(duì)15、在數(shù)據(jù)結(jié)構(gòu)中，哈希表的負(fù)載因子對(duì)性能有很大影響。以下關(guān)于負(fù)載因子的描述，不正確的是（）A.負(fù)載因子越大，哈希沖突的可能性越大B.負(fù)載因子越小，存儲(chǔ)空間利用率越高C.負(fù)載因子通常在0.5到1之間D.可以通過(guò)調(diào)整負(fù)載因子來(lái)優(yōu)化哈希表性能16、在一個(gè)棧中，若入棧序列為1,2,3,4，且在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.1717、平衡二叉樹(shù)是一種特殊的二叉搜索樹(shù)，其目的是為了保證查找效率。以下哪種操作可能會(huì)導(dǎo)致平衡二叉樹(shù)失去平衡？A.插入節(jié)點(diǎn)B.刪除節(jié)點(diǎn)C.查找節(jié)點(diǎn)D.以上都可能18、已知一個(gè)哈希表的長(zhǎng)度為11，哈希函數(shù)為H(key)=key%11，采用二次探測(cè)法處理沖突。若依次插入關(guān)鍵字15、38、61、84，則在查找關(guān)鍵字61時(shí)需要進(jìn)行幾次探測(cè)？（）A.1B.2C.3D.419、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，要?jiǎng)h除隊(duì)頭元素，需要進(jìn)行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;20、在一個(gè)字符串匹配算法中，BM算法相對(duì)于樸素的字符串匹配算法，其優(yōu)勢(shì)在于？（）A.平均性能更好B.代碼更簡(jiǎn)潔C.空間復(fù)雜度更低D.適用于短字符串匹配二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述紅黑樹(shù)的插入操作中，顏色調(diào)整的具體步驟和邏輯。2、（本題10分）詳細(xì)說(shuō)明如何在一個(gè)有序數(shù)組中查找第一個(gè)大于等于給定值的元素，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。3、（本題10分）解釋在一個(gè)帶權(quán)無(wú)向圖中，如何使用弗洛伊德算法求解任意兩點(diǎn)之間的最短路徑，說(shuō)明算法的空間復(fù)雜度和時(shí)間復(fù)雜度。4、（本題10分）在圖的遍歷中，如何處理帶負(fù)權(quán)邊的圖？有哪些算法可以解決帶負(fù)權(quán)邊的最短路徑問(wèn)題？三、設(shè)計(jì)題（本大題共2個(gè)小