北京郵電大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法導(dǎo)論》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁北京郵電大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法導(dǎo)論》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，則判斷隊(duì)滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front2、在一棵完全二叉樹中，若節(jié)點(diǎn)個(gè)數(shù)為n，那么其葉子節(jié)點(diǎn)的個(gè)數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/33、已知一個(gè)有序表為{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值為35的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.44、在一個(gè)具有n個(gè)元素的順序表中，若要將其逆置，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若存在從頂點(diǎn)i到頂點(diǎn)j的路徑，同時(shí)也存在從頂點(diǎn)j到頂點(diǎn)i的路徑，則該圖被稱為？（）A.強(qiáng)連通圖B.弱連通圖C.連通圖D.非連通圖6、在一個(gè)具有n個(gè)頂點(diǎn)的圖中，若存在回路，則深度優(yōu)先遍歷可能會出現(xiàn)什么情況？（）A.訪問某些頂點(diǎn)多次B.無法完成遍歷C.結(jié)果不正確D.以上都有可能7、對于一個(gè)有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點(diǎn)i到頂點(diǎn)j的邊的時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)8、以下關(guān)于字符串匹配算法的描述，哪一項(xiàng)是不正確的？（）A.BF算法的時(shí)間復(fù)雜度在最壞情況下較高B.KMP算法通過利用已匹配的部分信息來提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時(shí)間復(fù)雜度都與模式串的長度成正比9、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的反轉(zhuǎn)操作？A.棧B.隊(duì)列C.鏈表D.樹10、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無需調(diào)整11、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，通過哈希函數(shù)將關(guān)鍵字映射到存儲位置。關(guān)于哈希沖突的解決方法，錯誤的是（）A.開放定址法通過尋找空閑位置來解決沖突B.鏈地址法將沖突的元素存儲在鏈表中C.再哈希法通過更換哈希函數(shù)來解決沖突D.哈希沖突無法避免，且對查找效率沒有影響12、若對一棵二叉搜索樹進(jìn)行先序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空13、一棵完全二叉樹的第6層（根為第1層）有8個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹的節(jié)點(diǎn)總數(shù)最多為（）。A.39B.56C.111D.11914、對于一個(gè)具有n個(gè)頂點(diǎn)和m條邊的有向圖，使用鄰接表存儲，其入度和出度的計(jì)算時(shí)間復(fù)雜度分別為（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)15、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，采用中序遍歷將其轉(zhuǎn)換為一個(gè)有序的單鏈表。以下關(guān)于轉(zhuǎn)換過程的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)16、對于一個(gè)具有n個(gè)元素的直接插入排序，在最好情況下，需要進(jìn)行多少次比較操作？（）A.n-1B.nC.n(n-1)/2D.017、設(shè)有一個(gè)棧S和一個(gè)隊(duì)列Q，初始時(shí)棧為空，隊(duì)列為{1,2,3,4,5}。經(jīng)過一系列入棧和出棧、入隊(duì)和出隊(duì)操作后，棧頂元素為3，此時(shí)隊(duì)列的頭元素為？（）A.1B.2C.4D.518、在一棵二叉搜索樹中，刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點(diǎn)B.用右子樹的最小值替代該節(jié)點(diǎn)C.隨機(jī)選擇左子樹或右子樹的節(jié)點(diǎn)替代D.不進(jìn)行替代，直接刪除19、已知一個(gè)帶權(quán)無向圖的鄰接矩陣表示，若要計(jì)算圖中兩個(gè)頂點(diǎn)之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法20、在一個(gè)帶權(quán)的有向圖中，使用迪杰斯特拉算法求從源點(diǎn)到其他頂點(diǎn)的最短路徑，每次選擇的頂點(diǎn)是？（）A.距離源點(diǎn)最近的頂點(diǎn)B.距離源點(diǎn)最遠(yuǎn)的頂點(diǎn)C.未確定最短路徑的頂點(diǎn)中權(quán)值最小的頂點(diǎn)D.未確定最短路徑的頂點(diǎn)中權(quán)值最大的頂點(diǎn)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述如何使用A*算法在圖中進(jìn)行尋路，解釋其啟發(fā)函數(shù)的作用和設(shè)計(jì)原則，并分析其性能優(yōu)勢。2、（本題10分）描述二叉樹的中序遍歷在二叉搜索樹中的特殊意義。3、（本題10分）深入分析在具有n個(gè)元素的數(shù)組中，如何實(shí)現(xiàn)快速選擇算法，用于查找第k小的元素，并給出時(shí)間復(fù)雜度的分析。4、（本題10分）詳細(xì)說明在樹的應(yīng)用中，如何使用二叉樹實(shí)現(xiàn)表達(dá)式求值或存儲文件系統(tǒng)