山東某大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合歷年考研真題匯編

目錄

2014年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

2015年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

2016年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

2017年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

2018年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

2014年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

山東大學(xué)

二。一四年招收攻讀碩士學(xué)位研究生入學(xué)考試試題

科目代碼851科目名稱計(jì)算機(jī)基礎(chǔ)綜合

（答案必須寫在答卷紙上，寫在試題上無效）

一、數(shù)據(jù)結(jié)構(gòu)部分（共50分）

1.（8分）鐵路進(jìn)行列乍調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成極式結(jié)構(gòu)，如下圖所示?，F(xiàn)有編號(hào)

為1,2,3,4,5,6的6輛列車，順序開入棧式結(jié)構(gòu)的站臺(tái)，則可能的出找序列有多少種？

若進(jìn)站的6輛列車順序?yàn)?23456,那么是否能夠得到435612、32564k154623和135426

的出站序列?如果不能,說明為什么.

2.（10分）分析如下圖所示的AOE網(wǎng)絡(luò)工程，回答問題：a）這個(gè)工程最早可能在什

么時(shí)間結(jié)束？b）確定哪些活動(dòng)是關(guān)鍵活動(dòng).c）畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出加速

哪些活動(dòng)可以使整個(gè)工程提前完成.

3.（12分）分析比較插入排序、簡單選擇排序、快速排序和3并排序四種排序算法

的時(shí)間復(fù)雜度.并說明針對已經(jīng)有序的數(shù)據(jù)集情況，這些排序算法所需要進(jìn)行的實(shí)際關(guān)

鍵字比較次數(shù)的變化.

（（10分）給定采用二義徒存儲(chǔ)的二叉樹，設(shè)計(jì)算法輸出該二叉樹從根節(jié)點(diǎn)到葉子

節(jié)點(diǎn)的最長路徑，并輸出最長路徑長度。

5.（10分）給定采用鄰接表存儲(chǔ)的帶權(quán)無向連通圖G和圖中的一個(gè)頂點(diǎn)v,設(shè)計(jì)算法

I

求解圖G中用1離頂點(diǎn)v最遠(yuǎn)的一個(gè)頂點(diǎn).

二,操作系統(tǒng)部分（共50分）

I.（10分）解釋名詞：高速緩存（Caching）、臨界區(qū)（CriticalSection）

2.（10分）設(shè)有四個(gè)進(jìn)程，到達(dá)就緒隊(duì)列時(shí)間及執(zhí)行時(shí)間如下表所示，若分別采用剝

奪式最短作業(yè)優(yōu)先調(diào)度和三級反饋隊(duì)列調(diào)度（其中-級和二級隊(duì)列采用時(shí)間片調(diào)度，時(shí)

間片分別為2和4,三級隊(duì)列采用FCFS調(diào)度），分別給出各進(jìn)程的調(diào)度次序及平均等待時(shí)

間（給出計(jì)算過程）。

進(jìn)程到達(dá)就緒隊(duì)列時(shí)間執(zhí)行時(shí)間

pi06

P)18

Pi23

p*312

3.（10分）假設(shè)有個(gè)空盤了最多能存放10蘋果或者梨，爸爸每次隨機(jī)選擇一個(gè)率果或

者“個(gè)梨削皮后放到盤子中.兒子喜歡吃蘋果，每次從盤子中取?個(gè)草果并吃掉.并用

countAppleO來統(tǒng)計(jì)吃的蘋果個(gè)數(shù)。女兒喜歡吃梨，每次取?個(gè)梨并吃掉，用couniPearO

來統(tǒng)計(jì)吃掉的梨?zhèn)€數(shù).請用信號(hào)量機(jī)制來描述三者的同步關(guān)系.

4.（10分）文件系統(tǒng)采用混合索引結(jié)構(gòu),設(shè)塊長為512字節(jié),塊號(hào)占2個(gè)字節(jié),文件

控制塊中的直接索引塊號(hào)有M個(gè),另有分別指向?、二級索引的兩個(gè)指針.試問該文件

系統(tǒng)最多能存儲(chǔ)多大的文件？混合索引有什么優(yōu)點(diǎn)？

