清華08計(jì)算機(jī)考研試題

1、數(shù)據(jù)結(jié)構(gòu)                 一、選擇題 1 2 3 給了一序列比如.9.3.散列函數(shù)是H(key)=key%11.一問(wèn)成功時(shí)的平均搜索長(zhǎng)度 二問(wèn)不成功的平均搜索長(zhǎng)度 4 哪種數(shù)據(jù)結(jié)構(gòu)，從某一個(gè)結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑序列組成一個(gè)降序排列      a.  b.最大堆 c.最小堆 d5 還有一個(gè)題是關(guān)于關(guān)鍵路徑的，答案選項(xiàng)是49   /B -C A      

2、;/F   D-E     H        G/6  什么是數(shù)據(jù)結(jié)構(gòu)？ A  B  C定義在一個(gè)數(shù)據(jù)集合上的屬性和操作 D 7 高度為h的完全二叉樹(shù)，一共有多少種？A  B 2(h-1)  C  D 二、證明題 1. 什么樣的有向無(wú)環(huán)圖有唯一的拓?fù)溆行蛐蛄?，并證明。三、計(jì)算題 1 有n個(gè)結(jié)點(diǎn)的二叉樹(shù)最大高度，最小高度分別是多少？ 2 一棵有n個(gè)結(jié)點(diǎn)的樹(shù)有m

3、個(gè)葉節(jié)點(diǎn)，如果用做兄弟-右子女表示法，則有多少個(gè)結(jié)點(diǎn)的右指針域?yàn)榭? 3 霍夫曼樹(shù)中，有n個(gè)葉結(jié)點(diǎn)，問(wèn)一共有多少個(gè)結(jié)點(diǎn)? 4 有n個(gè)結(jié)點(diǎn)的樹(shù)的不同排列形式有多少種。 四、給定一個(gè)文件有1,000,000個(gè)記錄，每個(gè)200B，記錄中關(guān)鍵碼大小50B，頁(yè)面大小為4kB，現(xiàn)以B+樹(shù)（最大關(guān)鍵碼復(fù)刻）方式組織該文件，盡量使每結(jié)點(diǎn)擁有盡可能多的關(guān)鍵碼，已知每個(gè)指針占用5B。      問(wèn)1.該B+樹(shù)有多少個(gè)葉結(jié)點(diǎn)，共有多少層；2.該B+樹(shù)共有多少個(gè)索引結(jié)點(diǎn)；3.每次搜索要讀盤(pán)多少次？ 五、算法設(shè)計(jì)題 1.給定An,設(shè)計(jì)一個(gè)算法，重排數(shù)組，使得奇數(shù)都在數(shù)組前半部分，

4、偶數(shù)都在后半部分。要求時(shí)間復(fù)雜度O(n)。   函數(shù)頭：void exstorage(int A, int n) 2.重新設(shè)計(jì)一個(gè)直接選擇算法函數(shù)，采用遞歸方式。對(duì)一個(gè)大小為n的數(shù)組，初始的調(diào)用方式為：selectsort(A, 0, n-1)。   函數(shù)頭：void selectsort(int A,int left, int right) 操作系統(tǒng) 一、簡(jiǎn)答題 1. 磁盤(pán)I/O操作的時(shí)間組成部分，闡述優(yōu)化磁盤(pán)調(diào)度策略的目標(biāo)。 2. 什么是內(nèi)碎片，外碎片。3. 內(nèi)核線程和用戶線程的區(qū)別？各自有什么特點(diǎn)。 4. 什么是內(nèi)核模式和用戶模式？為什么系統(tǒng)要設(shè)置

5、這兩種模式 5. 什么是上下文（context),請(qǐng)說(shuō)出它的組成，系統(tǒng)是如何實(shí)行多個(gè)進(jìn)程之間調(diào)度的，具體過(guò)程是怎樣的。二、計(jì)算題 已知系統(tǒng)為32位實(shí)地址，采用48位虛擬地址，頁(yè)面大小4kB，頁(yè)表項(xiàng)大小為8個(gè)字節(jié)；每段最大為4G。 1. 系統(tǒng)將采用多少級(jí)頁(yè)表，頁(yè)內(nèi)偏移多少位？ 2. 假設(shè)系統(tǒng)采用一級(jí)頁(yè)表，TLB命中率為98%，TLB訪問(wèn)時(shí)間10ns，內(nèi)存訪問(wèn)時(shí)間100ns，并假設(shè)當(dāng)TLB訪問(wèn)失敗時(shí)才開(kāi)始訪問(wèn)內(nèi)存，問(wèn)平均頁(yè)面訪問(wèn)時(shí)間多少？ 3. 如果是二級(jí)頁(yè)表,頁(yè)面平均訪問(wèn)時(shí)間是多少？ 4. 每用戶最多可以有多少個(gè)段？段內(nèi)采用幾級(jí)頁(yè)表？ 5.如果要滿足訪問(wèn)時(shí)間<=120ns, 那么命中率需要

