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