选择题

数据结构

暂无，有些原理已经总结

计算机组成原理

1. P148 T16 -错题！！
   错误原因：我选了B，没有理解Cache分离的目的
   Cache-主存的平均访问时间有两种计算方式
   ①先访问Cache，Cache缺失后再访问主存：
                              Ta=H.Tc+(1-H).(Tm+Tc);
   ②同时访问Cache和主存
                              Ta=H.Tc+(1-H).( Tm );
   A中，降低Cache的缺失损失，和分离Cache无关，降低Cache的缺失损失需要降低主存的访问时间
   C中，降低CPU的平均访存时间应主要需要提高主存的访存时间，因为访存的时间太长，一点点的改变可能就会影响到CPU的平均访存时间
   B中，提高Cache的命中率的方式有两种：①提高Cache的容量使得能装更多的Cache表项，②增强程序的局部性。这里的Cache分离在一定程度上可能可以增加Cache的容量，但是可能这里的Cache分离只是逻辑上的分离，实际上并没有增加它的容量。
   D，在一个Cache的时候，一个时刻只能取指令或者是取数。那么就会容易发生流水线冲突
   而使用指令Cache和数据Cache的分离，那么就可以在流水线中同时取出指令和数据(指的是上一条指令的数据)
   

---

2. P148 T22 做对，但这里有个坑在第一轮的时候入了，需避一下

在第一轮的时候，我把50ns的时间单独拿了处理，以为是最长的时间位450ns，但是第一轮通过王道的视频就知道了这个50ns和100ns都是包含在400ns以内的，所以无论中断响应怎么延迟，CPU在400ns内都需要拿出100ns来处理，因此为100/400=1/4=25%

---

操作系统

3. P148 T22 做对，这类的题型有几类需弄一下
   

限制资源个数导致死锁的最大资源数目=每个进程的最大需求资源-1之和，在这题中三个进程的导致死锁的最大资源数目=2+3+4=9，而如果再+1为9+1=10个资源那么就至少有一个进程可以运作起来，那么就是不会发生死锁的最小资源数目。

解题思路
这题的题型就为：进程数已知，资源数未知。顺便把其他题型也搞了。

这题为资源数已知，进程数未知，求不可能发生死锁的最大进程数
每个进程最多请求3个资源，那么不会发生死锁的临界条件是，每个进程都有n-1个资源=3-2，同时还剩下1个资源给一个进程，就必定不会发生死锁。因此只要满足 X * (n-1) +1 = S 那么就不会发生死锁，X为进程数，n为每个进程的所需最大资源数，S为资源数，因此这题为 2 * 5 +1=11，刚好为5

资源数已知，进程数未知考发生死锁的最少进程数，如果每个进程都占用资源数为(n-1)，且X * (n-1)=S,那么计算发生死锁的最少进程数

该题为死锁检测与解除的----资源分配图


如果R2不先分给P4，且要发生死锁，那么就必须P1、P2、P3之间发生死锁，且不先分给P4也导致P1、P2、P3、P4发生死锁，因此最大处于死锁的进程数为4，如图所示。
因为每一种资源都已经分出去了，但是没有一个进程可以释放该资源。
至于为什么不先分给P4的情况下发生死锁的进程数为4是为什么？
假设法：如果不先分给P4，且先分给P1资源R2和R1，那么P1用完就会释放R2、R1，那么剩下的P4、P2、P3是否会发生死锁？，不会，因为R1的资源已经没有跟P3竞争的进程，肯定能分配，而P4只需要1个R2资源，P2需要R2、R3资源，如果先把R3分给P3，那么P3用完后就会释放资源R1、R3，那么剩下的P2、P4肯定不会死锁，同理分析其他情况可得，在P4不先分配的情况下，只要P1、P2、P3有一个先完成，那么就不会发生死锁，反之如果P1、P2、P3都各自占用一个资源，那么就会发生请求和保存条件发生死锁，导致P1、P2、P3、P4发生死锁，(因为这三者中两两都有共同需要请求的资源)，所以最大的发生进程死锁的进程数目是4个
而如果先给P4分配资源，那么发生死锁那么就必须P1、P2、P3之间发生死锁，且必须P1、P2、P3各占一个不同的资源，否则就不会发生死锁，这样的话就是发生处于死锁的最少进程数为3，为(P1、P2、P3)