6、至少多少?三、pv操作題 給定一個(gè)全局?jǐn)?shù)組an bn，然后是T1Tn-1 共n-1個(gè)線程，線程為代碼如下 Ti() a=g(a,ai-1); b=f(a); 其中g(shù)和f函數(shù)的作用是通過(guò)輸入?yún)?shù)，進(jìn)行一系列運(yùn)算后返回。相當(dāng)于Ti 以a和ai-1為輸入?yún)?shù)，a和b為輸出。 要求使用pv原語(yǔ)，實(shí)現(xiàn)T1Tn-1的并發(fā)互斥，盡量保證最大限度的并發(fā)。 (ai-1為T(mén)i-1線程的結(jié)果,)四、進(jìn)程同步問(wèn)題 假設(shè)當(dāng)前處于非搶占調(diào)度策略，進(jìn)程只有兩種方式可以放棄cpu，一個(gè)是主動(dòng)調(diào)用系統(tǒng)調(diào)度函數(shù)yield()，此時(shí)進(jìn)程主動(dòng)放棄cpu；另一個(gè)方式是當(dāng)進(jìn)程執(zhí)行I/O操作時(shí)，系統(tǒng)將調(diào)度下一個(gè)進(jìn)程。試分析如下三種進(jìn)程對(duì)，

7、何時(shí)會(huì)出現(xiàn)不符合下列原則，并說(shuō)明原因：1）空閑則入 2)有限等待 3）保證互斥。 第一種： Thread1()    yield();    -critical section-    g=g+b;    f=g-a;             /這部分確切的語(yǔ)句想不起來(lái)了，但不影響。只要記得臨界區(qū)不能被打斷。    -critical section- Thread2()    -critical

8、 section-    g=g+b;    f=g-a;                -critical section- 第二種： Thread1()    yield();    -critical section-    g=g+b;    f=g-a;              

9、;  -critical section-   Thread2()    -critical section-    g=g+b;    f=g-a;                -critical section-    yield();   第三種： Thread1()    yield();    -critical s

10、ection-    g=g+b;    fstring=printf() ;            / 調(diào)用I/O;    f=g-a;                -critical section-   Thread2()    yield();    -critical section-

11、   g=g+b;    f=g-a;                -critical section-   五 文件操作 題很長(zhǎng)，大意如下 給定兩種文件系統(tǒng)，分別采用FAT方式和索引方式組織文件結(jié)構(gòu)。然后給出緩沖區(qū)，緩沖區(qū)大小為4個(gè)數(shù)據(jù)塊，使用LRU替換算法，并假設(shè)所有操作均不涉及內(nèi)存或cache，只考慮緩沖區(qū)。 并聲明只有如下兩種狀態(tài)才會(huì)刷新緩沖區(qū)：a）緩沖區(qū)沖突 b)系統(tǒng)主動(dòng)調(diào)用一個(gè)同步函數(shù)sync()，同步緩沖區(qū)。然后給出當(dāng)前

12、根目錄文件共有10塊，分別分布在緩沖區(qū)的位置，緩沖區(qū)一個(gè)24個(gè)數(shù)據(jù)塊。用一個(gè)表格把它們對(duì)應(yīng)起來(lái)了。 然后就是一個(gè)超大的表格，給出一些列操作，例如讀第幾個(gè)數(shù)據(jù)塊，并偏移多少字節(jié)之類(lèi)的，然后讓填寫(xiě)在fat和索引方式下讀盤(pán)次數(shù)，寫(xiě)盤(pán)次數(shù)和當(dāng)前緩沖區(qū)內(nèi)容。 ps：本題實(shí)在記不清了，光讀題都要十分鐘 file表存放在第23塊(第一列都是類(lèi)似一下的語(yǔ)句)從偏移量100字節(jié)處讀入50字節(jié)從偏移量1000字節(jié)處讀入20字節(jié)從偏移量*字節(jié)處讀入*字節(jié)調(diào)用sync()FAT索引方式讀次數(shù) 寫(xiě)次數(shù) 緩存內(nèi)容 讀次數(shù)  寫(xiě)次數(shù)  緩存內(nèi)容從偏移量100字節(jié)處讀入50字節(jié) 計(jì)算機(jī)