5.（10分）請說明線程、進(jìn)程和程序的區(qū)別與聯(lián)系。

三'計(jì)算機(jī)組成原理部分（共50分）

1.（5分）DMA控制器的基本組成有哪些?

2.（5分）證明：已知［yH卜，通過連同符號(hào)位一起求反，最低位加1,可以得到卜y］補(bǔ).

3.（10分）CRC碼中的生成多項(xiàng)式應(yīng)當(dāng)滿足什么要求?

4.（10分）什么是中斷屏版？它是怎樣實(shí)現(xiàn)的？

5.（10分）設(shè)計(jì)?個(gè)基本時(shí)序系統(tǒng)，該系統(tǒng)具有4個(gè)節(jié)拍電平，畫出時(shí)序圖，畫出實(shí)

現(xiàn)此系統(tǒng)的邏輯結(jié)構(gòu)圖。

6、（10分）單總線結(jié)構(gòu)上機(jī)框圖如下，存儲(chǔ)器按字編址.指令格式為：

SUB（RS）,RD；源操作數(shù)RS為寄存器間接尋址，目的操作數(shù)RD為寄存器直接

尋址。操作形式為：口的操作數(shù)減源操作數(shù).寫出該指令的執(zhí)行流程（從取指令開始）。

2015年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

山東大學(xué)

二。一五年招收攻讀碩士學(xué)位研究生入學(xué)考試試題

科目代碼851科目名稱計(jì)笄機(jī)基礎(chǔ)綜合

(請將所有試題答案寫在答題紙上，寫在試題上無效)

一、填空題(共6題，每空1分，共10分)

1、［X］原一X1X2X3X4,若耍XA1/2成立，X1X2X3X4應(yīng)滿足的條件是：_.

2、流水線性能主要由、、三項(xiàng)指標(biāo)來衡量.

3、浮點(diǎn)數(shù)的精度生耍取決于的位數(shù)，浮點(diǎn)數(shù)的表示范圍主要取決于

__________的位數(shù)，

4、寄存器一次間接尋址方式中，操作數(shù)在.

5,設(shè)機(jī)器數(shù)字長為32位，欲表示±10萬的卜進(jìn)制數(shù)，在保證數(shù)的技大精度的前

提下，除階符、數(shù)符各取1位外，尾數(shù)取_______________位.

6,某機(jī)器指令字長16位，每個(gè)操作數(shù)的地址碼長5位，設(shè)操作碼長度固定，指令

分等地址、單地址和二地址格式。若零地址指令有T種，二地址指令有M種，則

單地址指令有種；若按變長操作碼考慮，則單加址指令有種.

二、名詞解析(共4題，每題2.5分，共10分)

1、進(jìn)程(Process)

2、死鎖①cadLock)

3、虛擬存儲(chǔ)器(VirtualMemory)

4、設(shè)備驅(qū)動(dòng)程序(DeviceDriver)

三、簡答題（共11題，共90分）

1（5分）、主存用來存儲(chǔ)程序和數(shù)據(jù)，CPU如何區(qū)分從內(nèi)存中讀取出的內(nèi)容是程序還

是數(shù)據(jù)？

2（5分）、設(shè)某計(jì)算機(jī)主存容量為1MB,Cache容最為16KB,每個(gè)字塊有8個(gè)字，每

個(gè)字為32位，果用4路組相聯(lián)映像，問：

（1）Cache,主存地址各字段如何劃分（各需多少位）?

（2）寫出內(nèi)存地址.45986H可能映射成的Cache地址（用16進(jìn)制表示）。

3（5分）、假設(shè)定點(diǎn)小數(shù)具有1位符號(hào)位、4位數(shù)據(jù)位.

已知：A=-巳，B--《，求：IA-B］補(bǔ)并判斷是否溢出.

4（5分）、計(jì)算定點(diǎn)原碼?位乘法［XXY］原？其中X=0.I011,Y=0.1010.寫出計(jì)

算步照

5（10分）、簡要描述進(jìn)程調(diào)度中多級反俄隊(duì)列調(diào)度算法的基本思想，并且說明它是

