中國人民大學1999年數據庫與數據結構試題
來源：
時間：2007-06-06 14:46:09
招生專業：計算機應用
考試科目：數據庫與數據結構
《數據庫》部分
一、簡答題（每小題3分，共15分）
1．數據模型是由哪幾部分組成？簡要說明這些部分所定義的是什么？
2．在嵌入式SQL中游標的作用是什么？
3．如果對數據庫中運行的事務不進行并發控制，數據庫會產生哪些不一致？
4．試述滿足BCNF的關系與滿足4NF的關系的區別。
5．試述數據庫物理設計的內容與步驟。
二、回答題（每小題6分，共12分）
1．在關系數據庫系統中為佬要進行查詢優化？請說明查詢優化的一般策略和一般步驟。
2．試述數據庫系統中的完整性概念。在關系數據庫系統中是如何定義完整性約束條件的？你認為DBMS中應該怎樣實現完整性定義與完整性檢查？
三、現有下面四個關系模式：（共23分）
EMP（EMPNO,ENAME,HIREDATE,MONTH SAL,DEPTNO）；
DEPT（DEPTNO,DNAME,MGR）；
BONUS（WORKPERIOD,MONTH BONUS）；
HONOR（HNAME,EMPNO,WIN YEAR）；
其中：
雇員表EMP由主碼雇員號（EMPNO），以及雇員姓名（ENAME），參加工作的年份（HIREDATE），月工資（MONTH SAL），所在部門（DEPTNO）組成；
部門表DEPT由主碼部門號（DEPTNO），以及部門名稱（DNAME）和部門經理的雇員號（MGR）組成，一個部門可以有一至兩個經理；
獎金表BONUS由主碼工齡（WORKPERIOD）和相應的月獎金額（MONTH BONUS）組成，雇員每月的資金數額取決于他的工齡，工齡只精確到年；
榮譽表HONOR由榮譽名（HNAME），獲該榮譽稱號的職工代碼（EMPNO）和相應年份（WIH YEAR）組成。
（一）請用SQL語句完成下列操作：
1．查詢每個職工1998年12月的總收入（4分）
2． 查詢每個部門經理的名字（4分）
3． 查詢新參加工作人數最多的年份及其人數（4分）
4． 查詢至少榮獲了編號為E901的職工曾榮獲過的所有榮譽稱號的職工姓名（4分）
5．把查詢EMP表（月工資屬性除外）的權力授予所有用戶（2分）
（二）試用關系代數求沒有獲得任何榮譽稱號的職工姓名（3名）
（三）試用關系演算求沒有獲得任何榮譽稱號的職工姓名（2分）
《數據結構》部分
一、簡答（20分）
1．什么是二叉樹的樹高（或深度）？簡述一種計算樹高的算法思想。
2．試分析說明堆排序和快排序的平均時間復雜度。
3．如果只想得到一系列中第M個最小元素之前的部分排序，用什么方法最好？再舉出另外一種方法，比較它們的時間復雜度。
4．取哈希函數為H（K）=K MOD 13。給定關鍵字序列為{19,14,23,01,68,20,84,27,55,11,10,79}試分別用拉鏈法和線性探測法解決碰撞
構造哈希表,畫出示意圖(不要求計算過程)。
二、用類PASCAL或SPARKS語言寫算法（30分）
1．已知P0，Q0，R0為三條按升序鏈接的單鏈表（P0，Q0，R0為相應的鏈頭指針），試寫一算法從鏈表P0中刪去那些既出現在Q0中又出現在
R0中的結點。
2．按如下示意圖，通過改鏈的方法將鏈表P0改成Q0（只考慮結點數為5的倍數的情形）。
3．設有一棵由M叉樹轉化而得的二叉樹，并建立了中序線索。寫出從這棵二叉樹中刪去原M叉樹的安自左向右順序的第J棵子樹的算法（自選
并說明存儲結構；只考慮1＜J＜M的情形）。
結束
特別聲明：①凡本網注明稿件來源為"原創"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；
②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。
閱讀全文
招生服務平臺始創于1999年
打開微信掃一掃，關注育路教育官方微信
