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

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁安徽科技學(xué)院

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若front=rear，則隊(duì)列的狀態(tài)可能為（）A.隊(duì)空B.隊(duì)滿C.既不空也不滿D.以上都有可能2、在一個用數(shù)組實(shí)現(xiàn)的堆中，若要刪除堆底的元素，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在一個用鄰接矩陣表示的無向圖中，矩陣中的元素表示什么？A.頂點(diǎn)之間的距離B.頂點(diǎn)之間是否有邊C.邊的權(quán)重D.以上都有可能4、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機(jī)位置D.以上都不對5、在一個循環(huán)鏈表中，若要刪除鏈表中的最后一個節(jié)點(diǎn)，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個具有n個元素的小根堆中，最小元素的值位于（）。A.根節(jié)點(diǎn)B.任意節(jié)點(diǎn)C.葉子節(jié)點(diǎn)D.無法確定7、在一個具有n個元素的最小堆中，刪除堆頂元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對于一個具有n個元素的哈希表，若采用鏈地址法處理沖突，以下關(guān)于查找操作的平均時間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、在一個具有n個頂點(diǎn)的無向圖中，使用廣度優(yōu)先遍歷算法。以下關(guān)于遍歷過程中使用的輔助隊(duì)列的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(n^2)10、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接已選頂點(diǎn)和未選頂點(diǎn)的權(quán)值最小的邊C.任意一條邊D.以上都不對11、在一個字符串匹配算法中，BM算法相對于樸素的字符串匹配算法，其優(yōu)勢在于？（）A.平均性能更好B.代碼更簡潔C.空間復(fù)雜度更低D.適用于短字符串匹配12、在數(shù)據(jù)結(jié)構(gòu)中，跳表的索引層數(shù)是根據(jù)數(shù)據(jù)量動態(tài)調(diào)整的，以下關(guān)于索引層數(shù)調(diào)整的描述，錯誤的是（）A.當(dāng)數(shù)據(jù)量增加時，可能增加索引層數(shù)B.索引層數(shù)越多，查找效率越高C.調(diào)整索引層數(shù)的過程比較復(fù)雜D.索引層數(shù)的調(diào)整不會影響數(shù)據(jù)的存儲結(jié)構(gòu)13、對于一個具有n個元素的選擇排序，在最壞情況下，需要進(jìn)行多少次交換操作？（）A.n-1B.nC.n(n-1)/2D.014、在一個小根堆中，最小的元素總是位于堆頂。若要將一個元素插入到堆中并保持堆的性質(zhì)，以下哪種操作是必須的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先刪除堆頂元素再插入D.以上都不對15、鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，包括單鏈表、雙向鏈表等。在單鏈表中，要刪除一個指定節(jié)點(diǎn)，以下操作錯誤的是（）A.首先找到要刪除的節(jié)點(diǎn)B.直接將該節(jié)點(diǎn)從鏈表中移除，無需處理前后節(jié)點(diǎn)的鏈接C.修改前一個節(jié)點(diǎn)的指針，使其指向要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)D.釋放被刪除節(jié)點(diǎn)所占用的內(nèi)存16、對于一個采用鏈?zhǔn)酱鎯Φ年?duì)列，若隊(duì)頭指針和隊(duì)尾指針相同，則隊(duì)列的狀態(tài)為：A.隊(duì)空B.隊(duì)滿C.不確定D.隊(duì)列中只有一個元素17、對于一個具有n個元素的無序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)18、圖是一種更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，它由頂點(diǎn)和邊組成。以下關(guān)于圖的說法中，錯誤的是？（）A.圖可以分為有向圖和無向圖兩種。B.圖的存儲方式有鄰接矩陣和鄰接表兩種。C.圖的遍歷方式有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種。D.圖的最短路徑算法只有迪杰斯特拉算法一種。19、隊(duì)列是一種先進(jìn)先出的線性表，若用一個數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列，隊(duì)頭指針front指向隊(duì)頭元素的前一個位置，隊(duì)尾指針rear指向隊(duì)尾元素，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)滿的條件是什么？（）A.(rear+1)%MAX_SIZE==frontB.rear==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-120、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何在一個雙向鏈表中刪除指定節(jié)點(diǎn)，并保持鏈表的正確性。2、（本題10分）論述如何使用回溯法解決組合總和問題。3、（本題10分）論述歸并排序的算法思想、步驟和時間復(fù)雜度，以及它在處理大規(guī)模數(shù)據(jù)時的優(yōu)勢。4、（本題10分）深入分析在具有n個元素的有序數(shù)組中，如何進(jìn)行折半插入排序，并比較其與直接