考研計算機專業(yè)基礎綜合（綜合應用

題）模擬試卷3（共9套）

（共180題）

考研計算機專業(yè)基礎綜合（綜合應用

題）模擬試卷第1套

一、綜合應用題（本題共20題，每題，.0分，共20

分。）

1、假設以I和o分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧

的操作序列可表示為僅由I和o組成的序列，稱可以操作的序列為合法序列，否則

稱為非法序列。（1）卜面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIO

C.IIIOIOIOD.11100100（2）通過對（1）的分析，寫出一個算法，判定所給的操作

序列是否合法。若合法，返回true,否則返回false（假定被判定的操作序列已存入

一維數(shù)組中）。

標準答案：（1）A和D是合法序列，B和C是非法序列。（2）設被判定的操作序列已

存入一維數(shù)組A中。intJudge（charA[]）｛//判斷字符數(shù)組A中的輸入/輸出序列

是否是合法序列。如是，返回true,//否則返回falseinti=0；//i為下標int

j=k=O;//j和k分別為I和字母0的個數(shù)while（A[i]!=）

O'）｛switch（A[i]）｛cascT：j++；break；//入棧次數(shù)增1casc'O'；k++；if（k>

j）｛printf（"序列非法\n"）；exit（O）；｝｝i++i//不論A|i]是T或O,指針i均后移｝

if（j!=k）｛printf（"序列非法\n"）；retum（false）；｝else｛printf（"序列合法\n"）；

return（true）：｝｝｝提示：在入棧出棧序歹U（即由T和U組成的字符串）的任一位置，

入棧次數(shù)（T的個數(shù)）都必須大于等于出棧次數(shù)（即'0'的個數(shù)），否則視作非法序列，

立即給出信息，退出算法。整個序列（即讀到字符數(shù)組中字符串的結束標記'

入棧次數(shù)必須等于出棧次數(shù)（題目中要求棧的初態(tài)和終態(tài)都為空），否則視為非法序

列。

知識點解析：暫無解析

2、已有鄰接表表示的有向圖，請編程判斷從第u頂點至第v頂點是否有簡單路

徑，若有則打印出該路徑上的頂點。

