考研計算機學(xué)科專業(yè)基礎(chǔ)綜合

考研計算機學(xué)科專業(yè)基礎(chǔ)綜合-33（總分80,考試時間90分鐘）一、單項選擇題在每小題給出的四個選項中，請選出一項最符合題目要求的。1.若已知一個棧的入棧序列是1，2，3....n,其輸出序列為pl,p2,p3,...pn，若p1=n,則pi是（）。A.iB.n—i C.n—i+1 D.不確定2,將一個A[1..100,1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1.,298]中，A中元素A66,65（即該元素下標i=66,j=65），在B數(shù)組中的位置k為（）。A.198B.195C.197D.196查找效率最高的二叉排序樹是（）。所有結(jié)點的左子樹都為空的二叉排序樹B?所有結(jié)點的右子樹都為空的二叉排序樹平衡二叉樹沒有左子樹的二叉排序樹一棵深度為k的平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0,則該樹的結(jié)點數(shù)是（）。A.2k-1-1B.2k-1C.2k-1+1 D.2k-1判斷以下敘述的正確性I對有向圖G,如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖II連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存訪問過的頂點III圖的深度優(yōu)先搜索中一般要采用棧來暫存訪問過的頂點a.i、iB.n、mC.i、mD.i、ii、m一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中零元素的個數(shù)是

()。A.eB.2eC.n2-eD.n2-2e從二叉樹的任一結(jié)點出發(fā)到根的路徑上，所經(jīng)過的結(jié)點序列必按其關(guān)鍵字降序排列的是（）。二叉排序樹B.大頂堆C.小頂堆D.平衡二叉樹順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在等概率的情況下，分塊查找成功的平均查找長度為（）。A.21B.23C.41D.62在下列存儲結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系的是（）。樹形存儲結(jié)構(gòu)B.鏈式存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)若對27個元素只進行三趟多路歸并排序，則選取的歸并路數(shù)是（）。A.2B.3C.4D.5下列序列中，執(zhí)行第一趟快速排序的結(jié)果是（）。A.[da,ax,eb,de,bb]ff[ha,gc] B.[cd,eb,ax,da]ff[ha,gc,bb]C.[gc,ax,eb,cd,bb]ff[da,ha] D.[ax,bb,cd,da]ff[eb,gc,ha]若一臺計算機的機器字長為4字節(jié)，則表明該機器（）。能處理的數(shù)值最大為4位十進制數(shù)能處理的數(shù)值最多為4位二進制數(shù)組成在CPU中能夠作為一個整體處理的32位的二進制代碼在CPU中運算的結(jié)果最大為2325位二進制定點小數(shù)，用補碼表示時，最小負數(shù)是（）。A.0.1111B.1.0001 C.1.1111D.1.0000下列說法中正確的是（）。采用變形補碼進行加減法運算可以避免溢出只有定點數(shù)運算才可能溢出，浮點數(shù)運算不會發(fā)生溢出定點數(shù)和浮點數(shù)運算都有可能產(chǎn)生溢出