13、原理 一、填空題 1. 寫(xiě)出-1.125的IEEE754 32位標(biāo)準(zhǔn)的浮點(diǎn)數(shù)。 2.控制器部件由哪五部分組成_  _ _  _  _； 3.五級(jí)指令流水線哪五部分組成 IF,  _  _  _  _; 二、下述指令集能否用單字指令（字長(zhǎng)為12位）實(shí)現(xiàn)，包括：a 4條三寄存器指令  b 255條單寄存器指令 c 16條0寄存器指令 三、cache和虛擬地址相關(guān)的計(jì)算題 一個(gè)標(biāo)記位Tag, 一個(gè)有效位, 一個(gè)臟位(Dirty), 塊號(hào)(Of

14、fset), 采用全相連方式, 為什么要采用全相連方式? 1 畫(huà)圖表示標(biāo)記，塊號(hào)，塊內(nèi)地址。  2.cache的存儲(chǔ)效率 （即除掉標(biāo)記位，access位，dirty位）。 四、輸入輸出方式都有哪幾種？請(qǐng)簡(jiǎn)要敘述各自特點(diǎn)。 五、1在虛擬頁(yè)式系統(tǒng)中，給了虛擬地址的位數(shù)大概48位，可用的最大主存空間位128GB，每頁(yè)大小4KB 。問(wèn)了四個(gè)問(wèn)題，大概有涉及的多級(jí)頁(yè)表，訪存的平均時(shí)間，命中率等等。 (假設(shè)沒(méi)有TLB存在)2. 系統(tǒng)中為什么要設(shè)計(jì)TLB畫(huà)圖表示出虛擬地址到真實(shí)地址的轉(zhuǎn)化-2008年清華大學(xué)計(jì)算機(jī)系上機(jī)題（回憶版）一、輸入：兩行第一行：M和N第二行：XM和N是一個(gè)十進(jìn)制數(shù)

15、，M和N都在2-36之間，X是一個(gè)M進(jìn)制數(shù)，X在1-2*1019輸出：一行第一行：現(xiàn)在要求你將M進(jìn)制數(shù)X轉(zhuǎn)換成N進(jìn)制數(shù)輸出輸入一：16 10F輸出一：15二、按照手機(jī)鍵盤(pán)輸入字母的方式，計(jì)劃所花費(fèi)的時(shí)間如：a,b,c都在“1”鍵上，輸入a只需要按一次，輸入c需要連續(xù)按三次。如果連續(xù)兩個(gè)字符不在同一個(gè)按鍵上，則可直接按，如：ad需要按兩下，kz需要按6下如果連續(xù)兩字符在同一個(gè)按鍵上，則兩個(gè)按鍵之間需要等一段時(shí)間，如ac，在按了a之后，需要等一會(huì)兒才能按 C?，F(xiàn)在假設(shè)每按一次需要花費(fèi)一個(gè)時(shí)間段，等待時(shí)間需要花費(fèi)兩個(gè)時(shí)間段?，F(xiàn)在給出一串字符，需要計(jì)劃出它所需要花費(fèi)的時(shí)間。輸入一：bob輸出一：7輸入

16、二：www輸出二：7考完筆試，將試題回憶了出來(lái)。希望能有利于后人，也算是對(duì)前人給予的幫助的一種回報(bào)吧。（此資料不得被任何人以任何形式販賣(mài)！請(qǐng)賣(mài)考研資料者自律。）下面的是人工智能和多媒體技術(shù)的試題。=人工智能=一、對(duì)下圖所示博弈樹(shù)進(jìn)行-剪枝，標(biāo)明各結(jié)點(diǎn)的倒推值及何處發(fā)生剪枝。（見(jiàn)附圖1。數(shù)值不準(zhǔn)，僅作參考。）二、對(duì)狀態(tài)空間圖進(jìn)行搜索，標(biāo)出下述算法的擴(kuò)展結(jié)點(diǎn)序列和求得的解路徑。序列和解路徑用字母串表示，如SABC。（見(jiàn)附圖2。數(shù)值不準(zhǔn)，僅作參考。）1. 寬度優(yōu)先搜索；2. 深度優(yōu)先搜索；3. A算法。其中各節(jié)點(diǎn)旁標(biāo)記的是該節(jié)點(diǎn)的h值，路徑上的數(shù)字表示該路徑的耗散值。三、請(qǐng)回答下列問(wèn)題：1. -剪枝

