2010
题目5：
度和结点数的关系：N_0+N_1+N_2+N_3+N_4=0\times N_0+N1+2\times N_2+3\times N_3+4\times N4+~1代入得N_0=82。
题目7：
有七个顶点，要保证任意时刻都连通，需要的最少的情况为，其中6个顶点两两相连，多一条边恰好7个顶点都相连。C_6^2+1=16条，6个顶点任意选两个相连，再加1条边即为所求。
题目15：
法1：2K \times4位\to8K \times8位，首先进行位拓展，将2个芯片连在一起，变成2K\times 8位，两片一组，一共需要4组。由8K\times8位可知，该存储器按字节编址，8k/4=2K，2k=2^{11}, 每一组最大可表示范围为11位。 第一组：0000H—07FFH。第二组：0800H-0FFFH。第三组：1000H-17FFH。第四组：1800H-1FFFH 0B1FH属于第二组，第二组最小地址为0800H。
法2：总存储器大小为8K，按字节编址，一共占13位，0B1FH=000==0.1==011.0001.1111B，一共四组，所以13位的高2位为片选号，即01为第二组。为0000.1000.0000.0000B=0800H。
题目26：
A.进程的时间片用完，可对其进行降低优先级操作。
B.进程刚完成I/O，此时应该尽快处理I/O，应该提高优先级。
C.进程长期处于就绪也要提高其优先级，避免饥饿。
D.刚从就绪就转为运行就降低其优先级不合理。
题目27：
题目为皮特森算法的具体实现，设置turn位，可用保证进程互斥进入临界区，并且，每个进程都会“谦虚”表示让对方先使用资源，也不会出现饥饿。
题目29：
题目30：
题目34：
需要的最少时间，则走上面的路线，只用经过两次中转，到达H2。传播过程如图所示。
题目41： 
注意，根据装填因子算出散列表的表长，7/x=0.7 x=10。查找不成功的平均查找长度，为从要找的散列位置到第一个出现空白的位置（空白说明这个元素没有在表中。）从0到6，因为任何数mod 7 只会得到0到6，超过这个值就不用计算查找不超过的查找长度。
题目42： 
1.向左移k位等于将整个数组反转后再将前p个数反转，再将后面剩余的n-p个元素反转。最后变换为题目所求。
2.
void reverse(int R[], int start, int end){
int temp=0; //临时变量，用于交换。
for(int i=0;i<(end-start+1)/2;i++){
temp=R[start+i];
R[start+i]=R[end-i];
R[end-i]=temp;
} // 实现反转
}
void func(){
reverse(R[],0,n-1);
reverse(R[],0,n-p-1);
reverse(R[],n-p,n-1);
}
3.时间复杂度为O(n)，空间复杂度为O(1)。
题目43：
1.根据OP的位数为4位可得，该指令系统最多有16条指令。根据Rs和Rd的位数为3可得，最多有8个通用寄存器。 字长为16位，主存地址空间为128KB, 得最多有64K个存储单元，所以MAR至少要16位，MDR位数要和机器字长系统，至少16位。
2.(PC)+(Rn)可表示的范围取决于寄存器的位数，所以为0到2^{16}-1。0000H~FFFFH 。
3.add(R4),(R5)+ 对应的机器码为0010 001 100 010 101 为2315H。执行后，R5和存储单元5678H会改变，R5变为5679H， 存储单元5678H变为68ACH。
题目44：
1.按字节编址，主存空间一共256MB，一共有28位，Cache有8行，需要3位作为cache行号，每个Cache行的大小64B，按字节编址，需要6位作为块内地址，Tag的位数为：28-3-6=19位，还需要一位有效位。一共20位，整个数据Cache的容量：8\times (64B+\frac{20bit}{8}B)=532B
2.法一：一个int型占4B，a[0][31]的首地址为：320+4*31=444，所在主存块号为\left \lfloor \frac{444}{64}\right \rfloor=6，所在cache行号为6 mod 8=6。a[1][1]的首地址为：320+255*4+2*4=1368。所在主存块号为\left \lfloor\frac{1368}{64} \right \rfloor=21，所在cache行号为 21 mod 8 =5.
法二：a[0][31]为444，其二进制低6位位块内地址，低7-9位为块号，444= ，二进制为 ==110==11 1100，所以组号为110B=6。a[1][1]为1368，二进制位10==101==01 1000，所以组号位101B=5。
3.程序A每次存取以行为单位，只有第一次丢失，命中率为15/16=93.75%，程序B中每次访存都不命中，命中率为0，访问cache比访问主存的速度快得多，所以程序A执行的时间更短。
题目45：
1.2KB=2*1024*8=16384bit，刚好每一bit表示一个磁盘块的空闲状态，采用位示图进行管理。
2.访问磁道顺序：120，30，50，90，经过磁道数20+90+20+40=170.磁盘转一圈所需时间：60/6000=10ms，扫过一个扇区所需时间10/100=0.1ms，旋转延迟：4*10ms*0.5=20ms，一共需要170+20+0.1*4=190.4ms。（时间为平均寻道时间+旋转延迟+读取时间）
3.采用FCFS磁盘调度策略，Flash半导体存储器无需进行磁盘寻道和旋转延迟。比CSCAN磁盘调度策略更高效。
题目46：
1.一共64KB，按字节编址，占16位，页的大小为1KB需要10位，剩下6位为页号，即高6位为页号
17CAH=0001 0111 1100 1010 页号为0001 01=5。
2.FIFO算法，0号最先进入，将0号置换，页框号为7，物理地址为页框号拼接，为0001 1111 1100 1010=1FCAH。
3.时钟置换算法，查看指向的访问位，如果为1则不换出，经过后将其的访问位改为0，转一圈后将2号页换出，页框号为2，对应的物理地址为0000 1011 1100 1010=0BCAH。
题目47：
Comments NOTHING