如何降低系統(tǒng)開銷、減小進(jìn)程平均等待時(shí)間和維護(hù)調(diào)度的公平性的。

6（10分）、在某個(gè)采用頁式存儲(chǔ)管理系統(tǒng)中，某作業(yè)有4個(gè)頁面，被分別裝入到主

存的第3,4.6,8塊中，骸定頁面和頁框的大小均為1024字節(jié),主存容存為10K

字節(jié)。當(dāng)該作業(yè)執(zhí)行到地址為500的一條傳送指令MOVAX,［3100］時(shí)，霜計(jì)算指

令中［31001（十進(jìn)制）對應(yīng)的物理地址，試說明地址變換的過程及得到的物理地址.

7（10分）、為防止某種病毒的傳播，機(jī)場對每個(gè)到來航班中的所有乘客都要進(jìn)行檢

杳，沒有任何感染癥狀者才準(zhǔn)予放行。機(jī)場設(shè)置/一個(gè)容納50人的休息室供乘客

休息并等候醫(yī)生檢瓷，開始的時(shí)候休息室是空的，當(dāng)乘客下飛機(jī)提取自己的行李

后，若休息空中有空座位，則進(jìn)入休息室等候檢設(shè)，否則需要在休息室門口等待.

醫(yī)生每次呼叫一個(gè)在休息室中等待的乘客進(jìn)入檢查室對其進(jìn)行檢查，無乘客時(shí)醫(yī)

生休息.試用信號(hào)量描述乘客及醫(yī)生的活動(dòng).

8（10分）、在一個(gè)多線程的進(jìn)程中，線程之間可以共享如下駢些資源：1）寄存器；

2）堆;3）棧;4）全程變量：5）1/0端口,并說明共享或不能共享的理由。

9(10分)、設(shè)散列表長度為11,散列函數(shù)Hash(k)=k$ll,若輸入序列為122,41,

53,46,30,13,01,67),解決溢出的方法為線性開型尋址散列，

(1)請構(gòu)造該散列表。

(2)搜索元素30和元素67所需要的比較次數(shù)是多少？

(3)給出刪除元素01以后的散列表結(jié)構(gòu).

(4)在線性開型尋址散列表中實(shí)現(xiàn)刪除時(shí)，如果只是把刪除元素所在的桶置空，

會(huì)出現(xiàn)什么問題？給出一種你的解決辦法.

10(10分)、已知以下森林，將其轉(zhuǎn)換成一義樹，給出二叉樹的中序、后序遍歷序

列.

11(10分)、有n個(gè)學(xué)生選課，(i,j)表示學(xué)生i和學(xué)生j選擇了同一門課程.對任

意給出的選課集合S={(1,3),(2,4),(5,7),(7,9),(1,6),…},n個(gè)學(xué)生共選擇了

多少門不同的課程？

四'算法題(共2題，每題10分，共20分)

I、在包含n個(gè)元素的單向鏈表中，找到徒表中倒數(shù)第k個(gè)元素，k<n.要求攵雜性

為O(n).敘述算法思想并給出算法實(shí)現(xiàn).

2、為最大雄MaxHeap類中設(shè)“一個(gè)共享成員函數(shù)ChangeMax(x),將當(dāng)前最大兀索

改為元素x,x的值可以大于或小于當(dāng)前最大元素的值，敘述算法思想并給出算法

實(shí)現(xiàn),給出算法的時(shí)間復(fù)雜性.

五'分析設(shè)計(jì)題（共2題，每題10分，共20分）

L某8位微型機(jī)地址碼為18位，控制信號(hào)為R/次（讀/寫），MREQ（存儲(chǔ)器訪問

信號(hào)）.用2Kx8的ROM芯片（片選信號(hào)為以）形成16Kx8的ROM模塊板,

使用4KX4位的RAM芯片組成32Kx8位RAM模塊板,現(xiàn)在系統(tǒng)配置為ROM模塊板

I個(gè)，起始地址為OQOOOH；RAM模塊板4個(gè),占用連續(xù)高端地址空間，問：

（1）共有多少片RAM?多少片ROM?

