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

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

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