2009年408大题总结

第41题

这个最容易想到的方法就是举反例，但是我们可以分析一下，每一次都取最短的路径，实际上就是贪心策略的应用——每次都是最优，但是最终的结果却一般不是最优，因此很容易想到这个方法是不可行的

拓展：最短路径算法

---

第42题

1. 暴力法
   策略：遍历两次，第一次遍历查看总共有n个，第二次遍历n-k+1个
   这样可以获得1/2到2/3的分数，因为你的算法不够高效，需要遍历两次
   错误方法：这里是绝对不能反过来遍历的，题目已经说明是带头结点的单链表，不改变链表结构

// 数据结构定义
typedef struct LNode {
	int data; // 数据域
	struct LNode *next;	// 指针域 ，改成 LinkList *next 也可以
} *LinkList;

// 算法实现
int Search_Node (LinkList &L, int k) {
	LinkList p = L-> next;	// 定义移动的指针
	int sum = 0;	// 链表长度
	if(L == NULL) return 0; // 链表为空
	while(p != NULL) {
		p = p -> next;	// 不断地指向下一个结点
		sum++;	// 计算链表长度
	}
	p = L -> next; // 重新回到链头
	for(int i = 0; i < sum - k + 1; i++) { // 倒数第k个就是正数n-k+1个
		p = p -> next;
	}
	return p -> data; // 返回数据域的内容
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. 最优解
   个人算法实力很垃圾，所以建议考场还是暴力为主，节省时间（算法大神勿喷），除非遇到了碰巧刷过类似的算法题，所以这里给出答案看看就不浪费时间手敲了
   

---

第43题

这类问题是比较简单的，我的一般方法就是找1s中断/DMA执行了多少个时钟周期，然后除以主频

1. 第一小问：
   一次20条指令，则为100个时钟周期
   一次4B的数据，速度为0.5MB/s，则1s有 0.5M / 4 = 125000次
   那么1s的中断使用了100 * 125000 = 12.5M个时钟周期
   12.5M / 500M = 2.5%

2. 第二小问：
   一次500个时钟周期
   1s有5MB/s / 5000B = 1000次
   那么1s的DMA使用了0.5M个时钟周期
   0.5M / 500M = 0.1%

第44题

这种题个人觉得比较难，但是可以捞分不至于全部不会，首先对于计组的第五章数据通路那一块要有“亿”点点的印象，不至于看不懂题目在问什么

ps：墙裂建议背一下一些功能操作，比如固定的取指令

1. 指令地址给MAR
2. 主存取内容给MDR，PC+1
3. 指令送IR
4. 指令译码（不一定需要写，但是感觉可以凑4的倍数，强迫症）

然后就是不固定的指令执行阶段，我个人做的时候，其实很少看他讲的一大段内容，直接看主要部分——要你干嘛

这里就是一个加法指令（看红框框的东西）
那么就需要对照这个图看，先写指令再考虑信号

1. R1打了个(())，那就得去主存取，(R1) -> MAR，一个()就是寄存器取就行
2. M(MAR) -> MDR，取回来的数放到MDR
3. (MDR) -> A，给A是因为要来计算了
4. (A) + (R0) -> AC，执行加法给AC
5. (AC) -> MDR，要放回主存，先给MDR
6. (MDR) -> M(MAR)，放回主存

参考答案

拓展：CPU数据通路的知识

---

第45题

这个跟上面那个题的性质一样，不求全对，求多捞分！！！
首先得先判断是什么类型的同步互斥关系（咸鱼学长yyds，最前面的三篇）
这里是一个吸烟者问题，很巧，咸鱼学长没讲过模板

但是可以明确，不需要用纯代码，中文描述伪代码也可——对代码小白的我十分友好
虽然但是，这个题得用题目里给的函数，变相伪代码

semaphore metux = 1 // 互斥访问缓冲区
semaphore empty = N
semaphore odd = 0
semaphore even = 0
1
2
3
4

1. 找事做，每个人都干了啥，并且加锁（锁是加在访问缓冲区的那个操作）

p1() { //生产
	while(1) {
		produce() //生产正整数
		p(metux)
		put()	//放入缓冲区
		v(metux)
	}
}

p2() { //拿奇数
	while(1) {
		p(metux)
		getodd()	//拿奇数
		v(metux)
	}
}

p3() { //拿偶数
	while(1) {
		p(metux)
		geteven()	//拿偶数
		v(metux)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2. 找条件
   1. p1放入得确定缓冲区还有没有位置，所以放之前得p一下
   2. p2、p3拿之前得知道有没有，所以拿之前得p一下

p1() { //生产
	while(1) {
		produce() //生产正整数
		p(empty)	// 让我看看有没有
		p(metux)
		put()	//放入缓冲区
		v(metux)
	}
}

p2() { //拿奇数
	while(1) {
		p(odd)
		p(metux)
		getodd()	//拿奇数
		v(metux)
	}
}

p3() { //拿偶数
	while(1) {
		p(even)
		p(metux)
		geteven()	//拿偶数
		v(metux)
	}
}
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
26
27

3. 然后找v

p1() { //生产
	while(1) {
		produce() //生产正整数
		p(empty)	// 让我看看有没有
		p(metux)
		put()	//放入缓冲区
		v(metux)
		if(生产的是偶数)	v(even)
		else v(odd)
	}
}

p2() { //拿奇数
	while(1) {
		p(odd)
		p(metux)
		getodd()	//拿奇数
		v(metux)
		v(empty)
		countodd()
	}
}

p3() { //拿偶数
	while(1) {
		p(even)
		p(metux)
		geteven()	//拿偶数
		v(metux)
		v(empty)
		counteven()
	}
}
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
26
27
28
29
30
31
32
33

v之间的位置关系是没有关系的
这里可能跟咸鱼学长的观念不太一样，找一个p对应找一个v

---

第46题

这个题个人觉得比价简单（当然不是每次都能这么简单，需要对虚拟地址=>物理地址的过程比较熟悉，不然就很容易漏了步骤少了时间）

最容易漏掉的就是访问了快表/内存的慢表查询到了页面之后，还需要一次访问内存页面的操作（如果缺页了还得加上缺页的时间）

看懂了下面这个感觉这个题就没啥问题了
驻留集：系统给进程分配了多少个页框，这里是2

---

第47题

这个题的考点是子网划分和网络聚合，以及路由表的编写

• 第一小问
  120 < 2⁷，因此需要7为作为子网的主机号，24位为网络号，则剩一位作为子网号
  子网的地址格式：网络号 子网号 主机号
  202.118.1.(8位：0/1 + 主机号)
  则两个子网为202.118.1.0 和 202.118.1.128

如何进行子网划分

• 第二小问
  格式已经给了

标黄色的我暂时没懂，是默认的还是？大神可以在发个评论解释一下
最后一个是默认路由，也就是通往互联网的路由

• 第三小问
  路由聚合的问题，就是子网多变少，找前缀就行了

202.118.1.(0000 0000)
202.118.1.(1000 0000)

聚合结果为：202.118.1.(0000 0000) / 24，前24位是一样的，最后8位就取0了

如何进行路由聚合