清华大学912

数据结构（70分）
一．        判断题（10*2分）
1.n^log(log(log n)) = O([logn!])
2.汉夫曼编码树不同深度的两颗子树互换，必定会改变编码长度。
3.序列中逆序数互换，逆序对必定减少。
4.伸展树若不具备局部性，平摊复杂度就无法达到O(logn)
5.KMP的next[]表即使不采取优化，也能使得KMP达到线性的效率
6.具有2018个叶节点的树，对其进行层次遍历辅助队列大小最多不超过2018
7只通过前序遍历和后序遍历无法唯一确定树形
8.基数排序的底层排序如果不稳定，最终结果有可能会出错
9.有2019个叶节点的树的种类要比2018？？的种类要多
10．

二．        论述题（8 * 4分）
1.        逆波兰表达式为什么相比普通表达式计算上有效？既然在将普通表达式转换成为逆波兰的过程中已经将表达式计算出来，为什么还要进行转换？
2.        深度优先搜索时，什么情况下是是前向边，什么情况下是后向边
3.        插入排序相比于选择排序有什么优点，举两个并简要说明。
4.        Dijkstra在处理稠密图时候利用多叉堆而非二叉堆，这是为什么？如何确立多叉堆的叉数
5.        相比于一般的锦标赛树，败者树有什么优点
6.        红黑树在什么情况下要优于AVL树，并解释说明为什么
7.        相比于开散列，闭散列有什么优点，举两个并简要说明。
8.        KMP相比于蛮力算法，在什么情况下才能发挥效用，并解释说明为什么
三．        算法题（7+3+4分）
struct BinNode {
int size;
BinNode* lc, rc
}
Binnode* rank(Binnode* T,  int k) {
//请填写代码
}
求出后序遍历的第k大的结点，要求时间复杂度和空间复杂度不超过O(depth(x))(x为第k大的节点)，请不要试图直接模拟后序遍历，那样效率一定不达标，不得分
1.        填写代码已完成上述功能 （不超过12行）
2.        解释说明代码思想，可以画一幅图
3.        分析和计算你代码的时间复杂度和空间复杂度

计算机原理（30分）
一．        选择题
1.下列哪一项没有容错能力
A.        RAID0
B.        RAID1
C.        RAID5
D.        RAID6
2.下列关于静态存储器和动态存储器的描述正确的是
反正选那个静态存储器靠D触发器，不需要定期刷新，动态存储器靠电容，要定期刷新
3.
4.
5

二．        填空题
1.        +1234的32位补码 （16进制）
2.        -27.625的IEEE574表示（16进制）
3.        解决数据冲突的方法，给出三个
4.        缓存丢失的方式，给出三个
三．        计算题（5分）
给你一堆参数，然后给你5条指令，让你计算
1．        在单周期cpu下运行时间
2．        在多周期cpu下运行时间
3．        在5级流水下运行时间

操作系统（30分）
一．        填空题
1.系统里面会有stride机制，就是说进程分配时间和其优先级成反比，优先级越低进程上CPU运行的时间就会更长，用八位无符号数来表示进程A的运行时间有可能会溢出，但是只要做小小的技巧就可以判断时间，然后又引入进程B，讨论他们stride的关系
2.PV操作填空
3.A的节点引用为1，B对A的进行硬链接，C对B进行硬链接，D对A软连接，问B，C的节点引用
4.
二．        判断题
1.        main()函数只有一个线程
2.        不安全状态一定是死锁
3.       
三．        选择题
1．下列哪个是对的
A．        虚拟内存空间比实际的地址空间大
B．        虚拟内存空间比实际的地址空间小
C．        虚拟内存空间连续存放，实际内存一定连续存放
D．        虚拟内存空间不连续存放，实际内存有可能连续存放
2.

四．        回答题（不记得什么题，我瞎起的名字）
1.给你一长段ucore代码
问代码中哪里体现了页表的切换，堆栈的切换，和代码中switch_to的两个参数的来源
2.给你一张内存图，告诉你A的起始位置0x00, B的起始0x10,问A访问0x04和B访问0x??的过程

计算机网络（20分）
一．        选择题
1.        以太网中最短帧长1000bit，最远两点相距离100m,数据在光纤中的传播速率为2*10^8m/s,问最大发送速率
A.1Gb/s B.2Gb/s C.100Mb/s 4.200Mb/s
2.       
二．        给你一幅图，图中有三个子网，子网1有100台主机，子网2有50台主机，子网3有20台主机，而且还有三个路由器R1，R2，R3，给你一个地址的路由集合。
第一问，让你合理地分配子网1，2，3和路由器R1，R2，R3各个端口的IP地址
第二问，A，B是子网1中的主机，C是子网2中的主机
问A-B， A-C之间通信时候ARP协议的不同
第三问，问A-C通信，在这个过程中数据报中IP的源地址和目的地址，MAC源地址和目的地址