（2）求每塊ROM板和最后一塊RAM板的地址范圍（16進(jìn)制表示）。

（3）畫出連線框圖，其它器件自選.RAM模塊板不需要畫出板內(nèi)結(jié)構(gòu).

2、設(shè)?單總線結(jié)構(gòu)主機(jī)框圖如下，ALU可以完成加、減等運(yùn)算功能，存儲(chǔ)器按字

編址。寫出單字轉(zhuǎn)子指令CALLAD（AD為轉(zhuǎn)移地址）和返回指令RET的執(zhí)行時(shí)的指

令流程（從取指令開始）.

Z

2016年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

山東大學(xué)

二。一六年招收攻讀碩士學(xué)位研究生入學(xué)考試試題

科目代碼851科目名稱計(jì)算機(jī)基礎(chǔ)綜合

（請將所有試題答案寫在答題紙匕寫在試題上無效）

一、填空題（共5題，每空1分，共】0分）

1,設(shè)16位浮點(diǎn)數(shù)格式為：1位為符,10位尾數(shù)、1位階符、4位階碼（尾數(shù)在前、

階碼在后）;階碼為移碼，尾數(shù)為補(bǔ)碼,則浮點(diǎn)數(shù)53/128對應(yīng)的規(guī)格化的機(jī)器數(shù)

表示為（用十六進(jìn)制表示）?

2、無條件轉(zhuǎn)移指令屬『類指令，地址碼表示的是0

3、是指CPU回應(yīng)各中斷源請求的優(yōu)先順序，是指CPI

實(shí)際M各中斷源請求處理的優(yōu)先順序,可以通過修改來改變。

4、寄存器A中的值為A7H（補(bǔ)碼衣示），則對A進(jìn)行兩次算術(shù)右移后A中的值是

5、磁盤存儲(chǔ)器上耍技術(shù)指標(biāo)有存儲(chǔ)密發(fā)、

二、名詞解析（共4題，每題2.5分，共10分）

I、線程（Thread）

2、保護(hù)域（ProtectionDomain）

3、設(shè)備.驅(qū)動(dòng)程序（Devicedriver）

1、虛擬地址（VitrualAdress）

三,簡答題（共II題，共90分）

1、（5分）什么是總線？系統(tǒng)總線匕專送的信息通常分為哪兒類？

2、（5分）在某機(jī)耕中浮點(diǎn)數(shù)包括1位階碼符號(hào)、2位階碼數(shù)值位、1位尾數(shù)符號(hào)位、

4位尾數(shù)數(shù)值位。已知:兩浮點(diǎn)數(shù)x=0.1101X210,y=0.1011X201,

求：x+y

3、（5分）中斷方式和DMA方式有何異同點(diǎn)？各應(yīng)用于哪些場合？

4、（5分）試比較組合邏軾控制方式和微程序控制方式的優(yōu)缺點(diǎn).

5、（10分）描述外存空間分配的三種不同方法，并分析比較各自的優(yōu)缺點(diǎn).

6、（10分）進(jìn)程有哪些基本狀態(tài)?畫出進(jìn)程狀態(tài)轉(zhuǎn)換圖，同時(shí)給出轉(zhuǎn)換的饃因.當(dāng)

系統(tǒng)中出現(xiàn)死鎖時(shí)，用戶進(jìn)程可能處于什么狀態(tài)？說明一個(gè)進(jìn)程處「死鎖狀態(tài)和

處于阻塞狀態(tài)之間的區(qū)別.

1、（1（）分）什么是傾簸？顛簸產(chǎn)生的原因是什么?列舉出可以處理頗簸問題的兩種

方式，并說明其工作原理.

8、（10分）設(shè)有一個(gè)可以裝A、B兩種物品的倉庫，其容易無限火，但要求倉庫中A、

B兩種物品的數(shù)量滿足下述不等式:-MWA物品數(shù)量-B物品數(shù)量WN,其中M和

N為正整數(shù)。請用信號(hào)策模擬A、B兩種物品的入庫過程，寫出偽代碼,并說明每

個(gè)信號(hào)量的作用.