---

4. P149 T31 -错题！！

错误原因：对管道的内容概念忘记了，我选了D
管道只能采用半双工的工作方式，一个时刻只允许一边读，或者一边写，且为单向传输。A错误
进程通信，管道是采用(共享文件的方式进行通信的)，而共享文件只能存放在内存中，因此是不受磁盘容量的限制的。B错误
而一个管道内读进程可能只有1个，但是写进程是可以有多个的，可以理解为，多个写进程对一个读进程进行写操作，其实也可也进程多读多写-----用前驱问题保证读的顺序。D错误
C中，管道的进程通信，当管道内无数据时，读进程阻塞，而当管道内有数据时，写进程阻塞。因此读进程和写进程都时有可能被阻塞的

---

5. P149 T32 -错题！！
   

错误原因：我选了C，对多级页表还理解的不够透
A：在一级页表中，因为一级页表常驻内存，因此不会缺页，访问该页表得到PA只需要1次访存；
而如果在多级页表中，M级的页表，把VA->PA需要M次访存(在无缺页的情况下)，且除了页目录表常驻内存以外，剩下的页表可能会发送缺页，因此采用多级页表，需要多次访存A错误，多级页表除了页目录之外都有可能发生缺页，因此是增加了缺页中断的次数，B错误

采用多级页表，除了页目录之外的页表，其大小不能超过一个页面的大小，而页目录中必须指出下一级的页表的地址的起始位置，因此本来一级页表只需要一个页表项对应一个页面，而采用了多级页表的话，就需要多存储一些指向下一级页表的页表项，导致了页表项的增多。因此C错误

计算机网络

6. P150 T33 做对，巧记
   

物联(链)网淑(输)慧(会)试(表示层)用

7. P150 T34 做对，好题！！！需总结----强化课楼楼学姐有说过

转发端口和广播能接收到数据的主机的区别！！！

在下面这道题中，能接受到数据因为是广播所以，所有同一个局域网的主机都能接受到数据，所以选B

而转发端口则与其不同，是不包括发生方的端口的，因为发送方也能接受到是因为自己发送的数据在缓冲区中可以收到，而不是转发出去了，因为转发端口如(集线器)，是转发不包含发送方的端口的端口

根据转发表来转发就可以了，本来1要转发给3的，但是转发表中没有1到3的路由表项，因此就把广播信息转发出去给出发送端口1之外的端口2和端口3，并将端口1的信息添加到转发表上，因为交换机知道，哦哦！！原来主机00-e1-d5-00-23-a1可以通过端口1到达，就记录在转发表中了。而主机00-e1-d5-00-23-ca接收到广播帧后，知道这个帧是发给自己的，所以发送确认帧回00-e1-d5-00-23-a1主机，且因为交换机中有转发给00-e1-d5-00-23-a1的表项，接口为1，所以就直接转发给端口1了，无需再全部转发。

---

8. P150 T37 做对，好题！！！考了一个(码分复用)
   

C从链路上收到的序列是A、B、C码片序列在传输过程中线性相加得到的结果，而到达C之后，需要对序列进行分离才能得到对应的站点所发送的比特信息，而获取对应站点发送的比特信息，就需要知道对应站点的码片序列，且不同站点的码片序列相互正交，想要获取对应站点发送过来的比特信息，只需要把C从链路上接收到的序列按一组的码片进行算内积，那么就能获得对应站点发送一次码片所传输的比特信息。
C收到的序列以和A、B、C码片序列的个数进行分组，这里以4个位一组分别为
(2,0,2,0)、(0,-2,0,-2)、(2,0,2,0)，分别与A的码片序列(1,1,1,1)进行正交内积，并除以一组的序列长度，即可获得比特信息
(2,0,2,0).(1,1,1,1)/4=1
(0,-2,0,-2).(1,1,1,1)/4=-1
(2,0,2,0).(1,1,1,1)/4=1
在码分多路复用中，规定，-1为0，1为1，因此传输的比特信息就为101

综合题

数据结构

考了WPL、图的存储结构、DJ最短路径和费由
DS-第五章-二叉树的遍历、图-DS-第五章

计算机组成原理

1. P152 T44 ----错题----难题
   

