学习-----好资料 【参考答案】 (1) 算法思想：
定义一个大小为N的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。
(2) 节点的数据结构定义如下：
typedef struct Node {
Int data;
Struct Node * next; }Node;
(3) int a[n]; // 全局数组 标志节点的绝对值的值是否出现过 void DeleteABSEqualNode(Node * head) {
memset(a,0,n); // 初始化为0
Node * p = head; Node * r = head; while (p != NULL) {
if (a[abs(p->data)] == 1) //如果此绝对值已经在节点值的绝对值中出现过 { //则删除当前节点
r->next = p->next; delete p; p = r->next;
if (head == NULL) { }
return NULL;
更多精品文档
学习-----好资料
}
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)邻接矩阵为
更多精品文档
学习-----好资料
?0?1???1?0???0
（2）
1100?
0011???0010? 1101?
?
1030??
?0?1?2?A=?2?2???21122?0211???1012? 1101??1210??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 ③ sub R3, (R1),R2 ; ((R1)) – (R2) → R3
(3) 假定寄存器X的输入和输出控制信号分别为Xin和Xout，其值为1表示有效，为0表示无效（例如，PCout=1 表示PC内容送总线）；存储器控制信号为MEMop，用于控制存储器的读(read）和写(write)操作。写出题44图a中标号①⑧处的控制信号或控制信号的取值。
(4) 指令“sub R1,R3,(R2)”和“inc R1”的执行阶段至少各需要多少个时钟周期？ 【参考答案】 (1) 128
(2) ① 0280H，② (3) ① 0，②
04A8H，③ 06EEH
left，⑤ read，⑥ sub，⑦mov，⑧ Srout。
mov，③ mova，④
(4) 至少各需要8和7个时钟周期。
【考查知识点】指令的格式与寻址方式，指令执行过程
45. 有A、B两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中，设A的信箱最多放M个邮件，B的信箱最多放 N个邮件。初始时A的信箱中有x个邮件（0
最新-计算机专业基础综合真题及答案解析
