學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁長(zhǎng)安大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、若要對(duì)一棵二叉排序樹進(jìn)行中序遍歷，得到的序列是一個(gè)有序序列，這是因?yàn)槎媾判驑涞亩x具有什么特性？（）A.左子樹的值小于根節(jié)點(diǎn)，右子樹的值大于根節(jié)點(diǎn)B.左子樹和右子樹的深度相同C.每個(gè)節(jié)點(diǎn)的值都不同D.以上都不是2、在一個(gè)有n個(gè)頂點(diǎn)和e條邊的無向圖中，采用鄰接矩陣存儲(chǔ)，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)3、若哈希函數(shù)H(key)=key%7，要將關(guān)鍵字38插入到長(zhǎng)度為7的哈希表中，其存儲(chǔ)位置是：A.3B.5C.6D.04、對(duì)于一個(gè)具有n個(gè)元素的無序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、在一個(gè)循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，隊(duì)列最大容量為MAXSIZE，若當(dāng)前隊(duì)列長(zhǎng)度為n，則判斷隊(duì)滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE6、以下關(guān)于字符串匹配算法的描述，哪一項(xiàng)是不正確的？（）A.BF算法的時(shí)間復(fù)雜度在最壞情況下較高B.KMP算法通過利用已匹配的部分信息來提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時(shí)間復(fù)雜度都與模式串的長(zhǎng)度成正比7、在一個(gè)具有n個(gè)元素的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)的元素個(gè)數(shù)為：A.n-iB.iC.n-i+1D.n-i-18、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB9、以下關(guān)于哈夫曼樹的描述，正確的是：A.哈夫曼樹一定是完全二叉樹B.哈夫曼樹中不存在度為1的節(jié)點(diǎn)C.哈夫曼樹的帶權(quán)路徑長(zhǎng)度是唯一的D.哈夫曼樹的構(gòu)建過程不需要進(jìn)行節(jié)點(diǎn)的比較和交換10、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，若底層從左到右依次編號(hào)，節(jié)點(diǎn)i的左孩子節(jié)點(diǎn)編號(hào)是多少（假設(shè)根節(jié)點(diǎn)編號(hào)為1）？A.2iB.2i+1C.i*2D.以上都不對(duì)11、一個(gè)有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用二分法查找值為90的元素時(shí)，需要比較的次數(shù)是（）。A.1B.2C.3D.412、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若底層從左到右填充，則第i個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的編號(hào)為？A.2iB.2i+1C.i*2D.i*2+113、對(duì)于一個(gè)用鏈表表示的線性表，在表頭插入一個(gè)新元素和在表尾插入一個(gè)新元素，哪個(gè)操作更復(fù)雜？A.表頭插入B.表尾插入C.復(fù)雜度相同D.取決于鏈表長(zhǎng)度14、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的反轉(zhuǎn)是一個(gè)常見的操作，以下關(guān)于鏈表反轉(zhuǎn)的實(shí)現(xiàn)方法，錯(cuò)誤的是（）A.使用三個(gè)指針依次遍歷并調(diào)整節(jié)點(diǎn)的鏈接關(guān)系B.遞歸方式實(shí)現(xiàn)時(shí)不需要額外的輔助空間C.迭代方式的時(shí)間復(fù)雜度為O(n)D.遞歸方式的空間復(fù)雜度比迭代方式低15、在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，每個(gè)頂點(diǎn)的度為多少？（）A.n-1B.nC.2(n-1)D.2n16、已知一個(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,V517、對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要獲取棧中元素的個(gè)數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個(gè)計(jì)數(shù)器C.以上效率相同D.以上都不對(duì)18、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)19、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)20、在一個(gè)具有n個(gè)元素的有序雙向鏈表中，刪除一個(gè)節(jié)點(diǎn)并保持鏈表有序，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述如何在一個(gè)有向圖中判斷是否存在回路，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。2、（本題10分）解釋什么是紅黑樹，說明其性質(zhì)和特點(diǎn)，并闡述如何進(jìn)行插入和刪除操作以維持紅黑樹的性質(zhì)。3、（本題10分）闡述冒泡排序算法的基本思想和優(yōu)化策略，分析其在不同規(guī)模數(shù)據(jù)下的性能表現(xiàn)。4、（本題10分）詳細(xì)闡述在利用二叉樹進(jìn)行層次遍歷的過程中，如何使用隊(duì)列實(shí)現(xiàn)