考研計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合

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

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

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

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

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

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

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