2016年湖北武漢紡織大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題

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