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