華中農(nóng)業(yè)大學(xué)2018考研真題之867-數(shù)據(jù)結(jié)構(gòu)與算法

1、華中農(nóng)業(yè)大學(xué)2018年碩士研究生入學(xué)考試試科目代碼及名稱：867數(shù)據(jù)結(jié)構(gòu)與算法題紙第1頁(yè)共4頁(yè)注意：所有答案必須寫在答題本上，不得寫在試題紙上，否則無(wú)效。一、名詞解釋（共20分，每題4分）1、算法及算法的特性2、樹(shù)的度及深度3、完全二叉樹(shù)4、索引文件5、強(qiáng)連通性二、選擇題（共30分，每題2分）1、設(shè)核S和隊(duì)列Q的初始狀態(tài)均為空，元素ABCDEFG依次進(jìn)技S。若每個(gè)元素出校后立即進(jìn)入隊(duì)列Q，且7個(gè)元素的出隊(duì)順序是BDCFEAG，則核S的容

2、量至少是：A.1B.2C.3D.42、已知一棵完全二叉樹(shù)的第六層（根為第一層〉有8個(gè)葉子結(jié)點(diǎn)，則完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是：A.39B.52C.111D.1193、下列敘述中不符合m階B樹(shù)定義要求的是：A.根結(jié)點(diǎn)最多有m棵子樹(shù)B.所有葉結(jié)點(diǎn)在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過(guò)指針鏈接4、若無(wú)向圖中含有7個(gè)頂點(diǎn)，貝。保證圖在任何情況下都是連通的，需要的邊數(shù)最少是：A.6B.15C.16D.215、對(duì)一組數(shù)據(jù)（71

3、721931016）進(jìn)行排序，若前三趟排序結(jié)果如下，則采用的排序方法是：第一趟：71721101693第二趟：71710162193第二趟：71016172193A.冒泡排序B.希爾排序C.歸并排序D.基數(shù)排序6、已知一才果有2011個(gè)結(jié)點(diǎn)的樹(shù)，其葉結(jié)點(diǎn)個(gè)數(shù)為116，該樹(shù)對(duì)應(yīng)的二叉樹(shù)中無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)是：A.115B.116C.1895D.18967、已知字符串S為“abaabaabacacaabaabcc“.模式串t為“abaabc

4、”，采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失自己”（s[i]!=t[i］）時(shí)，i=j習(xí)，則下次開(kāi)始匹配時(shí)，i和j的值分別是：A.i=lj=OB.i二5j=OC.i=5j=2D.i=6j=28、用哈希（散列〉方法處理沖突（碰撞〉時(shí)可能出現(xiàn)堆積（聚集）現(xiàn)象，下列選項(xiàng)中，會(huì)受堆積現(xiàn)象直接影響的是：A.存儲(chǔ)效率B.數(shù)列函數(shù)C.裝填（裝載〉因子D.平均查找長(zhǎng)度華中農(nóng)業(yè)大學(xué)2018年碩士研究生入學(xué)考試試科目代碼及名稱：867數(shù)據(jù)結(jié)構(gòu)與算法題紙第3頁(yè)共

5、4頁(yè)32211注意：所有答案必須寫在答題本上，不得寫在試題紙上，否則無(wú)效。2、在雙循環(huán)鏈表中，刪除指針p所指結(jié)點(diǎn)的語(yǔ)句序列是一一一和一一一。3、快速排序是一一一排序改進(jìn)后的結(jié)果。4、求解一個(gè)圖的單源和多源最短路徑的算法分別是一一一和Floyd算法。5、通常稱表示前驅(qū)和后繼的指針叫做一一一’而這種使樹(shù)中結(jié)點(diǎn)的空指針成員存放前驅(qū)或后繼信息的過(guò)程叫做一一一。6、圖的一一一優(yōu)先搜索類似于樹(shù)的層次遍歷。7、設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總

6、數(shù)為一一一。8、希爾排序、快速排序和冒泡排序中一一一是穩(wěn)定的排序方法。9、堆排序的兩個(gè)重要步驟其一是一一一’其二是調(diào)整堆。10、KMP算法中，串＇ababaaababaa’的next數(shù)組為一一一。四、應(yīng)用題（共50分，第16題每題7分，第7題8分）l、給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：EBIDGCAHF中序遍歷序列：EIGDCBHFA(1）試畫出二叉樹(shù)；(2）并給出二叉樹(shù)的后序遍歷序列。2、下圖是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)按照Pr

7、im算法從A節(jié)點(diǎn)出發(fā)構(gòu)造一棵最小生成樹(shù)，并畫出其生成過(guò)程。781210168203、給定一組數(shù)列（101816256916）分別代表字符ABCDEFG出現(xiàn)的頻率，試畫出哈夫曼樹(shù)的構(gòu)造過(guò)程，并給出各字符的編碼值。4、已知長(zhǎng)度為12的表（janfebmaraprmayjunejulyaugsepoctnovdec），請(qǐng)按表中元素順序構(gòu)造一棵二叉平衡樹(shù)，并簡(jiǎn)單的畫出構(gòu)造過(guò)程。其中，無(wú)旋轉(zhuǎn)的調(diào)整可以直接畫在一張圖上，有旋轉(zhuǎn)的調(diào)整請(qǐng)單獨(dú)畫圖并備注