標準答案：voidAllpath(AdjListg,vertypeu,Vertypev){//求有向圖g中頂點u

到頂點v的所有簡*.路徑，初始調用形氐imtop=0,s[]；s[++top]=u；

visitcd[u]=l；while(top>0||P){p=g[s[top]].firstarc；//第一個鄰接點

while(p!=null&&visited|p~^>adjvex|==l)p=p—^>next；//下一個訪問鄰接點表

if(p==null)top--；//退棧else{i=p—*>adjvex；//取鄰接點(編號)

if(i==v){//找到從u到V的一條簡單路徑，輸出for(k=I；k<=top：

k++)printf(''%3d",s[k])；printfT%3d\n”,V)；}//ifelse{visited[i]=l；

s[++top]=i；}//else深度優(yōu)先遍歷}//else}//while}

知識點解析：暫無解析

3、基帶信號與寬帶信號的傳輸備有什么特點？

標準答案：基帶信號將數(shù)字1和0直接用兩種不同的電壓表示，然后送到線路上傳

輸。寬帶信號是將基帶信號調制后形成的頻分復用模擬信號。采用基帶信號傳輸，

一條電纜只能傳輸一路數(shù)字信號，而采用寬帶信號傳輸，一條電纜中可同時傳送多

路數(shù)字信號，提高了線路的利用率。

知識點解析：暫無解析

4、如下圖所示，有一個移動主機，原來的IP地址是160.80.40.20/16,為了

移動到其他網絡，它將160.80.40.26設置為了本地代理.之后它移動到了

179.56.0.0/16的網絡中，設置了179.56.0.1為外部代理，并且獲得了新

的IP地址179.56.78.69o請問：(1)如果這時候該主機和其他主機通信，對端

需要把數(shù)據發(fā)給什么地址？(2)當一個160.80.40.20到達160.80.0.0/16網

絡后，會有主機響應該ARP請求嗎？(3)本地代理需要將發(fā)送給移動主機的分組發(fā)

送到哪個地址？一

標準答案：本題主要考查移動IP的知識點。移動IP技術的基本通信流程如下：

(1)遠程通信實體通過標準IP路由機制，向移動結點發(fā)出一個IP數(shù)據包；(2)移動

結點的歸屬代理截獲該數(shù)據包，將該包的目標地址與自己移動綁定表中移動結點的

歸屬地址比較，若與其中任一地址相同，繼續(xù)下一步，否則丟棄：(3)歸屬代理用

封裝機制將該數(shù)據包封裝，采用隧道操作發(fā)給移動結點的轉發(fā)地址：（4）移動結點

的拜訪地代理收到該包后，去其包封裝，采用空中信道發(fā)給移動結點；（5）移動結

點收到數(shù)據后，用標準IP路由機制與遠程通信實體建立連接。①移動IP技術是

移動結點以固定的網絡IP地址，實現(xiàn)跨越不同網段的漫游功能，并保證了基于網

絡IP的網絡權限在漫游過程中不發(fā)生任何改變。設立移動IP的目的就是為了在任

何地方都能夠使用同樣的IP,所以通信對端還是使用160.80.40.20和主機通

信。②當一個160.80.40.20分組到達網絡后，本地代理160.80.40.26將

會響應查詢160.80.40.20的ARP分組。③本地代理在接收到需要提交給

160.80.40.20的1P分組后，將該分組采用隧道的方式發(fā)送給主機的新IP地址

179.56.78.69o

知識點解析：暫無解析

5、如圖所示，某計算機的內部數(shù)據通路如下：完成如下要求:

A總線

B總線

⑴數(shù)據指令STARi，（R＞，其指令的功能是將寄存器Ri的內容傳送至（R》中存儲

的內存地址所代表的存儲單元中。請畫出指令周期流程圖。（2）標出各微操作信號

序列。

PC-ARPC^CpAR

M-DRR，W=1（讀）

取指DR7RDl，Gi，R

執(zhí)

行

指

令

一

*

標準答案：見流程圖。

知識點解析：暫無解析

6、接口按數(shù)據傳輸寬度分為哪幾類?按操作的節(jié)拍分為哪幾類?按信息傳送的控制

方式分為哪幾類？

標準答案：（1）按數(shù)據傳輸寬度分類①并行接口：主機與接口、接口與外部設冬之

間都是對1字節(jié)或幾字節(jié)各位同時進行處理的方式完成信息傳遞工作的，即每次傳

送1字節(jié)或兒字節(jié)的全部代碼。因此并行接口的數(shù)據通路是按字或字節(jié)設置的。一

般當I/0設備本身是按照并行方式工作，并且主機與外部設備之間距離較近時，

選用并行接口。②串行接口：接口與主機之間完全按照并行的方式傳遞數(shù)據。但

接口與I/。設備之間有時是按照每次傳送一位的方式實現(xiàn)數(shù)據傳遞，即每字節(jié)是

按位依次傳送的。因此要求串行接口必須設置具有移位功能的數(shù)據緩沖器，以實現(xiàn)

數(shù)據格式的串一并轉換。同時還要求接口中使用同步定時脈沖信號來控制信息的傳

遞速率，以保證信號能夠在接口與外部設備之間實現(xiàn)同步串行傳送。一般的低速I

/0設備、計算機網絡的遠程終端設備以及通信系統(tǒng)的終端采用串行接口。（2）按

操作的節(jié)拍分類①同步接口：同步接口的數(shù)據傳送是按照CPU的控制節(jié)拍進行

的。無論是CPU與接口之間，還是接口與外部設備之間的數(shù)據交換都由CPU的控

制節(jié)拍來協(xié)調，與CPU的節(jié)拍同步。這種接口的控制簡單，但其操作時間必須與

CPU的時鐘同步。②異步接口：異步接口不由CPU的時鐘控制。CPU與I/O設

備之間的信息交換采用應答方式。連接在總線上的任何兩個設備均可以交換信息，

在交換信息的兩個設備中，負責控制和支配總線控制權的設備稱為主設備，與主設

備交換信息的設備稱為從設備。如將CPu看作主設備，將IYO設備看作從設各。

在信息交換時，主設備發(fā)出交換信息的“請求”信號，經過接口傳送給從設備，從設

備完成主設備指定的操蚱后向主設備發(fā)出“回答”信號。按這種一問一答的方式分步

完成信息的交換。其中從“請求”到“回答”之間的時間是由完成操作所需的實際工作

時間決定的，與CPU的時鐘節(jié)拍無關。(3)按信息傳送的控制方式分類根據接口

對信息傳送的控制方式，可將接口分為：有程序控制的輸入/輸出接口；程序中

斷輸入/輸出接口；直接存儲器存取(DMA)接口。

知識點解析：暫無解析

7、設計一個算法，判斷一個算術表達式中的括號是否配對。算術表達式保存在帶

頭結點的單循環(huán)鏈表中，每個結點有兩個域：ch和link,其中ch域為字符類型。

標準答案：表達式中的話號有以下三對：‘(‘、')'、‘['、小使用棧，當為

左括號時入棧，右括號時，若棧頂是其對應的左括號，則退棧，若不是其對應的左

括號，則結論為括號不配對。當表達式結束，若棧為空，則結論表達式括號配對：

否則，結論表達式括號不配對。intMatch(LinkedListla){//算術表達式存儲在以

la為頭結點的單循環(huán)鏈表中，本算法判斷括號是否正確配對charS|]；//s為字

符棧，容量足夠大P=la—>link；//p為工作指針，指向待處理結點Stack

Init(S)；//初始化棧Swhile(P!=la){//循環(huán)到頭結點為止switch(p

一>ch){caseX*：push(s,p一,ch)；break；case')'：

if(StackEmpty(s)HStackGetTop⑸!='('){printf("括號不配對\n'')；retum(O)：)else

pop(S)；break；casc'['：push(s,p->ch)；break；casc'[\if(StackEmpty⑸||

StackGetTop(s)!=l['){printR”括號不配對\n'')；return(O)；)elsepop(S)；breaki

case'{'：push(s,p->ch)：break；case'}'：

if(StackEmpty(s)||StackGctTop(s)!=,{'}{printf("括號不配對\n")：rcturn(O)；}else

pop(S)：break；}P=p->link：//后移指針}//whileif(StackEmpty(S)){primff'

括號配對\n")：return⑴：}else{primf("括號不配對\n")；return(O)：)}

知識點解析：暫無解析

8、假定用兩個一維數(shù)組UN]和R[N]作為有N個結點1,2,…，N的二叉樹的存

儲結構°“口和R[i]分別指示結點i的左兒子和右兒子：L[i]=O(R[i]=O)表示i的左

(右)兒子為空。試寫一個算法，由L和R建立一個一維數(shù)組T|n|,使T[i]存放結點

i的父親；然后再寫一個判別結點U是否為結點V的后代的算法。

標準答案：由指示結點i左兒子和右兒子的兩個一維數(shù)組L[i]和R[i],很容易建立

指示結點i的雙親的一維數(shù)組巾|,根據T數(shù)組，判斷結點U是否是結點V后代的

算法轉為判斷結點V是否是結點U的祖先的問題。intGeneration(intU,V,N,

L[],R[],T[]){//L口和R[]是含有N個元素且指示二義樹結點i左兒子和右兒子

的一維數(shù)組//本算法據此建立結點i的雙親數(shù)組T,并判斷結點U是否是結點V

的后代inti：for(i=l：i<=N；i++)T[i]=0：〃T數(shù)組初始化for(i=l；i<=N：i++)//

根據1和區(qū)填寫丁[我14口后0)11印1]一；//若結點i的左子女是L,則結點L的

雙親是結點ifor(i=l；i<=N；i++)if(R|i]!=O)T[R[i]]=i；//i的右子女是R,則R

的雙親是iintparent=U：//判斷U是否是V的后代

while(parent!=V&&parent!=O)parent=T[parent]；if(parent==V){printf(”結點U是結點

V的后代”)；retum(l)；}else{printf(“結點u不是結點V的后代”)；return(O)；}}/

/結束Generation

知識點解析：暫無解析

9、判斷下列序列是否為堆，若不是堆，則把它們調整為堆。(1)(100,85,95,

75,80,60,82,40,20,10,65)(2)(100,95,85,82,80,75,65,60,4),

20,10)(3)(100,85,40,75,80,60,65,95,82,10,20)(4)(10,20,40,

60,65,75,80,82,85,95,100)

標準答案：依據堆定義可知：序列(1)、(2)、(4)是堆，(3)不是堆，從而可對其調整

使之成為大根堆(100,95,65,85,80,60,40,75,82,10,20)。

知識點解析：暫無解析

10、下圖所示的處理機邏輯框圖中，有兩條獨立的總線和兩個獨立的存儲器。已知

指令存儲器IM最大容量為16384字(字長18位)，數(shù)據存儲器DM最大容量是65

536字(字長16位)。各寄存器均有“打入”(Rin)和“送出”(Rout)控制命令，但圖中未

標出。

BUS,

BUS2

設處理機格式為：

171090

OPX

指令可寫為“ADDX(R。"。其功能是(AC())+((Ri)+X)-AC1，其中((Ri)+X)部分通過

尋址方式指向數(shù)據存儲器，現(xiàn)取R為試畫出ADD指令從取指令開始到執(zhí)行

結束的操作審列圖，寫明基本操作步驟和相應的微操作控制信號o

標準答案：加法指令“ADDX(Ri)”是一條隱含指令，其中一個操作數(shù)來自ACo，另

一個操作數(shù)在數(shù)據存儲器中，地址由通用寄存器的內容(R。加上指令格式中的X量

值決定，可認為這是一種變址尋址。因此，指令周期的操作流程圖如下圖所示。相

應的微操作控制信號列在框圖外。

流程圖內容為：

(PC-IAR.PC^.IARJ

(IM-1DR,讀IM,lDR.n)

(IDRT1R,IDRM,IR,,)

(R(+1R(X)->ACJ

(R-,X.3,+AC”.)

(ACLDAR,AC")AR.J

(DM,DDR.)

(ACo+DDR?AC,,AJ(BUS,)+DDR?,(BUS2),ACIW)

11、何謂靜態(tài)分配?何謂動態(tài)分配？

標準答案：（1）靜態(tài)分配：在裝配程序把目標模塊進行連接裝入時確定它們在主存

中的位置。這種靜態(tài)存儲分配方式要求在一個作業(yè)裝入時必須分配所需的全部存儲

空間；如果沒有足夠的存儲空間，就不能裝入該作業(yè)。（2）動態(tài)分配：同靜態(tài)分配

時一樣，作業(yè)在存儲空間的位置也是在裝入時確定的，但在其執(zhí)行過程中可根據需

要申請附加的存儲空間，而且一個作業(yè)已占用的部分存儲空間不再需要時可以要求

歸還給系統(tǒng)。

知識點解析：暫無解析

12、為什么要引入虛擬存儲器的概念？

標準答案：引入虛擬存儲器是為了滿足用戶對存儲器容量的巨大需求而虛構的一個

非常大的地址空間，從而使用戶在編程序時無須擔心存儲器容量之不足。

知識點解析：暫無解析

13、分區(qū)分配有哪幾種。試比較各種分區(qū)分配的優(yōu)缺點。

標準答案：（1）單一連續(xù)分區(qū)管理原理優(yōu)點：方法簡單，易于實現(xiàn)。缺點：僅適用

于單道程序，因此不能使處理機和主存得到充分利用。（2）固定式分區(qū)管理主要優(yōu)

點是簡單易行，特別是對于作業(yè)大小可以事先知道的專用系統(tǒng)，這種方法比較實

用。（3）可變分區(qū)存儲管理優(yōu)點：消除固定式分區(qū)分配造成的“內零頭”。缺點：主

存中經常可能出現(xiàn)大量的不能充分利用的小空閑區(qū)。（4）可重定位分區(qū)存儲管理優(yōu)

點：減少碎片，使存儲器的利用率提高。缺點：需要硬件支持，提高了計算機成

本，同時拼接也將降低計算機的處理速度。

知識點解析：暫無解析

14、一個UNIX/Linux文件，如果一個盤塊的大小為1KB,每個盤塊占4B,那

么，若進程欲訪問偏移為263168B處的數(shù)據，需經過幾次間接尋址？

標準答案：UNIX/Linux文件系統(tǒng)中，直接尋址為10塊，一次間接尋址為256

塊，二次間接尋址為2562塊，三次間接尋址為2563塊。偏移為263168B的邏輯

塊號是263168口024=257。塊內偏移量=263168—257x1024=0。由于10V257V

256+10,故263168B在一次間接尋址內。

知識點解析：暫無解析

15、信道速率為4kb/s,采用停止一等待協(xié)議，傳播時延tp=20ms,確認幀長度

和處理時間均可忽略。問幀長為多少才能使信道利用率達到至少50%?

標準答案：根據下圖所示停止一等待協(xié)議中的時間關系：

傳播時延％

處理時間J

兩個成功發(fā)送的

數(shù)據幀之間確認幀發(fā)送時間。

的會小時間間隔

傳播時廷9

處理時間J

時間

停止一等待協(xié)議中數(shù)據幀的確認幢的發(fā)送時間關系

（圖中內容：兩個成功發(fā)送數(shù)據幀之間的最小間隔）

在確認幀長

度和處理時間均可忽略的情況下，要使信道利用率達到至少50%必須使數(shù)據幅的

發(fā)送時間等于2倍的單程傳播時延。即：t尸2tp已知：t尸Lf/C,其中C為信道容

量或信道速率。Lf為幀長（以比特為單位）。所以得幀長L尸CxtaCx2tp=4

000x0.04=160b

知識點解析：暫無解析

16、已知單鏈表L是一個遞增有序表，試寫一高效算法，刪除表中值大于min且

小于max的結點（若表中有這樣的結點），同時釋放被刪結點的空間，這里min和

max是兩個給定的參數(shù)1

標準答案：struetnode{Datatypedata；structnode*next；[ListNode；typedef

ListNode*LinkList：voidDeleteList（LinkListL,DaiaTypemin,DataType

max）（ListNode木P,*q,*h；P=L—>next：//采用代表頭結點的單鏈表

while（P&&p—>data<=min）{//找比min大的前一個元素位置q=P：P=P

->next：)p=q：//保存這個元素位置while(q&&q->datanext；//找比max

小的最后一個元素位置while(p->next!=q){h=p->next；P=P—>next：free(h)；/

/釋放空間}p—>next=q；//把斷點鏈上}

知識點解析：暫無解析

關于堆的一些問題：

17、堆的存儲表示是順序的，還是鏈接的？

標準答案：堆的存儲是順序的。

知識點解析：暫無解析

18、設有一個最小堆，即堆中任意結點的關鍵字均大于它的左孩子和右孩子的關鍵

字。其具有最大值的元素可能在什么地方？

標準答案：最大值元素一定是葉子結點，在最下兩層上。

知識點解析：暫無解析

19、對n個元素進行初始建堆的過程中，最多做多少次數(shù)據比較(不用大0表示

法)？

標準答案：在建含有n個元素、深度為h的堆時，其比較次數(shù)不超過4n,推導如

下：由于第i層上的結點數(shù)至多是2用，以它為根的一叉樹的深度為h-i+l,則調

用[n/2]次篩選算法時總共進行的關鍵字比較次數(shù)不超過下式之值：

力2?"x2(/t-i)=22'x(人?i)=xjW(2n)W4n

而il點解析：此題差M勺知識點是贏勺基本定義及效率。堆定義為n個關鍵字序列

K|,K2，…，Kn，當且僅當該序列滿足如下性質(簡稱為堆性質)：(l)kWK2,且

k￡K2i+i或⑵k2上；fiki>K2i+i(l<i<n)o%相當于二叉樹的非葉結點,Ri則是左

孩子，k2i+i是右孩子。

20、冒泡排序方法是把大的元素向上移(氣泡的上浮)，也可以把小的元素向下移(氣

泡的下沉)。請給出上浮和下沉過程交替的冒泡排序算法。

標準答案:voidBubbleSort2(inta[],intn){//相鄰兩趟向相反方向起泡的冒泡排

序算法intchange=l；low=0；high=n—1；//冒泡的上下界

while(lowa[i+1]){a[i]++a[i+1]；change=1；)//有交換,修改標志changehigh--；

//修改上界for(i二high；i>low；i-----)//從下向上起泡if(a[i]

知識點解析：暫無解析

考研計算機專業(yè)基礎綜合(綜合應用

題)模擬試卷第2套

一、綜合應用題(本題共20題，每題1.0分，共20

分。)

1、一個SPOOLing系統(tǒng)由輸入進程I、用戶進程P、輸出進程O、輸入緩沖區(qū)、輸

出緩沖區(qū)組成。進程1通過輸入緩沖區(qū)為進程P輸入數(shù)據，進程P的處理結果通過

輸出緩沖區(qū)交給進程0輸出。進程間數(shù)據交換以等長度的數(shù)據塊為單位，這些數(shù)據

塊均存儲在同一個磁盤上，因此，SPOOLing系統(tǒng)的數(shù)據塊通信原語保證始終滿

足：i+o()max。其中，max為磁盤容量(以該數(shù)據塊為單位)，i為磁盤上輸入數(shù)據塊

總數(shù)，。為磁盤上輸出數(shù)據總數(shù)。該SPOOLing系統(tǒng)運行時：(1)只要有輸入數(shù)

據，進程I終究會將它放入輸入緩沖區(qū)；(2)只要輸入緩沖區(qū)有數(shù)據塊，進程P終

究會輸入、處理并產生結果數(shù)據寫到輸出緩沖區(qū)；(3)只要輸出緩沖區(qū)有數(shù)據塊，

進程0終究會輸出它。請說明該SPOOLing系統(tǒng)在什么情況下死鎖，并說明如何

修正約束條件(1)避免死鎖，同時仍允許輸入數(shù)據塊和輸出數(shù)據塊存儲在同一個磁

盤上。

標準答案：(l)i+ogmax(2)當i=max,P的輸出數(shù)據無處存放,i的輸入數(shù)據占滿磁

盤時，死鎖。(3)應該增加約束：i+ogmax,使得輸出數(shù)據塊的長度o>0。

知識點解析：暫無解析

2、如果以單鏈表表示集合，設集合A用單鏈表LA表示，集合B用單鏈表LB表

示，設計算法求兩個集合的差，即A-B。

標準答案：由集合運算的規(guī)則知，集合的差A-B為包含所有屬于A而不屬于B的

元素，因此，算法的思路在于對于所有屬于集合A中的元素e,在集合B中進行查

找，若能找到，則說明它不屬于A—B,應從LA中刪除。若LA的長度為O(n),

LB的長度為O(m),則該算法的時間復雜度為O(mXn)。算法參考偽代碼如下：

voidDifference(LinkList*LA,LinkList*LB)//設LA,LB均具有頭結點

{Node*pre,*pre*p*r：pre=LA；p=LA->next：//p指向LA表中的某一結

點，而pre指向P的前面一個結點while(P!=NULL)(q=LB—>next；//遍歷

LB表，判斷LA中元素是否在LB中Node*while(q|=NULL&&q->data!=—>

da⑶q=q—〉nextif(q!=NULL){//在LB中找到用同結點元素，則應在LA中刪

除該結點廠P：pre—>next=r->next：p=p->next：free(r)；}else{//未能

找到，說明該結點屬于A-B繼續(xù)在LA中對下一個元素進行判斷pre=P：p=p一>

next；)))

知識點解析：暫無解析

3、設有一個nxn的上三角矩陣⑶》將其上三角中的元素按先行后列的順序存于

數(shù)組B[m]中，使得B[k]=aij且k=f|(i)+f2(j)+c,請推導出函數(shù)fi、f2和常數(shù)c,要求

fl和f2中不含常數(shù)項。

標準答案：上三角矩陣第1行有n個元素，第i—|行有n—(i—1)+1個元素，第1

行到第i一1行是等腰梯形，而第i行上第j個元素(即aij)是第i行上第j-i+1個

元素，故元素aij在一維數(shù)組中的存儲位置(下標k)為：k=(n+(n—(i—l)+l))(i—1)

/2+(j-i+l)=(2n—i+2)(i-1)/2+j—i+1

進一步整理為：k=則得，(i)=(2n+；)

x2g/(j)=/，c=f。

知識點解析：暫無解析

4、試找出分別滿足下面條件的所有二叉樹：（1）前序序列和中序序列相同。（2）中

序序列和后序序列相同。（3）前序序列和后序序列相同。（4）前序、中序、后序序列

均相同。

標準答案：（1）前序序列和中序序列相同的二叉樹是只有一個根結點的樹和只有右

了樹的樹。（2）中序序列和后序序列相同的二叉樹是只有個根結點的樹和只有左

子樹的樹。（3）前序序列和后序序列相同的二叉樹是只有一個根結點的樹。（4）前

序、中序、后序序列均相同的二叉樹是只有一個根結點的樹。

知識點解析：暫無解析

5、假設用于通信的電文由字符集｛a,b,c,d,e,f,g,h｝中的字母構成，這8

個字母在電文中出現(xiàn)的概率分別為｛0.07,0.19,0.02,0.06,0_32,0.03,

0.21,0.10）o（1）為這8個字母設計哈夫曼編碼。（2）若用三位二進制數(shù)（0?7）對

這8個字母進行等長編碼，則哈夫曼編碼的平均碼長是等長編碼的百分之幾?它使

電文總長平均壓縮多少。

標準答案：（1）對應的哈夫變樹如下圖所示。各字母的哈夫域編碼如下：a：1010,

b：00,C：10000,d：1001,e：11,f：10001,g：01,h：1011

0.02x5+0.03x5+0.06x4+0.07x4+0.1x4+0.32x2+0.19x2+0.21x2=2.61

2.61^3=0.87,它是等長編碼的87%,它使電文總長平均壓縮13%。

知識點解析：暫無解析

6、寫出在二叉排序樹中刪除一個結點的算法，使刪除后仍為二叉排序樹。設刪除

結點由指針p所指，其雙親結點由指針f所指，并假設被刪除結點是其雙親結點的

右孩子。描述上述算法。

標準答案：voidDelete(BSTreet,P){//在二叉排序樹l中，刪除f所指結點的右

孩子(由P所指向)if(P—>lchild==nuH){f—>rchild=P一>rchild：free(P)；)//p

無左子女else{//用P左子樹中的最大值代替P結點的值q=P—>lchild；s=q；

while(q—>rchild){S=q；q=q->rchild；)//查P左子樹中序序列最右結點

if(s==p->lchild)//p左子樹的根結點無右子女{p一〉data=s-*>data；p—>

lchild=s->IchiId；free(S)；)else{p一>data=q->data；s一>rchild=q->

lehild；free(q)；))}

知識點解析：暫無解析

7、網絡層的主要功能有哪些？

標準答案：網絡層是OSI參考模型中的第三層，是通信子網的最高層。網絡層關

系到通信子網的運行控制，體現(xiàn)了網絡應用環(huán)境中資源子網訪問通信子網的方式。

網絡層的主要任務是設法將源結點發(fā)出的數(shù)據包傳送到目的結點，因此要向傳輸層

提供最基本的端到端的數(shù)據傳送服務。概括地說，網絡層應該具有以下功能：(1)

為傳輸層提供服務網絡層提供的服務有兩類：面向連接的網絡服務和無連接的網

絡服務。(2)組包和拆包在網絡層，數(shù)據傳輸?shù)幕締挝皇菙?shù)據包(也稱為分組)。

數(shù)據包的頭部包含源結點和目標結點的網絡地址(邏輯地址)。(3)路由選擇路由選

擇也叫做路徑選擇，是艱據一定的原則和路由選擇算法在多結點的通信子網中選擇

?條最佳路徑。確定路由選擇的策略稱為路由算法。(4)流量控制流量控制的作用

是控制阻塞，避免死鎖。

知識點解析：暫無解析

8、在TCP的擁塞控制中，慢開始和擁塞避免算法是怎樣使用的？

標準答案：慢開始：在主機剛剛開始發(fā)送報文段時可先將擁塞窗口cwnd設置為一

個最大報文段MSS的數(shù)值.在每收到一個對新的報文段的確認后.將擁塞窗口增

加至多一個MSS的數(shù)值。用這樣的方法逐步增大發(fā)送端的擁塞窗口cwnd,可以使

分組注入網絡的速率更加合理。擁塞避免：當擁塞窗口值大于慢開始門限時，停

止使用慢開始算法而改用擁塞避免算法。擁塞避免算法使發(fā)送端的擁塞窗口每經過

一個往返時延RTT就增加一個MSS的大小。

知識點解析：暫無解析

9、某指令流水線分為五級，分別完成取址(IF)、譯碼并取數(shù)(ID)、執(zhí)行(EX)、訪存

(MEM)、寫結果(WR)。設完成各階段操作的時間依次為：90ns,60ns,70ns,

100ns,50nso試問：流水線的時鐘周期應取何值?若第一條和第二條指令發(fā)生數(shù)

據相關，第二條指令需推遲多少時間才能不發(fā)生錯誤?若相鄰兩條指令發(fā)生數(shù)據相

關，而不推遲第二條指令的執(zhí)行可采取什么措施？

標準答案：流水線的時鐘周期應取其中最長的時間段，即100ns。第二條指令需推

遲300ns(即等待.卜.一條指令完成EX、MEM、wR三個周期后才能開始ID,才能

不發(fā)生錯誤。若相鄰兩條指令發(fā)生數(shù)據相關而不推遲第二條指令的執(zhí)行，可采取的

措施是在訪存與執(zhí)行之間設置相關專用通路。

知識點解析：暫無解析

10、下圖為多重中斷的示意圖，請說明該中斷系統(tǒng)中實現(xiàn)了幾重中斷，描述此多重

1_

2-----------

3~~-----

4[^—1--

5

6---

中斷的過程。,I。乙4。79丁113

標準答案：該中斷系統(tǒng)可以實行5重中斷，中斷優(yōu)先級的順序是：優(yōu)先權1最高，

主程序運行于最低優(yōu)先雙（優(yōu)先權為6）。圖中出現(xiàn)了4重中斷。圖中中斷過程如

下：主程序運行到「時刻，響應優(yōu)先權4的中斷源的中斷請求并進行中斷服務，

到T3時刻，優(yōu)先權4的中斷服務還未結束，但乂出現(xiàn)了優(yōu)先權3的中斷源的中斷

請求；暫停優(yōu)先權4的中斷服務而響應優(yōu)先權3的中斷。到T4時刻，又被優(yōu)先權

2的中斷源所中斷，直到T6時刻，返回優(yōu)先權3的服務程序，到T7時刻，又被優(yōu)

先權1的中斷源所中斷，到T8時刻，優(yōu)先權1的中斷服務完畢，返回優(yōu)先權3的

服務程序，直到Tio優(yōu)先權3的中斷服務結束，返回優(yōu)先權4的服務程序，優(yōu)先權

4的服務程序到Ti]結束，最后返回主程序。圖中，優(yōu)先權3的服務程序被中斷2

次。

知識點解析：暫無解析

II、線性表（a]，a2,a3,…，an）中元素遞增有序且按順序存儲于計算機內。要求

設計算法完成以下內容：（1）用最少的時間在表中查找數(shù)值為x的元素。（2）若找到

將其與后繼元素位置相交換。（3）若找不到將其插入表中并使表中元素仍遞增有

序。

標準答案：（1）順序存儲的線性表遞增有序，可以順序查找，也可折半查找。題目

要求“用最少的時間在表中查找數(shù)值為X的元素”，這里應使用折半查找方法。void

SearchExchangelnsert（ElemTypea[]；ElemTypex）||a是具有n個元素的遞增有序線

性表，順序存儲。本算法在表中查找數(shù)值為x的//元素，如查到則與其后繼交

換位置；如查不到，則插入表中，.日.使表仍遞增有序{low-O：high-n1；//

low和high指向線性表下界和上界的下標while（low<=high）{mid=（low+high）/2；

//找中間位置if（a[mid]==x）break；//找到x,退出while循環(huán)else

if（a[mid]high）//查找失敗，插入數(shù)據元素x{for（i=n?l；i>high；i一一）

a[i+l]=a[i]；//后移元素a[i+l]=x；//插入x}//結束插入}//結束本算

法(2)算法討論首先是線性表的描述。算法中使用一維數(shù)組a表示線性表，未使用

包含數(shù)據元素的一維數(shù)組和指示線性表長度的結構體。若使用結構體，對元素的引

用應使用a.另外，元素類型就假定是ElemType,未指明具體類型。其

次，C中一維數(shù)組下標從0開始，若說有n個元素的一維數(shù)組，其最后一個元素的

下標應是n-1。最后，本算法可以寫成三個函數(shù)，即查找函數(shù)、交換后繼函數(shù)與插

入函數(shù)，寫成三個函數(shù)顯得邏輯清晰、易讀。

知識點解析：暫無解析

12、設有一個雙鏈表L,每個結點中除有prior、data和next這3個域外，還有一

個訪問頻度域freq,在鏈表被啟用之前，其值均初始化為零。每當在鏈表進行一次

LocateNode(L,x)運算時,令元素值為x的結點中freq域的值加1,并調整表口結

點的次序，使其按訪問頻度的遞減排列，以便使頻繁訪問的結點總是靠近表頭。試

寫一符合上述要求的LocatcNode運算的算法。

標準答案：lypedefstruclDuLNode{ElemTypedata；intfreq；structDuLNode

pred,*next：}*DList：DListlocate(DListL,ElemTypex){//L是帶頭結點的

按訪問頻度遞減的雙向鏈表DListp=L一,next,q；//p為L表的工作指針，q

為p的前驅，用于杳找插入位置while(p&&p->data!=x)p=p一,nexl；//查找

值為X的結點if(!p){printf("不存在所查結點\n")；exit(O)；}else{p->freq++；

//令元素值為x的結點的freq域加1p—>next—>prcd=p—>prcd；//將p結

點從鏈表上摘下ppred—>next=p->next；q=p—>pred；//以下查找P結點

的插入位置while(q!=L&&q->freqfreq)q=q一>pred：p->next=q一Anext：q

->ncxt_*>prcd=p；//將p結點插入p->prcd=q；q—>ncxt=p；)rcturn(p)；

//返回值為x的結點的指針}提示：在算法中先杳找數(shù)據x,查找成功時結點的

訪問頻度域增1,最后將該結點按頻度遞減插入鏈表中。

知識點解析：暫無解析

13、3個進程PI、P2、P3互斥使用一個包含N個(N>0)單元的緩沖區(qū)，P1每次用

produce。生成一個正整數(shù)并用put()送入緩沖區(qū)某一空單元中：P2每次用getodd()從

該緩沖區(qū)中取出一個奇數(shù)并用countodd。統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven。從該緩

沖區(qū)中取出一個偶數(shù)并用counteven。統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這3個進

程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。

標準答案：(1)定義信號是si控制P1與P2之間的同步，s2控制PI與P3之間的同

步，empty控制生產者與消費者之間的同步，mulex控制進程間互斥使用緩沖區(qū)。

(2)程序如下：varsl=0,s2=0,empty=N,mutex=1：parbeginPl：begin

X=produce()；/*生成一個數(shù)*/P(empty)；/*判斷緩沖區(qū)是否有空單元*/

P(mutex)；/*緩沖區(qū)是否被占用*/Put()：IfX%2==0V(s2)；/*如果是偶數(shù)，

向P3發(fā)出信號*/elseV(sl)；/*如果是奇數(shù)，向P2發(fā)出信號*/V(mutex)；/*

使用完緩沖區(qū)，釋放*/endP2：beginP(sl)；/*收到Pl發(fā)來的信號，已產生一

個奇數(shù)*/P(mutex)；/*緩沖區(qū)是否被占用*/Getodd()；Countodd()：

=eountodd()+l；V(mutex)：/*釋放緩沖區(qū)*/V(empty)；/*向Pl發(fā)信號，多出

一個空單元*/endP3：beginP(s2)/*收到PI發(fā)來的信號，已產生一個偶數(shù)*/

P(mutex)；/*緩沖區(qū)是否被占用*/Geteven()；Counteven()：=courlteven()+l；

V(mulex)；/*釋放緩沖區(qū)*/v(emply)：/*向Pl發(fā)信號，多出一個空單元*/

endparend

知識點解析：暫無解析

14、假設一個僅包含二元運算符的算術表達式以鏈表形式存儲在二叉樹BT中，寫

出計算該算術表達式值的算法。

標準答案：以二義樹表示算術表達式，根結點用于存儲運算符。若能先分別求出左

子樹和右子樹表示的子表達式的值，最后就可以根據根結點的運算符的要求，計算

出表達式的最后結果。lypedefstructnode{ElemTypedata；floatval；charoptr；

//只取‘十‘，'一'，‘叱，’/'sin?nodeSchild,*rchild；)BiNode,^BiTree：

floatPostEval(BiTreebt)(//以后序遍歷算法求以二叉樹表示的算術表達式的值

floatlv,rv；if(bt!=null){lv=PostEval(bt一>lchild)；//求左子樹表示的子表達式

的值rv=PostEval(bt—>rchild)；//求右子樹表示的子表達式的值

switch(bt->optr){case,+,：value=lv+rv；break；case'一'：value=lv—rv；break；

case'*。：value=lvzKn;：break；case'/'：value=lv/rv：)}return(value)；)

知識點解析：暫無解析

已知下列各種初始狀態(tài)(長度為n)元素，試問當利用直接插入法進行排序時，至少

需要進行多少次比較(要求排序后的文件按關鍵字從大到小順序排列)？

15、關鍵字自小到大有序(key1Vkye2V…Vkcyn);

標準答案：本題主要考杳直接插入法的算法思想及性能分析。根據題目所給出的

條件，最好情況下的比較次數(shù)即為最少比較次數(shù)。在關鍵字自小到大有序的情況

下，插入第i個(2SiWn)元素的比較次數(shù)為1,因此，總的比較次數(shù)為

l-t-l+l+...+l=n—1o

知識點解析：暫無解析

16、關鍵字自大到小逆序(key]>key2>…>key"

標準答案：在關鍵字自大到小有序的情況下，插入第i個(2SiSn)元素的比較次數(shù)為

i,因此，總的比較次數(shù)為2+3+4+...十n=[n(n+l)/2]—l=(n—l)(n+2)/2。

知識點解析：暫無解析

17、奇數(shù)關鍵字順序有序，偶數(shù)關鍵字順序有序(keyiVkey3〈...，key2<key4

標準答案：在奇數(shù)關鍵字順序有序和偶數(shù)關鍵字順序有序的情況下，比較次數(shù)最少

的情況是所有記錄關鍵字均按升序排列，這時，總的比較次數(shù)為n—1。

知識點解析：暫無解析

18、前半部分元素按關鍵字順序有序，后半部分元素按關鍵字順序逆序(key|V

key2V…Vkeym，keym41>keyni+2>...>keyn，m為中間位置)。

標準答案：在前半部分元素按關鍵字有序，后半部分按關鍵字逆序的情況下，后半

部分元素的關鍵字均大于前半部分元素的關鍵字較次數(shù)最少，此時前半部分的比較

次數(shù)為m—1,后半部分的比較次數(shù)為(n—m—l)(n—m+2)/2,因此，總的比較

次數(shù)為m—l+(n—m—l)(n—m,m+2)/2=(n-l)(n+8)/8(假設n為偶數(shù)，m=n

/2)o

知識點解析：暫無解析

19、假設程序PA和PB單獨執(zhí)行時所需的時間分別用TA和TB表示，并且假設

TA=lh,TB=1.5h,其中處理器工作時間分別為TA=18min,TB=27min,如果采用

多道程序設計方法，讓PA和PB并行工作，假定公理器利用率達到50%,系統(tǒng)開

銷為15min,請問系統(tǒng)效率能提高多少？

標準答案：（1）在串行情況下，兩個程序運行時間共計2.5h：在并行方式下，處理

器利用率為50%,說明處理器的工作時間占總運行時間的50%。根據已知條件，

“處理器工作時間分別為TA=18min,TB=27min",即總運行時間為（18+27戶50%

（min）,考慮到還有15min系統(tǒng)開銷，故并行與串行的效率比為并行處理所需的時

間?串行處理所需要的時間總和=［（18+27）：50%+15卜2.5-60=70%o（2）即采用多

道處理技術之后，完成程序PA和程序PB所需的時間為串行處理方法的70%。因

此可以說效率提高了30%。

知識點解析：暫無解析

20、物理層的接口有哪幾個特性?各包含什么內容？

標準答案：（1）機械特性：指明接口所用的接線器的形狀和尺寸、引線數(shù)目和排

列、固定和鎖定裝置，等等。（2）電氣特性：指明在接口電纜的各條線上出現(xiàn)的電

壓的范圍。（3）功能特性：指明某條線上出現(xiàn)的某一電平的電壓表示何意。（4）規(guī)程

特性：說明對于不同功能的各種可能事件的出現(xiàn)順序。

知識點解析：暫無解析

考研計算機專業(yè)基礎綜合（綜合應用

題）模擬試卷第3套

一、綜合應用題（本題共20題，每題7.0分，共20

分。）

K兄弟倆共同使用一個賬號，每次限存或取10元，存錢與取錢的進程分別如下所

示：intamount=0：SAVE（）｛TAKE（）｛intml；intm2：ml=amount；

m2二amount：m2=m2—10：amount=m2：）ml=ml+10：amount=ml：｝由于兄

弟倆可能同時存錢和取戰(zhàn)，因此兩個進程是并發(fā)的。若哥哥先存了兩次錢，但在第

三次存錢時弟弟在取錢。請問：（1）最后賬號amount上面可能出現(xiàn)的值是多少？（2）

如何用P、V操作實現(xiàn)兩并發(fā)進程的互斥執(zhí)行？

標準答案：本題考查P、V操作實現(xiàn)進程的互斥。(1)哥哥存兩次錢后，共享變量

amount的值為20。哥哥的第三次存錢與弟弟的取錢同時進行，如果兩者順序執(zhí)

行，則最后amount的值為20：如果在一個進程的執(zhí)行過程中進行CPU調度，轉

去執(zhí)行另一進程，則最后amount的值取決于amount=m1及amount=m2的執(zhí)行先

后次序，若前者先執(zhí)行，則最后amount的值為10,若后者先執(zhí)行，則最后amount

的值為30。因此，最后賬號amount上可能出現(xiàn)的值有10、20、30。(2)在上述問

題中，共享變量amount是一個臨界資源，為了實現(xiàn)兩并發(fā)進程對它的互斥訪問，

可為它設置一初值為1的互斥信號量mutex,并將上述算法修改為：int

amount=0：scm叩horcmutcx=1：//互斥訪問amount變量的信號量

cobegin{processSAVE(){intml；P(mutex)；ml=amount；ml=ml+10：

amount=ml：V(mutex)；)processTAKE(){intm2：P(mutex)；m2=amount：

m2=m2-10：amount=m2：V(mutcx)；}Jcocnd

知識點解析：暫無解析

2、請簡述SPOOLing系統(tǒng)的實現(xiàn)思想。

標準答案：“預輸入程序”把作業(yè)流中作業(yè)信息傳送到“輸入井”保存。作業(yè)被選中執(zhí)

行時不必再啟動輸入機，而是從磁盤上輸入井區(qū)域中讀取信息。作業(yè)執(zhí)行中產生的

結果也可暫時先存放在“輸出井”中，待作業(yè)執(zhí)行結束后由“緩輸出程序”把作業(yè)執(zhí)行

結果打印輸出。“預輸入程序''和"緩輸出程序、'的執(zhí)行都是在“算機控制下進行的。

知識點解析：暫無解析

3、一個nxn的對稱矩陣，如果以行或列為主序存入內存，則其容量為多少？

標準答案：n(n+l)/2(壓縮存儲)或戶(不采用壓縮存儲)。提示：此問題考查的知識

點是數(shù)組的存放問題。對稱矩陣可以只存上三角或下三角。所用空間為1,2,

3,...,n之和0

知識點解析：暫無解析

4、設有15000個無序的元素，希望用最快的速度挑選出其中前10個最大的元

素。在快速排序、堆排序、歸并排序、基數(shù)排序和希爾排序中，宜采用哪種方法

并說明理由？

標準答案：上面所說的幾種排序方法中，排序速度都很快，但快速排序、歸并排

序、基數(shù)排序和希爾排序都是在排序結束后才能確定數(shù)據元素的全部序列，而排序

過程中無法知道部分連續(xù)位置上的最終元素。而堆排序則是每次輸出一個堆頂元素

(即最大或最小值的元素)，然后對堆進行再調整，保證堆頂元素總是當前剩下元素

的最大或最小的，從而可知，如果在一個大量數(shù)據的文件中，如含有15000個元

素的記錄文件中選取前10個最大的元素，宜采用堆排序。

知識點解析：暫無解析

5、說明頁表的組成與程序邏輯地址到內存物理地址的變換過程?？毂硎且欢ㄒ?/p>

的嗎?說明快表內容的組成與讀寫原理

標準答案：頁表由若干表項組成，每個虛頁號對應頁表中的一個表項，表項的內容

可以由如下部分組成：最重要的是一個虛頁被分配在主存中的實際頁號，還可能包

括頁裝入(有效)位、修改標記位、替換控制位、其他保護位等組成的控制位字段。

地址變換過程：用虛地址中的虛頁號與頁表基地址相加，求出對應該虛頁的頁表表

項在主存中的實際地址，從該表項的實頁號字段取出實頁號再拼上虛地址中的頁內

地址，就得到讀主存數(shù)據用的實際地址。為了解決當要讀頁內的某個存儲單元

時，需讀兩次主存才能取得要讀的數(shù)據的問題(讀兩次主存過程：首先要讀一次主

存，通過查頁表求出實存地址，然后再讀一次主存)，設立一個完全用快速硬件實

現(xiàn)的容量很小的快速頁表，又稱轉換旁路緩沖器，用于存放在頁表中使用最頻繁

的、為數(shù)不多的那些表項的內容?？毂碇饕刑擁撎柡蛯嶍撎杻身梼热?。經快表

實現(xiàn)的地址轉換過程：用虛地址中的虛頁號去與快表中虛頁號字段的內容相比較，

與哪個表項中的虛頁號相同，則可以取出該表項中的實頁號，并與頁內地址拼接出

主存實際地址。這一過程可以很快完成，類似于高速緩；中存儲器的運行原理。當

在快表中找不到該虛頁號時，就要到主存中經慢表找出該虛頁號對應的實頁號，在

得到一個主存實際地址的同時用該虛頁號和實頁號替換快表的一個表項的內容，以

反映這次操作的形勢。

知識點解析：暫無解析

6、假設用于通信的電文由字符集｛a,b,c,d,e,f,g,h｝中的字母構成，這8

個字母在電文中出現(xiàn)的概率分別為｛0.07,0.19,0.02,0.06,0.32,

0.03,0.21,0.10),(1)為這8個字母設計哈夫曼編碼。(2)若用三位二進制數(shù)

(0?7)對這8個字母進行等長編碼，則哈夫曼編碼的平均碼長是等長編碼的百分之

幾?它使電文總長平均壓縮多少？

標準答案：(1)對應的哈夫曼樹如下圖所示。各字母的哈夫曼編碼如下：a：1010,

b：00,C：10000,d：1001,e：11,f：10001,g：01,h：1011

(2)哈夫曼編碼的平均碼長

為：

0.02x5+0.03x5+0.06x4+0.07x4+0.1x4+0.32x2+0.19x2+0.21x2=2.61

2.61+3=0.87,它是等長編碼的87%,它使電文總長平均壓縮13%。

知識點解析：暫無解析

7、已有鄰接表表示的有向圖，請編程判斷從第u