全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考

PAGEPAGE19計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合試題1～40280求整數(shù)n(n≥0)intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A.O(log2n) B.O(n) C.(nlog2n) D.O(n2)‘+’‘-’‘*’‘/’‘(’和‘)’a+b-a*((cd)/e-f)+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+A.5 B.7 C.8 D.11a,e,b,d,c，后序遍歷序列為b,c,d,e,aA.只有e B.有eb C.有、c D.無(wú)確定平二樹(shù)高為6，且有葉點(diǎn)平衡子為1，該衡二樹(shù)結(jié)總為A.10 B.20 C.32 D.33neA.O(n) B.O(e) C.O(n+e) D.O(n*e)A.存，唯一 B.，且唯一C.在可不一 D.無(wú)確定否在（Dijkstra）abcA.d,e,f B.e,d,f C.f,d,e D.f,e,d用普里姆（Prim）（Kruskal）A.僅I B.僅II C.僅、III D.僅、3階B78BA.60 B.60,62 C.62,65 D.65I.簡(jiǎn)單選排序 希排序 快速排序 IV排序 二歸排序A.僅、、IV B.僅、III、VC.僅II、、IV D.僅、IV、VA.排的趟數(shù) B.素移次數(shù)C.用助間數(shù)量 D.元之的較數(shù)A10090CPUCPU50%，I/O速度不變，則運(yùn)行基準(zhǔn)程序AA.55秒 B.60秒 C.65秒 D.70秒intshort3216位，執(zhí)行下列Cunsignedshortx=65530;unsignedinty=x;得到y(tǒng)的機(jī)器數(shù)為A.00007FFA B.0000C.FFFF7FFA D.FFFAfloat即IEEE754）A.2126-2103 B.2127-2104 C.2127-2103 D.2128-2104int和short3216，并且數(shù)據(jù)按邊界對(duì)齊存儲(chǔ)。某Cstruct{int a;charb;short }record;record.a=273;若record變量的首地址為0Xc008，則低至0Xc008中內(nèi)容及record.c的地址分別為A.0x00、0xC00D B.0x00、0xC00EC.0x110xC00D D.0x11、0xC00E（FlashMemory）MOSCache4Cache1個(gè)字。若Cache2路組相聯(lián)映射方式和LRU0,4,8,2,0,6,8,6,4,8時(shí)，命中CacheA.1 B.2 C.3 D.433573、12、56A.5位 B.6位 C.15位 D.33位100MHz32/（）“128A.20ns B.40ns C.50ns D.20．下列關(guān)于USB221．下列選項(xiàng)中，在I/O總線(xiàn)的數(shù)據(jù)線(xiàn)上傳輸?shù)男畔↖.接口的令字 接口狀態(tài)字 中斷類(lèi)號(hào)A.僅、II B.僅、III C.僅、III D.I、II、22．應(yīng)部斷過(guò)中，斷指完的作，保斷外還括I.關(guān)中斷 保存用存的容 形成中服序入地送PCA.僅、II B.僅、III C.僅、III D.I、II、23．列項(xiàng)，可在用態(tài)生事是A.系調(diào)用 B.部斷 C.程換 D.缺頁(yè)A.程計(jì)器 B.序態(tài)存器C.用據(jù)存器 D.用址器A.虛存只基連分配術(shù) B.虛擬儲(chǔ)能于連分配術(shù)C.擬儲(chǔ)量受容量限制 D.虛擬儲(chǔ)量受存量的制5P0P1P2P3P4R1、R2、R318、622。T0進(jìn)程已分配資源資源最大需求R1R2R3R1R2R3P03235510P1403536P24054011P3204425P4314424A.P0,P2,P4,P1,P3 B.P1,P0,P3,P4,P2C.P2，P1，P0，P3，P4 D.P3,P4,P2,P1,P0readread系統(tǒng)調(diào)用會(huì)導(dǎo)致CPUreadA.僅、II B.僅、III C.僅、III D.I、II和III一個(gè)多道批處理系統(tǒng)中僅有P1和P2P2比P15ms到達(dá)，它的計(jì)算和P160ms，I/O80ms20msP2120ms，I/O40ms40ms若不考慮調(diào)度和切換時(shí)間，則完成兩個(gè)作業(yè)需要的時(shí)間最少是A.240ms B.260ms C.340ms D.360msA.重排求序 B.在個(gè)上設(shè)多分區(qū)C.讀滯寫(xiě) D.優(yōu)文理的布TCP/IPICMPA.PPP B.IP C.UDP D.TCPA.機(jī)特性 B.功能性 C.特性 D.氣35．太的MAC提供是A.無(wú)接不靠服務(wù) B.連接可的務(wù)C.連的靠服務(wù) D.連接不靠服務(wù)NB傳輸數(shù)據(jù)數(shù)據(jù)傳輸速率為16kbp270ms128~512A.5 B.4 C.3 D.2IPIPIPIPIPIPA.僅、IV B.僅、、III C.僅、、IV D.I、、III、38．ARP議功是A.根據(jù)址詢(xún)MAC地址 B.據(jù)MAC址詢(xún)IPC.據(jù)名詢(xún)IP地址 D.據(jù)IP址域名180.80.77.55255.255.252.0A.180.80.76.0 B.180.80.76.255 C.180.80.77.255 D.180.80.79.25512A.SMTP、SMTP、SMTP B.POP3SMTPPOP3C.POP3、SMTP、SMTP D.SMTP、SMTPPOP341～477041.（106ABCDE1035405060200561個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。n（n≥2）42.（13分）假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)，則可共享相同的后綴存儲(chǔ)空間，例如，“l(fā)oading”和“being”的存儲(chǔ)映像如下圖所示。oldastr1oldastr2gnieb^pgnieb^設(shè)str1和str2分別指向個(gè)單所單表頭點(diǎn)，表點(diǎn)構(gòu)為 ，設(shè)計(jì)個(gè)間可能效算出由s1和s2指兩鏈共同綴起位（中符i所結(jié)的置要：C或C++JAVA43.（11）假設(shè)某計(jì)算機(jī)的CPU80MHz，CPI41.5次，主存與Cache16B，Cache99%32MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMACPUCache0.0005%CPU4KBDMA32位，則磁盤(pán)接口平均每秒發(fā)出的DMACPU和DMA41/450ns，則主存能提供的最大帶寬是多少？44.（12）16Cache和指令Cache44部分指令格式，其中RsRdmem表示存儲(chǔ)單元地址，（x）xx的內(nèi)容。題44表指令系統(tǒng)中部分指令格式名稱(chēng)指令的匯編格式指令功能加法指令A(yù)DD Rs，Rd(Rs)+(Rd)->Rd算術(shù)/邏輯左移SHL Rd2*(Rd)->Rd算術(shù)右移SHR Rd(Rd)/2->Rd取數(shù)指令LOAD Rd，mem(mem)->Rd存數(shù)指令STORE Rs，memRs->(mem)該計(jì)算機(jī)采用5段流水方式執(zhí)行指令，各流水段分別是取指（IF）、譯碼/讀寄存器（ID）、執(zhí)行/計(jì)算有效地址（EX）、訪(fǎng)問(wèn)存儲(chǔ)器（M）和結(jié)果寫(xiě)回寄存器（WB），流水線(xiàn)采用“按序發(fā)射，按序完成”方式，沒(méi)有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一寄存器的讀和寫(xiě)操作不能在同一個(gè)時(shí)鐘周期內(nèi)進(jìn)行。請(qǐng)回答下列問(wèn)題。intx，存放在寄存器R1“SHLR1”44x=a+b，x、abint[x]、[a]和[b]44I1LOADR1，[a]I2LOADR2，[b]I3ADDR1，R2I4STORER2，[x]444I3IDI4IFx=x*2+a，xaunsignedint4445.(7分)某請(qǐng)求分頁(yè)系統(tǒng)的頁(yè)面置換策略如下：0532、1521、41。進(jìn)程P<><1,1><3,2><0,4><0,6><0,13><2,14><0,4>46（8分41B240B512B0~7<>504分H192.168.0.8SIP211.68.71.80H與S使用TCP通信時(shí)，在H上捕獲的其中5個(gè)IP分組如題47-a表所示。題47-a表編號(hào)IP分組的前40字節(jié)內(nèi)容（十六進(jìn)制）145000030 019b4000 80061de8 c0a80008 d34447500bd91388 846b41c5 00000000 70024380 5db00000243000030 00004000 31066e83 d3444750 c0a8000813880bd9 e0599fef 846b41c6 701216d0 37e10000345000028 019c4000 80061def c0a80008 d34447500bd91388 846b41c6 e0599ff0 50f04380 2b320000445000038 019d4000 80061dde c0a80008 d34447500bd91388 846b41c6 e0599ff0 50184380 e6550000545000028 684000 3106067a d3444750 c0a8000813880bd9 e0599ff0 846b41d6 501016d0 57d20000回答下列問(wèn)題。47-aIPHTCP47-aIP分組，分析S47-aIPS4047-bIPH少個(gè)路由器？

