成都師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》2022-2023學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁成都師范學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)文件系統(tǒng)中的目錄結(jié)構(gòu)？（）A.棧B.隊(duì)列C.樹D.哈希表2、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)操作系統(tǒng)中的進(jìn)程調(diào)度？A.隊(duì)列B.棧C.樹D.圖3、在一個(gè)具有n個(gè)元素的二叉排序樹中，查找一個(gè)不存在的元素，其時(shí)間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)4、對(duì)于一個(gè)滿二叉樹，若其高度為h，則其節(jié)點(diǎn)總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-15、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+16、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個(gè)根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹C.所有節(jié)點(diǎn)只有右子樹D.是一棵滿二叉樹7、若要從一個(gè)具有n個(gè)元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個(gè)元素的值都不同，最優(yōu)的算法時(shí)間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)8、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列，隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針front指向隊(duì)頭元素，若隊(duì)列非空，則隊(duì)列中元素的個(gè)數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+19、對(duì)于一個(gè)具有n個(gè)元素的哈希表，負(fù)載因子（loadfactor）為0.7，當(dāng)表中元素?cái)?shù)量超過一定閾值時(shí)需要進(jìn)行擴(kuò)容。以下關(guān)于擴(kuò)容操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(1)B.O(n)C.O(logn)D.O(nlogn)10、對(duì)于一個(gè)采用鏈表存儲(chǔ)的隊(duì)列，若要實(shí)現(xiàn)隊(duì)列的逆置操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)11、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組12、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.1543213、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，若每個(gè)節(jié)點(diǎn)都有左右子樹，則該二叉樹的葉子節(jié)點(diǎn)數(shù)量與度為2的節(jié)點(diǎn)數(shù)量之間存在特定關(guān)系。以下關(guān)于這種關(guān)系的描述，哪一項(xiàng)是正確的？A.葉子節(jié)點(diǎn)數(shù)量等于度為2的節(jié)點(diǎn)數(shù)量B.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量多1C.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量少1D.兩者之間沒有固定關(guān)系14、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在有向圖中，頂點(diǎn)的入度是指指向該頂點(diǎn)的邊的數(shù)量。若要計(jì)算一個(gè)有向圖中所有頂點(diǎn)的入度，哪種算法較為合適？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.以上都可以15、對(duì)于一個(gè)具有n個(gè)元素的無序數(shù)組，若要對(duì)其進(jìn)行排序，以下哪種算法在最壞情況下時(shí)間復(fù)雜度最高？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序16、對(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è)用數(shù)組實(shí)現(xiàn)的最小堆，若要?jiǎng)h除堆頂元素并調(diào)整堆，以下操作正確的是？（）A.將堆尾元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素與堆尾元素交換，然后從堆頂向下調(diào)整C.將堆頂元素刪除，然后重新構(gòu)建堆D.以上都不對(duì)18、排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度是衡量算法性能的重要指標(biāo)，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.時(shí)間復(fù)雜度是指算法執(zhí)行所需的時(shí)間與問題規(guī)模之間的關(guān)系。B.空間復(fù)雜度是指算法執(zhí)行所需的存儲(chǔ)空間與問題規(guī)模之間的關(guān)系。C.不同的排序算法具有不同的時(shí)間復(fù)雜度和空間復(fù)雜度，選擇合適的排序算法可以提高算法的性能。D.排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度越低越好，不需要考慮其他因素。19、哈希表的沖突解決方法有多種，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.開放定址法是一種常用的沖突解決方法，它通過在哈希表中尋找下一個(gè)空閑位置來解決沖突。B.鏈地址法是另一種常用的沖突解決方法，它將沖突的元素存儲(chǔ)在鏈表中。C.再哈希法是通過使用不同的哈希函數(shù)來解決沖突。D.哈希表的沖突解決方法只有開放定址法和鏈地址法兩種。20、在一個(gè)帶權(quán)有向圖中，若以頂點(diǎn)v為源點(diǎn)，利用迪杰斯特拉算法求從v到其他頂點(diǎn)的最短路徑，在算法執(zhí)行過程中，每個(gè)頂點(diǎn)的最短路徑值是如何確定的？（）A.初始時(shí)都設(shè)為無窮大，逐步更新B.初始時(shí)都設(shè)為0，逐步更新C.隨機(jī)設(shè)定，逐步更新D.根據(jù)頂點(diǎn)的權(quán)值設(shè)定，逐步更新二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，如何判斷是否為二部圖。2、（本題10分）解釋如何在一個(gè)二叉搜索樹中實(shí)現(xiàn)迭代器，使得能夠按照中序遍歷的順序訪問節(jié)點(diǎn)，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。3、（本題10分）詳細(xì)論述在具有n個(gè)頂點(diǎn)的無向圖中，如何使用克魯斯卡爾（Kruskal）算法生成最小生成樹，并說明算法的基本思想和關(guān)鍵步驟。4、（本題10分）論述在動(dòng)態(tài)規(guī)劃的問題建模中，如何將實(shí)際問題轉(zhuǎn)化為