全國碩士碩士入學統一考試計算機科學專業基礎綜合試題一、單項選擇題：1～40小題，每題2分，共80分。在每題給出的四個選項中，請選出一項最符合題目規定的。1．若元素a、b、c、d、e、f依次進棧，容許進棧、退棧操作交替進行。但不容許持續三次進行退棧工作，則不也許得到的出棧序列是（D）A.dcebfaB.cbdaefC.bcaefdD.afedcb2．某隊列容許在其兩端進行入隊操作，但僅容許在一端進行出隊操作，則不也許得到的次序是（C）A.bacdeB.dbaceC.dbcaeD.ecbad3．下列線索二叉樹中（用虛線表達線索），符合後序線索樹定義的是（B）A.B.C.D.4.在下列所示的平衡二叉樹中插入關鍵字48後得到一棵新平衡二叉樹，在新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保留的關鍵字分別是（C）A.13，48B.24，48C.24，53D.24，905.在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則數T的葉節點個數是（B）A.41B.82C.113D.1226.對n（n≥2）個權值均不相似的字符構成哈夫曼樹，有關該樹的論述中，錯誤的是（B）A.該樹一定是一顆完全二叉樹B.樹中一定沒有度為1的結點C.樹中兩個權值最小的結點一定是兄弟結點D.樹中任一非葉結點的權值一定不不不小于下一層任一結點的權值7.若無向圖G=（V.E）中含7個頂點，則保證圖G在任何狀況下都是連通的，則需要的邊數至少是（A）A.6B.15C.16D.218.對下圖進行拓撲排序，可以得到不一樣的拓撲序列的個數是（B）A.4B.3C.2D.19.已知一種長度為16的次序表L，其元素按關鍵字有序排列，若采用折半查找法查找一種不存在的元素，則比較次數最多的是（A）A.4B.5C.6D.710.采用遞歸方式對次序表進行迅速排序，下列有關遞歸次數的論述中，對的的是（D）A.遞歸次數與初始數據的排列次序無關B.每次劃分後，先處理較長的分區可以減少遞歸次數C.每次劃分後，先處理較短的分區可以減少遞歸次數D.遞歸次數與每次劃分後得到的分區處理次序無關11.對一組數據（2，12，16，88，5，10）進行排序，若前三趟排序成果如下：（A）第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88則采用的排序措施也許是A.起泡排序B.希爾排序C.歸并排序D.基數排序12.下列選項中，能縮短程序執行時間的措施是（D）Ⅰ提高CPU時鐘頻率，Ⅱ優化數據通過構造，Ⅲ對程序進行編譯優化A.僅Ⅰ和ⅡB.僅Ⅰ和ⅢC.僅Ⅱ和ⅢD.Ⅰ，Ⅱ，Ⅲ13.假定有4個整數用8位補碼分別表達r1=FEH，r2=F2H，r3=90H，r4=F8H，若將運算成果寄存在一種8位寄存器中，則下列運算會發生溢出的是（C）A.r1×r2B.r2×r3C.r1×r4D.r2×r414.假定變量i，f，d數據類型分別為int，float和double（int用補碼表達，float和double分別用IEEE754單精度和雙精度浮點數據格式表達），已知i=785，f=1.5678e3，d=1.5e100.若在32位機器中執行下列關系體現式，則成果為真是（C）（Ⅰ）i==（int）（float）I（Ⅱ）f==（float）（int）f（Ⅲ）f==（float）（double）f（Ⅳ）(d+f)-d==fA.僅Ⅰ和ⅡB.僅Ⅰ和ⅢC.僅Ⅱ和ⅢD.僅Ⅲ和Ⅳ15.假定用若干個2k×4位芯片構成一種8k×8位存儲器，則地址0B1FH所在芯片的最小地址是（D）A.0000HB.0600HC.0700HD.0800H16.下列有關RAM和ROM的論述中，對的的是（A）ⅠRAM是易失性存儲器，ROM是非易失性存儲器ⅡRAM和ROM都采用隨機存取方式進行信息訪問ⅢRAM和ROM都可用作CacheⅣRAM和ROM都需要進行刷新A.僅Ⅰ和ⅡB.僅Ⅱ和ⅢC.僅Ⅰ，Ⅱ，ⅢD.僅Ⅱ，Ⅲ，Ⅳ17.下列命令組合狀況中，一次訪存過程中，不也許發生的是（D）A.TLB未命中，Cache未命中，Page未命中B.TLB未命中，Cache命中，Page命中C.TLB命中，Cache未命中，Page命中D.TLB命中，Cache命中，Page未命中18.下列寄存器中，匯編語言程序員可見的是（B）A.存儲器地址寄存器（MAR）B.程序計數器（PC）C.存儲器數據寄存器（MDR）D.指令寄存器（IR）19.下列不會引起指令流水阻塞的是（A）A.數據旁路B.數據有關C.條件轉移D.資源沖突20.下列選項中的英文縮寫均為總線原則的是（D）A.PCI、CRT、USB、EISAB.ISA、CPI、VESA、EISAC.ISA、SCSI、RAM、MIPSD.ISA、EISA、PCI、PCI-Express21.單級中斷系統中，中斷服務程序執行次序是（A）Ⅰ保護現場Ⅱ開中斷Ⅲ關中斷Ⅳ保留斷點Ⅴ中斷事件處理Ⅵ恢復現場Ⅶ中斷返回A.Ⅰ→Ⅴ→Ⅵ→Ⅱ→ⅦB.Ⅲ→Ⅰ→Ⅴ→ⅦC.Ⅲ→Ⅳ→Ⅴ→Ⅵ→ⅦD.Ⅳ→Ⅰ→Ⅴ→Ⅵ→Ⅶ22.假定一臺計算機的顯示存儲器用DRAM芯片實現，若規定顯示辨別率為1600×1200,顏色深度為24位，幀頻為85HZ,顯示總帶寬的50%用來刷新屏幕，則需要的顯存總帶寬至少約為(D)A.245MbpsB.979MbpsC.1958MbpsD.7834Mbps23.下列選項中，操作S提供的給應用程序的接口是（A）A.系統調用B.中斷C.庫函數D.原語24.下列選項中，導制創進新進程的操作是（C）Ⅰ顧客登陸成功Ⅱ設備分派Ⅲ啟動程序執行A.僅Ⅰ和ⅡB.僅Ⅱ和ⅢC.僅Ⅰ和ⅢD.Ⅰ、Ⅱ、Ⅲ25.設與某資源有關聯的信號量初值為3，目前值為1，若M表達該資源的可用個數，N表達等待該資源的進程數，則M,N分別是（B）A.0，1B.1，0C.1，2D.2，026.下列選項中，減少進程優先權級的合理時機是（A）A.進程的時間片用完B.進行剛完畢Z/0,進入就緒隊列C.進程長期處在就緒隊列中D.就緒從就緒狀態轉為運行態27、進行P0和P1的共享變量定義及其初值為（A）booleanflag[2];intturn=0;flag[0]=faulse;flag[1]=faulse;若進行P0和P1訪問臨界資源的類C代碼實現如下：Voidp0()//進程p0Voidp1()//進程p1{while(TURSE){{while(TURE){Flag[0]=TURE;ture=1;Flag[1]=TURE;turn=0;While(flag[1]＆＆（turn==1）;While(flag[0]＆＆（turn==0）;臨界區；臨界區；Flag[0]=FALSE;Flag[1]=FALSE;}}}}則并發執行進程P0和P1時產生的狀況是（）A不能保證進程互斥進入臨界區，會出現“饑餓”現象B不能保證進程互斥進入臨界區，不會出現“饑餓”現象C能保證進程互斥進入臨界區，會出現“饑餓”現象D能保證進程互斥進入臨界區，不會出現“饑餓”現象28、某基于動態分區存儲管理的計算機，其主存容量為55Mb（初始為空間），采用最佳適配（BestFit）算法，分派和釋放的次序為：分派15Mb,分派30Mb，釋放15Mb，分派8Mb，分派6Mb，此時主存中最大空閑分區的大小是（B）A7MbB9MbC10MbD15Mb頁目錄號頁號頁內偏移量29、某計算機采用二級頁表的分頁存儲管理方式，按字節編制，頁大小為210字節，頁表項大小為2字節，邏輯地址構造為邏輯地址空間大小為216頁，則表達整個邏輯地址空間的頁目錄表中包括表項的個數至少是（B）A64B128C256D51230、設文獻索引節點中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節，若磁盤索引塊和磁盤數據塊大小均為256字節，則可表達的單個文獻最大長度是（C）A33KBB519KBC1057KBD16513KB31、設置目前工作目錄的重要目的是（C）A節省外存空間B節省內存空間C加緊文獻的檢索速度D加緊文獻的讀/寫速度32、當地顧客通過鍵盤登陸系統時，首先獲得鍵盤輸入信息的程序是（B）A命令解釋程序B中斷處理程序C系統調用程序D顧客登陸程序33、下列選項中，不屬于網絡體系構造中所描述的內容是（C）A網絡的層次B每一層使用的協議C協議的內部實現細節D每一層必須完畢的功能34.在下圖所示的采用“存儲—轉發”方式分組的互換網絡中所有鏈路的數據傳播速度為100Mbps，分組大小為1000B，其中分組頭大小20B，若主機H1向主機H2發送一種大小為980000B的文獻，則在不考慮分組拆裝時間和傳播延遲的狀況下，從H1發送到H2接受完為止，需要的時間至少是（A）A.80msB.80.08msC.80.16msD.80.24ms35.某自治系統采用RIP協議，若該自治系統內的路由器R1收到其鄰居路由器R2的距離矢量中包括信息<net1,16>，則也許得出的結論是（A）A.R2可以通過R1抵達net1，跳數為17B.R2可以抵達net1，跳數為16C.R1可以通過R2抵達net1，跳數為17D.R1不能通過R2抵達net136.若路由器R由于擁塞丟棄IP分組，則此時R可向發出該IP分組的源主機發送的ICMP報文獻的類型是（C）A.路由重定向B.目的不可達C.源克制D.超時37.某網絡的IP地址空間為192.168.5.0/24采用長子網劃分，子網掩碼為255.255.255.248.則該網絡的最大子網個數，每個子網內的最大可分派地址個數為（B）A.32，8B.32，6C.8，32D.8，3038.下列網絡設備中，可以克制網絡風暴的是（C）Ⅰ中繼器Ⅱ集線器Ⅲ網橋Ⅳ路由器A.僅Ⅰ和ⅡB.僅ⅢC.僅Ⅲ和ⅣD.僅Ⅳ39.主機甲和主機乙之間已建立一種TCP連接，TCP最大段長度為1000字節，若主機甲的目前擁塞窗口為4000字節，在主機甲向主機乙持續發送2個最大段後，成功收到主機乙發送的第一段確實認段，確認段中通告的接受窗口大小為字節，則此時主機甲還可以向主機乙發送的最大字節數是（A）A.1000B.C.3000D.400040.假如當地區名服務無緩存，當采用遞歸措施解析另一網絡某主機域名時，顧客主機當地區名服務器發送的域名祈求條數分別為（A）A.1條，1條B.1條，多條C.多條，1條D.多條，多條二、綜合應用題：41~47小題，共70分。41．（10分）將關鍵字序列（7、8、30、11、18、9、14）散列存儲到散列列表中，散列表的存儲空間是一種下標從0開始的一種一維數組散列函數維：H（key）=(key×3)MODT，處理沖突采用線性探測再散列法，規定裝填（載）因子為0.7問題：（1）請畫出所構造的散列表；（2）分別計算等概率狀況下，查找成功和查找不成功的平均查找長度。解答：（1）由裝載因子0.7，數據總數7個-->存儲空間長度為10-->P=10。因此：構造的散列表為：H（7）=（7*3）MOD10=1。。。。。。012345678930714118189查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.242、（13分）設將n（n?1）個整數寄存到一維數組R中。試設計一種在時間和空間兩方面盡量有效的算法，將R中保有的序列循環左移P（0QUOTEPQUOTEn）個位置，即將R中的數據由（X0X1……Xn-1）變換為（XPXp+1……Xn-1X0X1……Xp-1）規定：（1）、給出算法的基本設計思想。（2）、根據設計思想，采用C或C++或JAVA語言描述算法，關鍵之處給出注釋。（3）、闡明你所設計算法的時間復雜度和空間復雜度解答：（1）前P個數依次進隊，while(i<n-p)A[i]=A[i+p]；P個數依次出隊，進入數組末尾（2）詳細程序略（3）時間復雜度O(N)，空間復雜度O(P)43、（11分）某計算機字長為16位，主存地址空間大小為128KB，按字編址，采用字長指令格式，指令名字段定義如下：151211650OPMsRsMdRd源操作數目的操作數轉移指令采用相對尋址方式，相對偏移是用補碼表達，尋址方式定義如下：Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數=（Rn）001B寄存器間接（Rn）操作數=（（Rn））010B寄存器間接、自增（Rn）+操作數=（（Rn））,（Rn）+1→Rn011B相對D（Rn）轉移目的地址=（ＰＣ）＋（Rn）注：（X）表達有儲蓄地址X或寄存器X的內容，請回答問題：（1）、該指令系統最多可有多少條指令？該計算機最多有多少個通用寄存器？存儲器地址寄存器（MAR）和存儲器數據寄存器（ＭＤＲ）至少各需多少位？（2）、轉移指令的目的地址范圍是多少？（3）、若操作碼００１０Ｂ表達加法操作（助記符為ａｄｄ），寄存器Ｒ４和Ｒ５的編號分別為１００Ｂ和１０１Ｂ，Ｒ４的內容為１２３４Ｈ，Ｒ５的內容為５６７８Ｈ，地址１２３４Ｈ中的內容為５６７８Ｈ，地址５６７８Ｈ中的內容為１２３４Ｈ，則匯編語言為ａｄｄ（Ｒ４），（Ｒ５）＋（逗號前為源操作數，逗號後為目的操作數）對應的機器碼是什么（用拾六進制表達）？該指令執行後，哪些寄存器和存儲單元的內容會變化？變化後的內容是什么？解答：該題的考點是指令系統設計，注意操作碼位數與指令條數的關系，地址碼與寄存器數的關系，指令字長與MDR的關系，存儲容量與MAR的關系；注意補碼計算的偏移地址。44、（12分）某計算機的主存地址空間大小為256MB，按字節編址，指令Cache和數據Cache分離，均有8個Cache行，每個Cache行大小為64ＭＢ，數據Cache采用直接映射方式，既有兩個功能相似的程序Ａ和Ｂ，其偽代碼如下所示：程序Ｂ：ｉｎｔａ［２５６］［２５６］；程序Ｂ：ｉｎｔａ［２５６］［２５６］；………ｉｎｔＳｕｍ＿ａｒｒａｙ２（）｛ｉｎｔｉ，ｊ，Ｓｕｍ＝０；ｆｏｒ（ｊ＝０；ｊQUOTE２５６；ｊ＋＋）ｆｏｒ（ｉ＝０；ｉQUOTE２５６；ｉ＋＋）Ｓｕｍ＋＝ａ［ｉ］［ｊ］；ｒｅｔｕｒｎＳｕｍ；｝程序Ａ：ｉｎｔａ［２５６］［２５６］；………ｉｎｔＳｕｍ＿ａｒｒａｙ１（）｛ｉｎｔｉ，ｊ，Ｓｕｍ＝０；ｆｏｒ（ｉ＝０；ｉQUOTE２５６；ｉ＋＋）ｆｏｒ（ｊ＝０；ｊQUOTE２５６；ｊ＋＋）Ｓｕｍ＋＝ａ［ｉ］［ｊ］；ｒｅｔｕｒｎＳｕｍ；｝假定int類型數據用32位補碼表達，程序編譯時i,j,sum均分派在寄存器中，數組a按行優先方式寄存，其地址為320（拾進制數）。請回答問題，規定闡明理由或給出計算過程。（1）、若不考慮用于Cache一致性維護和替代算法的控制位，則數據Cache的總容量為多少？（2）、數組元素a[0][31]和a[1][1]各自所在的主存塊對應的Cache行號分別是多少（Cache行號從0開始）？（3）、程序A和B的數據訪問命令中率各是多少？哪個程序的執行時間更短？解答：考點：Cache容量計算，直接映射方式的地址計算，以及命中率計算（行優先遍歷與列優先遍歷命中率差異很大）45．（7分）假設計算機系統采用CSCAN（循環掃描）磁盤調度方略，使用2KB的內存空間記錄16384個磁盤塊的空閉狀態.（1）、請闡明在上述條件下怎樣進行磁盤塊空閑狀態管理。（2）、設某單面磁回旋轉速度為每分鐘6000轉，每個磁道有100個扇區，相臨磁道間的平均移動時間為1ms。若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動（如下圖所示），磁道號祈求隊列為50，90，30，120，對祈求隊列中的每個磁道需讀取1個隨機分布的扇區，則讀完這個扇區點共需要多少時間？規定給出計算過程。隨機分布的某扇區隨機分布的某扇區100號磁道0號磁道磁頭運動方向解答：（1）使用位示圖法，每一位表達一種磁盤快與否空閑；（2）每分鐘6000轉，轉1圈需要0.01秒，通過一種扇區需要0.0001秒。100-->120：20*1ms（尋道）+0.01*0.2s（尋扇）+0.0001s（讀一種扇區）=20ms+2ms+0.1ms0-->30：30*1ms（尋道）+0.01*0.2s（尋扇）+0.0001s（讀一種扇區）30-->50：20*1ms（尋道）+0.01*0.2s（尋扇）+0.0001s（讀一種扇區）50-->90：40*1ms（尋道）+0.01*0.2s（尋扇）+0.0001s（讀一種扇區）Sum=110ms+（2ms+0.1ms）*4=118.4ms46.（8分）設某計算機的邏輯地址空間和物理地址空間均為64KB，按字節編址。若某進程最多需要6頁（Page）數據存儲空間，頁的大小為1KB，操作系統采用固定分派局部置換方略為此進程分派4個頁框（PageFrame）。頁號頁框號裝入時刻訪問位071301142301222001391601當該進程執行屆時刻260時，要訪問邏輯地址為17CAH的數據。請回答問題：（1）、該邏輯地址對應的頁號是多少？（2）、若采用先進先出（FIFO）置換算法，該邏輯地址對應的物理地址是多少？規定給出計算過程。（