计组部分
一、填空题
1. a,b为两个1位2进制数，carryin为低位进位，carryout为高位进位，用and,or写出带进
位的1位加法器的carryout并化简，carryout=____
2. 5段流水线分别为if,__,ex,__,wb.
3. 一个串行程序可并行部分占%90，规模不变的情况下，串行程序并行化后加速比不超过
_______
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是计算机中的二进制整数算术标准。
8.全相联与直接映象cache的比较
9.intel p4功率小于10w
10.64位cpu一般比32位cpu快一倍
11.增加流水线段数可提高cpu频率
12.vhdl是硬件描述语言。
13.epic是vliw的发展
三、简答题
1.试说明为何编译程序要进行如下优化
for(j=0;j<200;j++)
{for(i=0;i<20;i++)
{
a[i][j]=a[i][j]+1;
}
}
编译优化后
for(i=0;i<20;i++)
{for(j=0;j<200;j++)
{
a[i][j]=a[i][j]+1;
}
}
2.硬盘平均寻道时间为12ms，传输速率为10mb/s，磁盘控制器延时为2ms,则一个转速为72
00r/min的硬盘写1kb数据时间为多少?
3.为什么要设置二叉分支预测指令？画出2bit转移预测的状态图
数据结构
证明题:
1 证明在一棵满二叉树中分支b与叶子节点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的排列数。
作图题:
给了一个dijkstra无向连通图的最小生成树算法描述，要你根据该描述作出最小生成树及
并查集的变化。
程序填空
给了一段排序算法，用静态链表描述的
1 问你这是什么排序算法（里面写着selectsort）
2 把挖去的5个空填上 （发现只有4个）
程序设计题
用链表表示的多项式
1 写类的描述
2 insert算法，如果相同指数合并，没有就插入
3 利用insert,给出多项式乘法的算法
操作系统
1 给出一个并发程序的描述:
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各自能有多少并发执行，会不会出现饿死？
2 给出一个cpu的频率，使用基于时间片的轮转队列调度，并给出了参数。求调度的效率和
响应时间。
3 使用多级页表，给出一些参数，如虚实地址空间大小、页大小、页表项大小等，问:
a) 多级页表的优点
b) 如果页表限制在一个页面里，问有多少页表项？
c) 进程页表占用多少内存？
4 把一个unix文件卷复制到另一个磁盘上，问:
a) unix文件卷由哪几部分组成？
b) 只复制文件数据，包括目录之后，不能访问，为什么？
c) 终于搞好了之后，发现有重复的硬链接，为什么？
5 给出了一个使用pthread的程序代码，里面系统调用包括fork()，thread()，join()等等
，中间穿插print hello。问最后一共打印了多少个hello
