金狀元試卷網(wǎng)-江西財經(jīng)大學(xué)考研真題數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫原理2004.doc

江 西 財 經(jīng) 大 學(xué)2004年攻讀碩士學(xué)位研究生入學(xué)考試試題（A卷）專 業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)考試科目：數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫原理重要提示：考生必須將所有答案寫在答題紙上，本試題上的任何標(biāo)記均不作判題依據(jù)第一部分：數(shù)據(jù)庫系統(tǒng)原理一、概念題（每小題3分，共15分）1、數(shù)據(jù)模型 2、外碼3、日志文件及其作用 4、數(shù)據(jù)庫設(shè)計(jì)5、數(shù)據(jù)庫系統(tǒng)用 描述現(xiàn)實(shí)世界的實(shí)體及實(shí)體間的聯(lián)系。關(guān)系模型是用 表示實(shí)體，用 表示實(shí)體間的聯(lián)系。層將和網(wǎng)狀模型是用 表示實(shí)體，用 表示實(shí)體間的聯(lián)系，而用 實(shí)現(xiàn)實(shí)體間的聯(lián)系。其中，第5題供選擇的答案有：數(shù)據(jù)模型 概念模型 外模型 內(nèi)模型 結(jié)點(diǎn) 表數(shù)據(jù)結(jié)構(gòu) 指針 連線 模式 外模式 內(nèi)模式數(shù)據(jù)描述語言 數(shù)據(jù)操縱語言 高級程序設(shè)計(jì)語言二、簡答題（每小題5分，共15分）1、簡述數(shù)據(jù)庫系統(tǒng)的三級模式結(jié)構(gòu)。2、對數(shù)據(jù)庫系統(tǒng)中的故障進(jìn)行分類，并簡述系統(tǒng)故障的恢復(fù)過程。3、簡述關(guān)系數(shù)據(jù)庫實(shí)施完整性約束的內(nèi)容有哪些?三、（共14分）有一個成績管理的數(shù)據(jù)庫，它包含如下三張表： (1) 學(xué)生表：STUDENT 學(xué)號 姓名 性別 專業(yè)(2) 課程表：COURSE 課程號 課程名 學(xué)時 學(xué)分 (3) 成績表：SCORE 學(xué)號 課程號 成績 學(xué)期根據(jù)上面三張表，完成以下各題： 1、試用關(guān)系代數(shù)表示查詢2002-2003學(xué)年第一學(xué)期（“02-03/1”）選修了“數(shù)據(jù)結(jié)構(gòu)”課程的學(xué)生姓名。（4分）2、用SQL語句表示查詢重修過“計(jì)算機(jī)原理”課程（即該課程在成績表中有2條或2條以上記錄）的學(xué)生姓名及重修次數(shù)。（4分）3、寫出下列SQL語句的查詢語義（即功能）： SELECT 姓名, 課程名, 成績 FROM STUDENT S, COURSE C, SCORE SC WHERE (S.學(xué)號=SC.學(xué)號) AND (C.課程號=SC.課程號) AND SC.成績=( SELECT MAX(SCORE.成績) FROM SCORE WHERE SCORE.課程號=SC.課程號)請給出三個實(shí)例關(guān)系表（其中學(xué)生表至少3個學(xué)生、課程表至少2門課程），并根據(jù)給出的實(shí)例關(guān)系表寫出該SQL查詢的執(zhí)行結(jié)果。（6分）四、（共13分）設(shè)有如下商品庫存關(guān)系R：商品編號商品名稱采購批次單價庫存數(shù)量倉庫號倉庫地點(diǎn)A1A1A2A3A4ABC彩電ABC彩電XYZ冰箱PPP西裝FK自行車12212226022001050 98045054685S1S1S1S2S3中山路5號中山路5號中山路5號勝利路8號勝利路8號請僅在R中已給出數(shù)據(jù)的范圍內(nèi)分析其函數(shù)依賴關(guān)系并解答如下問題：1、R最高為第幾范式？為什么？（3分）2、將它分解為滿足3NF范式的關(guān)系模式。（5分）3、分解后比分解前有什么好處？為什么？（5分）五、敘述在一個DBMS中，事務(wù)管理部件（恢復(fù)子系統(tǒng)、并發(fā)控制子系統(tǒng)）的主要職能及其分別常用的基本技術(shù)和手段。（8分）六、（共10分）假設(shè)數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)A、B和C的初值均為100?，F(xiàn)有兩個事務(wù)T1和T2，分別包含如下操作：事務(wù)T1：y=Read(C); x=Read(A); x=x+y; Write(A, x); （即，讀數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)C的值并賦給變量y； 讀數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)A的值并賦給變量x；變量x的值與變量y的值相加的結(jié)果賦給變量x；將變量x的值寫到數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)A中；） 事務(wù)T2：v=Read(C); u=Read(B); u=u+v; Write(A, u);下面是利用鎖機(jī)制來實(shí)現(xiàn)事務(wù)T1、T2的一個并發(fā)調(diào)度S： T1 T2 Slock C Slock C v=Read(C) Unlock C Slock B y=Read(C) Unlock C Slock A u=Read(B) Unlock B u=u+v Xlock A x=Read(A) 等待 Unlock A 等待 Write(A, u) （獲得排它鎖，并實(shí)現(xiàn)寫） x=x+y Xlock A 等待 Unlock A（獲得排它鎖，并實(shí)現(xiàn)寫） Write(A, x) Unlock A完成以下解答：1、調(diào)度S是否是可串行化調(diào)度？為什么？（4分）2、利用鎖機(jī)制給出關(guān)于事務(wù)T1、T2的一個可串行化并發(fā)調(diào)度S(不能是串行調(diào)度)，使它與串行調(diào)度T1T2的執(zhí)行結(jié)果等價。并說明等價的理由。（6分）第二部分：數(shù)據(jù)結(jié)構(gòu)一、概念題（每小題3分，共9分）1、棧2、二叉排序樹3、存儲結(jié)構(gòu)二、簡答題(每小題10分，共20分)1、用類C描述語言定義稀疏矩陣的三元組存儲結(jié)構(gòu)，并寫出下列矩陣的存儲表示。2、若有一個待排序的無序序列為：49,38,65,97,76,13,27,49，現(xiàn)用堆排序方法對其排序，請圖示初始堆的建立過程。三、算法填空題（每空3分，共30分）1、在以下算法中填上適當(dāng)?shù)念怌程序設(shè)計(jì)語言語句，使之實(shí)現(xiàn)求矩陣M的轉(zhuǎn)置矩陣T的功能。其中：矩陣用三元組表示，mu為矩陣行數(shù)、nu為矩陣列數(shù)，tu為矩陣非零個數(shù)，三元組(i, j, e)表示矩陣第i行第j列的值為e。Status TransposeSMatrix(TSMatrix M, TSMatrix &T) _(1)_;if (T.tu)for (col=1; col=M.nu; +col) numcol=0;for (t=1; tM.nu; +t) +num_(2)_;cpot1=1;for (col=2; colj。注釋：有向圖的存儲結(jié)構(gòu)為鄰接表，且在頭結(jié)點(diǎn)中增加二個數(shù)組：一個存放頂點(diǎn)入度的數(shù)組（indegree），一個存放本算法生成的頂點(diǎn)序號No。另設(shè)一棧S暫存所有入度為零的頂點(diǎn)。Status SortDAG( Algraph G) FindIndegree(G,indegree);/對各頂點(diǎn)求入度indegree0.vexnum-1InitStack(S);for (i=0; inextarc) k=p-adjv