错误原因:看了偏移量16位，而指令字长为32为，就写了半字编址。但是编址单位不是这么看的，是要看一条指令在主存中占了多少个地址单元

第一问：
因为一条指令占4B，而一条指令在主存中的地址存放单位是4个存储单元（如第一条指令为00H~03H），因此4B/4=1B，主存是按字节编址的

第二问

分析其执行过程，其实关键的还是第一句的指令(R2)<< 2—>R4,R2的值每次乘4放在R4中，而R2通过编号5的指令可知，其值是中0,1,2,3,…,n这样变化的，因此每次R4偏移的单位为4，而数组A的地址每次累加R4的内容，因此主存地址也是每循环一轮移动4个单元，而主存由第一问可知是按字节编址的，因此数组A的每个元素占4B

第三问
①根据题目的条件，锁定要算的指令为编号6的机器代码，因为OFFSET占2B，因此最后两个字节为FFFAH，因为是补码，通过一休学长的方法，可以快速算出补码，为-0006H，真值为-6
②因为编号6的指令地址为08048114H，而在取值后PC自增指令字长，因此取值后，PC的值为08048118H，而要跳转到08048100H，之间相差了18H，即24，而OFFSET的值为-6，因此其偏移量的单位为24/6=4
因此可以得出转移目的地址的公式为:PC=(PC)+4+4*OFFSET

第四问：考点：指令流水线
①通过对同一个寄存器前写，后读，中间没有隔开3个时钟周期的话，就有数据相关，因此可得，因数据相关阻塞的指令编号为：2,3,4,6。因为编号2,3,4,6指令与前一条指令没有隔开3条指令，产生了数据相关。因此导致了流水线的阻塞。
②编号6的指令的执行会发送控制冒险，控制冒险只有在转移指令、call调用、ret返回指令使得PC改变，才会导致控制冒险，因此编号6的指令的执行会发送控制冒险
③通过对同一个寄存器前写，后读，中间没有隔开3个时钟周期的话，就有数据相关，而编号5和编号1中间只隔开了一条指令，但是因为分支指令的执均会引起3个时钟周期的阻塞，刚好使得编号5和编号1的指令没有数据相关的冲突。

---

2. P153 T45

第二问的第二小问Cache的命中率、第三问。错误原因:我理解第一次访问指令的时候指令Cache肯定是缺失的，因为指令在主存中，而指令只需要6 * 4B=24B<32B，一次存储这6条指令只需要一个块，我拿了15/16=93.75%，错误算法，因为这16个Cache指令行都没装满，只用了6行，所以不能这么算

第二问的第二小问Cache的命中率
正确算法：因为这些指令都要执行1000次，而只在第一次执行的时候的第一条指令Cache缺失，而之后的执行都没有缺失了。因此
Cache的命中率=(1000 * 6-1) / (1000 * 6）=99.98%

第三问

由题目得，数组A是未调入主存的，当指令要访问数组A的时候，VA->PA，访问TLB，因为数组A还未调入主存，因此TLB肯定是不命中的，这时候TLB已经访问了一次，然后TLB未命中，VA就需要去访问主存得到数组A存放的物理地址，得到数组A的物理地址后就去访问页表，也是未命中，因此产生了缺页，发送缺页请求，CPU进行缺页处理，访问磁盘将数组A存放的物理块，由题目的数组元素存放在同一页，且存储在磁盘的同一个扇区，因为一个扇区就是一个物理块，因此将该物理块调入主存，就更新TLB和页表，之后就回到TLB上再次访问，因为数组A都在一个页面上，因此在TLB中都处于同一个页表项，因此在后面的访问数组A，VA->PA的过程中，TLB都是命中的，而因为数组A要访问1000次，而因为缺页导致TLB也不命中也访问了1次，一共访问了TLB次数=1001次。

---

操作系统

挂在了第二问:错误原因：4B=32bit，可以表示2³²个链接指针，我把它和4B相除了。导致错了。我以为是2³²B/2²B=2³⁰个指针，这样的算法是错的
正确的思路是：4B=32bit，可以表示2³²个链接指针，而每个链接指针表示一个磁盘块，那么最多可以表示2³²个磁盘块，因此，该文件系统的所支持的文件最大长度=(1024-4)B * 2³²=4080GB

计算机网络

和数据结构联动考察，但是考得不难，就考转发表、默认路由、TTL、Metric费用