2018南航考研真題829計算機專業(yè)基礎(chǔ)

1、科目代碼：829科目名稱：計算機專業(yè)基礎(chǔ)第1頁共5頁南京航空航天大學南京航空航天大學2012018年碩士研究生入學考試初試試題年碩士研究生入學考試初試試題（A卷）科目代碼:829滿分:150分科目名稱:計算機專業(yè)基礎(chǔ)注意:①認真閱讀答題紙上的注意事項；認真閱讀答題紙上的注意事項；②所有答案必須寫在所有答案必須寫在答題紙答題紙上，寫在本試題紙或草稿紙上均無上，寫在本試題紙或草稿紙上均無效；效；③本試題紙須隨答題紙一起裝入試題袋中交回！本試

2、題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)部分（數(shù)據(jù)結(jié)構(gòu)部分（5050分）分）1（10分）給定n個村莊之間的交通圖，邊上的值表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院的路程最短？試選擇或構(gòu)造一種適當?shù)臄?shù)據(jù)結(jié)構(gòu)并設(shè)計一個算法，并應用該算法解答下圖所示的實例，給出算法執(zhí)行過程示意圖。2（10分）詳細解釋哈希表的工作原理。以此為例，將關(guān)鍵字序列（51，83，43，1

3、5，62，59，74，61）存儲在長度為10的哈希表中，使用哈希函數(shù)H(key)=Key%10，并采用鏈地址法解決沖突，畫出哈希表示意圖。3（10分）設(shè)有一批需實時處理的數(shù)據(jù)元素組成集合S，實時處理開始后，每隔一秒鐘收到一個新的數(shù)據(jù)元素加入S?，F(xiàn)要求在每次接收一個新元素之前，找出S中現(xiàn)有的最小元素并將其輸出（從S中刪除）。試選擇或構(gòu)造一種適當?shù)臄?shù)據(jù)結(jié)構(gòu)并設(shè)計一個算法，盡可能高效地完成上述任務。例如：S=(5931291878264810

4、6535)，新接受的數(shù)據(jù)為39，12，46….。以此為例說明算法執(zhí)行過程示意圖。4（10分）設(shè)一個帶頭結(jié)點的單鏈表L，數(shù)據(jù)元素為整數(shù)，其中大部分為正數(shù)，少數(shù)為負數(shù)，編寫函數(shù)，采用高效的算法調(diào)整鏈表，實現(xiàn)將負數(shù)結(jié)點移到鏈表尾部，并返回調(diào)整后鏈表中的第一個負數(shù)結(jié)點位置。先給出算法思想，再寫相應代碼。5.（10分）設(shè)二叉樹T，用二叉鏈表結(jié)構(gòu)存儲，元素值為整數(shù)且互不相同。編寫非遞歸函數(shù)，對給定的2個整數(shù)，若2個都不是T的元素，輸出2；若1個不是

5、T的元素，輸出1；若2個都是T的元素，輸出兩者所在的層數(shù)的間隔數(shù)。要求先給出算法思想，再寫代碼。V3V2V4V1346102科目代碼：829科目名稱：計算機專業(yè)基礎(chǔ)第3頁共5頁1）（2分）將上述指令轉(zhuǎn)換為2進制表示的32位機器碼，其中操作碼對應的機器編碼可以相同位數(shù)的號代替，請按照MIPS32指令的格式區(qū)分各部分以方便查閱。2）（10分）除非特別聲明，請以10進制方式填寫下表中執(zhí)行該指令時的數(shù)據(jù)通路信號值和控制信號值，若值未知或不需要，