题量大，而且有好几个难题。答完之后都吓傻了，过年也就没心情回去了。
DS
一. 证明题：10分，每题5分
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的排列数。
二. 作图题（手工画图）10分
给了一个Dijkstra无向连通图的最小生成树算法描述，就是山大的“破圈法”，和习题解析185页8---14一个模样，要你根据该描述画出加入各边之后最小生成树的形态和并查集的变化情况。
为了使答案唯一，题目给定了加入边的顺序，比如（0，3，6），（0，2，15）。。。。边的格式是（tail,head,weight)
三. 画图并求搜索长度 10分
一个数组大小为8*N,下标从0到8N - 1,现在这样搜索:
A[7],A[15],A[23]......A[8*N-1] 用顺序搜索
在A[0]到A[6]之间,在A[8]到A[14]之间,，，A[8*(N-1)]到A[8*N-2]之间采用折半搜索.
1. 画出判定树 5分
2. 求ASL(succ) 3分
3. 求ASL(unsucc) 2分
四. 程序填空 10分
先给出了一个算法，用静态链表描述的.中间缺了4个空.原题的函数名是selectsort
1. 这是什么排序算法? 2分
2. 填上挖去的4个空 8分
注：就是习题解析上210页9---11上的那个基于静态链表的简单选择排序,
挖去的空我就不写了,你应该能把整个算法写出来才是
五. 算法设计 10分
1.让我们用C++语言设计一个多项式类。3分
在此问之前先给了一大段话,大意是要求用单链表实现,每个结点包括3个域:coef，exp，link；结点按exp递减排列。原题给出了简单的结点类和多项式类的格式，用了template
来描述的，
2. 根据题目给出的类声明，和我们自己刚才定义的那个类，来写一个Insert（）函数.
要求是：顺序搜索链表，当找到与已知exp相等的结点时，将它们合并，否则插入。 2分
1 写类的描述
3. 写出两个多项式相乘的算法。 5分
OS
一. 信号量 8分
给出一个并发程序的描述：
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)
问: 1.最多有多少个进程来并发执行 ....computeA.... 和 ....computeB.....？
2.是否会造成饥饿？
二. 4分
一个CPU的性能是10MIPS,现在编写了一个Scheduler,用RR实现调度，
每轮转1次要1us,让我们评价调度的效率和响应时间。
三. 10分
1. 简述多级页表的实现原理。
2. 虚地址空间为64bit,实存地址空间为36bit,页块大小为4KB,每个页表项占8B,
问：
（1）页表要分几级？
（2）页表占多少内存？
四. 8分 一个三级存储系统，Cache命中率为95%,Cache存取要20ns,内存命中率为80%，
内存存取时间为60ns,外存存取要12ms,问：
此系统的平均存取时间，要求写出计算过程。
五.10分 把一个UNIX文件卷复制到另一个磁盘上，问：
a) UNIX文件卷由哪几部分组成？
b) 只复制文件数据，包括目录之后，不能访问，为什么？
c) .....忘了。
d) 终于搞好了之后，发现有重复的hardlink，为什么？
六, 10分 给出一个使用pthread的程序代码，里面系统调用有fork()，thread()，join()等，中间穿插print HELLO。问共打印了多少个HELLO。只是记得主进程用了2个fork()创建了2个子进程，又有一个thread()，其中那个thread()自己又用fork()创建了一个子进程。
和02年那个题目差不多，可惜我不会，记不住了。
CA
一、填空
1. a,b为两个1位2进制数，Carryin为低位进位，Carryout为高位进位，用and,or写出带进位的1位加法器的Carryout并化简，Carryout=____
2. 一条流水线一般分为IF,__,EX,__,WB 5级.
3. 一个串行程序可并行部分占%90，规模不变的情况下，串行程序并行化后加速比不超过_______
4. 已知 1111 1111 1111 1111 1111 1111 1111 1100 是一个二进制数的补码，则这个数对应的十进制数是_______
二、判断 15分
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 CPU的功率小于10w。
10.同频率的64位CPU一般比32位CPU快一倍
11.增加流水线段数可提高CPU频率
12.VHDL是一种硬件描述语言。
13.EPIC是VLIW技术的发展。
三. 简答
试说明为何编译程序要进行如下优化
for (j = 0; j < 200; j++){
for (i = 0; i < 20; i++){
A[j] = A[j] + 1;
}
}
编译优化后
for (i = 0; i < 20; i++){
for (j = 0; j < 200; j++){
A[j] = A[j] + 1;
}
}
四. 硬盘平均寻道时间为12ms，传输速率为10MB/s，磁盘控制器延迟为2ms,则一个转速为
7200r/min的硬盘写1KB数据时间为多少?
五. 1. 什么是分支预测？
2. 画出2bit转移预测的状态图。 |
收藏
点赞!
反对!