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

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

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