清華大學 - 話題

計組部分

一、填空題
1. a,b為兩個1位2進制數(shù)，Carryin為低位進位，Carryout為高位進位，用and,or寫出帶進位的1位加法器的Carryout并化簡，Carryout=____
2. 5段流水線分別為IF,__,EX,__,WB.
3. 一個串行程序可并行部分占%90，規(guī)模不變的情況下，串行程序并行化后加速比不超過_______
4. 二進制補碼1111 1111 1111 1111 1111 1111 1111 1011化為十進制后為_______

二、判斷題
1.CISC計算機比RISC計算機指令多。
2.速度為10MIPS的計算機一定比速度為5MIPS的計算機快。
3.SRAM比DRAM的速度快，成本高。
4.SCSI硬盤與SATA硬盤的速度，價格比較.
5.PCI-Express與AGP都可用于顯卡接口
6.SPECCPU 2000基準測試程序可用于測I/O性能。
7.IEEE 754是計算機中的二進制整數(shù)算術標準。
8.全相聯(lián)與直接映象Cache的比較
9.INTEL P4功率小于10w
10.64位CPU一般比32位CPU快一倍
11.增加流水線段數(shù)可提高CPU頻率
12.VHDL是硬件描述語言。
13.EPIC是VLIW的發(fā)展

三、簡答題
1.試說明為何編譯程序要進行如下優(yōu)化
for(j=0;j<200;j++)
{for(i=0;i<20;i++)
{
A[j]=A[j]+1;
}
}
編譯優(yōu)化后
for(i=0;i<20;i++)
{for(j=0;j<200;j++)
{
A[j]=A[j]+1;
}
}
2.硬盤平均尋道時間為12ms，傳輸速率為10MB/s，磁盤控制器延時為2ms,則一個轉速為7200r/min的硬盤寫1KB數(shù)據(jù)時間為多少?
3.為什么要設置二叉分支預測指令？畫出2bit轉移預測的狀態(tài)圖

數(shù)據(jù)結構

證明題:
1 證明在一棵滿二叉樹中分支B與葉子節(jié)點n0滿足關系 B=2(n0-1)
2.證明，完全無向圖中,兩個頂點之間簡單路徑書目為:
1 + A(n-2,1) + A(n-2,2) + ... + A(n-2,n-2)
其中A(m,n)是m取n的排列數(shù)。

作圖題:
給了一個Dijkstra無向連通圖的最小生成樹算法描述，要你根據(jù)該描述作出最小生成樹及并查集的變化。

程序填空
給了一段排序算法，用靜態(tài)鏈表描述的
1 問你這是什么排序算法（里面寫著selectsort）
2 把挖去的5個空填上 （發(fā)現(xiàn)只有4個）

程序設計題
用鏈表表示的多項式
1 寫類的描述
2 insert算法，如果相同指數(shù)合并，沒有就插入
3 利用insert,給出多項式乘法的算法


操作系統(tǒng)

1 給出一個并發(fā)程序的描述:
semaphore X1=X2=Y=1;
int c1=c2=0;

procedure f1:
p(X1)
if (++c1 = 1) p(Y)
v(X1)
compute A
p(X1)
if (--c1 = 0) v(Y)
v(X1)

procedure f2:
p(X2)
if (++c2 = 1) p(Y)
v(X2)
compute B
p(X2)
if (--c2 = 0) v(Y)
v(X2)
問computeA和computeB各自能有多少并發(fā)執(zhí)行，會不會出現(xiàn)餓死？

2 給出一個cpu的頻率，使用基于時間片的輪轉隊列調度，并給出了參數(shù)。求調度的效率和響應時間。

3 使用多級頁表，給出一些參數(shù)，如虛實地址空間大小、頁大小、頁表項大小等，問:
a) 多級頁表的優(yōu)點
b) 如果頁表限制在一個頁面里，問有多少頁表項？
c) 進程頁表占用多少內存？

4 把一個UNIX文件卷復制到另一個磁盤上，問:
a) UNIX文件卷由哪幾部分組成？
b) 只復制文件數(shù)據(jù)，包括目錄之后，不能訪問，為什么？
c) 終于搞好了之后，發(fā)現(xiàn)有重復的硬鏈接，為什么？

5 給出了一個使用pthread的程序代碼，里面系統(tǒng)調用包括fork()，thread()，join()等等，中間穿插print HELLO。問最后一共打印了多少個HELLO。

在中國6月1日是什么節(jié)？（答案為兩個字）

考研論壇提示：
1、請勿發(fā)布個人聯(lián)系方式或詢問他人聯(lián)系方式，包括QQ和手機等。
2、未經允許不得發(fā)布任何資料出售、招生中介等廣告信息。
3、如果發(fā)布了涉及以上內容的話題或跟帖，您在考研網的注冊賬戶可能被禁用。