自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁湖北中醫藥大學

《數據結構》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一棵度為4的樹中，若有20個度為4的節點，10個度為3的節點，1個度為2的節點，10個葉子節點，那么這棵樹的總節點數是多少？A.82B.81C.79D.782、以下哪種數據結構可以方便地實現字符串的模式匹配操作？A.二叉樹B.哈希表C.棧D.后綴樹3、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數最多為（）。A.i-1B.n-iC.n-i+1D.n-14、對于一個具有n個元素的希爾排序，其時間復雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是5、以下關于哈夫曼樹的描述，正確的是：A.哈夫曼樹一定是完全二叉樹B.哈夫曼樹中不存在度為1的節點C.哈夫曼樹的帶權路徑長度是唯一的D.哈夫曼樹的構建過程不需要進行節點的比較和交換6、在數據結構中，鏈表的每個節點通常包含數據域和指針域。若要在一個單向鏈表中刪除一個指定節點，以下哪種操作是關鍵步驟？A.修改被刪除節點的前一個節點的指針B.修改被刪除節點的后一個節點的指針C.釋放被刪除節點的內存D.以上都是7、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)8、在一個循環隊列中，若隊頭指針front=5，隊尾指針rear=2，則隊列中的元素個數為：A.7B.3C.2D.不確定9、在一個具有n個頂點的強連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)10、在一棵二叉搜索樹中，刪除一個只有左子樹的節點，其右子樹的節點需要（）A.替換被刪除節點B.保持不動C.全部刪除D.移動到左子樹11、在一個鏈式存儲的線性表中，若要在第i個位置插入一個新元素，需要修改多少個指針？（）A.1B.2C.iD.i+112、以下哪種數據結構常用于實現字符串的最長公共子序列問題？A.二維數組B.棧C.隊列D.樹13、數組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值14、在一個具有n個元素的數組中，進行順序查找，若查找成功，平均比較次數約為？A.n/2B.nC.lognD.115、對于一個具有n個元素的無序數組，若要找出第k小的元素，以下哪種算法較為合適？（）A.冒泡排序B.快速排序C.選擇排序D.堆排序16、以下關于平衡二叉樹旋轉調整的描述，正確的是：A.旋轉調整一定會改變樹的中序遍歷結果B.左旋操作是將右子樹變為根節點，原根節點變為左子節點C.右旋操作是將左子樹變為根節點，原根節點變為右子節點D.平衡二叉樹不需要進行旋轉調整17、在一個具有n個元素的堆中，查找最大元素的時間復雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)18、設有一個字符串S="helloworld"，要計算字符串S的長度（不包括結束符'\0'），以下函數正確的是？（）A.intlength(char*s){intcount=0;while(*s!='\0'){count++;s++;}returncount;}B.intlength(char*s){intcount=0;for(;*s!='\0';s++){count++;}returncount;}C.intlength(char*s){intcount=0;do{count++;s++;}while(*s!='\0');returncount;}D.intlength(char*s){intcount=0;while(s[count]!='\0'){count++;}returncount;}19、在一個具有n個節點的完全二叉樹中，若節點編號從1開始，對于編號為i的節點，其雙親節點的編號是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不對20、對于一個具有n個節點的二叉樹，若每個節點都有左子樹和右子樹，則其葉子節點的個數至少為？A.n/2B.(n+1)/2C.n-1D.logn二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述在一個具有n個頂點的無向圖中，如何使用克魯斯卡爾算法從不同的邊集開始構建最小生成樹，并比較結果。2、（本題10分）闡述后綴數組與后綴樹的關系，以及它們在字符串處理中的不同應用場景。3、（本題10分）數組作為一種數據結構有哪些特點？在什么情況下適合使用數組，什么情況下不適合？4、（本題10分）描述二叉樹的后序遍歷在二叉樹的計算節點高度、平衡檢查等操作中的應用。三、設計題（本大題共2個小題，共20分)1、（