題47-b表來(lái)自S的分組45000028 684000 4006ecad d3444750 ca7601061388a108 e0599ff0 846b41d6 501016d0 b7d60000注：IP分組頭和TCP段頭結(jié)構(gòu)分別如題47-a圖，題47-b圖所示。題47-a圖 組結(jié)構(gòu)題47-b圖TCP段頭結(jié)構(gòu)計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)綜合試題參考答案一、單項(xiàng)選擇題：每小題2分，共80分。1-5BAABC 6-10CCADA 11-15DDBDD 16-20ACCCD21-25DBCBB 26-30ADABC 31-35ABBCA 36-40BCADD二、綜合應(yīng)用題：41~47小題，共70分。5X-5，XNX這樣，最壞情況下比較的總次數(shù)為：N=(10+35)×4+(40+50+60)×3+200?5=825（2）N（N≥2）個(gè)不等長(zhǎng)升序表的合并策略：N理由：NN-1X-N+1，XNkk① L1，L2；② L1，L2L=|L1-L2|；③ L④ LinkListSearch_First_Common(LinkListL1,LinkListL2){//本算法實(shí)現(xiàn)線(xiàn)性時(shí)間內(nèi)找到兩個(gè)單鏈表的第一個(gè)公共結(jié)點(diǎn)intlen1=Length(L1);,len2=Length(L2);LinkListlongList,shortlist;//LinkListSearch_First_Common(LinkListL1,LinkListL2){//本算法實(shí)現(xiàn)線(xiàn)性時(shí)間內(nèi)找到兩個(gè)單鏈表的第一個(gè)公共結(jié)點(diǎn)intlen1=Length(L1);,len2=Length(L2);LinkListlongList,shortlist;//分別指向較長(zhǎng)和較短的鏈表if(len1>len2){longList=L1->next;shortlist=L2->next;L=len1-len2;//表長(zhǎng)之差}else{longList=L2->next;shortlist=L1->next;L=len2-len1;//表長(zhǎng)之差}While(L--)longList=longList->next;while(longList!=NULL){if(longList==shortList)//同步尋找共同結(jié)點(diǎn)returnlongList;else{longList=longList->next;shortlist=shortlist->next;}}//whilereturnNULL;}算法的時(shí)間復(fù)雜度為O(len1+len2)，空間復(fù)雜度為O(1)。MIPS=CPU主頻6/CPI=80M/4=201.5次,Cache99%Cache=0M1.1=30000（次；）在不使用DMA傳送的情況下，所有主存的存取操作都需要經(jīng)過(guò)CPU，所以主存帶寬至少應(yīng)為。由于頁(yè)式虛擬存儲(chǔ)方式的頁(yè)表始終位于內(nèi)存，則產(chǎn)生缺頁(yè)異常的只能是指令的訪(fǎng)存。每秒產(chǎn)生缺頁(yè)中斷20M/s×1.5×0.0005%=150次。因此平均每秒發(fā)出的DMA請(qǐng)求次數(shù)至少是150×4KB/4B=150K次。優(yōu)先響應(yīng)DMADMA通常連接高速44×4B/50ns=320MB/s。（1）x的機(jī)器碼為[x]補(bǔ)=111111011111B，即指令執(zhí)行前（R1）=FDFFH，右移1位后位1111111011111111B，即指令執(zhí)行后（R1）=FEFFH。4+（5-1）=8I3IDI3I1I2I1I2I3讀寄存器內(nèi)容，所以I3的ID段被阻塞。I4的IF段被阻塞的原因：因?yàn)镮4的前一條指令I(lǐng)3在ID段被阻塞，所以I4的IF段被阻塞。2*xx=x*2+aI1LOADR1，[x]I2