9、（10分）已知完全一叉樹的第7層有6個(gè)葉f結(jié)點(diǎn)，則整個(gè)一叉樹的結(jié)點(diǎn)數(shù)最多

是多少?

10、（10分）⑴已知某加權(quán)連通無向圖邊的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于頂點(diǎn)的個(gè)數(shù)，若求其最小

生成樹用哪種修法最好？簡述該算法的基本思想。

⑵下面是某圖的鄰接矩陣，使用在⑴中選擇的算法構(gòu)造該圖的最小生成樹，給

出其構(gòu)造過程.

0120050000

120881000

OC8000003

5OCoo06X

0010006011

0083OC110

Ik（10分）表達(dá)式由數(shù)字、加、減、乘、除和括號(hào)組成，如何計(jì)算表達(dá)式的運(yùn)算

結(jié)果？

四、算法題（共2題，每題10分，共20分）

1、某一叉樹中每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)（如果有的流的值，二叉樹使用

二叉錐表方式存儲(chǔ)，根節(jié)點(diǎn)指針為rooi,左6/節(jié)點(diǎn)指針分別為left和righl。

請?jiān)O(shè)計(jì)算法，找到該二義樹中最小值的節(jié)點(diǎn)，分析舞法復(fù)雜性，

2、采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫?個(gè)判別無向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在

?條長度為％的簡單路徑的穌法。（注：?條路徑為簡單路徑指的是其頂點(diǎn)序列中

不含有重現(xiàn)的頂點(diǎn).）

五'分析設(shè)計(jì)題（共2題，每題10分，共20分）

I、地址總線A15?A0,數(shù)據(jù)總線D7?D0,讀/寫線折,片選低電平有效。存儲(chǔ)器

地址空間為4000H?6FFFH,按字節(jié)編址。其中4000H?5FFFH為ROM區(qū)，選用EPROM

芯片（4KX8位/片）;6000H?6FFFH為RAM區(qū)，選用SRAM芯片（2KXI位/片）。

（1）根據(jù)存儲(chǔ)器容量，EPROM芯片和SRAM芯片各需多少片？

（2）各芯片應(yīng)分期連入哪兒根地址線？

（3）寫出每個(gè)片選信號(hào)的邏輯表達(dá)式。

（4）畫出存儲(chǔ)器框圖，圖中應(yīng)包括存儲(chǔ)芯片,片選邏輯電路，以及地址線、數(shù)據(jù)線、

片選線和讀/寫線的連接.

2、假設(shè)某（以采用微程序控制器設(shè)計(jì)。請從取指開始，按序?qū)懗鐾瓿?條加法指令

U）D?（?為主〃:地址，該加法指令實(shí)現(xiàn)ACC寄存器內(nèi)容加上該內(nèi)存地址的數(shù)

據(jù)，結(jié)果保存到KC寄〃:器）的微操作命令及節(jié)拍安排。（提示：需要從控制存儲(chǔ)

器讀取微指令）

2017年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

山東大學(xué)

二。一七年招收攻讀碩士學(xué)位研究生入學(xué)考試試題

科目代碼851科目名稱計(jì)算機(jī)基礎(chǔ)綜合

(請將所有試題答案寫在答題紙上，寫在試題上無效)

一、填空題(共7題，每空1分，共1()分)

1、計(jì)算機(jī)最主要的三大性能指標(biāo)是、、.

2、設(shè)變址寄存器為X,形式地址為A,則先間址再變址尋址的有效地址為:

