【参考答案】
(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
if (head == NULL)
{
return NULL;
}
Node * p = head;
Node * r = head;
while (p != NULL)
{
if (a[abs(p->data)] == 1) //如果此绝对值已经在节点值的绝对值中出现过
{ //则删除当前节点
r->next = p->next;
delete p;
p = r->next;
}
else //否则，将数组中对应的元素置1，并将指针指向下一个元素
{
a[abs(p->data)] = 1;
r = p;
p = p->next;
}
}
return head;
}
(4)只遍历一次链表，所以时间复杂度为O(n)，
因为申请大小为n的数组，所以空间复杂度为O(n)，(n为节点绝对值的最大值)。
【考查知识点】链表的操作。
42. 已知有5个顶点的图G如下图所示
图G
请回答下列问题
(1) 写出图G的邻接矩阵A(行、列下标从0开始)
(2) 求A2，矩阵A2中位于0行3列元素值的含义是什么?
(3) 若已知具有n(n>=2)个顶点的邻接矩阵为B，则Bm(2<=m<=n)非零元素的含义是什么?
【参考答案】
(1)略
(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 指令格式
图b
该机指令格式如题44图b所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0~R3的编号分别为0、1、2和3。
指令格式
请回答下列问题。
