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

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

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

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

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

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