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

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

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