【2005．4
浙江大学计算机博士入学考试部分题目】
体系结构：
1． 有关循环展开，调度的题目
2． C＝A＋B的四种表示
（第二章）
3． 一段相关性分析代码（逆相关，输出相关，真相关）
4． Amdahl定律的计算：
Cache速度比主存快10倍，利用率90％，问加速比是多少。
5． CPUtime计算公式，各分量的含义，列举减少CPUtime的技术
6． 分布式多处理机存储方式，相应的通讯方式
7． 有关直接映射的地址结构的题目tag，index和offset
8．
【2005．10 浙江大学计算机博士入学考试部分题目】
高级操作系统与体系结构
1、 进程的周转时间为进入就绪队列的时间加上cpu执行的时间，现有三个进程如下：
1） 平均周转时间？
2） 空等1秒后的平均周转时间。
进程p0，进入就绪队列时间0秒，执行时间8秒。
进程p1，进入就绪队列时间0.4秒，执行时间4秒。
进程p2，进入就绪队列时间1秒，执行时间1秒。
2、 对一系统进行改造，有两种方案：（一）对硬件进行改造，则40%的硬件将提高性能10倍。（二）对软件进行改造，则60%、10%的软件将分别提高性能2倍和20倍。
1) 对硬件进行改造的性能比是多少
。
2) 对软件进行改造的性能比是多少。
3) 你的选择。
3、 下表是常用windows系统框架，请用Linux、JDK1.4，Shell，SQL改写下列框架
外部工具
| 应用程序 | |
| 接口 |
| 通讯协议 |
|
|
| X－Windows内核 |
| | | | | |
4、 汇编的编译问题（
忘了）
5、 写无效cache一致性问题，cache状态：1）无效、2）共享、3）独占
四种访问方式：1）cpu读、2）cpu写、3）总线读、4）总线写
Cpu动作 | 总线动作 | CpuA的Cache内容 | CpuB的Cache内容 | 内存X的内容 |
|
|
|
| 0 |
A读X | Cache miss for X |
|
|
|
B读X |
|
|
|
|
A写X＝‘2’ |
|
|
|
|
B读X |
|
|
|
|
计算理论
1） 正则表达式与上下文无关文法之间的问题：
A）
a式为正则表达式，b式为上下文无关文法，证a×b为正则。
B）
举一反例说明正则与上下文无关文法的关系。（具体内容忘了，考的是这方面的）
2）
3）设计有穷自动机
F（X，Y）＝2x 当Y为奇数时；
F（X，Y）＝4x＋1 当Y为偶数时；
a)、设计有穷自动机（记的有些模糊）
b)、写出逆推式有穷自动机
4）找到一个数 Pn; 满足 PnXn（Xn的M次方，不会表达）
＝P0X0＋P1X1＋…＋
P（n－1）X（n－1）＋P（n＋1）X(n+1) + …+PmXm;
a） 计算时间复杂度；
b） 证明这是个P问题。
注：括号里表示下标。
面向对象问题
1） 名词解释
a） 过程抽象、b）数据抽象。（共4个，忘了）
2）
5）什么是OOA方法，过程如何？
6）简述两种OOA或OOD方法？
