1.(1997年)本題要求設計一個學生試卷成績輸入、查詢和成績單輸出系統(簡稱SRS)的資料結構和演算法要點。問題描述如下：
要輸入到SRS系統中的每一份試卷成績反映一個學生選修一門課程的考試結果，它包括以下資料項：學號、姓名、課程名、成績。由於實行了靈活的選課制度，所以每個學生選修多少門課程，選修哪些課程都可以不同。要輸入的多份試卷成績並未按任何資料項排列順序，它們以任意的順序被輸入到系統中來。
SRS系統要具有以下功能：①試卷成績插入，將試卷成績逐個插入到SRS系統的資料結構中。②學生成績查詢，給出學號查詢該學生所選修的各門課程的考試成績。③成績單輸出，按學號遞增的順序依次輸出所有學生的學號、姓名，及其所選修的各門課程的課程名和成績。(為簡單起見，假設上述所有工作都在計算機記憶體中進行。)
請設計SRS系統的資料結構和演算法要點，使上述三項操作都有較高的執行效率。從以下方面闡述你的設計：
(1)SRS系統的資料結構(15分)
①資料結構的Pascal語句描述
②資料結構的示意圖
③資料結構的簡單文字說明
(2)SRS系統的演算法要點(10分)
(只要簡單的`文字說明，不必寫出Pascal程式)
①試卷成績插入
②學生成績查詢
③成績單輸出
(3)簡單陳述你的上述設計的理由(5分)
答案:
本題可有多種不同的設計方案，下面給出其中一個較好的方案。
(1)資料結構(15分，其中對三種操作的有效支援各4分，敘述的條理性3分。)
①資料結構的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;
②資料結構的示意圖
9508027Liu٨٨
OS72
OS60
9408023Fang٨٨
9508091Chen ٨
9508010Li
DS85
DB66٨
SE89
AI92٨
DS90
OS95
t
③資料結構的簡單文字說明
每個學生結點包含學生的學號和姓名，所有學生結點組織成一棵二叉排序樹，用link-rlink法儲存。
每份試卷成績作為一個連結串列結點，包含課程名和成績，每個學生的所有試卷成績結點連結成一個單鏈表，並且二叉排序樹的學生結點中有一個指標指向該單鏈表的第一個結點。
(2)演算法要點(10分，三種操作各3分，敘述的條理性1分)
①試卷成績插入，根據試卷的學號在二叉排序樹中查詢該學生結點。若找到，則在該學生結點所指的成績連結串列中插入一個成績結點;若未找到，則先在二叉排序樹中插入一個新的學生結點，然後再往這個學生結點所指的(空的)成績連結串列中插入一個成績結點。
②學生成績查詢，根據所給學號在二叉排序樹中查詢該學生結點，再在該結點所指的成績連結串列中沿著指標讀出所有成績。
③成績單輸出。對二叉排序樹進行對稱序周遊，在訪問到每個學生結點時輸出該結點指向的成績連結串列中的所有成績。
(3)設計理由(5分)
①學生結點組織成二叉排序樹，使三種操作都有較高的效率:插入n個學生結點O(nlog2n),查詢一個學生結點O(log2n),輸出所有學生結點O(n)。
②每個學生的所有成績結點組織成連結串列，動態空間，適合於每個學生選修的課程數不等的實際情況，節省空間。
2.(1998年)
人們在實踐中發現，資料庫技術是資訊資源的整理、儲存、管理和使用的最有效的手段。資料庫按其資料結構模型分類，通常可分為層次型資料庫、型資料庫、關係型資料庫和麵向物件型資料庫，各種類似的資料模型都有自身的特點。試從關係資料模型的優點和弱點論述：
(1)為什麼人們在開發以事務處理為主的資訊系統(例如管理資訊系統)時，大多選用關係型資料庫作為開發環境?(18分)
(2)在許多含有複雜資料結構或豐富語義的實際應用領域中，為什麼要選用面向物件資料庫或要對關係型資料庫作某些擴充和修改?(12分)
答案:
(1)首先，關係資料模型結構簡單，為二維表格結構與目前事務處理系統中資料多以二維表格結構組織和表示相適應。(10分)
其次，關係資料模型的其他優點也適應事務處理的要求：
①表格是一集合，因此集合論等知識可以引入關係型資料模型中，使它具有堅實的數學理論基礎。(4分)
②有簡單、易懂`易學的關係資料庫的標準語言SQL的支援。(2分)
③資料具有較高的獨立性。(2分)
(2)在含有複雜資料結構或豐富語義的實際應用領域中，一般選用面向物件資料庫，或要對關係資料庫作某些擴充和修改是因為：
①關係資料模型不擅長於表示複雜物件資料型別。(4分)
②也不擅長於表示實體間的語義聯絡。(4分)
③而面向物件資料模型在這兩方面有優勢。(4分)
3.(2000年)設計一個用於管理會議室的資料庫。經調查分析，得到的資料項列出如下：
房間號r#CHAR(4)，部門號d#CHAR(3)，部門名稱dnameCHAR(20)，
房間容量contentINT，部門主管dmanagerCHAR(8)，開會日期mdateDATE，
會議名稱cnameCHAR(20)，會議主題(subject)CHAR(80)，會議型別(type)，
部門人數dnumINT，當前房間狀態stateCHAR(1)，
並確定以會議室(room)資訊，部門(department)資訊，會議(conference)資訊為實體，它們通過“開會(meeting)”聯絡起來。為了簡化問題做如下假定：
l 會議以部門召開，但一個部門在同一會議室不能重複召開同一個會議。
l 會議室按部門借用，且不預借。
l 當前房間狀態取值為‘1’表示該會議室當前正在開會，取值為‘0’表示該會議室當前未被借用。
資料庫概念設計的只包含主鍵屬性的簡化E-R圖如下：
cname
r#
會議conference
房間room
部門department
d#
開會meeting
m
n
p
要求：
⑴資料庫的邏輯結構設計：給出相應的表名、表的屬性名(資料型別可省)、主鍵。(14分)
⑵給出下列查詢的SQL語句：(16分，每小題4分)
a)當前未借用的會議室(房間號)和容量：
b)2000年4月8日有哪些部門(部門名稱)在開會?他們的主管是誰?
c)2000年4月8日‘資訊中心’在哪個會議室(房間號)開會?會議名稱和主題是什麼?
d)當前能夠適合‘資訊中心’開會的有哪些會議室(房間號)?
答案:
(1)資料庫的邏輯結構設計(給出相應的表名,表結構,主鍵;(14分)
room(r#,content,state)主鍵:r#(3分)
department(d#,dname,dmanager,dnum)主鍵:d#(3分)
conference(cname,subject,type)主鍵:cname(3分)
meeting(r#,d#,cname,mdate)主鍵(r#,d#,cname)(5分)
(2)給出下列查詢的SQL語句:(16分,每小題4分)
a)當前未借用的會議室(房間號)和容量:
selectr#,contentfromroomwherestate=’0’
b)2000年4月8日有哪些部門(部門名稱)在開會?他們的主管是誰?
Selectdname,dmanagerfromdepartmentd,meetingm
whered.d#=m.d#andmdate=’2000年4月8日’
或
Selectdname,dmanagerfromdepartmentd
whered.d#=in(selectm.d#=frommeetingmWheremdate=’2000年4月8日’)
c)2000年4月8日’資訊中心’在哪個會議室(房間號)開會?會議名稱和主題是什麼?
Selectr#,e,subjectfromdepartmentd,meetingm,conferencec
whered.d#=m.d#e=eand
Mdate=’2000年4月8日’anddname=’資訊中心’
或(注:本題中Selectr#,e,......也可以是Selectr#,e,......
Selectr#,e,subjectfrommeetingm,conferencec
WhereMdate=’2000年4月8日’e=eand
m.d#=(selectd.d#fromdepartmentdwheredname=’資訊中心’)
d)當前能夠適合’資訊中心’開會的有哪些會議室(房間號)?
Selectr#fromroomwherestate=’O’and
content>=(selectdnumfromdepartmentwheredname=’資訊中心’)
