西安電子科技大學《數(shù)據(jù)結構和算法應用》2021-2022學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁西安電子科技大學《數(shù)據(jù)結構和算法應用》

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