裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)北京聯(lián)合大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》

2023-2024學(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)圖的廣度優(yōu)先遍歷的輔助隊(duì)列？A.循環(huán)隊(duì)列B.鏈隊(duì)列C.優(yōu)先隊(duì)列D.雙端隊(duì)列2、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,53、在一個(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)4、字符串匹配是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重要問(wèn)題，KMP算法是一種高效的字符串匹配算法。關(guān)于KMP算法，以下描述錯(cuò)誤的是（）A.通過(guò)利用已經(jīng)匹配的部分信息來(lái)提高匹配效率B.計(jì)算next數(shù)組是KMP算法的關(guān)鍵步驟C.KMP算法的時(shí)間復(fù)雜度為O(m+n)，其中m和n分別是主串和模式串的長(zhǎng)度D.KMP算法在任何情況下都比暴力匹配算法快5、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，若每個(gè)節(jié)點(diǎn)都有左右子樹(shù)，則該二叉樹(shù)的葉子節(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.兩者之間沒(méi)有固定關(guān)系6、以下關(guān)于字符串匹配的BM算法的描述，哪一項(xiàng)是不正確的？（）A.從模式串的尾部開(kāi)始匹配B.利用了壞字符和好后綴規(guī)則C.在一般情況下比KMP算法效率低D.可以通過(guò)預(yù)處理提高匹配速度7、在一個(gè)用鄰接表表示的無(wú)向圖中，若要?jiǎng)h除一條邊，需要進(jìn)行的操作是？（）A.在兩個(gè)頂點(diǎn)的鄰接表中刪除對(duì)應(yīng)的邊節(jié)點(diǎn)B.只在一個(gè)頂點(diǎn)的鄰接表中刪除對(duì)應(yīng)的邊節(jié)點(diǎn)C.重新構(gòu)建鄰接表D.以上都不對(duì)8、堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，分為大頂堆和小頂堆。對(duì)于大頂堆，以下描述不正確的是（）A.根節(jié)點(diǎn)的值大于其左右子節(jié)點(diǎn)的值B.可以用于實(shí)現(xiàn)優(yōu)先隊(duì)列C.構(gòu)建大頂堆的時(shí)間復(fù)雜度為O(nlogn)D.每次刪除堆頂元素后，需要重新調(diào)整堆以保持大頂堆的性質(zhì)9、在數(shù)據(jù)結(jié)構(gòu)中，伸展樹(shù)（SplayTree）通過(guò)自調(diào)整保持較好的性能，以下關(guān)于伸展樹(shù)的操作，不正確的是（）A.查找操作會(huì)將被查找的節(jié)點(diǎn)旋轉(zhuǎn)到根節(jié)點(diǎn)B.插入操作可能會(huì)引起多次旋轉(zhuǎn)C.伸展樹(shù)的平均性能較好D.伸展樹(shù)的空間復(fù)雜度較高10、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，每個(gè)頂點(diǎn)的度為多少？（）A.n-1B.nC.2(n-1)D.2n11、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，采用鄰接表存儲(chǔ)，其時(shí)間復(fù)雜度為？（）A.O(n+e)B.O(n2)C.O(e2)D.O(ne)12、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若每個(gè)頂點(diǎn)的度都為k，則邊的數(shù)量為多少？（）A.nk/2B.nkC.n(k-1)/2D.n(k-1)13、對(duì)于一個(gè)棧，若入棧序列為1、2、3、4、5，在入棧過(guò)程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.3142514、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無(wú)需調(diào)整15、已知一個(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,516、對(duì)于一個(gè)具有n個(gè)元素的待排序序列，若采用冒泡排序算法進(jìn)行排序，在最壞情況下需要進(jìn)行的比較次數(shù)為？（）A.n(n-1)/2B.nlognC.n-1D.n17、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.518、數(shù)組是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，它具有固定的大小和連續(xù)的存儲(chǔ)位置。以下關(guān)于數(shù)組的說(shuō)法中，錯(cuò)誤的是？（）A.數(shù)組可以通過(guò)下標(biāo)快速訪問(wèn)其中的元素。B.數(shù)組的插入和刪除操作比較耗時(shí)，因?yàn)樾枰苿?dòng)大量的元素。C.數(shù)組可以存儲(chǔ)不同類(lèi)型的數(shù)據(jù)元素。D.數(shù)組的長(zhǎng)度在創(chuàng)建后不能改變。19、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)20、對(duì)于一個(gè)具有n個(gè)元素的冒泡排序，在最壞情況下，需要進(jìn)行多少次比較操作？（）A.n(n-1)/2B.nC.n+1D.n-1二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入分析在具有n個(gè)元素的數(shù)組中，如何實(shí)現(xiàn)計(jì)數(shù)排序，以及其適用的場(chǎng)景和限制條件。2、（本題10分）詳細(xì)論述在利用二叉樹(shù)進(jìn)行排序的過(guò)程中，如何構(gòu)建二叉排序樹(shù)，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題10分）在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，如何找出所有的強(qiáng)連通分量，給出一種有效的算法并分析其時(shí)間復(fù)雜度。4、（本題10分）深入分析在一個(gè)具有n個(gè)元素的順序表中，如何使用排序算法進(jìn)行數(shù)據(jù)篩選，如找出大于某個(gè)值的所有元素。三、設(shè)