2017年全國計算機等級考試四級模擬試題及答案8

2017年全國計算機等級考試四級模擬試題及答案8二、論述題（兩個論述題可任選其一，并只選其一，多選無效，滿分30分。）

論述題１

本題要求設(shè)計一個學(xué)生試卷成績輸入、查詢和成績單輸出系統(tǒng)(簡稱SRS)的數(shù)據(jù)結(jié)構(gòu)和算法要點。問題描述如下：

要輸入到SRS系統(tǒng)中的每一份試卷成績反映一個學(xué)生選修一門課程的考試結(jié)果，它包括以下數(shù)據(jù)項：學(xué)號、姓名、課程名、成績。由于實行了靈活的選課制度，所以每個學(xué)生選修多少門課程，選修哪些課程都可以不同。要輸入的多份試卷成績并未按任何數(shù)據(jù)項排列順序，它們以任意的順序被輸入到系統(tǒng)中來。

SRS系統(tǒng)要具有以下功能：①試卷成績插入，將試卷成績逐個插入到SRS系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中。②學(xué)生成績查詢，給出學(xué)號查找該學(xué)生所選修的各門課程的考試成績。③成績單輸出，按學(xué)號遞增的順序依次輸出所有學(xué)生的學(xué)號、姓名，及其所選修的各門課程的課程名和成績。（為簡單起見，假設(shè)上述所有工作都在計算機內(nèi)存中進行。）

請設(shè)計SRS系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和算法要點，使上述三項操作都有較高的執(zhí)行效率。從以下方面闡述你的設(shè)計：

(1)SRS系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)（15分）

①數(shù)據(jù)結(jié)構(gòu)的Pascal語句描述

②數(shù)據(jù)結(jié)構(gòu)的示意圖

③數(shù)據(jù)結(jié)構(gòu)的簡單文字說明

(2)SRS系統(tǒng)的算法要點（10分）

（只要簡單的文字說明，不必寫出Pascal程序）

①試卷成績插入

②學(xué)生成績查詢

③成績單輸出

(3)簡單陳述你的上述設(shè)計的理由（5分）

論述題２

在一個盜竊案件中，已知下列事實：

①甲或乙是竊賊。

②若甲是竊賊，做案時間不會發(fā)生在夜間12點鐘以前。

③若乙的證詞正確，在夜間12點鐘時被盜物品所在房間燈光未滅。

④若乙的證詞不正確，則做案時間發(fā)生在夜間12點鐘以前。

⑤夜間12點鐘被盜房間燈光滅了。

根據(jù)以上事實解答或論證以下各題：

(1)將①～⑤中所出現(xiàn)的簡單命題符號化，然后用命題符號寫出①～⑤各復(fù)合命題的符號化形式。(10分)

(2)以(1)中給出的5個復(fù)合命題為前提，判斷甲、乙二人誰是竊賊(以符號形式給出)。(5分)

(3)用命題邏輯推理理論寫出(2)中結(jié)論的判斷過程(要求寫出每一步所用的推理規(guī)則)。(15分)二、論述題(兩個論述題可任選其一,并只選其一,多選無效,滿分30分)

論述題1評分參考：

本題可有多種不同的設(shè)計方案，下面給出其中一個較好的方案。

(1)數(shù)據(jù)結(jié)構(gòu)（15分，其中對三種操作的有效支持各4分，敘述的條理性3分。）

①數(shù)據(jù)結(jié)構(gòu)的Pascal語句描述

TYPEpptr=↑pnode;

pnode=RECORD

cname:string;

score:0..100;

next:pptr

END;

sptr=↑pnode;

snode=RECORD

sno:integer;

sname:string;

llink,rlink:sptr;

plink:pptr

END;

VARt:sptr;

②數(shù)據(jù)結(jié)構(gòu)的示意圖

③數(shù)據(jù)結(jié)構(gòu)的簡單文字說明

每個學(xué)生結(jié)點包含學(xué)生的學(xué)號和姓名，所有學(xué)生結(jié)點組織成一棵二叉排序樹，用link-rlink法存儲。

每份試卷成績作為一個鏈表結(jié)點，包含課程名和成績，每個學(xué)生的所有試卷成績結(jié)點鏈接成一個單鏈表，并且二叉排序樹的學(xué)生結(jié)點中有一個指針指向該單鏈表的第一個結(jié)點。

（2）算法要點（10分，三種操作各3分，敘述的條理性1分）

①試卷成績插入，根據(jù)試卷的學(xué)號在二叉排序樹中查找該學(xué)生結(jié)點。若找到，則在該學(xué)生結(jié)點所指的成績鏈表中插入一個成績結(jié)點；若未找到，則先在二叉排序樹中插入一個新的學(xué)生結(jié)點，然后再往這個學(xué)生結(jié)點所指的（空的）成績鏈表中插入一個成績結(jié)點。

②學(xué)生成績查詢，根據(jù)所給學(xué)號在二叉排序樹中查找該學(xué)生結(jié)點，再在該結(jié)點所指的成績鏈表中沿著指針讀出所有成績。

③成績單輸出。對二叉排序樹進行對稱序周游，在訪問到每個學(xué)生結(jié)點時輸出該結(jié)點指向的成績鏈表中的所有成績。

（3）設(shè)計理由（5分）

①學(xué)生結(jié)點組織成二叉排序樹，使三種操作都有較高的效率:插入n個學(xué)生結(jié)點O(nlog2n),查找一個學(xué)生結(jié)點O(log2n),輸出所有學(xué)生結(jié)點O(n)。

②每個學(xué)生的所有成績結(jié)點組織成鏈表，動態(tài)申請空間，適合于每個學(xué)生選修的課程數(shù)不等的實際情況，節(jié)省空間。

論述題2評分參考：

本題考查考生是否具有較強的邏輯思維和邏輯推理能力，并且考查考生是否掌握了邏輯推理的主要步驟和推理規(guī)則。

（1）的要點：考查考生命題符號化能力。（1）中含5個簡單命題：

p:甲是竊賊，

q:乙是竊賊，

r：做案時間發(fā)生在夜間12點鐘以前，

s:乙的證詞正確，

t:夜間12點鐘被盜房間燈光未滅。

（1）中含5個復(fù)合命題：

p∨q,p→┐r,s→t,┐s→r,┐t,每個復(fù)合命題2分，（1）的分值為10。

（2）的要點：考查考生邏輯思維能力。結(jié)論為乙是竊賊，符號化形式為q。(2)的分值為5。

（3）的要點：考查考生邏輯推理步驟和規(guī)則的掌握情況，整個推理由下面9步組成

①s→t前提引入

②┐t前提引入