2016 408选择题错题

1

设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编 为1-9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7.若期望驶出的次序依次为1-9，则n至少是 4
这有点像栈，先入的反而要后出。
8进，8后面只能跟9，89一队
4进，4后面只能跟567，4567是一队
2进，2后面只能跟3，23是一队
1独自是一队

2

有一个100阶的三对角矩阵M，其元素mi，j（1 对角矩阵也称为带状矩阵，对于n阶方阵A中的任一元素ai，j，当|i-j|>1时，有ai，j=0（1 在三对角矩阵中，所有非0元素都集中在以主对角线为中心的三条对角线的区域，其他区域的元素都为0。

稀疏矩阵：矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即s>>t的矩阵成为稀疏矩阵。
将非零元素及其相应的行和列构成一个三元组（行标，列标，值），稀疏矩阵压缩存储后便失去了随机存取特性。稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。

3

对10TB的数据进行排序，应使用的方法是 归并排序。
在排序过程中，根据数据元素是否完全在内存，可将排序算法分为两类：
1内部排序，是指排序期间元素全部存放在内存的排序；
2外部排序，是指在排序期间元素无法全部同时存放在内存之中，必须在排序的过程中根据要求不断地在内存，外存之间移动的排序。

4

翻译程序是指把高级语言源程序转换成机器语言程序（目标代码）的软件。翻译程序有两种：一种是编译程序，它将高级语言源程序一次全部翻译为目标程序，每次执行程序时，只需执行目标程序，因此，只要源程序不变，就无需重新编译。另一种是解释程序，它将源程序的一条语句翻译成对应的机器目标代码，并立即执行，然后翻译下一条源程序语句并执行，直至所有源程序语句全部被翻译并执行完。所以解释程序的执行是翻译一句执行一句，并且不会生成目标程序。汇编程序也是一种语言翻译程序，它把汇编语言源程序翻译为机器语言程序，汇编语言是一种面向机器的低级语言，是机器语言的符 表示，与机器语言一一对应。

5

有如下c语言程序段：
short si = -32676；
unsigned short usi = si；
执行上述两条语句后，usi的值为

-32676的原码为：1111 1111 1111 1111，最高一位为符 位；
数据在计算机中以补码的形式存在
补码为：1000 0000 0000 0001；
它变为无符 数后，最高位不再代表符 ，代表2^15=32768；
加上末尾的1就是32769；

6

