湖北中醫(yī)藥大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線第1頁(yè)，共3頁(yè)湖北中醫(yī)藥大學(xué)

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