兩個正數(shù)相加時一定產(chǎn)生溢出15.如果一個高速緩沖存儲系統(tǒng)中，主存的容量為12MB,Cache的容量為400KB，則該存儲系統(tǒng)的總?cè)萘繛椋ǎ?。A.12MB+400KBB.12MBC.400KBD.12MB-400KB16.某計算機的存儲系統(tǒng)由Cache一主存系統(tǒng)構(gòu)成，Cache的存取周期為10ns，主存的存取周期為50ns。在CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為4800次，主存完成的存取次數(shù)為200次，該Cache一主存系統(tǒng)的效率是（）。A.0.856B.0.862 C.0.958 D.0.96017,對于RISC機和CISC機，以下說法錯誤的是（）。RISC機的指令條數(shù)比CISC機少RISC機指令的平均字長比CISC機指令的平均字長短對大多數(shù)計算任務(wù)來說，RISC機程序所用的指令條數(shù)比CISC機少RISC機和CISC機都在發(fā)展微程序在計算機中存放的位置是（）。主存儲器 B.控制存儲器C.通用寄存器 D.指令寄存器下列各敘述中正確的命題是（）。I在取指周期中也可能從內(nèi)存取到操作數(shù)IICPU的訪存時間是由存儲器的容量決定的，存儲容量越大，訪存時間就越長III在主存與Cache之間的直接映射方式下，不采用替換策略也可以實現(xiàn)正確的塊替換W動態(tài)存儲器的讀操作也具有刷新的功能A.i、n、mb.i、ii、wC.n、m、wD.i、m、w在菊花鏈方式中，靠近控制器的設(shè)備與遠處設(shè)備的（）。優(yōu)先級高B.優(yōu)先級相等C.優(yōu)先級低 D.不一定21.RAID利用冗余技術(shù)實現(xiàn)高可靠性，其中RAID1的磁盤利用率是（）。A.25%B.50% C.75%D.100%22.設(shè)存儲器容量為32字，字長64位，模塊數(shù)m=4，存儲周期T=200ns，數(shù)據(jù)總線寬度為64位，總線傳送周期T=50ns用交叉方式進行組織，交叉存儲器的帶寬是（）。A.32x107位/秒B.8x107位/秒 C.73x107位/秒D.18x107位/秒

操作系統(tǒng)為用戶提供了多種接口，它們是（）。I計算機高級指令I(lǐng)I終端命令I(lǐng)II圖標菜單W匯編語言VC語言W系統(tǒng)調(diào)用a.i、ii、vB.n、m、wc.m、w、vd.ii、w、w在交互式操作系統(tǒng)中，當選擇調(diào)度算法時，不作為主要調(diào)度準則考慮的是（）。盡量提高處理機的利用率盡可能高地提高系統(tǒng)的吞吐量盡可能地降低用戶響應(yīng)時間盡量公平地對待每一個進程在解除死鎖的方法中，代價最大的是（）。A.終止一個死鎖進程 B.終止所有的死鎖進程C.重啟系統(tǒng)D.剝奪一個死鎖進程的資源若有一進程擁有100個線程，這些線程都屬于內(nèi)核級線程，則在系統(tǒng)調(diào)度執(zhí)行時間上占用的時間片是（）。A.1B.100C.1/100D.027.某計算機采用頁式存儲管理，內(nèi)存中現(xiàn)有1000個頁表項，CPU的cache中可以存放N個頁表項，該系統(tǒng)中，CPU內(nèi)存訪問的時間為100ns，對cache訪問的時間是5ns，如果希望頁表映射的平均時間降到20ns以下，那么cache中的N必須高于（）。A.850B.858C.923 D.842在分頁系統(tǒng)中，程序員編制的程序，其地址空間是連續(xù)的，分頁過程的完成是（）。A.由程序員進行分頁 B.由操作系統(tǒng)自動分頁C.由用戶進行分頁 D.由編程工具進行分頁某操作系統(tǒng)的文件管理采用直接索引和多級索引混合方式，文件索引表共有10項，其中前8項是直接索引項，第9項是一次間接索引項，第10項是二次間接索引項，假定物理塊的大小是1K，每個索引項占用4個字節(jié)，則該文件系統(tǒng)中最大的文件可以達到（）。A.65793KB.32768KC.65536KD.34000K30,設(shè)磁盤的IO請求隊列中所要訪問的磁道號為：96，184，25，120，12，126，73，75,當前磁頭在96,前一次在90。當采用最短尋道時間優(yōu)先算法（SSTF）和電梯算法所要移動的距離是（）。