3,[XI補(bǔ)=1.XIX2X3X4，若要XW-8成立,XIX2X3X4應(yīng)滿足的條件是:

1、設(shè)16位浮點(diǎn)數(shù)格式為：I位數(shù)符、1()位尾數(shù)、1位階符、4位階碼(尾數(shù)在前、

階碼在后)；階碼、尾數(shù)為補(bǔ)碼，則A987H的其值為(十進(jìn)制).

5、計(jì)算機(jī)中，琲法指令屬于產(chǎn)生的中斷。

6、將一個(gè)8位一進(jìn)制數(shù)X中的最高位語0,其它位保持不變，其方法是

7、RISC指令系統(tǒng)的最大特點(diǎn)是___________少、冏定.

二、名詞解析(共4題，每題2.5分，共10分)

1、臨界區(qū)(CriticalSection)

2、死鎖(Deadlock)

3、顛簸(Thrashing)

4、自陷(Trap)

三、簡答題(共11題，共90分)

1（5分）、上存用來存儲(chǔ)程序和數(shù)據(jù)，CPU如何區(qū)分從內(nèi)存中讀取出的內(nèi)容是程序還

是數(shù)據(jù)?

2（5分）、假設(shè)定點(diǎn)小數(shù)具有1位符號(hào)位、4位數(shù)據(jù)位。

IIn__2

已知：16-16求：IA+B］補(bǔ)并判斷是否溢出。

3（5分）、什么是禁止中斷？它是怎樣實(shí)現(xiàn)的？

4（5分）、計(jì)算定點(diǎn)原碼一位乘法居乂丫］原=?其中X=0.1011,Y=-0.1010,寫出計(jì)

算步驟，

5（10分）、操作系統(tǒng)中和程序執(zhí)行有關(guān)的調(diào)度有作業(yè)調(diào)度、內(nèi)存調(diào)度和進(jìn)程調(diào)度。

請說明這三者的聯(lián)系與區(qū)別。這三種調(diào)度程序中執(zhí)行頻率最高和最低的各是哪一

個(gè)？

6（10分）、一個(gè)理發(fā)師有n張椅子,當(dāng)顧客到來時(shí),如有空椅子,就坐在椅子上,

否則站著等待。當(dāng)有顧客時(shí)，理發(fā)師就理發(fā)，否則他就睡覺。當(dāng)顧客到來時(shí)，如

果理發(fā)師正在睡覺，就喚醒他。理發(fā)師給顧客理完發(fā)后打發(fā)顧客走入，空出椅子,

如〃站著的顧客,就讓其坐下.試用P、V操作描述理發(fā)師和顧客之間的同步關(guān)系.

7（1（）分）、設(shè)月四個(gè)進(jìn)程，它們到達(dá)就緒隊(duì)列的時(shí)間及執(zhí)行時(shí)間如下表，若采用剝

奪式短作業(yè)優(yōu)先，非剝奪式短作業(yè)優(yōu)先及時(shí)間片輪轉(zhuǎn)法（時(shí)間片=2）,分別給出各進(jìn)

程的關(guān)廣各算法的調(diào)度次序及平均等待時(shí)間。

進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間

pl06

P215.5

P323

P434.5

8（10分）、某進(jìn)程有下面的頁面弓I用序列：7,0,1,2,0,3,0,4,23032.假定系統(tǒng)分配

給該進(jìn)程3個(gè)頁框，并且開始時(shí)這三個(gè)貞框都是空的。該系統(tǒng)采用LRU頁而置換

算法，請給出缺頁次數(shù)（給出求解步驟）.

9（8分）、什么是間接尋址？利用它來存儲(chǔ)線性表與鏈?zhǔn)酱鎯?chǔ)相比有何優(yōu)缺點(diǎn)？

10（12分）、已知一個(gè)無向圖的鄰接表如圖所示，要求：

0a

1b工

2

3

4

5

⑴畫出此無向圖;

⑵根據(jù)鄰接表分別寫出用深度優(yōu)先遍歷和廣度優(yōu)先遍歷從頂點(diǎn)a開始遍比該圖所

得到的序列;

⑶畫出從頂點(diǎn)a出發(fā)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹；

⑷若以頂點(diǎn)a為根求得高度最小和高度最大的生成樹，各應(yīng)采用什么方法？

11（10分）、有n個(gè)雜亂無章的正整數(shù),請?jiān)O(shè)計(jì)盡可能快的算法,從中找到第[n/2]

大的整數(shù)。敘述思想，并說明算法復(fù)雜性。

四,算法題（共2題，每題10分，共20分）

1、二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)算法，判斷二叉樹是否為AVI.樹。敘述算法

思想并給出算法實(shí)現(xiàn).

