2015年考研計算機專業(yè)基礎(chǔ)綜合真題及分析(3)

來源：唯學網(wǎng)•教育培訓(m.ormdc.com) 【唯學網(wǎng) • 中國教育電子商務(wù)平臺】加入收藏

【參考答案】

(1) 算法思想：

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

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

typedef struct Node

{

Int data;

Struct Node * next;

}Node;

(3) int a[n]; // 全局數(shù)組標志節(jié)點的絕對值的值是否出現(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é)點值的絕對值中出現(xiàn)過

{ //則刪除當前節(jié)點

r->next = p->next;

delete p;

p = r->next;

}

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

{

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

r = p;

p = p->next;

}

return head;

}

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

因為申請大小為n的數(shù)組，所以空間復雜度為O(n)，(n為節(jié)點絕對值的最大值)。

【考查知識點】鏈表的操作。

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中非零元素的含義是：假設(shè)此頂點位于i行j列，如果i==j，則表示i頂點到自己的距離為0;如果i≠j，則表示頂點i到達不了頂點j。

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

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

圖片二