A.618,418 B.306,260C.306,418D.618,260文件系統(tǒng)中若文件的物理結(jié)構(gòu)為單一索引結(jié)構(gòu)，則在文件控制塊中有關(guān)文件的信息中，不會有的是（）。A.文件大小 B.文件首塊地址C.索引表地址D.文件創(chuàng)建時間在設(shè)備管理中，用來實現(xiàn)設(shè)備分配的四個數(shù)據(jù)結(jié)構(gòu)中，每個設(shè)備一張，描述設(shè)備的特性和狀態(tài)，反映設(shè)備的特性、設(shè)備和控制器的連接情況的數(shù)據(jù)結(jié)構(gòu)是（）。A.設(shè)備控制表（DCT）B.系統(tǒng)設(shè)備表（SDT）C.控制器控制表（COCT）D.通道控制表（CHCT）33.在OSI參考模型中，第N層和其上的第N+1層的關(guān)系是（）。第N層為第N+1層提供服務(wù)第N+1層將從第N層接收的信息增加了一個頭第N層利用第N+1層提供的服務(wù)第N層對N+1層沒有任何作用34.電路交換的優(yōu)點是（）。I傳輸時延小II分組按序到達m無需建立連接w線路利用率高a.i和II b.i和m c.i和m d.i和w若數(shù)據(jù)鏈路的發(fā)送窗口尺寸WT=4，在發(fā)送3號幀、并接到2號幀的確認幀后，發(fā)送方還可連續(xù)發(fā)送的幀數(shù)是（）。A.2幀B.3幀C.4幀D.1幀下列對于IP分組的分片和重組的描述正確的是（）。IP分組可以被源主機分片，并在中間路由器進行重組IP分組可以被路徑中的路由器分片，并在目的主機進行重組IP分組可以被路徑中的路由器分片，并在中間路由器上進行重組IP分組可以被路徑中的路由器分片，并在最后一跳的路由器上進行重組為了限制路由信息傳播的范圍，OSPF協(xié)議把網(wǎng)絡(luò)劃分成4種區(qū)域（Area），其中連接各個區(qū)域的傳輸網(wǎng)絡(luò)是（）。A.不完全存根區(qū)域 B.標準區(qū)域C.主干區(qū)域D.存根區(qū)域

38.一臺主機的IP地址為00,子網(wǎng)掩碼為?，F(xiàn)在用戶需要配置該主機的默認路由。經(jīng)過觀察發(fā)現(xiàn)，與該主機直接相連的路由器具有如下4個IP地址和子網(wǎng)掩碼：IIP地址:,子網(wǎng)掩碼:IIIP地址:,子網(wǎng)掩碼:miP地址:,子網(wǎng)掩碼:WIP地址:,子網(wǎng)掩碼:請問IP地址和子網(wǎng)掩碼可能是該主機的默認路由的是（）。a.i和Ib.i和m c.i、m和w D.m和w39.以太網(wǎng)交換機中的端口/MAC地址映射表是（）。是由交換機的生產(chǎn)廠商建立的是交換機在數(shù)據(jù)轉(zhuǎn)發(fā)過程中通過學(xué)習(xí)動態(tài)建立的是由網(wǎng)絡(luò)管理員建立的是由網(wǎng)絡(luò)用戶利用特殊的命令建立的FTP客戶端登陸到FTP服務(wù)器，并下載了一個文件，請問這個過程中需要建立TCP連接和斷開TCP連接的次數(shù)分別是（）。A.2, 1 B. 1, 1 C. 1,2 D. 2, 2、綜合應(yīng)用題任意給定1,2,...,n指定為一棵樹的先根遍歷序列；同時任意給定這n個數(shù)值（1,2,...,n）的一個排列p1,p2,...pn為這棵樹的后根遍歷序列。（1） 根據(jù)這樣的先根遍歷序列和后根遍歷序列，是否都可以得到一棵樹？如果能夠，請簡述理由（不要求形式化證明）。如果不能，請給出一個簡單反例。（2） 如果能得到樹，所得到的樹是否唯一?如果能夠，請簡述理由（不要求形式化證明）。如果不能，請給出一個簡單反例。42.設(shè)有一個雙向鏈表h,每個結(jié)點中除有prior、data和next共3個域外，還有一個訪問頻度域freq,在鏈表被起用之前，每個結(jié)點中的freq域的值均被初始化為零。每當進行LocateNode（h,x）運算時，令元素值為x的結(jié)點中freq域的值加1,并調(diào)整表中結(jié)點的次序，使其按訪問頻度的遞減序列排序，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的LocateNode運算的算法。43.已知兩個實數(shù)x=-68,y=-8.25,它們在C語言中定義為float型變量，分別存放在寄存器A和B中。另外，還有兩個寄存器C和D。A、B、C、D都是32位的寄存器。

