2010年408大题总结

第41题

这个考的是散列表（巧了，我没复习，这就去看）
第一个要记住的是装填因子，关键字个数/装填因子 = 数组长度
第二个是线性探测再散列，表示如果当前的下标被占据那就一直往下找，直到找到空位就放上

---

第42题

1. 暴力法
   这个题暴力法就很暴力，但是性能就很低（起码有分）
   用一个数组存前面p个数，用一个数组存后面n-p个数，然后再组装起来
   空间复杂度为O(n)，时间复杂度也为O(n)

int LeftMove(int a[n], int p) {
	int i, j, k = 0;
	int b[p] = [], c[n - p] = [];
	// 拿数
	for(i = 0; i < n; i++) {
		if(j < p) {
			b[i] = a[i];
		} else {
			c[k] = a[i];
			k++;
		}
		j = i; 
	}	
	// 组装
	j = 0, k = 0;
	for(i = 0; i < n; i++) {
		if(j < n - p) {
			a[i] = c[i];
		} else {
			a[i] = b[k];
			k++;
		}
		j = i;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

第43题

如果今年能考这个，直接烧高香（别直接给汇编，实在看不懂）
第一小问：
指令数量看OP位数，寄存器数量看Rs/Rd寄存器位数，MAR看主存地址，MDR看机器字长
那就明朗了：16条，8个，16位，16位
这里有个坑：按字编址，需要除以（16/8）

第二小问：
这个不用说吧，主存多少就查多少——0-2¹⁶ -1

第三小问：
这个要看懂的是他这个指令，按照指令格式来填充对应的机器码
首先操作数0010，
其次源操作数和目的操作数分为寻址方式+寄存器编号，分别为
001 100
010 101
拼接起来 0010 001100 010101 = 2315H
哪些地方被修改了：数据最后放到了R5那么跟他有关的就变了
R5变了：5679H
R5内容所指的主存地址的内容：68ACH

---

第44题

这种题得分析一下，因为没有图，很容易忘记一些信息点（别问我为啥知道）

1. 主存地址位数28位 => cache 的位数28位
2. 8行，一行64B
3. 直接映射
4. 数组a按行优先

第一小问：
除了块内的，还有标记位28-9 = 19位，有效位1位
64 * 8 + 8 * [（19+1）/8] = 532B

第二小问：
这里是巨大的坑啊，直接坑麻了
没有告诉主存块号，只能通过计算主存地址来分析存放的位置
a[0][31] 那就是第32个
（320 + 4*31） / 64 = 6
a[1][1] 那就是第33个？错！！！一行是256个元素
（320 + 256 * 4 + 1 * 4）/64 mod 8 = 5

第三小问：这个比较简单，肯定是A执行时间短（局部性原理）
A：15/16
B：0

---

第45题

第一小问：

位示图 2¹¹B = 2¹⁴bit

第二小问：

寻道方法：CSCAN/CLOCK
时间 = 寻道 + 延迟 + 传输
延迟：5ms
传输：1min / 6000 / 100 = 0.1ms
寻道：
100 => 120 => 30 => 50 => 90
20+5+0.1 + 90+5+0.1 + 20+5+0.1 + 40+5+0.1 ms = 190.4ms

第三小问：（我是真不会这种）

---

第46题

理论是这个题是没有难度的，唯一有问题的就是记不住clock算法的流程（哭哭）

前两个小问送分题，计组存储器那块学明白了，这个肯定也没有问题，判断好分别占几位就可以了

第一小问：

第二小问：

第三小问：

---

第47题

这个没啥好说的
第一问最短就是单程，最长就是双程；
第二问主要是各种时间相加：发送传输时延+发送帧传播时延+确认传输时延+确认帧传播时延

画红线的部分就是我被坑的地方，真是一下子没想到