�牐牰�、論述題（兩個論述題可任選其一，并只選其一，多選無效，滿分30分。）
�牐犝撌鲱}１
�牐牨绢}要求設計一個學生試卷成績輸入、查詢和成績單輸出系統(簡稱SRS)的數據結構和算法要點。問題描述如下：
�牐犚�輸入到SRS 系統中的每一份試卷成績反映一個學生選修一門課程的考試結果，它包括以下數據項：學號、姓名、課程名、成績。由于實行了靈活的選課制度，所以每個學生選修多少門課程，選修哪些課程都可以不同。要輸入的多份試卷成績并未按任何數據項排列順序，它們以任意的順序被輸入到系統中來。
�牐燬RS系統要具有以下功能：①試卷成績插入，將試卷成績逐個插入到SRS系統的數據結構中。②學生成績查詢，給出學號查找該學生所選修的各門課程的考試成績。③成績單輸出，按學號遞增的順序依次輸出所有學生的學號、姓名，及其所選修的各門課程的課程名和成績。（為簡單起見，假設上述所有工作都在計算機內存中進行。）
�牐犝堅O計SRS系統的數據結構和算法要點，使上述三項操作都有較高的執行效率。從以下方面闡述你的設計：
�牐�(1) SRS系統的數據結構（15分）
�牐牏贁祿�結構的Pascal語句描述
�牐牏跀祿�結構的示意圖
�牐牏蹟祿�結構的簡單文字說明
�牐�(2) SRS系統的算法要點（10分）
�牐牐ㄖ灰�簡單的文字說明，不必寫出Pascal程序）
�牐牏僭嚲沓煽儾迦�
�牐牏趯W生成績查詢
�牐牏鄢煽儐屋敵�
�牐�(3) 簡單陳述你的上述設計的理由（5分）
�牐犝撌鲱}２
�牐犜谝粋�盜竊案件中，已知下列事實：
�牐牏偌谆蛞沂歉`賊。
�牐牏谌艏资歉`賊，做案時間不會發生在夜間12點鐘以前。
�牐牏廴粢业淖C詞正確，在夜間12點鐘時被盜物品所在房間燈光未滅。
�牐牏苋粢业淖C詞不正確，則做案時間發生在夜間12點鐘以前。
�牐牏菀归g12點鐘被盜房間燈光滅了。
�牐牳鶕�以上事實解答或論證以下各題：
�牐�(1) 將①～⑤中所出現的簡單命題符號化，然后用命題符號寫出①～⑤各復合命題的符號化形式。(10分)
�牐�(2) 以(1)中給出的5個復合命題為前提，判斷甲、乙二人誰是竊賊(以符號形式給出)。(5分)
�牐�(3) 用命題邏輯推理理論寫出(2)中結論的判斷過程(要求寫出每一步所用的推理規則)。(15分)

�牐�1997年全國 計算機等級 考試四級筆試試卷
�牐牬鸢讣霸u分標準
�牐犚弧⑦x擇題:(共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語句描述
�牐燭YPE 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;
�牐燰AR 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。