請回答下列問題(要求剛十六進制表示二進制序列)：寄存器A和B的內(nèi)容分別是什么？x和y相加后的結(jié)果存放在c寄存器中，寄存器C中的內(nèi)容是什么？x和y相減后的結(jié)果存放在D寄存器中，寄存器D中的內(nèi)容是什么?44,一個字節(jié)多路通道連接D1、D2、D3、D4、D5共5臺設(shè)備，這些設(shè)備分別每10四、30卜、30卜、50四和75gs向通道發(fā)出一次數(shù)據(jù)傳送的服務(wù)請求，請回答下列問題：計算這個字節(jié)多路通道的實際流量和工作周期。如果設(shè)計字節(jié)多路通道的最大流量正好等于通道實際流量，并假設(shè)對數(shù)據(jù)傳輸率高的設(shè)備，通道響應(yīng)它的數(shù)據(jù)傳送請求的優(yōu)先級也高。5臺設(shè)備在0時刻同時向通道發(fā)出第一次傳送數(shù)據(jù)的請求.并在以后的時間里按照各自的數(shù)據(jù)傳輸率連續(xù)工作。畫出通道分時為每臺設(shè)備服務(wù)的時間關(guān)系圖，并計算這個字節(jié)多路通道處理完各臺設(shè)備的第一次數(shù)據(jù)傳送請求的時刻。從時間關(guān)系圖上可以發(fā)現(xiàn)什么問題?如何解決這個問題？設(shè)某多道程序系統(tǒng)中有用戶使用的內(nèi)存1000M，打印機1臺。系統(tǒng)采用可變分區(qū)動態(tài)分配算法管理內(nèi)存，而對打印機采用靜態(tài)分配。假設(shè)輸入輸出操作時間忽略不計，采用最短剩余時間優(yōu)先的進程調(diào)度算法，進程最短剩余時間相同時采用先來先服務(wù)的算法，進程調(diào)度時機選擇在進程執(zhí)行結(jié)束或新進程創(chuàng)建時，現(xiàn)有進程如下：進程創(chuàng)建時間要求執(zhí)行時間要求內(nèi)存申請打印機008150M1144300M12101600M031120200M141614100M0假設(shè)系統(tǒng)優(yōu)先分配內(nèi)存低地址區(qū)域，且不允許移動，那么，求:給出進程調(diào)度算法選中進程的次序，并說明理由。全部進程執(zhí)行結(jié)束所用的時間是多少？假定某采用頁式虛擬存儲管理的計算機系統(tǒng)中，主存儲器容量為1GB，被分為262144塊物理塊，物理塊號為0,1，2,......，262143。某進程的地址空間占4頁，邏輯頁號為0,1，2，3，被分配到主存儲器的第20,45，101，58號物理塊中。回答：內(nèi)存物理地址至少應(yīng)該用多少位字長來表示？進程每一頁的長度為多少字節(jié)?邏輯地址中的頁內(nèi)地址應(yīng)占用多少位字長？把進程中每一頁在分到的主存物理塊中的起始地址和結(jié)束地址填入下表： 邏輯頁號物理起始地址 物理結(jié)