一、单项选择题：第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．已知表头元素为c的单链表在内存中的存储状态如下表所示。
现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a, e, f的“链接地址”依次是___。
A．1010H, 1014H, 1004H
B．1010H, 1004H, 1014H
C．1014H, 1010H, 1004H
D．1014H, 1004H, 1010H
解答：题目中说了该链表的表头元素是c,然后从上图我们可以看出各个元素之间的链接关系是c–>a–>e–>b–>d,
而现在题目要求我们将f插入该链表，并且要让f在逻辑上位于a和e之间，即c–>a–>f–>e–>b–>d，题目中也说了要将f存放于1014H处，也就是使得a的下一个链接地址应是1014H, 而f的下一个链接地址是e,所以使得f的下一个链接地址应该是1010H, 到这里我们已经选出正确答案D了
解答: 在删除p之前一定要把p的前驱节点和后继节点连接好，再删除。 把A,B,C,D一个个检验就可以了，符合条件的就可以选, 最后答案选D.
解答：首先我们分析一下题意，“轨道”类似于什么数据结构，想到了吗？先进先出啊，当然是“队列”，
然后根据队列的先进先出特性， 最后我们可以得出这道题的结果
总共是4条轨道，所以选C
4．有一个100阶的三对角矩阵M，其元素mi,j（1≤i≤100,1≤j≤100）按行优先依次压缩存入下标从0开始的一维数组N中。元素m30,30在N中的下标是____。
A.86 B.87 C.88 D.89
解答：做这道题之前，我们必须要先知道什么是“三对角矩阵”，看看下面的定义吧
然后对于元素m30,30而言，因为在它之上总共是29行（题目条件：元素mi,j（1≤i≤100,1≤j≤100）），其中第一行有2个元素，其他28行每行有3个元素，而元素m30,30所在的那一行还有一个元素在元素m30,30之前，是元素m30,29，所以元素m30,30之前总共有2+28*3+1=87个元素，所以选B
5．若森林F有15条边、25个结点，则F包含树的个数是____。
A.8 B.9 C.10 D.11
解答：首先我们要清楚什么是森林，森林就是很多个单独的树组成的嘛。 而树有什么特性？ 我们知道一颗树的节点数和边数的关系是 节点数=边数+1。 如此一来，这道题就很简单了。因为每一棵树都符合节点数=边数+1 这个规律，那每多一颗树，那总结点数就比总边数多一个，而题目中告诉了我们该森林总共有15条边，25个节点， 那25-15=10 ，所以树的总数是10，选C即可
解答：做这道题之前，我们先要明白什么是深度优先遍历，就是一根筋深挖到底。 对于ABCD这4个选项，我们可以一个个的做实验，最后发现A,B,C都符合深度优先遍历的结果。而唯独D不符合，D中V1, V2, V3, V4, V5， 这个V2到V3就是错的，图中根本没有V2到V3的指向指针，所以D不是深度优先遍历序列，所以本题答案选D
7．若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是____。
A．O(n)
B．O(n+e)
C．O(n2)
D．O(n*e)
解答：做这道题之前，我们首先要知道什么是拓扑排序算法。拓扑排序算法的操作步骤如下：
从有向无环图中找到一个没有前驱的顶点输出。(可以遍历，也可以用优先队列维护)
删除以这个点为起点的边。(它的指向的边删除，为了找到下个没有前驱的顶点)
重复上述，直到最后一个顶点被输出。如果还有顶点未被输出，则说明有环！
明白了这个规则以后，我们就可以来做本题了，每访问到一个顶点，我们都会删除与之相关的边。而题目中有n个顶点，那就删n次，而题目中有e条弧，所以也要删e次。 所以删除节点和删除弧一共要进行n+e次删除操作。所以本题选B
8．使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是____。
A．5, 2, 3, 4, 6
B．5, 2, 3, 6, 4
C．5, 2, 4, 3, 6
D．5, 2, 6, 3, 4
解答：做这道题之前，我们首先要知道什么是迪杰斯特拉（Dijkstra）算法。明白了这个算法以后我们再来解这道题就容易了
,选B
9．在有n（n＞1000）个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示
本算法与折半查找算法相比，有可能具有更少比较次数的情形是____。
A．当x不在数组中
B．当x接近数组开头处
C．当x接近数组结尾处
D．当x位于数组中间位置
解答：我们首先来看一下这段伪代码的逻辑，看完以后发现其实代码思想很简单，就是从数组第一个元素开始，3步3步的跳，本质还是一个顺序查找思想，从头往后遍历罢了，只不过是每次跳3步而已。 所以本题我们就是需要比较顺序查找和折半查找算法的优缺点嘛，然后看ABCD这4个选项，一看发现B是顺序查找的优点，那就选B即可
10．B+树不同于B树的特点之一是____。
A．能支持顺序查找
B．结点中含有关键字
C．根结点至少有两个分支
D．所有叶结点都在同一层上
正确答案: A
解答：做这道题之前，我们首先要明白什么是B+树，什么是B树。 B树和B+树的区别
正确答案: D
解题思路:
首先我们写出-32767的原码是1111 1111 1111 1111，那对应的补码就是1000 0000 0000 0001
而unsigned short usi=si; 说明usi是无符号整数。 所以1000 0000 0000 0001对应的无符号整数值是32769.
正确答案：A
解题思路：题目说了按字节编址，也就是说每个单元存一个字节的数据，也就是8bit.
正确答案: C
解题思路：先看for循环执行的代码，说白了就是先访问a[k],然后把a[k]加上32以后再写回a[k].所以访问了2次。
而主存与cache之间进行数据交换是以数据块为单位，本题说
了数据块大小是16B，而int型数据是4B， 也就是说一次性可以加载4个int型数据到cache中。
打个比方，第一-次访问a[1]的时候，cache缺失，然后一次性加载a[1], a[2],a[3],a[4]到cache中，这个时候第二次访问a[1]的时候，cache命中。然后取a[2]命中，a[2]+32以后写回a[2]也命中…
也就是说对a[1], a[2],a[3],a[4]的8次访问中，只有第一次是发生
了cache缺失，后面7次都是cache命中，故而缺失率是12.5%
正确答案:C
解题思路: 本题无非就是考察什么是变址寻址和间址寻址。
正确答案: B
解题思路:
首先我们要明白程序计数器PC里面存放的是下一条指令的地址； 而指令寄存器(IR)是存放的是指令的内容本身；
而题目中说了指令是按字边界对齐存放，而题目中也说了一个字长是32位，所以最多有
4
G
B
32
b
i
t
=
2
30
\frac{4GB}{32bit}=2^{30}
32bit4GB?=230，所以啊PC的位数就是30
而指令寄存器IR的位数是跟指令的长度有关的，本题说了指令是定长指令32位，所以指令寄存器也是32位。
正确答案:B
解题思路：首先我们要明白什么是数据冒险,所谓的数据冒险就是读了脏数据
数据冒险，即数据相关，指在一个程序中存在必须等前一条指令 执行完才能执行后一条指令 的情况，则这两条指令即为数据相关。当多条指令重叠处理时就会发生冲突。
指令I2在时钟5时将结果写入寄存器(R5)，但指令I3在时钟3时读寄存器(R5)。本来指令 I2应先写入R5，指令I3后读R5，结果变成指令I3先读R5，指令12后写入R5，因而发生数据冲突。
正确答案:A
解题思路:
首先看A,如下图所示，如果是单总线的话，那就会有很多的冲突问题， IO接口之间互相交换数据，主存与IO之间交换数据等等。 所以不能采用单总线结结构。一般是单周期处理器和多总线结构搭配。 或者是多周期处理器和单总线结构搭配。
再看B选项，由于把所有指令的执行过程都压缩到一个时钟周期，那如果时钟周期太短，那怎么可能执行的完这些过程呢？所以时钟周期应该很长。从而时钟频率肯定就比较低了
再看选项C,在指令执行过程中，控制信号不变，这个确实是的，记住就行
最后看选项D,说每条指令的CPI是1，这个是肯定的了，因为题目说了每条指令的周期是一个时钟周期，那CPI当然是1啊
正确答案: A
解题思路: 先看选项A, 随着技术的发展，如果时钟频率越来越高，那并行总线之间会产生相互的干扰会影响最后的传输速度。
再看选项B, 信号先复用技术，当然可以减少信号线数量啊
再看选项C, 我们要知道什么是突发传输方式，突发（Burst是指在同一行中相邻的存储单元连续进行数据传输的方式，连续传输的周期数就是突发长度（Burst Lengths，简称BL）。在突发传输模式下，多个数据单元当做一个单元（相当一个数据块）来传送，从而提高了传输效率。
最后看看选项D, 分离事务通信方式提高总线利用率，这个记下就行
正确答案: A
解题思路： 先看选项A, 我们知道访存操作是处理器内部操作，访问某个数据，发现找不到，即缺页异常。 所以A不是中断，应该是异常才对
再看选项B, 整数除以0，肯定是处理器内部的操作了，故而也是异常
再看选项C, DMA是个I/O接口，DMA传输结束告诉CPU,然后可以CPU就知道I/O处理结束，可以干别的事情了。
最后看选项D, 也是由于处理器往存储器里存数据发生的异常。
正确答案: A
解题思路: 首先看I,肯定是错的，因为批处理系统是不支持用户与计算机交互的。 分时操作系统才支持交互
然后再看II, 说法没问题。 再看III,也是正确的。
正确答案: B
解题思路: 对于这种题，画个甘特图就一目了然了 （注：题目里面说了是单CPU，所以作业的计算也只能顺序执行，不能并发执行。 也就是说下图里的输入，计算，输出都是排他性的，不支持并发）
正确答案:C
解题思路:
对于本题，先满足P4进程的资源需求，再看其他进程是否能出现死锁状态。因为P4只申请一个资源，当将R2分配给P4后P4执行完后将R2释放，这时使得系统满足死锁的条件是R1分配给P1，R2分配给P2，R3分配给P3 (或者R2分配给P1,R3分配给P2, R分配给P3)。穷举其他情况如P1申请的资源R1和R2，先都分配给P1，运行完并释放占有的资源后，可以分别将R1、R2和R3分配给P3、P4和P2， 也满足系统死锁的条件。各种情况需要使得处于死锁状态的进程数至少为3。
所以本题只能一个个枚举，推导，没有其他更简单的办法。
正确答案:A
解题思路; 首先我们要知道什么是改进型CLOCK置换算法
改进型Clock算法 由 访问位A 和 修改位M 可以组合成下面四种类型的页面：
1类(A=0, M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。（说不定什么时候就有可能会访问了，所以没必要把该页置换出去）
3类(A=1, M=0)：最近已被访问， 但未被修改，该页有可能再被访问。所以没必要把该页置换出去
4类(A=1, M=1)：最近已被访问且被修改，该页可能再被访问。所以没必要把该页置换出去