2、設(shè)有n個(gè)村莊之間的鐵路交通圖，若村莊I和J之間有道路則有邊相連，權(quán)為道

路長度.現(xiàn)要在n個(gè)村莊中選一處建醫(yī)院，試編寫算法確定醫(yī)院應(yīng)建在那個(gè)村莊

才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的距離最近.給出算法使用數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)描述。

五、分析設(shè)計(jì)題（共2題，每題10分，共20分）

1、某計(jì)算機(jī)用2Kx8的ROM芯片（片選信號(hào)為最）形成2Kx8的ROM區(qū)域，

起始地址為0000H；用8Kx8的RAM芯片（片選信號(hào)為Z,讀寫信號(hào)為麻）形

成16Kx8的RAM區(qū)域，起始地址為6000H。CPU地址總線為A15-A0,數(shù)據(jù)總線

為D7-I）O,控制信號(hào)為R//（讀/寫），“必。（存儲(chǔ)器訪問信號(hào)）.畫出連線框

圖，其它器件自選。

2、設(shè)?單總線結(jié)構(gòu)上機(jī)框圖如下，ALU可以完成加、減等運(yùn)算功能，存儲(chǔ)器按字編

址.

指令格式為：JMPCAD；

其中C為運(yùn)算器產(chǎn)生的進(jìn)位，山C「l時(shí)程序轉(zhuǎn)移；該指令為兩字指令，轉(zhuǎn)移地址

AD在第二個(gè)字中.寫出該指令執(zhí)行的指令流程（從取指令開始）.

7.

2018年山東大學(xué)851計(jì)算機(jī)基礎(chǔ)綜合考研真題

山東大學(xué)

二0一八年招收攻讀碩士學(xué)位研究生入學(xué)考試試題

科目代碼851科目名稱計(jì)算機(jī)基礎(chǔ)綜合

（答案必須寫在答題紙上，寫在試題上無效）

數(shù)據(jù)結(jié)構(gòu)

一、簡答題（共3題，共26分）

1.（8分）如果只想在一個(gè)有n個(gè)元素的任意序列中得到其中由最小的k（k<=n）個(gè)元

素組成的部分排序序列，那么最好采用什么排序方法？為什么？例如有這樣一個(gè)序列

[57,40,38,11,13,34,48,75,6,19,9,7）,要得到其中由最小的4個(gè)元素組成的部分有序

序列[6,7,9,11）,用所選擇的算法實(shí)現(xiàn)排序過程，描述排序過程，并說明要進(jìn)行多少次

比較.

2.（8分）一個(gè)歸并段是一組元素的有序序列.假設(shè)兩個(gè)歸并段合并成一個(gè)歸并段

的時(shí)間開銷是0（r+s）,其中r與s分別為要合并的兩個(gè)歸并段的長度。通過不斷地合

并兩個(gè)歸并段，可將n個(gè)不同長度的歸并段最終合并成一個(gè)歸并段。設(shè)有n個(gè)歸并段,

其長度分別為11,12，…,加，要求將這n個(gè)歸并段合并成一個(gè)歸并段，描述一個(gè)時(shí)間開銷最

小的實(shí)現(xiàn)方案，給出時(shí)間復(fù)雜性分析。

3.（10分）已知下面是某無向圖的鄰接表，畫出該無向圖，并分別給出從A出發(fā)的

深度優(yōu)先搜索生成樹和廣度優(yōu)先搜索生成樹。

二,算法題（共2題，每小題12分，共24分）

1.（12分）令A(yù)和B都是帶表頭結(jié)點(diǎn)的單鏈表，假定A和B的元素都是按序（遞增

次序）排列的，設(shè)計(jì)算法用以創(chuàng)建一個(gè)新的有序（遞增次序）鏈表C,C表中包含了A和

B的所有元素。要求使用A和B的物理結(jié)點(diǎn)來建立鋅表C,捷表C建立后，A和B變?yōu)榭铡?/p>

⑴描述算法的設(shè)計(jì)思想⑵根據(jù)設(shè)計(jì)思想，給出算法實(shí)現(xiàn),關(guān)健之處請給出注釋.⑶說

明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度.

2.（12分）有