初試-17年912回憶版3擴(kuò)充

判斷1）若T(n)=a>0，對于()

+??(1)，則不管a多大，總有T(n)=O(lognTn=T(2?)即使不優(yōu)化next[]數(shù)組，KMP?)完全二叉堆的時(shí)間復(fù)雜度為?)?)?)?)最優(yōu)PFC兩不同深度互換后不是最優(yōu)選擇就地算法是指T(n)=（A.O(1)B.O(n)C.忘了不重要DA.加號B.減號C.乘號D.除號E.乘方F.階乘?)對于長度為mgs[0]=0

C.

D.?)一個(gè)右側(cè)路徑長度為k（）為（A.至少；2??B.至少；2??+11C.至多；2??D.至多；2??+1是“兩次構(gòu)造的堆相同”的（）A.充分不必要條件B.必要不充分條件C.充分必要條件D.?)一個(gè)具有20177階B-樹，若根節(jié)點(diǎn)常駐內(nèi)存，則一次查找最多進(jìn)行（）I/OA.7B.6C.5標(biāo)記 B.十 C. D.?)某個(gè)的逆波蘭表達(dá)式會輸出什么?)單峰向量（單峰向量定義為A[0n)，其中前綴{a0a1ak}嚴(yán)格遞增，后綴{ak+1ak+2an-1}嚴(yán)格遞減。1）設(shè)計(jì)算法在O(logn)的時(shí)間內(nèi)找到最大值所在位置k。最大子序列和求一個(gè)向量A[0n)中和最大的子序列。1）說明你的算法。分，蠻力算法不得分（因?yàn)槠鋾r(shí)間復(fù)雜度為O(n3)））?)Cache和主存的方式有（）、（）和（）201732（）（162017.0IEEE（）（16LWR1(0)R2SUBR3R1R4ORR7R1R8???R9R1一．填空 ，分子優(yōu)先級倒置 任務(wù) 任務(wù)搶二．判斷structPage*p=le2page(le,調(diào)用了幾個(gè)宏命令，是什么意思mutex//信號量，初值為1while{}六．InX86-32CPU使用分頁管理，每頁4KB，邏輯地址格式，這種CPU最多支持4GB內(nèi)存。64GB644KB。試設(shè)計(jì)邏輯地址格式，使其可以在支持物理內(nèi)存擴(kuò)展技術(shù)的X86-32CPU上運(yùn)行。（4’） 22 12 pagecategory 一．選擇?.適用定理的Ⅰ光 Ⅱ.同軸電 30001.544Mbps64n到收到確認(rèn)需要16微秒，為了使傳輸率盡量大，序號應(yīng)至少有（）位。 B.報(bào) 二．網(wǎng)橋題，填轉(zhuǎn)，和王道上的一道原題幾乎一樣。三．（10’）兩個(gè)路由器R1、R2，R1的e0端口著局域網(wǎng)LAN1，R2的e0端口連接著局域網(wǎng)LAN2，R1的e1端口連接著R2的e1端口。主機(jī)A在LAN1內(nèi)，主機(jī)B在LAN2內(nèi)。A~R1B12BR1~R2512B12B頭部，R2~B的網(wǎng)段最多容納912B，包括12B的頭部。現(xiàn)在有IP地址161.111.1.0/24分給這些網(wǎng)，包括R1和R2的兩個(gè)端口，問該如何分配，才能使LAN1LAN2IPLAN1、LAN2IP空間，R1、R2A900B，TCP20B20BIPIdentificationXIPA~R1，R1~R2，R2~B上傳輸時(shí)，分組的Totallength、Identification、