北京師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)北京師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(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)一個(gè)可以快速查找最大值和最小值的數(shù)據(jù)集合？A.鏈表B.棧C.隊(duì)列D.堆2、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖，其生成樹(shù)中邊的條數(shù)為（）。A.nB.n-1C.eD.e-13、排序算法的穩(wěn)定性和時(shí)間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.穩(wěn)定性對(duì)于某些應(yīng)用場(chǎng)景非常重要，如對(duì)具有多個(gè)關(guān)鍵字的記錄進(jìn)行排序時(shí)。B.時(shí)間復(fù)雜度是衡量排序算法效率的重要指標(biāo)，不同的排序算法具有不同的時(shí)間復(fù)雜度。C.可以根據(jù)實(shí)際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時(shí)間復(fù)雜度較低的排序算法。D.排序算法的穩(wěn)定性和時(shí)間復(fù)雜度只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。4、已知一個(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)過(guò)的中間頂點(diǎn)依次為？（）A.2,4B.3,4C.2,3D.3,55、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問(wèn)？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組6、在一個(gè)哈希表中，解決沖突的方法通常有開(kāi)放定址法和鏈地址法。如果要保證查找的平均時(shí)間復(fù)雜度較低，應(yīng)該優(yōu)先選擇哪種方法？（）A.開(kāi)放定址法B.鏈地址法C.兩者效果相同D.取決于哈希函數(shù)7、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？（）A.二叉樹(shù)B.鏈表C.堆D.棧8、對(duì)于一個(gè)具有n個(gè)元素的選擇排序，在最壞情況下，需要進(jìn)行多少次交換操作？（）A.n-1B.nC.n(n-1)/2D.09、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖中，使用Prim算法生成最小生成樹(shù)。若采用鄰接矩陣存儲(chǔ)圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)10、對(duì)于一個(gè)具有n個(gè)元素的小根堆，若要?jiǎng)h除堆頂元素并重新調(diào)整堆，以下關(guān)于操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，則隊(duì)列中的元素個(gè)數(shù)為：A.7B.3C.2D.不確定12、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)文件系統(tǒng)的目錄結(jié)構(gòu)？A.二叉樹(shù)B.多叉樹(shù)C.鏈表D.棧13、若要對(duì)n個(gè)元素進(jìn)行快速排序，在最壞情況下，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)14、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用二分查找查找一個(gè)不存在的元素，其時(shí)間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)15、以下關(guān)于哈希沖突解決方法中二次探測(cè)法的描述，哪一項(xiàng)是不正確的？（）A.可以減少聚集現(xiàn)象B.探測(cè)的位置是連續(xù)的C.可能會(huì)出現(xiàn)找不到空閑位置的情況D.相比線性探測(cè)法，性能更優(yōu)16、若要對(duì)一個(gè)具有n個(gè)元素的數(shù)組進(jìn)行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、在一個(gè)具有n個(gè)元素的單鏈表中，若要在第i個(gè)位置（1<=i<=n）插入一個(gè)新元素，平均需要遍歷多少個(gè)節(jié)點(diǎn)？（）A.i-1B.iC.(i-1)/2D.i/218、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)19、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠方便地實(shí)現(xiàn)集合的交、并、差等運(yùn)算？（）A.二叉樹(shù)B.鏈表C.哈希表D.樹(shù)狀數(shù)組20、對(duì)于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無(wú)數(shù)種二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列，如何實(shí)現(xiàn)循環(huán)隊(duì)列的擴(kuò)容操作，給出算法思路和代碼實(shí)現(xiàn)。2、（本題10分）詳細(xì)解釋在一個(gè)具有n個(gè)元素的順序表中，如何進(jìn)行冒泡排序，并分析其優(yōu)化方法。3、（本題10分）論述在樹(shù)的遍歷中，如何使用Morris遍歷算法優(yōu)化空間復(fù)雜度。4、（本題10分）解釋如何使用桶排序?qū)σ欢ǚ秶鷥?nèi)的整數(shù)進(jìn)行排序，分析其適用條件和時(shí)間復(fù)雜度。三、設(shè)計(jì)題（本大題共