有如下c语言段：
for(k=0;k a[k]=a[k]+32;
若数组a及变量k均为int型，int型数据占4B，数据Cache采用直接映射方式，数据区大小为1KB，块大小为16B，该程序段执行前Cache为空，则该程序段执行过程中访问数组a的cache缺失率为

程序访问的局部性原理包括时间局部性和空间局部性。时间局部性是指在最近的未来要用到的信息，很可能是现在正在使用的信息，因为程序中存在循环。空间局部性是指在最近的未来要用到的信息，很可能与现在正在使用的信息在存储空间上是邻近的，因为指令通常是顺序存放，顺序执行的，数据一般也是以向量，数组等形式簇聚地存储在一起的。
一个块为16B，一个int型数据为4B，所以一个块内装有4个数据。
a[k]=a[k]+32;
首先需要取出a[k]这个数。访存一次，之后加上32再访存一次将其写回。
对于一个块而言，需要访存八次，只有一次需要从主存调取。

7

2000H就是0010 0000 0000 0000 就是2^13B，单位是B不是bit。
也就是8KB

高速缓存的局部性原理。

8

为什么单周期处理器不能采用单总线结构。
单周期处理器要求在一个周期内完成所有的工作
完成一条指令最多需要四个工作周期，包括取值，间值，执行和中断。
单周期处理器在一个时钟周期内把这些工作都完成了，而单总线结构一个时钟周期内只能传送一类数据。比如取了指令就取不了操作数。
所以单周期处理器不能采用单总线结构。

控制信 即指的是PC中的内容，PC用来存放当前欲执行指令的地址，可以自动+1形成下一条指令的地址。在指令执行过程中控制信 不变化。

9

总线通信有四种方式：
总线定时是指总线在双方交换数据的过程中需要时间上配合关系的控制，这种控制称为总线定时，其实质是一种协议或规则，主要有同步和异步两种基本定时方式。
申请分配阶段
寻址阶段
传输阶段
结束阶段
同步定时方式的优点：传送速度快，具有较高的传送速率；总线控制逻辑简单
缺点：主从设备属于强制性同步；不能及时进行数据通信的有效性检验，可靠性较差。
同步通信适用于总线长度较短及总线所接部件的存取时间比较接近的系统。

异步通信方式：
优点：总线周期长度可变，能保证两个工作速度相差很大的部件或设备之间可靠地进行信息交换，自动适应时间的配合。
缺点：比同步控制方式稍复杂一些，速度比同步定时方式慢。

分离式通信可以充分挖掘总线的潜力
其原因是每个模块在使用完总线后即放弃总线，而且采用同步方式，无需等待对方应答。

并行总线传输通常比串行总线传输较快，但这不是绝对的。在实际时钟频率比较低的情况下，并行总线因为可以同时传送若干比特，速度确实比串行总线快。但随着时钟频率越来越高，并行导线之间的干扰越来越严重，当时钟频率提高到一定程度时，传送的数据已经无法恢复，而串行总线因为导线少，线性干扰容易控制，反而速率更快。

10

页面置换算法
时钟置换算法：
CLOCK算法是最近未用算法，指将最近访问过的帧的使用位置1，优先将使用位为0，即最近未使用的帧换出。
改进型CLOCK置换算法：
改进的CLOCK算法又增加了修改位，不过修改位的优先级要低于使用位。

11

TSL指令是一种需要硬件支持的方案，它将一个存储字读到一个寄存器中，然后在该内存地址上存上一个非零值，读数和写数操作保证是不可分割的-即该指令结束前其他处理机均不允许访问该存储字，，执行TSL指令的CPU将锁住内存总线以禁止其他CPU在本指令结束之前访问内存。
TSL伪代码
do{
。。。。。。
while（TSL（&lock））；
critical section；
lock=FALSE；
。。。
}while（TRUE）；
这段代码有个大坑：
while（TSL（&lock））；它有分 代表它是一个独立的循环，当while里面为TRUE时，一直进行循环，相当于卡在这了；当while里面为FALSE时，才会跳出这个循环。
critical section表示临界的区域。
所以等待进入临界区的进程不会主动放弃CPU，它会一直在那卡着循环，直到while里面为FALSE，能跳出来的时候才会放弃CPU。

12

进程工作集：一个进程当前使用页的集合

13

管程
在信 量机制中，每个要访问临界资源的进程都必须具备同步的PV操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致进程死锁。于是，便产生了一类进程新的进程同步工具-管程。管程的特性保证了进程互斥，无需程序员自己实现互斥，从而降低了死锁发生的可能。系统中的各种硬件资源和软件资源，均可用数据结构抽象的描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略他们的内部结构和实现细节。
利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请，释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程。

管程定义了一个数据结构和在该数据结构上的一组操作，这组操作能同步进程和改变管程中的数据。
管程很像一个类，把对共享资源的操作封装起来，每次仅允许一个进程进入管程，从而实现互斥。
x.wait 当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。
x.signal x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程。

莞城可以实现互斥，也可以实现同步。

14

香农定理给出了带宽受限且有高斯白噪声干扰的信道的极限数据传送速率，香农定理定义为：
信道的极限数据传输速率=Wlog2（1+S/N）,单位bps。其中S/N为信噪比，即信 的平均功率和噪声的平均功率之比。信噪比=10log10（S/N），单位dB

当S/B为1000时，信噪比为30dB，则该链路上的实际数据传送速率约为50%Wlog2（1+S/N）=0.58kHz*10=40kbps。

15

DNS协议
DNS系统采用客户/服务器模型，其协议运行在UDP之上，使用53 端口。
顶级域名
.cn中国，.us美国，.uk英国
.com公司，.net 络服务机构，.org非盈利性组织，.gov国家或政府部门

根域名服务器用来管辖顶级域（.com），通常它并不直接把待查询的域名直接转换成IP地址，而是告诉本地域名服务器下一步应当找哪个顶级域名服务器进行查询

顶级域名服务器负责管理在该顶级域名服务器所注册的的所有二级域名。

授权域名服务器

本地域名服务器

递归查询和递归与迭代相结合的查询。

16

若交换机再生比特流过程中，会产生1.535us延时，信 传播速度为200m/us，不考虑以太 帧的前导码，则H3和H4之间理论上可以相距的最远距离是。
因为要解决“理论上可以相距的最远距离”，所以最远肯定要保证能检测到碰撞，而以太 帧规定最短帧长为64B，其中交换机为100Base-T集线器，可知线路的传送速率为100Mbps，则单程的传播时延为2.56us，从而两台主机之间理论上可以相距的最远距离为200m/us*（2.56-1.535）=205m