青島黃海學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

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

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若按層序編號，則編號為i的節(jié)點(diǎn)，其雙親節(jié)點(diǎn)的編號為？A.i/2B.(i-1)/2C.2iD.2i+12、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，若節(jié)點(diǎn)編號從1開始，對于編號為i的節(jié)點(diǎn)，其雙親節(jié)點(diǎn)的編號是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不對3、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉平衡樹，若要插入一個(gè)新節(jié)點(diǎn)并保持平衡，以下關(guān)于插入操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、對于一個(gè)具有n個(gè)元素的無序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、對于一個(gè)具有n個(gè)元素的有序數(shù)組，若要查找某個(gè)元素是否存在，以下哪種查找算法效率最高？（）A.順序查找B.二分查找C.分塊查找D.以上算法效率相同6、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向連通圖，利用Prim算法構(gòu)造最小生成樹時(shí)，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)7、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實(shí)現(xiàn)集合的交集運(yùn)算，并具有較低的時(shí)間復(fù)雜度？A.鏈表B.二叉搜索樹C.哈希表D.并查集8、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的存儲？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊(duì)列D.數(shù)組和哈希表9、跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，用于實(shí)現(xiàn)有序集合的快速查找。關(guān)于跳表的特點(diǎn)，以下描述錯(cuò)誤的是（）A.跳表的查找、插入和刪除操作的平均時(shí)間復(fù)雜度為O(logn)B.跳表通過增加索引層次來提高查找效率C.跳表的空間復(fù)雜度比普通鏈表高D.跳表的性能不如二叉搜索樹10、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)11、在一個(gè)長度為n的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)12、在一棵AVL樹中，進(jìn)行插入操作后，可能導(dǎo)致樹失去平衡，此時(shí)需要進(jìn)行的旋轉(zhuǎn)操作最多為（）A.1次B.2次C.logn次D.n次13、以下關(guān)于圖的遍歷算法的描述，哪一項(xiàng)是正確的？（）A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都能訪問到圖中的所有節(jié)點(diǎn)B.深度優(yōu)先遍歷適合用于求解最短路徑問題C.廣度優(yōu)先遍歷的空間復(fù)雜度低于深度優(yōu)先遍歷D.兩種遍歷算法的時(shí)間復(fù)雜度都與圖的邊數(shù)成正比14、在一棵平衡二叉樹中，插入一個(gè)新節(jié)點(diǎn)后可能導(dǎo)致失衡，需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整15、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹B.二叉搜索樹C.堆D.鏈表16、在一個(gè)順序存儲的循環(huán)隊(duì)列中，隊(duì)頭指針front和隊(duì)尾指針rear都指向同一個(gè)位置時(shí)，隊(duì)列的狀態(tài)可能是？（）A.隊(duì)滿B.隊(duì)空C.既不滿也不空D.以上都有可能17、在一個(gè)具有n個(gè)元素的最小堆中，插入一個(gè)新元素后，為了重新調(diào)整為最小堆，最壞情況下需要比較多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)18、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實(shí)現(xiàn)字符串的模式匹配操作？A.二叉樹B.哈希表C.棧D.后綴樹19、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+120、以下關(guān)于線索二叉樹的描述，錯(cuò)誤的是：A.線索二叉樹便于在中序遍歷中查找前驅(qū)和后繼節(jié)點(diǎn)B.線索二叉樹中的線索是指向空指針的指針C.線索二叉樹的存儲空間利用率比普通二叉樹高D.線索二叉樹的構(gòu)建過程非常簡單，不需要復(fù)雜的算法二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述紅黑樹的性質(zhì)和插入、刪除操作時(shí)的顏色調(diào)整規(guī)則，以及其在實(shí)際應(yīng)用中的優(yōu)勢。2、（本題10分）解釋如何在一個(gè)具有n個(gè)頂點(diǎn)的圖中計(jì)算每個(gè)頂點(diǎn)的鄰居頂點(diǎn)數(shù)量。3、（本題10分）闡述后綴數(shù)組與后綴樹的關(guān)系，以及它們在字符串處理中的不同應(yīng)用場景。4、（本題10分）簡述哈希表的哈希沖突解決方法中線性