17、的原理，即為什么可以-剪枝。2. 模擬退火算法的特點(diǎn)。3. 簡(jiǎn)述遺傳算法的過(guò)程。=多媒體=一、什么是多媒體技術(shù)（定義）？其關(guān)鍵技術(shù)是什么？二、寫(xiě)出音頻差分編碼(DPCM)的原理。列舉參數(shù)編碼的兩個(gè)國(guó)際標(biāo)準(zhǔn)，說(shuō)明它們的編碼參數(shù)和數(shù)據(jù)率。三、量化方法的分類(lèi)？某均勻量化器的輸出為L(zhǎng)階，輸出編碼位數(shù)n位。則已知L的話，n的值是多少？已知n的話，L的值為多少？四、信息的量如何度量？離散信源的無(wú)損編碼的理論極限（好像是這么寫(xiě)的）是什么？已知某信源的四個(gè)符號(hào)的概率分別為：a1 - 0.5，a2 - 0.2412，a3 - 0.1702，a4 - 0.0886（數(shù)值記得不太準(zhǔn)），求信源的Huffman編碼，計(jì)

18、算信源的熵以及編碼的平均碼長(zhǎng)。五、基于內(nèi)容檢索的多媒體數(shù)據(jù)庫(kù)由哪些部分組成？請(qǐng)描述基于內(nèi)容檢索的工作過(guò)程。=另外，這里對(duì)考應(yīng)用方向的學(xué)弟學(xué)妹們有些建議：1. 筆試四選二里選人智和多媒體。據(jù)我所知應(yīng)用方向的大多數(shù)人都選的是這兩科。其他的兩科比較難。如果你四科都一樣是沒(méi)學(xué)過(guò)的話，AI和MM還是比較容易看懂的。2. 去網(wǎng)上找到“計(jì)算機(jī)系網(wǎng)絡(luò)課堂”這套課件，里面有人智和多媒體，還有信號(hào)處理原理的課件。仔細(xì)地做做期末試題中跟歷年復(fù)試題相近的題。大多數(shù)真題是從這里改編的。在本版的精華區(qū)里可以找到05至07年歷年的應(yīng)用方向筆試題目，這些試題具有很大的參考價(jià)值。為了節(jié)省大家的時(shí)間，這里附上歷年試題回憶的原帖。

19、排版有些混亂，需要的人自己整理吧。祝后來(lái)的學(xué)弟學(xué)妹們考試順利。首先要非常感謝knightma，是knightma去年的辛勤勞動(dòng)-復(fù)試題目回憶，為大家今年的復(fù)試準(zhǔn)備做出了巨大的幫助。為了回報(bào)一下之前的牛人和回報(bào)新水木，我也回憶一下題目吧。我考的人智和多媒體。題目基本上跟去年一樣，多媒體多了個(gè)量化處理的原理和計(jì)算。其他的都沒(méi)變。人工智能有一點(diǎn)變化。題目總共才三道題，第一道是給出了8數(shù)碼問(wèn)題的一個(gè)h函數(shù)，求證單調(diào)，然后再用A*求出最優(yōu)解，畫(huà)圖很麻煩。第二題是謂詞的歸結(jié)題，較繁，不僅要反演證明，還要用修改證明樹(shù)求出一個(gè)結(jié)果。第三題是名詞解釋四選二：遺傳算法，模擬退火，神經(jīng)網(wǎng)絡(luò)，專(zhuān)家系統(tǒng)。今年所有的方向

20、都考上機(jī)，時(shí)間也比去年少了半個(gè)小時(shí)，題目我放在了附件里，照著拿出來(lái)的題目敲到了word文檔里。第一題5個(gè)測(cè)試數(shù)據(jù)，第二題8個(gè)，第三題7個(gè)。每個(gè)測(cè)試數(shù)據(jù)5分。編程環(huán)境在附件文檔里有說(shuō)明。不用vc6.0也可以用.net2005.終于塵埃落定，可以閑下心來(lái)寫(xiě)點(diǎn)東西。 想想自己也在考研版得益于前人的回憶，這次自己也回憶一篇， 雖然價(jià)值不是很大， 但聊表心意了。 希望有人用得著計(jì)算機(jī)的老師特別懶，今年的AI， MM題和去年比有70分一模一樣，因?yàn)樗麄儾话堰@個(gè)當(dāng)成什么大不了的事，所以抓到竅門(mén)可以少走歪路。人智用書(shū)是馬少平的， 多媒體用高教版鐘玉琢的（千萬(wàn)表像我， 開(kāi)始選了林福宗的，近似白看）。可以找到網(wǎng)絡(luò)課堂的一定要下來(lái)看看， 都是從上面的的幾套卷子和課后習(xí)題里挑。 人智部分：一,4個(gè)問(wèn)答（10分）   1,產(chǎn)生式系統(tǒng)的三要素   2，正向演繹系統(tǒng)中， 如何判斷是否一致解   3，8數(shù)碼問(wèn)題，找出一個(gè)滿足單調(diào)條件的h， 證明為何滿足單調(diào)條件