清華08計算機考研試題詳解

標(biāo)準(zhǔn)實用《數(shù)據(jù)結(jié)構(gòu)》一、選擇題123給了一序列比如散列函數(shù)是H(key)=key%11.一問成功時的平均搜索長度二問不成功的平均搜索長度哪種數(shù)據(jù)結(jié)構(gòu)，從某一個結(jié)點到根結(jié)點的路徑序列組成一個降序排列a.b.最大堆c.最小堆d還有一個題是關(guān)于關(guān)鍵路徑的，答案選項是49/B-C\A /F\\\D-E H\G/6什么是數(shù)據(jù)結(jié)構(gòu)？ABC定義在一個數(shù)據(jù)集合上的屬性和操作D7高度為h的完全二叉樹，一共有多少種？AB2^(h-1)CD二、證明題什么樣的有向無環(huán)圖有唯一的拓?fù)溆行蛐蛄校⒆C明。三、計算題有n個結(jié)點的二叉樹最大高度，最小高度分別是多少？文案大全標(biāo)準(zhǔn)實用一棵有n個結(jié)點的樹有m個葉節(jié)點，如果用做兄弟-右子女表示法，則有多少個結(jié)點的右指針域為空?霍夫曼樹中，有n個葉結(jié)點，問一共有多少個結(jié)點?有n個結(jié)點的樹的不同排列形式有多少種。四、給定一個文件有1,000,000個記錄，每個200B，記錄中關(guān)鍵碼大小50B，頁面大小為4kB，現(xiàn)以B+樹（最大關(guān)鍵碼復(fù)刻）方式組織該文件，盡量使每結(jié)點擁有盡可能多的關(guān)鍵碼，已知每個指針占用5B。問1.該B+樹有多少個葉結(jié)點，共有多少層；2.該B+樹共有多少個索引結(jié)點；3.每次搜索要讀盤多少次？五、算法設(shè)計題給定A[n],設(shè)計一個算法，重排數(shù)組，使得奇數(shù)都在數(shù)組前半部分，偶數(shù)都在后半部分。要求時間復(fù)雜度O(n)。函數(shù)頭：voidexstorage(intA[],intn)重新設(shè)計一個直接選擇算法函數(shù)，采用遞歸方式。對一個大小為n的數(shù)組，初始的調(diào)用方式為：selectsort(A,0,n-1) 。函數(shù)頭：voidselectsort(intA[],intleft,intright)《操作系統(tǒng)》一、簡答題1. 磁盤I/O操作的時間組成部分，闡述優(yōu)化磁盤調(diào)度策略的目標(biāo)。文案大全標(biāo)準(zhǔn)實用什么是內(nèi)碎片，外碎片。內(nèi)核線程和用戶線程的區(qū)別？各自有什么特點。什么是內(nèi)核模式和用戶模式？為什么系統(tǒng)要設(shè)置這兩種模式什么是上下文（context),請說出它的組成，系統(tǒng)是如何實行多個進(jìn)程之間調(diào)度的，具體過程是怎樣的。二、計算題已知系統(tǒng)為32位實地址，采用48位虛擬地址，頁面大小4kB，頁表項大小為8個字節(jié)；每段最大為4G。系統(tǒng)將采用多少級頁表，頁內(nèi)偏移多少位？假設(shè)系統(tǒng)采用一級頁表，TLB命中率為98%，TLB訪問時間10ns，內(nèi)存訪問時間100ns，并假設(shè)當(dāng)TLB訪問失敗時才開始訪問內(nèi)存，問平均頁面訪問時間多少？如果是二級頁表,頁面平均訪問時間是多少？每用戶最多可以有多少個段？段內(nèi)采用幾級頁表？如果要滿足訪問時間<=120ns,那么命中率需要至少多少?三、pv操作題給定一個全局?jǐn)?shù)組 a[n] b[n]，然后是T1~Tn-1共n-1個線程，線程為代碼如下Ti(){a=g(a,a[i-1]);b=f(a);}其中g(shù)和f函數(shù)的作用是通過輸入?yún)?shù)，進(jìn)行一系列運算后返回。相當(dāng)于 Ti 以文案大全標(biāo)準(zhǔn)實用a和a[i-1] 為輸入?yún)?shù)，a和b為輸出。要求使用pv原語，實現(xiàn)T1～Tn-1的并發(fā)互斥，盡量保證最大限度的并發(fā)。(a[i-1] 為Ti-1線程的結(jié)果,)四、進(jìn)程同步問題假設(shè)當(dāng)前處于非搶占調(diào)度策略，進(jìn)程只有兩種方式可以放棄cpu，一個是主動調(diào)用系統(tǒng)調(diào)度函數(shù)yield()，此時進(jìn)程主動放棄cpu；另一個方式是當(dāng)進(jìn)程執(zhí)行I/O操作時，系統(tǒng)將調(diào)度下一個進(jìn)程。試分析如下三種進(jìn)程對，何時會出現(xiàn)不符合下列原則，并說明原因：1）空閑則入2)有限等待3）保證互斥。第一種：Thread1(){yield();----criticalsection-----g=g+b;f=g-a;//這部分確切的語句想不起來了，但不影響。只要記得臨界區(qū)不能被打斷。----criticalsection-----}Thread2(){----criticalsection-----g=g+b;f=g-a;----criticalsection-----}文案大全標(biāo)準(zhǔn)實用第二種：Thread1(){yield();----criticalsection-----g=g+b;f=g-a;----criticalsection-----}Thread2(){----criticalsection-----g=g+b;f=g-a;----criticalsection-----yield();}第三種：Thread1(){yield();----criticalsection-----g=g+b;fstring=printf( ??); // 調(diào)用I/O;文案大全標(biāo)準(zhǔn)實用f=g-a;----criticalsection-----}Thread2(){yield();----criticalsection-----g=g+b;f=g-a;----criticalsection-----}五文件操作題很長，大意如下給定兩種文件系統(tǒng)，分別采用FAT方式和索引方式組織文件結(jié)構(gòu)。然后給出緩沖區(qū)，緩沖區(qū)大小為4個數(shù)據(jù)塊，使用LRU替換算法，并假設(shè)所有操作均不涉及內(nèi)存或cache，只考慮緩沖區(qū)。并聲明只有如下兩種狀態(tài)才會刷新緩沖區(qū)：a）緩沖區(qū)沖突b)系統(tǒng)主動調(diào)用一個同步函數(shù)sync()，同步緩沖區(qū)。然后給出當(dāng)前根目錄文件共有10塊，分別分布在緩沖區(qū)的位置，緩沖區(qū)一個24個數(shù)據(jù)塊。用一個表格把它們對應(yīng)起來了。然后就是一個超大的表格，給出一些列操作，例如讀第幾個數(shù)據(jù)塊，并偏移多少字節(jié)之類的，然后讓填寫在fat和索引方式下讀盤次數(shù)，寫盤次數(shù)和當(dāng)前緩沖區(qū)內(nèi)容。ps：本題實在記不清了，光讀題都要十分鐘文案大全標(biāo)準(zhǔn)實用file 表存放在第23塊(第一列都是類似一下的語句 )從偏移量100字節(jié)處讀入50字節(jié)從偏移量1000字節(jié)處讀入20字節(jié)從偏移量***字節(jié)處讀入**字節(jié)調(diào)用sync()FAT索引方式讀次數(shù) 寫次數(shù) 緩存內(nèi)容 讀次數(shù) 寫次數(shù) 緩存內(nèi)容從偏移量100字節(jié)處讀入50字節(jié)文案大全標(biāo)準(zhǔn)實用《計算機原理》一、填空題1. 寫出-1.125的IEEE75432位標(biāo)準(zhǔn)的浮點數(shù)。2.控制器部件由哪五部分組成__________________________；3.五級指令流水線哪五部分組成IF,_______________________;二、下述指令集能否用單字指令（字長為12位）實現(xiàn)，包括：a4條三寄存器指令b255條單寄存器指令c16條0寄存器指令三、cache和虛擬地址相關(guān)的計算題一個標(biāo)記位Tag,一個有效位,一個臟位(Dirty),塊號(Offset),采用全相連方式,為什么要采用全相連方式 ?畫圖表示標(biāo)記，塊號，塊內(nèi)地址。2.cache的存儲效率 （即除掉標(biāo)記位，access位，dirty 位）。四、輸入輸出方式都有哪幾種？請簡要敘述各自特點。五、1在虛擬頁式系統(tǒng)中，給了虛擬地址的位數(shù)大概48位，可用的最大主存空間位128GB，每頁大小4KB。問了四個問題，大概有涉及的多級頁表，訪存的平均時間，命中率等等。(假設(shè)沒有TLB存在)系統(tǒng)中為什么要設(shè)計TLB畫圖表示出虛擬地址到真實地址的轉(zhuǎn)化--文案大全標(biāo)準(zhǔn)實用2008年清華大學(xué)計算機系上機題（回憶版）一、輸入：兩行第一行：M和N第二行：XM和N是一個十進(jìn)制數(shù)，M和N都在[2-36]之間，X是一個M進(jìn)制數(shù)，X在[1-2*10^19]輸出：一行第一行：現(xiàn)在要求你將 M進(jìn)制數(shù)X轉(zhuǎn)換成N進(jìn)制數(shù)輸出輸入一：10F輸出一：二、按照手機鍵盤輸入字母的方式，計劃所花費的時間如：a,b,c 都在“1”鍵上，輸入a只需要按一次，輸入 c需要連續(xù)按三次。如果連續(xù)兩個字符不在同一個按鍵上，則可直接按，如：ad需要按兩下，kz需要按6下如果連續(xù)兩字符在同一個按鍵上，則兩個按鍵之間需要等一段時間，如ac，在按了a之后，需要等一會兒才能按C?，F(xiàn)在假設(shè)每按一次需要花費一個時間段，等待時間需要花費兩個時間段?，F(xiàn)在給出一串字符，需要計劃出它所需要花費的時間。輸入一：bob輸出一：7輸入二：www輸出二：7考完筆試，將試題回憶了出來。希望能有利于后人，也算是對前人給予的幫助的一種回報吧。（此資料不得被任何人以任何形式販賣！請賣考研資料者自律。 ）下面的是人工智能和多媒體技術(shù)的試題。====人工智能====一、對下圖所示博弈樹進(jìn)行α -β剪枝，標(biāo)明各結(jié)點的倒推值及何處發(fā)生剪枝。（見附圖1。數(shù)值不準(zhǔn)，僅作參考。）文案大全標(biāo)準(zhǔn)實用二、對狀態(tài)空間圖進(jìn)行搜索，標(biāo)出下述算法的擴展結(jié)點序列和求得的解路徑。序列和解路徑用字母串表示，如SABC。（見附圖2。數(shù)值不準(zhǔn)，僅作參考。）寬度優(yōu)先搜索；深度優(yōu)先搜索；3.A算法。其中各節(jié)點旁標(biāo)記的是該節(jié)點的h值，路徑上的數(shù)字表示該路徑的耗散值。三、請回答下列問題：α-β剪枝的原理，即為什么可以α-β剪枝。模擬退火算法的特點。簡述遺傳算法的過程。=====多媒體=====一、什么是多媒體技術(shù)（定義）？其關(guān)鍵技術(shù)是什么？二、寫出音頻差分編碼(DPCM)的原理。列舉參數(shù)編碼的兩個國際標(biāo)準(zhǔn)，說明它們的編碼參數(shù)和數(shù)據(jù)率。三、量化方法的分類？某均勻量化器的輸出為L階，輸出編碼位數(shù)n位。則已知L的話，n的值是多少？已知n的話，L的值為多少？四、信息的量如何度量？離散信源的無損編碼的理論極限 （好像是這么寫的）是什么？已知某信源的四個符號的概率分別為： a1-0.5 ，a2-0.2412 ，a3-0.1702 ，a4-0.0886（數(shù)值記得不太準(zhǔn)），求信源的Huffman編碼，計算信源的熵以及編碼的平均碼長。五、基于內(nèi)容檢索的多媒體數(shù)據(jù)庫由哪些部分組成？請描述基于內(nèi)容檢索的工作過程。================另外，這里對考應(yīng)用方向的學(xué)弟學(xué)妹們有些建議：筆試四選二里選人智和多媒體。據(jù)我所知應(yīng)用方向的大多數(shù)人都選的是這兩科。其他的兩科比較難。如果你四科都一樣是沒學(xué)過的話，AI和MM還是比較容易看懂的。去網(wǎng)上找到“計算機系網(wǎng)絡(luò)課堂”這套課件，里面有人智和多媒體，還有信號處理原理的課件。仔細(xì)地做做期末試題中跟歷年復(fù)試題相近的題。大多數(shù)真題是從這里改編的。在本版的精華區(qū)里可以找到 05至07年歷年的應(yīng)用方向筆試題目，這些試題具有文案大全標(biāo)準(zhǔn)實用很大的參考價值。為了節(jié)省大家的時間，這里附上歷年試題回憶的原帖。排版有些混亂，需要的人自己整理吧。祝后來的學(xué)弟學(xué)妹們考試順利。首先要非常感謝knightma，是knightma去年的辛勤勞動--復(fù)試題目回憶，為大家今年的復(fù)試準(zhǔn)備做出了巨大的幫助。為了回報一下之前的牛人和回報新水木，我也回憶一下題目吧。我考的人智和多媒體。題目基本上跟去年一樣，多媒體多了個量化處理的原理和計算。其他的都沒變。人工智能有一點變化。題目總共才三道題，第一道是給出了8數(shù)碼問題的一個h函數(shù)，求證單調(diào)，然后再用A*求出最優(yōu)解，畫圖很麻煩。第二題是謂詞的歸結(jié)題，較繁，不僅要反演證明，還要用修改證明樹求出一個結(jié)果。第三題是名詞解釋四選二：遺傳算法，模擬退火，神經(jīng)網(wǎng)絡(luò)，專家系統(tǒng)。今年所有的方向都考上機，時間也比去年少了半個小時，題目我放在了附件里，照著拿出來的題目敲到了word文檔里。第一題5個測試數(shù)據(jù)，第二題8個，第三題7個。每個測試數(shù)據(jù)5分。編程環(huán)境在附件文檔里有說明。不用vc6.0也可以用.net2005.終于塵埃落定，可以閑下心來寫點東西。想想自己也在考研版得益于前人的回憶，這次自己也回憶一篇，雖然價值不是很大，但聊表心意了。希望有人用得著計算機的老師特別懶，今年的AI，MM題和去年比有70分一模一樣，因為他們不把這個當(dāng)成什么大不了的事，所以抓到竅門可以少走歪路。人智用書是馬少平的，多媒體用高教版鐘玉琢的（千萬表像我，開始選了林福宗的，近似白看）?？梢哉业骄W(wǎng)絡(luò)課堂的一定要下來看看，都是從上面的的幾套卷子和課后習(xí)題里挑。人智部分：一,4個問答（10分）1,產(chǎn)生式系統(tǒng)的三要素2，正向演繹系統(tǒng)中， 如何判斷是否一致解3，8數(shù)碼問題，找出一個滿足單調(diào)條件的 h，證明為何滿足單調(diào)條件文案大全標(biāo)準(zhǔn)實用4，忘了，二（15分）,圖1所示博弈樹，按從左到右的順序進(jìn)行α-β剪枝搜索，試標(biāo)明各生成節(jié)點的到推值，何處發(fā)生剪枝，及應(yīng)選擇的走步。三（15分），某問題的狀態(tài)空間圖如圖2所示，其中括號內(nèi)標(biāo)明的是各節(jié)點的