北京郵電大學(xué)2017年計(jì)算機(jī)學(xué)科基礎(chǔ)綜合考試真題803

考試科目：803計(jì)算機(jī)學(xué)科基礎(chǔ)綜合9/9北京郵電大學(xué)2017年碩士研究生入學(xué)考試試題考試科目：計(jì)算機(jī)學(xué)科基礎(chǔ)綜合請(qǐng)考生注意：①所有答案（包括選擇題和填空題）一律寫在答題紙上，否則不計(jì)成績(jī)。②不允許使用計(jì)算器一、單項(xiàng)選擇題（每小題2分，共80分）1.下列選項(xiàng)中與算法的時(shí)間復(fù)雜度有關(guān)的是A.問(wèn)題規(guī)模 B.計(jì)算機(jī)硬件性能C.編譯程序質(zhì)量 D.程序設(shè)計(jì)語(yǔ)言2.用單鏈表存儲(chǔ)兩個(gè)各有n個(gè)元素的有序表，若要將其歸并成一個(gè)有序表，最少的比較次數(shù)是A.n-l B.n C.2n-1 D.2n3.一個(gè)隊(duì)列用只帶尾指針的單循環(huán)鏈表存儲(chǔ)，則隊(duì)列插入和刪除操作的時(shí)間復(fù)雜度分別是A.O（l）、O（l）B.O（l）、O（n）C.O（n）、o（l）D.O（n）、O（n)4.已知一個(gè)三維數(shù)組A[l.15][0.9][-3.6]的每個(gè)元素占用5個(gè)存儲(chǔ)單元，該數(shù)組總共需要的存儲(chǔ)空間單元數(shù)為A.1500 B.4050 C.5600 D.75005.一棵具有n（m>1）個(gè)結(jié)點(diǎn)的樹(shù)，其高度最小和最大分別是A.1、log2n B.1、n C.2、n D.log2n、n6.在下列選項(xiàng)中，不能作為樹(shù)的存儲(chǔ)形式是A.孩子鏈表表示法 B.雙親表示法C.按層次的順序存儲(chǔ)表示法 D.孩子兄弟表示法7.一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通圖，邊數(shù)最多是A.n-1 B.n C.n（n-1）/2 D.n（n-l）8.下列關(guān)于圖的敘述中，正確的是A.在有向圖中，各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和。B.若圖的臨界矩陣是對(duì)稱矩陣，則該圖一定是連通的無(wú)向圖。C.連通分量是無(wú)向圖中的極小連通子圖。D.用臨界表存儲(chǔ)圖所用的空間大小只與圖的頂點(diǎn)數(shù)有關(guān)。9.查找有序表中的某一指定元素時(shí)，折半查找比順序查找的比較次數(shù)A.一定少 B.一定多 C.相同 D.不確定10.下列關(guān)于排序算法的敘述中，正確的是A.算法的穩(wěn)定性是指在各種情況下的時(shí)間效率相差不大的特性。B.希爾（Shell）排序的實(shí)質(zhì)是多次利用直接插入排序方法。C.所有時(shí)間復(fù)雜度為O（n2）的簡(jiǎn)單排序算法都是穩(wěn)定的。D.在待排序列數(shù)據(jù)基本有序的情況下，快速排序效率最高。11.用堆排序方法將待排序列（3，2，4，1，5）建成的初始堆是A.5，4，3，2，1 B.1，2，3，4，5C.5，3，4，1，2 D.l，2，4，5，312.馮·諾依曼結(jié)構(gòu)計(jì)算機(jī)工作方式的基本特點(diǎn)是A.多指令流單數(shù)據(jù)流 B.按地址訪問(wèn)并順序執(zhí)行C.數(shù)據(jù)存儲(chǔ)器和程序存儲(chǔ)器分離 D.存儲(chǔ)器按內(nèi)容選擇地址13.已知某計(jì)算機(jī)為定點(diǎn)整數(shù)計(jì)算機(jī)，其中央處理機(jī)的通用寄存器為16位，若（R0）=FFF9H，則有如下結(jié)論A.中央處理機(jī)的位數(shù)為16位；寄存器R0的真值為65529B.中央處理機(jī)的位數(shù)為16位；寄存器R0的真值為無(wú)法確定C.中央處理機(jī)的位數(shù)為16位；寄存器R0的真值為-7D.中央處理機(jī)的位數(shù)無(wú)法確定；寄存器R0的真值為-714.已知IEEE754單精度浮點(diǎn)數(shù)十六進(jìn)制值為42E48000，那它的十進(jìn)制為A.114.25 B.57.125 C.50.25 D.28.562515.下列關(guān)于儲(chǔ)存器的敘述中正確的是I.動(dòng)態(tài)存儲(chǔ)器是利用電容電荷來(lái)存儲(chǔ)信息的，需要周期逐個(gè)刷新每一個(gè)存儲(chǔ)單元Ⅱ.FLASH具有不易失特性，所以它是ROM且無(wú)法更新存儲(chǔ)單元Ⅲ.DRAM是動(dòng)態(tài)存儲(chǔ)器，采用隨機(jī)存取方式，存取地址需分兩次送入A.I B.I和Ⅱ C.Ⅱ和Ⅲ D.Ⅲ16.一個(gè)四體低位交叉存儲(chǔ)器，存取周期為400ns，若每個(gè)單體的存儲(chǔ)容量為1M×32位，在下述說(shuō)法中正確的是A.在100ns內(nèi)，存儲(chǔ)器可向CPU提供128位信息B.在400ns內(nèi)，存儲(chǔ)器可向CPU提供128位信息C.該存儲(chǔ)器的容量為4MBD.該存儲(chǔ)器的容量為16Mb17.下列說(shuō)法中，正確的是A.變址尋址時(shí)，有效地址存放在主存中B.程序執(zhí)行時(shí)，指令的尋址和數(shù)據(jù)的尋址是交替進(jìn)行的C.高級(jí)語(yǔ)言的源程序比匯編語(yǔ)言的源程序短小D.堆棧尋址按照先進(jìn)先出的順序?qū)崿F(xiàn)數(shù)據(jù)的存取18.下列幾項(xiàng)中，不符合RISC指令系統(tǒng)特征的是A.控制器多采用微程序控制方式，以期更快的設(shè)計(jì)速度B.指令格式簡(jiǎn)單，指令數(shù)目少C.尋址方式少且簡(jiǎn)單D.所有指令的平均執(zhí)行時(shí)間約為一個(gè)時(shí)鐘周期19.下列關(guān)于機(jī)器指令與微指令關(guān)系的陳述中，正確的是A.每條機(jī)器指令通過(guò)一條微指令解釋執(zhí)行B.每條機(jī)器指令由一段微程序解釋執(zhí)行C.每條微指令由若干條機(jī)器指令解釋執(zhí)行D.每條機(jī)器指令由若干段微程序解釋執(zhí)行20.某計(jì)算機(jī)的顯存容量為8MB，若采用2048×1024分辨率，則每個(gè)像素最多可以使用的顏色數(shù)是A.256 B.64k C.16M D.4G21.某總線在一個(gè)總線周期中并行傳送8個(gè)字節(jié)的數(shù)據(jù)，總線時(shí)鐘頻率是66MHz，每個(gè)總線周期等于一個(gè)總線時(shí)鐘周期，則總線的帶寬為A.528MB/s B.132MB/s C.264MB/S D.66MB/s22.單級(jí)中斷系統(tǒng)中，CPU一旦響應(yīng)中斷，應(yīng)立即執(zhí)行下面的動(dòng)作，以避免在中斷響應(yīng)的過(guò)程中響應(yīng)其他中斷源造成的干擾。A.關(guān)中斷 B.清除中斷請(qǐng)求標(biāo)志C.禁止DMA D.清除該中斷源的中斷屏蔽位23.個(gè)人計(jì)算機(jī)或筆記本電腦加電啟動(dòng)后，開(kāi)始執(zhí)行系統(tǒng)引導(dǎo)過(guò)程，CPU首先執(zhí)行的代碼A.磁盤引導(dǎo)塊（bootblockondisk） B.系統(tǒng)程序C.OS內(nèi)核 D.BIOS中的bootstrap程序24.進(jìn)程被成功創(chuàng)建以后，該進(jìn)程的進(jìn)程控制塊將會(huì)首先插入到的隊(duì)列是A.就緒隊(duì)列 B.等待隊(duì)列 C.運(yùn)行隊(duì)列 D.活動(dòng)隊(duì)列25.如果系統(tǒng)中有n個(gè)用戶進(jìn)程，則在等待隊(duì)列中用戶進(jìn)程的個(gè)數(shù)最多是A.1 B.n C.n-l D.026.在多進(jìn)程的系統(tǒng)中，為了保證公共變量的完整性，各進(jìn)程應(yīng)互斥進(jìn)入臨界區(qū)，所謂臨界區(qū)是指A.一個(gè)緩沖區(qū) B.一段數(shù)據(jù)區(qū)C.同步機(jī)制 D.一段程序27.在交互式系統(tǒng)中，若用戶數(shù)為10，為保證響應(yīng)時(shí)間≤100ms，忽略其他系統(tǒng)開(kāi)銷，則操作系統(tǒng)應(yīng)將時(shí)間片設(shè)為A.≤lms B.≤l0ms C.≤l00ms D.≤1000ms28.進(jìn)程調(diào)度算法的選擇?？紤]因素之一是使系統(tǒng)有最高的吞吐率，為此應(yīng)該是A.不讓處理機(jī)空閑 B.能夠處理盡可能多的系統(tǒng)進(jìn)程C.響應(yīng)時(shí)間短 D.用戶能和系統(tǒng)交互29.使用文件必須先做的操作是A.打開(kāi) B.打印 C.改名 D.備份30.一般在文件系統(tǒng)中采用樹(shù)型目錄，主要解決的是A.不同用戶文件的命名沖突 B.不同用戶文件的拷貝C.用戶文件的查找 D.不同用戶文件的顯示31.在一個(gè)采用一級(jí)索引結(jié)構(gòu)的文件系統(tǒng)中，磁盤塊大小為lKB。若某文件的大小為1300B，則該文件需要占用的磁盤塊是A.0 B.1 C.2 D.332.磁帶上的文件只能是A.順序存取 B.隨機(jī)存取C.以雙字為單位存取 D.直接存取33.某信道帶寬為3kHz，若該信道的信噪比（SN）為1023，則該信道的最大數(shù)據(jù)傳輸速率為A.3kbps B.6kbps C.30kbps D.60kbps34.數(shù)據(jù)鏈路層采用“回退N步”（Go-Back-N）協(xié)議實(shí)現(xiàn)可靠傳輸，若幀頭中序號(hào)字段占3比特，則發(fā)送窗口的最大值為A.1 B.3 C.7 D.835.數(shù)據(jù)鏈路層采用CRC進(jìn)行校驗(yàn)，生成多項(xiàng)式G（x）=x3+1，待發(fā)送比特流為10101010，則校驗(yàn)信息為A.101 B.110 C.100 D.01036.以太網(wǎng)交換機(jī)生成轉(zhuǎn)發(fā)表時(shí)，使用接收幀中的地址為A.目的MAC地址 B.源MAC地址C.目的IP地址 D.源IP地址37.下列選項(xiàng)中，可作為IP數(shù)據(jù)報(bào)頭中源IP地址的是A. B.2C.55 D.38.使用手機(jī)中的瀏覽器訪問(wèn)北京郵電大學(xué)主頁(yè)過(guò)程中，手機(jī)中不會(huì)用到的協(xié)議為A.IP B.TCP C.DNS D.OSPF39.IP數(shù)據(jù)報(bào)頭中設(shè)置TTL字段的目的是A.解決路由環(huán)路問(wèn)題 B.解決擁塞問(wèn)題C.解決流量控制問(wèn)題 D.隔離廣播風(fēng)暴40.主機(jī)H使用TCP協(xié)議向服務(wù)器S發(fā)送大量數(shù)據(jù)，TCP連接的MSS為lK字節(jié)。H的擁塞窗口和接收窗口均為8K字節(jié)時(shí)，出現(xiàn)發(fā)送定時(shí)器超時(shí)，則H的發(fā)送窗口為A.0 B.lK C.4K D.8K二、綜合應(yīng)用題（共70分）41.（10分）已知有向圖描述為（<A，B，1>，<A，E，6>，<A，D，7>，<B，C，2>，<B，E，4>，<C，D，3>，<C，E，1>，<E，D，1>}，各項(xiàng)中的數(shù)字表示兩頂點(diǎn)間的權(quán)值。（1）畫出該有向圖；（2）利用迪杰斯特拉（Dijkstra）算法求頂點(diǎn)A到其它各頂點(diǎn)間的最短距離，寫出求解過(guò)程。42.（13分）設(shè)計(jì)算法Search_Insert：在一棵非空二又排序樹(shù)（按各元素的key值建立）上查找元素值為e的結(jié)點(diǎn)，若該結(jié)點(diǎn)存在，返回其指針；若該結(jié)點(diǎn)不存在，則插入一個(gè)元素值為e的新結(jié)點(diǎn)，并返回新結(jié)點(diǎn)的指針。typedefstruct{intkey;charinfo[10];}elemtype;typedefstructnode{elemtypedata;node*lchild，*rchild;}node，*bitptr;BitptrSearch_Insert（bitptrT，elemtypee）43.（11分）某計(jì)算機(jī)系統(tǒng)，主存按字節(jié)編址，容量為4MB。Cache容量為16KB，每塊有8個(gè)字，每字32位。只有Load/Store指令能對(duì)存儲(chǔ)器進(jìn)行讀寫操作，其它指令只對(duì)寄存器進(jìn)行操作。根據(jù)程序運(yùn)行的統(tǒng)計(jì)結(jié)果，每種指令所占的比例如題43表所示。已知Cache的命中率是98%，Cache訪問(wèn)命中時(shí)的CPI是2.0，而Cache訪問(wèn)不命中時(shí)，缺失的損失是25個(gè)時(shí)鐘周期。（1）請(qǐng)解釋CPI的含義 題43表指令種類指令所占比例算術(shù)邏輯運(yùn)算35%Load/Store40%轉(zhuǎn)移10%其他15%（2）若Cache采用四路組相聯(lián)映射，請(qǐng)給出主存地址中各個(gè)字段的位數(shù)。（3）若Cache采用直接映射，請(qǐng)給出主存地址中各個(gè)字段的位數(shù)。（4）如果Cache命中率提高到100%，那么機(jī)器的速度是原來(lái)（存在Cache缺失時(shí)）的多少倍？44.（12分）某模型機(jī)的數(shù)據(jù)通路如題44圖所示。R1和R2為通用寄存器，MDR為內(nèi)存數(shù)據(jù)緩沖寄存器，MAR為內(nèi)存地址寄存器，PC為程序計(jì)數(shù)器，IR為指令寄存器，M為內(nèi)存。所有帶箭頭信號(hào)為控制信號(hào)。題44圖 數(shù)據(jù)通路圖（1）圖中的Tl和T2是什么部件，有何作用？（2）圖中的部件X的名稱是什么，有何作用？（3）若二地址RS型指令采用如下格式：操作碼寄存器號(hào)地址“SUBRl，（R2）”指令的操作為：R1←R1-（R2），其中R1、R2為寄存器，（R2）表示寄存器R2指示的內(nèi)存地址。題44表給出指令取指周期各節(jié)拍的功能和控制信號(hào)，請(qǐng)按照題44表方式表示給出減法SUB指令執(zhí)行周期各節(jié)拍的功能和控制信號(hào)。題44表取指周期T1PC→MARPC-IB，IB-MART2M→IRRD，（DB-MDR，MDR-I），MDR-IB，IB-IRT3PC+1PC+1T4指令譯碼無(wú)（4）如果設(shè)計(jì)該模型機(jī)的操作控制器，常用的設(shè)計(jì)方法有幾種？請(qǐng)對(duì)比各種設(shè)計(jì)方法的優(yōu)缺點(diǎn)。45.（7分）公交車司機(jī)、售票員等的相關(guān)活動(dòng)，不考慮同步互斥的實(shí)現(xiàn)過(guò)程如下：假定：（1）售票員關(guān)車門后司機(jī)才可以啟動(dòng)車輛。（2）司機(jī)到站停車后，售票員方可開(kāi)車門。司機(jī)：While（true）{…Startvehicle…Drive…Busstop…}售票員：While（true）{…Passengersonboard…Closethedoor…Sellticket…Openthedoor…Passengersgetoff…}請(qǐng)用wait（）和signal()操作，實(shí)現(xiàn)上述活動(dòng)的同步互斥，給出信號(hào)量定義和初值，在上述過(guò)程中增加wait（）和signal（）操作，并寫出實(shí)現(xiàn)過(guò)程。46.（8分）對(duì)訪問(wèn)串：1，2，3，4，1，2，5，1，2，3，4，5，7假定：分配給一個(gè)進(jìn)程的內(nèi)存空間為4個(gè)空閑塊物理塊（frame），所有塊的內(nèi)容初始都為空。采用LRU算法，分別計(jì)算訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)和缺頁(yè)率，給出計(jì)算過(guò)程。47.（9分）如題47圖1所示，主機(jī)H1與H2使用TCP/IP協(xié)議進(jìn)行通信，H1與H2間的通信路徑中有Rl，R2和R3三個(gè)路由器，四段通信鏈路的MTU