河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁河北地質(zhì)大學(xué)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)元素的冒泡排序，若元素基本有序，其時(shí)間復(fù)雜度接近？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)2、在二叉樹的序列化和反序列化過程中，以下方法不能保證唯一性的是（）A.先序遍歷序列化B.中序遍歷序列化C.后序遍歷序列化D.層序遍歷序列化3、若一個(gè)圖的鄰接矩陣對(duì)角線以下（不包括對(duì)角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖4、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖中，采用鄰接表存儲(chǔ)，求頂點(diǎn)的入度的時(shí)間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)5、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，有鄰接矩陣和鄰接表兩種存儲(chǔ)方式。對(duì)于一個(gè)稀疏圖，以下說法正確的是（）A.鄰接矩陣比鄰接表更節(jié)省存儲(chǔ)空間B.鄰接表更適合用于存儲(chǔ)和遍歷C.兩種存儲(chǔ)方式的時(shí)間復(fù)雜度相同D.稀疏圖的邊數(shù)很少，節(jié)點(diǎn)數(shù)很多6、在一個(gè)有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.47、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的無向連通圖，其生成樹的邊數(shù)為（）A.n-1B.nC.n+1D.2n8、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)9、在一個(gè)具有n個(gè)元素的單鏈表中，若要在第i個(gè)位置（1<=i<=n）插入一個(gè)新元素，平均需要遍歷多少個(gè)節(jié)點(diǎn)？（）A.i-1B.iC.(i-1)/2D.i/210、以下關(guān)于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項(xiàng)是正確的？（）A.深度優(yōu)先搜索使用隊(duì)列實(shí)現(xiàn)B.廣度優(yōu)先搜索使用棧實(shí)現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑11、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以12、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，其葉子節(jié)點(diǎn)的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-113、哈希表的性能取決于哈希函數(shù)的設(shè)計(jì)和沖突解決方法的選擇，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來決定。C.哈希表的性能可以通過調(diào)整哈希函數(shù)和沖突解決方法來優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計(jì)，與沖突解決方法無關(guān)。14、AVL樹是一種高度平衡的二叉搜索樹，以下關(guān)于AVL樹的旋轉(zhuǎn)操作，描述不正確的是（）A.旋轉(zhuǎn)操作用于保持樹的平衡B.包括單旋轉(zhuǎn)和雙旋轉(zhuǎn)兩種類型C.旋轉(zhuǎn)操作不會(huì)改變二叉搜索樹的性質(zhì)D.每次插入或刪除節(jié)點(diǎn)都需要進(jìn)行旋轉(zhuǎn)操作15、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，使用克魯斯卡爾算法構(gòu)造最小生成樹時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對(duì)16、圖的存儲(chǔ)方式和遍歷方式對(duì)圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.鄰接矩陣適合存儲(chǔ)稠密圖，查找邊的時(shí)間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲(chǔ)稀疏圖，插入邊和刪除邊的時(shí)間復(fù)雜度為O(1)，但查找邊的時(shí)間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時(shí)間復(fù)雜度都為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。D.圖的存儲(chǔ)方式和遍歷方式一旦確定，就不能再改變，否則會(huì)影響圖的操作效率。17、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front18、對(duì)于一個(gè)具有n個(gè)元素的堆排序，其空間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要在棧頂插入一個(gè)元素，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)20、已知一個(gè)圖的鄰接表如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行廣度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V5二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入解釋在具有n個(gè)頂點(diǎn)的無向圖中，如何使用普里姆（Prim）算法求解最小生成樹，并說明算法的基本思想和關(guān)鍵步驟。2、（本題10分）詳細(xì)說明在字符串操作中，如何實(shí)現(xiàn)字符串的加密和解密。3、（本題10分）在圖的存儲(chǔ)中，如何處理圖的自環(huán)和重邊？有哪些影響？4、（本題10分）詳細(xì)闡述圖的拓?fù)渑判虻母拍詈蛻?yīng)用場(chǎng)景，給出拓?fù)渑判虻乃惴ú襟E，并分析其時(shí)間復(fù)雜