【參考答案】

(1) 算法思想：

定義一個(gè)大小為N的數(shù)組，初始化為0.在遍歷鏈表的同時(shí)將數(shù)組中索引值為節(jié)點(diǎn)的值的絕對值的元素置1.如果此元素已經(jīng)為1，說明此節(jié)點(diǎn)之前已經(jīng)有與此節(jié)點(diǎn)的值的絕對值相等的節(jié)點(diǎn)，需將此節(jié)點(diǎn)刪除。

(2) 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義如下：

typedef struct Node

{

Int data;

Struct Node * next;

}Node;

(3) int a[n]; // 全局?jǐn)?shù)組標(biāo)志節(jié)點(diǎn)的絕對值的值是否出現(xià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) //如果此絕對值已經(jīng)在節(jié)點(diǎn)值的絕對值中出現(xiàn)過

{ //則刪除當(dāng)前節(jié)點(diǎn)

r->next = p->next;

delete p;

p = r->next;

}

else //否則，將數(shù)組中對應(yīng)的元素置1，并將指針指向下一個(gè)元素

{

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

r = p;

p = p->next;

}

}

return head;

}

(4)只遍歷一次鏈表，所以時(shí)間復(fù)雜度為O(n)，

因?yàn)樯暾埓笮�為n的數(shù)組，所以空間復(fù)雜度為O(n)，(n為節(jié)點(diǎn)絕對值的最大值)。

【考查知識點(diǎn)】鏈表的操作。

42. 已知有5個(gè)頂點(diǎn)的圖G如下圖所示

圖G

請回答下列問題

(1) 寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始)

(2) 求A2，矩陣A2中位于0行3列元素值的含義是什么?

(3) 若已知具有n(n>=2)個(gè)頂點(diǎn)的鄰接矩陣為B，則Bm(2<=m<=n)非零元素的含義是什么?

【參考答案】

(1)略

(2)略

(3)Bm中非零元素的含義是：假設(shè)此頂點(diǎn)位于i行j列，如果i==j，則表示i頂點(diǎn)到自己的距離為0;如果i≠j，則表示頂點(diǎn)i到達(dá)不了頂點(diǎn)j。

【考查知識點(diǎn)】鄰接矩陣的概念，最短路徑。

43. (13分)某16位計(jì)算機(jī)主存按字節(jié)編碼。存取單位為16位;采用16位定長指令格式;CPU采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0~R3為通用寄存器;T為暫存器;SR為移位寄存器，可實(shí)現(xiàn)直送(mov)、左移一位(left)、右移一位(right)3種操作，控制信號為Srop,SR的輸出信號Srout控制;ALU可實(shí)現(xiàn)直送A(mova)、A加B(add)、A減B(sub)、A與B(and)、A或B(or)、非A(not)、A加1(inc)7種操作，控制信號為ALUop。

圖片二

請回答下列問題。

(1) 圖中哪些寄存器是程序員可見的?為何要設(shè)置暫存器T?

(2) 控制信號ALUop和SRop的位數(shù)至少各是多少?

(3) 控制信號Srout所控制郵件的名稱或作用是什么?

(4) 端點(diǎn)①~⑨中，哪些端點(diǎn)須連接到控制部件的輸出端?

(5) 為完善單總線數(shù)據(jù)通路，需要在端點(diǎn)①~⑨中相應(yīng)的端點(diǎn)之間添加必要的連線。寫出連線的起點(diǎn)和終點(diǎn)，以正確表示數(shù)據(jù)的流動方向。

(6) 為什么二路選擇器MUX的一個(gè)輸入端是2?

【參考答案】

(1) 圖中程序員可見的寄存器有通用寄存器R0~R3和程序計(jì)數(shù)器PC;設(shè)置暫存器T用于暫存數(shù)據(jù)總線發(fā)送的數(shù)據(jù)。

(2) ALUop和SRop的位數(shù)分別為3,2。

(3) Srout所控制的部件作用是控制計(jì)算機(jī)運(yùn)算結(jié)果的輸出。

(4) 須連接到控制部件的輸出端端點(diǎn)有①②③⑤⑧。

(5) ⑥→⑨，⑦→④。

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

【考查知識點(diǎn)】寄存器相關(guān)概念及寄存器的操作，單總線結(jié)構(gòu)

44. (10分)題43中描述的計(jì)算機(jī)，其部分指令執(zhí)行過程的控制信號如如題44圖a所示。

題44圖a 部分指令控制信號

該機(jī)指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1，通用寄存器R0~R3的編號分別為0、1、2和3。

題44圖b 指令格式

圖b

該機(jī)指令格式如題44圖b所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為0和1，通用寄存器R0~R3的編號分別為0、1、2和3。

指令格式

請回答下列問題。