常州大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁常州大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的有序鏈表中，若要查找第k個元素，以下關(guān)于查找操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(k)D.O(n)2、在數(shù)據(jù)結(jié)構(gòu)中，字典樹（Trie樹）常用于字符串的存儲和查找，以下關(guān)于字典樹的特點，不正確的是（）A.對于前綴相同的字符串可以節(jié)省存儲空間B.查找操作的時間復(fù)雜度與字符串長度有關(guān)C.適合用于詞頻統(tǒng)計D.插入和刪除操作比較復(fù)雜3、圖是一種更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，它由頂點和邊組成。以下關(guān)于圖的說法中，錯誤的是？（）A.圖可以分為有向圖和無向圖兩種。B.圖的存儲方式有鄰接矩陣和鄰接表兩種。C.圖的遍歷方式有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種。D.圖的最短路徑算法只有迪杰斯特拉算法一種。4、在一個具有n個元素的大根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進行調(diào)整，其時間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)5、在一個具有n個頂點的強連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)6、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則存儲空間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)7、對于一個用數(shù)組實現(xiàn)的小根堆，進行刪除堆頂元素操作后，需要重新調(diào)整堆以保持堆的性質(zhì)。以下關(guān)于刪除操作的時間復(fù)雜度的描述，哪一個是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對于一個具有n個元素的選擇排序，在最壞情況下，需要進行多少次交換操作？（）A.n-1B.nC.n(n-1)/2D.09、已知一個圖的鄰接矩陣如下所示，則從頂點V1出發(fā)進行深度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V510、在一個哈希表中，負載因子越大，說明什么？A.哈希沖突越少B.存儲空間利用率越高C.查找效率越高D.以上都不對11、在一個順序存儲的隊列中，若要在隊尾插入一個元素，需要移動元素的平均次數(shù)為（）A.0B.n/2C.nD.n-112、已知一個帶權(quán)有向圖G=(V,E)，頂點集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點1到頂點5的最短路徑，經(jīng)過的中間頂點依次為？（）A.2,4B.3,4C.2,3D.3,513、若要對一個具有n個元素的無序數(shù)組進行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序14、對于一個具有n個元素的快速排序，每次劃分選取的基準元素不同，對排序的時間復(fù)雜度有何影響？（）A.沒有影響B(tài).可能會提高C.可能會降低D.以上都不對15、在一個帶頭結(jié)點的雙向鏈表中，若要在p所指結(jié)點之后插入一個新結(jié)點q，需要修改幾個指針？（）A.2B.4C.6D.816、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.517、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.棧空C.棧中只有一個元素D.棧中至少有一個元素18、在一個具有n個節(jié)點的完全二叉樹中，其葉子節(jié)點的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-119、在一個具有n個節(jié)點的無向圖中，若要判斷兩個節(jié)點之間是否存在路徑，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.克魯斯卡爾算法20、對于一個具有n個元素的冒泡排序，在最壞情況下，需要進行多少次比較操作？（）A.n(n-1)/2B.nC.n+1D.n-1二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述伸展樹在處理隨機數(shù)據(jù)時的性能表現(xiàn)和優(yōu)化措施。2、（本題10分）詳細解釋在一個具有n個元素的二叉樹中，如何進行按層遍歷的廣度優(yōu)先搜索的非遞歸實現(xiàn)。3、（本題10分）論述在一個具有n個頂點的無向圖中，如何使用廣度優(yōu)先搜索算法來生成連通分量。4、（本題10分）深入分析在利用鏈表實現(xiàn)隊列時，如何解決假溢出問題，并說明其實現(xiàn)原理和代碼示例。三、設(shè)