黑龍江工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁黑龍江工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫》

2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，則判斷隊滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front2、在二叉樹的序列化和反序列化過程中，以下方法不能保證唯一性的是（）A.先序遍歷序列化B.中序遍歷序列化C.后序遍歷序列化D.層序遍歷序列化3、在一個具有n個元素的單鏈表中，若要在第i個位置（1<=i<=n）插入一個新元素，平均需要遍歷多少個節(jié)點？（）A.i-1B.iC.(i-1)/2D.i/24、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接已選頂點和未選頂點的權(quán)值最小的邊C.任意一條邊D.以上都不對5、在一個具有n個頂點的無向圖中，使用廣度優(yōu)先遍歷算法。以下關(guān)于遍歷過程中使用的輔助隊列的空間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(n^2)6、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則矩陣中非零元素的個數(shù)至少為：A.n-1B.nC.2(n-1)D.2n7、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)字符串的模式匹配操作？A.二叉樹B.哈希表C.棧D.后綴樹8、在一個具有n個元素的最大堆中，插入一個新元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹時，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對10、一棵二叉樹的先序遍歷序列為ABDECFGH，中序遍歷序列為DBEAFCGH，則該二叉樹的后序遍歷序列為（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA11、在一個具有n個元素的無序數(shù)組中，使用冒泡排序進(jìn)行排序。以下關(guān)于冒泡排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)12、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個有向圖，通?？梢允褂媚姆N存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可13、對于一個具有n個節(jié)點的無向連通圖，其生成樹的邊數(shù)為（）A.n-1B.nC.n+1D.2n14、在一個具有n個元素的無序數(shù)組中，使用選擇排序進(jìn)行排序，其空間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)15、對于一個具有n個頂點的無向連通圖，若要判斷其是否存在環(huán)，以下哪種算法的時間復(fù)雜度最低？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.以上算法時間復(fù)雜度相同16、在數(shù)據(jù)結(jié)構(gòu)中，字典樹（Trie樹）常用于字符串的存儲和查找，以下關(guān)于字典樹的特點，不正確的是（）A.對于前綴相同的字符串可以節(jié)省存儲空間B.查找操作的時間復(fù)雜度與字符串長度有關(guān)C.適合用于詞頻統(tǒng)計D.插入和刪除操作比較復(fù)雜17、在數(shù)據(jù)結(jié)構(gòu)中，棧是一種特殊的線性表，遵循先進(jìn)后出的原則。以下關(guān)于棧的操作，錯誤的是（）A.入棧操作將元素添加到棧頂B.出棧操作取出并刪除棧頂元素C.可以在棧的任意位置進(jìn)行插入和刪除操作D.棧頂指針始終指向棧頂元素18、數(shù)據(jù)結(jié)構(gòu)的應(yīng)用非常廣泛，以下關(guān)于它們的應(yīng)用場景的說法中，錯誤的是？（）A.數(shù)組可以用于存儲和處理大量的相同類型的數(shù)據(jù)。B.鏈表可以用于實現(xiàn)動態(tài)數(shù)據(jù)結(jié)構(gòu)，如棧、隊列和鏈表等。C.樹可以用于實現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫索引和表達(dá)式求值等。D.數(shù)據(jù)結(jié)構(gòu)只在計算機科學(xué)領(lǐng)域有應(yīng)用，在其他領(lǐng)域沒有實際價值。19、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結(jié)構(gòu)，則插入和刪除操作的時間復(fù)雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)20、對于一個具有n個元素的無序數(shù)組，若要對其進(jìn)行排序，以下哪種算法在最壞情況下時間復(fù)雜度最高？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)闡述如何在一個帶權(quán)有向圖中計算兩個頂點之間路徑經(jīng)過的頂點數(shù)量。2、（本題10分）詳細(xì)闡述在字符串的加密算法中，如何保證加密的強度和安全性。3、（本題10分）什么是二叉搜索樹的旋轉(zhuǎn)操作？在什么情況下需要進(jìn)行旋轉(zhuǎn)操作？請詳細(xì)說明。4、（本題10分）論述伸展樹在數(shù)據(jù)分布不均勻情況下的性能