2016年湖北武漢紡織大學數據結構考研真題

》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2016年湖北武漢紡織大學數據結構考研真題一、填空題（每空3分，共30分）1、_____是數據的基本單位，在計算機程序中通常作為一個整體進行考慮處理。2、數據結構在計算機中的表示(又稱映像)稱為數據的_____。3、算法具有五個重要特性：有窮性、_____、可行性、輸入和輸出。4、以下程序段的時間復雜度為_____。5、如果入棧序列為ABCDE，出棧序列為CBADE，則棧的深度最少為_____。6、樹中度為0的結點稱為_____。7、深度為10的二叉樹至多有_____個結點。8、對一棵完全二叉樹的結點按層序編號，根結點的編號為1，如果編號為n的結點有左孩子，則該左孩子的編號為_____。9、有向完全圖中共有100個頂點，該圖中有_____條弧。10、按排序方法的穩(wěn)定性而言，歸并排序是_____的排序方法。二、解答題（共80分）1、已知某二叉樹的中序遍歷序列為ABCDEFG，后序遍歷序列為GFEDCBA，試寫出該二叉樹的先序遍歷序列。(10分)2、有如下所示的森林，試構造該森林對應的二叉樹。(10分)3、已知電文中字母出現頻率的相應權值為{15，8，3，20，36，25，10}，試構造赫夫曼(Huffman)樹。(10分)4、設待查找的關鍵字序列為{45，24，53，12，37，93}，試構造二叉排序樹。(10分)5、有如下所示的連通網，要求：①采用普里姆(Prim)算法，從頂點C開始，給出構造最小生成樹的過程(10分)②采用克魯斯卡爾(Kruskal)算法，給出構造最小生成樹的過程(10分)6、已知待排序的關鍵字序列為{10，30，50，20，40，60}①采用“直接插入排序”方法，給出按從小到大的順序排序的過程(10分)②采用“簡單選擇排序”方法，給出按從小到大的順序排序的過程(10分)三、算法設計題（每題20分，共40分）1、輸入100個互不相同的分數，去掉最高分和最低分后求平均分。要求寫出完整的程序。2、輸入100個整數到一維數組t中，再輸入1個整數到變量x中。