華中農業(yè)大學2018考研真題之867-數(shù)據(jù)結構與算法

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

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

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

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

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

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

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