一、選擇題:(共90題,分為1分題和2分題,滿份120分。帶“*”的題為2分題,其餘均為1分題。)
1.B 2.C * 3.C * 4.A 5.D
6.B * 7.B 8.B 9.D 10.C
* 11.C 12.B 13.D 14.C 15.C
* 16.D 17.C 18.B * 19.D 20.C
21.D 22.C 23.B * 24.C 25.A
26.D 27.B * 28.A 29.C * 30.C
* 31.A 32.D 33.B 34.D * 35.B
36.B 37.D * 38.B 39.A 40.D
* 41.C 42.D 43.D 44.A 45.A
46.C 47.D * 48.C * 49.B * 50.D
* 51.C * 52.B * 53.D 54.C 55.C
56.A 57.C 58.A 59.B 60.D
61.B 62.C 63.D 64.D * 65.D
66.B * 67.C * 68.A 69.C 70.A
* 71.C 72.C * 73.D 74.C * 75.B
76.A 77.A 78.A * 79.B 80.B
* 81.B 82.B 83.D 84.B 85.B
* 86.A * 87.B 88.C 89.D 90.B
二、論述題(兩個論述題可任選其一,並只選其一,多選無效,滿分30分)
論述題1評分參考:
本題可有多種不同的設計方案,下面給出其中一個較好的方案。
(1) 資料結構(15分,其中對三種操作的有效支援各4分,敘述的條理性3分。)
① 資料結構的Pascal語句描述
TYPE pptr=↑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;
VAR t:sptr;
② 資料結構的示意圖
③ 資料結構的`簡單文字說明
每個學生結點包含學生的學號和姓名,所有學生結點組織成一棵二叉排序樹,用link-rlink法儲存。
每份試卷成績作為一個連結串列結點,包含課程名和成績,每個學生的所有試卷成績結點連結成一個單鏈表,並且二叉排序樹的學生結點中有一個指標指向該單鏈表的第一個結點。
(2) 演算法要點(10分,三種操作各3分,敘述的條理性1分)
① 試卷成績插入,根據試卷的學號在二叉排序樹中查詢該學生結點。若找到,則在該學生結點所指的成績連結串列中插入一個成績結點;若未找到,則先在二叉排序樹中插入一個新的學生結點,然後再往這個學生結點所指的(空的)成績連結串列中插入一個成績結點。
② 學生成績查詢,根據所給學號在二叉排序樹中查詢該學生結點,再在該結點所指的成績連結串列中沿著指標讀出所有成績。
③ 成績單輸出。對二叉排序樹進行對稱序周遊,在訪問到每個學生結點時輸出該結點指向的成績連結串列中的所有成績。
(3) 設計理由(5分)
① 學生結點組織成二叉排序樹,使三種操作都有較高的效率:插入n個學生結點O(nlog2n),查詢一個學生結點O(log2n),輸出所有學生結點O(n)。
② 每個學生的所有成績結點組織成連結串列,動態 申請 空間,適合於每個學生選修的課程數不等的實際情況,節省空間。
論述題2評分參考:
本題考查考生是否具有較強的邏輯思維和邏輯推理能力,並且考查考生是否掌握了邏輯推理的主要步驟和推理規則。
(1) 的要點:考查考生命題符號化能力。(1)中含5個簡單命題:
p:甲是竊賊,
q:乙是竊賊,
r:做案時間發生在夜間12點鐘以前,
s:乙的證詞正確,
t:夜間12點鐘被盜房間燈光未滅。
(1)中含5個複合命題:
p∨q, p→┐r, s→t, ┐s→r, ┐t,每個複合命題2分,(1)的分值為10。
(2) 的要點:考查考生邏輯思維能力。結論為乙是竊賊,符號化形式為q。(2)的分值為5。
(3) 的要點:考查考生邏輯推理步驟和規則的掌握情況,整個推理由下面9步組成
① s→t 前提引入
② ┐t 前提引入
③ ┐s ①②拒取式規則
④ ┐s→r 前提引入
⑤ r ③④假言推理
⑥ p→┐r 前提引入
⑦ ┐p ⑤⑥拒取式規則
⑧ p∨q 前提引入
⑨ q ⑦⑧析取三段論
每步1到2分,(3)的分值為15。