鹽城工學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁鹽城工學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》

2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的堆中，進(jìn)行插入操作的時間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)2、設(shè)有一個具有n個節(jié)點的二叉樹，若每個節(jié)點都有左右子樹，則該二叉樹的葉子節(jié)點數(shù)量與度為2的節(jié)點數(shù)量之間存在特定關(guān)系。以下關(guān)于這種關(guān)系的描述，哪一項是正確的？A.葉子節(jié)點數(shù)量等于度為2的節(jié)點數(shù)量B.葉子節(jié)點數(shù)量比度為2的節(jié)點數(shù)量多1C.葉子節(jié)點數(shù)量比度為2的節(jié)點數(shù)量少1D.兩者之間沒有固定關(guān)系3、哈希表是一種常用的數(shù)據(jù)結(jié)構(gòu)，它通過哈希函數(shù)將鍵映射到存儲位置。以下關(guān)于哈希表的說法中，錯誤的是？（）A.哈希表的查找速度非?？?，平均時間復(fù)雜度為O(1)。B.哈希函數(shù)的設(shè)計直接影響哈希表的性能。C.哈希表可能會出現(xiàn)沖突，即不同的鍵被映射到同一個存儲位置。D.哈希表只能存儲整數(shù)類型的鍵值對。4、在二叉搜索樹的刪除操作中，如果刪除的節(jié)點是其父節(jié)點的唯一子節(jié)點，以下處理方式錯誤的是（）A.直接將該節(jié)點刪除，不做其他調(diào)整B.將該節(jié)點的值替換為其父節(jié)點的值，并刪除父節(jié)點C.將該節(jié)點的左子樹或右子樹替代該節(jié)點D.以上處理方式都不對5、對于一個具有n個頂點和e條邊的無向圖，使用深度優(yōu)先搜索算法進(jìn)行遍歷。以下關(guān)于算法中使用的標(biāo)記數(shù)組的空間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)6、在一個具有n個節(jié)點的完全二叉樹中，若底層從左到右依次編號，節(jié)點i的左孩子節(jié)點編號是多少（假設(shè)根節(jié)點編號為1）？A.2iB.2i+1C.i*2D.以上都不對7、在一個具有n個元素的棧中，若要獲取棧底元素但不刪除，需要進(jìn)行多少次操作？（）A.1B.n-1C.nD.n+18、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.314259、一棵哈夫曼樹共有215個節(jié)點，對其進(jìn)行編碼，共能得到（）種不同的編碼。A.107B.108C.214D.21510、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.1543211、以下哪種數(shù)據(jù)結(jié)構(gòu)可以高效地支持集合的并、交、差等操作？A.二叉搜索樹B.哈希表C.并查集D.平衡二叉樹12、在一個具有n個元素的有序數(shù)組中，使用二分查找查找一個不存在的元素，最多比較次數(shù)約為？A.lognB.nC.n/2D.nlogn13、在一個具有n個元素的大頂堆中，若要將堆頂元素與最后一個元素交換，然后調(diào)整堆，其時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)15、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法16、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n17、在圖的存儲結(jié)構(gòu)中，鄰接多重表主要用于存儲無向圖，以下關(guān)于鄰接多重表的特點，描述錯誤的是（）A.可以方便地刪除邊B.存儲空間比鄰接矩陣節(jié)省C.對于判斷兩點之間是否有邊，效率較高D.不適合用于有向圖的存儲18、在一個具有n個元素的順序表中，要在中間位置插入一個新元素，平均移動元素的個數(shù)約為？A.n/2B.nC.lognD.119、在一個具有n個元素的最小堆中，插入一個新元素后，為了重新調(diào)整為最小堆，最壞情況下需要比較多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)20、在一個采用哈希表存儲的數(shù)據(jù)結(jié)構(gòu)中，哈希函數(shù)將關(guān)鍵字映射到存儲位置。若發(fā)生哈希沖突，通常采用開放定址法解決。以下關(guān)于開放定址法的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.查找操作的時間復(fù)雜度在平均情況下為O(1)，最壞情況為O(n)B.查找操作的時間復(fù)雜度始終為O(1)C.查找操作的時間復(fù)雜度在平均情況下為O(logn)，最壞情況為O(nlogn)D.查找操作的時間復(fù)雜度始終為O(n)二、簡答題（本大題共4個小題，共40分)1、（本題10分）分析在字符串匹配中，如何利用位運算提高匹配速度。2、（本題10分）詳細(xì)說明如何在一個二叉搜索樹中查找最大和最小元素。3、（本題10分）解釋如何在一個具有n個頂點的圖中計算每個頂點的鄰居頂點數(shù)量。4、（本題10分）比較插入排序和希爾排序在初始有序程度不同的情況下的性能差異。三、設(shè)計題（本大題共2個小題，