2015年计算机考研真题解析

}

else //否则，将数组中对应的元素置1，并将指针指向下一个

元素 }

(4) 只遍历一次链表，所以时间复杂度为O(n)，

因为申请大小为n的数组，所以空间复杂度为O(n)，（n为节点绝对值的最大值）。 【考查知识点】链表的操作。

42. 已知有5个顶点的图G如下图所示

}

return head;

{ }

a[abs(p->data)] = 1; r = p; p = p->next;

请回答下列问题

(1) 写出图G的邻接矩阵A(行、列下标从0开始) (2) 求A2，矩阵A2中位于0行3列元素值的含义是什么？

(3) 若已知具有n(n>=2)个顶点的邻接矩阵为B，则Bm(2<=m<=n)非零元素的含义是什么？ 【参考答案】 (1)邻接矩阵为

（2）

0行3列的元素的含义是顶点0到顶点3的最短距离为2.

（3）Bm中非零元素的含义是：假设此顶点位于i行j列，如果i==j，则表示i顶点到自己的距离为0；如果i≠j，则表示顶点i到达不了顶点j。

【考查知识点】邻接矩阵的概念，最短路径。

43. （13分）某16位计算机主存按字节编码。存取单位为16位；采用16位定长指令格式；CPU采用单总线结构，主要部分如下图所示。图中R0~R3为通用寄存器；T为暂存器；SR为移位寄存器，可实现直送(mov)、左移一位(left)、右移一位(right)3种操作，控制信号为Srop,SR的输出信号Srout控制；ALU可实现直送A(mova)、A加B(add)、A减B(sub)、A与B(and)、A或B(or)、非A(not)、A加1(inc)7种操作，控制信号为ALUop。

请回答下列问题。

(1) 图中哪些寄存器是程序员可见的？为何要设置暂存器T？ (2) 控制信号ALUop和SRop的位数至少各是多少？ (3) 控制信号Srout所控制邮件的名称或作用是什么？ (4) 端点①~⑨中，哪些端点须连接到控制部件的输出端？

(5) 为完善单总线数据通路，需要在端点①~⑨中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向。 (6) 为什么二路选择器MUX的一个输入端是2？ 【参考答案】

(1) 图中程序员可见的寄存器有通用寄存器R0~R3和程序计数器PC；设置暂存器T用

于暂存数据总线发送的数据。 (2) ALUop和SRop的位数分别为3,2。

(3) Srout所控制的部件作用是控制计算机运算结果的输出。 (4) 须连接到控制部件的输出端端点有①②③⑤⑧。 (5) ⑥→⑨，⑦→④。

(6) 使PC自增2以获取下一条指令地址。

【考查知识点】寄存器相关概念及寄存器的操作，单总线结构

44. （10分）题43中描述的计算机，其部分指令执行过程的控制信号如如题44图a所示。

题44图a 部分指令控制信号

该机指令格式如题44图b所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0~R3的编号分别为0、1、2和3。

题44图b 指令格式

请回答下列问题。

(1) 该机的指令系统最多可定义多少条指令？

(2) 假定inc、shl和sub指令的操作码分别为01H、02H和03H，则以下指令对应的机 器代码各是什么？

① inc R1 ; R1 + 1→R1 ② shl R2,R1 ; (R1) << 1→R2