(考試資料下載)清華大學(xué)2006年cs專業(yè)考研試題

清華大學(xué)2006年CS專業(yè)考研試題計(jì)組部分一、填空題1. a,b為兩個(gè)1位2進(jìn)制數(shù)，Carryin為低位進(jìn)位，Carryout為高位進(jìn)位，用and,or寫出帶進(jìn)位的1位加法器的Carryout并化簡(jiǎn)，Carryout=_2. 5段流水線分別為IF,_,EX,_,WB.3. 一個(gè)串行程序可并行部分占%90，規(guī)模不變的情況下，串行程序并行化后加速比不超過(guò)_4. 二進(jìn)制補(bǔ)碼1111 1111 1111 1111 1111 1111 1111 1011化為十進(jìn)制后為_二、判斷題1.CISC計(jì)算機(jī)比RISC計(jì)算機(jī)指令多。2.速度為10MIPS的計(jì)算機(jī)一定比速度為5MIPS的計(jì)算機(jī)快。3.SRAM比DRAM的速度快，成本高。4.SCSI硬盤與SATA硬盤的速度，價(jià)格比較.5.PCI-Express與AGP都可用于顯卡接口6.SPECCPU 2000基準(zhǔn)測(cè)試程序可用于測(cè)I/O性能。7.IEEE 754是計(jì)算機(jī)中的二進(jìn)制整數(shù)算術(shù)標(biāo)準(zhǔn)。8.全相聯(lián)與直接映象Cache的比較9.INTEL P4功率小于10w10.64位CPU一般比32位CPU快一倍11.增加流水線段數(shù)可提高CPU頻率12.VHDL是硬件描述語(yǔ)言。13.EPIC是VLIW的發(fā)展三、簡(jiǎn)答題1.試說(shuō)明為何編譯程序要進(jìn)行如下優(yōu)化for(j=0;j200;j+)for(i=0;i20;i+)Aj=Aj+1;編譯優(yōu)化后for(i=0;i20;i+)for(j=0;j200;j+)Aj=Aj+1;2.硬盤平均尋道時(shí)間為12ms，傳輸速率為10MB/s，磁盤控制器延時(shí)為2ms,則一個(gè)轉(zhuǎn)速為7200r/min的硬盤寫1KB數(shù)據(jù)時(shí)間為多少?3.為什么要設(shè)置二叉分支預(yù)測(cè)指令？畫出2bit轉(zhuǎn)移預(yù)測(cè)的狀態(tài)圖數(shù)據(jù)結(jié)構(gòu)證明題:1 證明在一棵滿二叉樹中分支B與葉子節(jié)點(diǎn)n0滿足關(guān)系 B=2(n0-1)2.證明，完全無(wú)向圖中,兩個(gè)頂點(diǎn)之間簡(jiǎn)單路徑書目為:1 + A(n-2,1) + A(n-2,2) + . + A(n-2,n-2)其中A(m,n)是m取n的排列數(shù)。作圖題:給了一個(gè)Dijkstra無(wú)向連通圖的最小生成樹算法描述，要你根據(jù)該描述作出最小生成樹及并查集的變化。程序填空給了一段排序算法，用靜態(tài)鏈表描述的1 問(wèn)你這是什么排序算法（里面寫著selectsort）2 把挖去的5個(gè)空填上 （發(fā)現(xiàn)只有4個(gè)）程序設(shè)計(jì)題用鏈表表示的多項(xiàng)式1 寫類的描述2 insert算法，如果相同指數(shù)合并，沒(méi)有就插入3 利用insert,給出多項(xiàng)式乘法的算法操作系統(tǒng)1 給出一個(gè)并發(fā)程序的描述:semaphore X1=X2=Y=1;int c1=c2=0;procedure f1:p(X1)if (+c1 = 1) p(Y)v(X1)compute Ap(X1)if (-c1 = 0) v(Y)v(X1)procedure f2:p(X2)if (+c2 = 1) p(Y)v(X2)compute Bp(X2)if (-c2 = 0) v(Y)v(X2)問(wèn)computeA和computeB各自能有多少并發(fā)執(zhí)行，會(huì)不會(huì)出現(xiàn)餓死？2 給出一個(gè)cpu的頻率，使用基于時(shí)間片的輪轉(zhuǎn)隊(duì)列調(diào)度，并給出了參數(shù)。求調(diào)度的效率和響應(yīng)時(shí)間。3 使用多級(jí)頁(yè)表，給出一些參數(shù)，如虛實(shí)地址空間大小、頁(yè)大小、頁(yè)表項(xiàng)大小等，問(wèn):a) 多級(jí)頁(yè)表的優(yōu)點(diǎn)b) 如果頁(yè)表限制在一個(gè)頁(yè)面里，問(wèn)有多少頁(yè)表項(xiàng)？c) 進(jìn)程頁(yè)表占用多少內(nèi)存？4 把一個(gè)UNIX文件卷復(fù)制到另一個(gè)磁盤上，問(wèn):a) UNIX文件卷由哪幾部分組成？b) 只復(fù)制文件數(shù)據(jù)，包括目錄之后，不能訪問(wèn)，為什么？c) 終于搞好了之后，發(fā)現(xiàn)有重復(fù)的硬鏈接，為什么？5 給出了一個(gè)使