廈門大學(xué)信科數(shù)據(jù)庫(kù)及數(shù)據(jù)結(jié)構(gòu)試題

廈門大學(xué)信科數(shù)據(jù)庫(kù)及數(shù)據(jù)結(jié)構(gòu)試題廈門大學(xué)信科數(shù)據(jù)庫(kù)及數(shù)據(jù)結(jié)構(gòu)試題廈門大學(xué)信科數(shù)據(jù)庫(kù)及數(shù)據(jù)結(jié)構(gòu)試題資料僅供參考文件編號(hào)：2022年4月廈門大學(xué)信科數(shù)據(jù)庫(kù)及數(shù)據(jù)結(jié)構(gòu)試題版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：一、選擇題(單選)1.關(guān)于數(shù)據(jù)元素，下列描述不正確的是（D）。A.數(shù)據(jù)元素可以包含多個(gè)數(shù)據(jù)項(xiàng)。B.數(shù)據(jù)結(jié)構(gòu)的算法大多以數(shù)據(jù)元素為基本操作單位。C.數(shù)據(jù)元素一般代表某種現(xiàn)實(shí)世界中的對(duì)象。D.數(shù)據(jù)元素必須有一個(gè)關(guān)鍵字。2.循環(huán)鏈表head的尾結(jié)點(diǎn)指針p的特點(diǎn)是（A）。A.p->next=headB.p->next=head->nextC.p=headD.p=head->next3.設(shè)一個(gè)棧的輸入序列是a,b,c,d,e，則下列序列是棧的合法輸出序列的是（D）。A.eabcdB.deacbC.dcabeD.cbaed4.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的隊(duì)尾指針操作為（D）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)5.在單鏈表中指針p所指的結(jié)點(diǎn)后插入新結(jié)點(diǎn)s有下列3個(gè)步驟：=1\*GB3①s->data=x（賦值）=2\*GB3②p->next=s=3\*GB3③s->next=p->next正確的步驟順序?yàn)椋˙）。A.=1\*GB3①=2\*GB3②=3\*GB3③B.=3\*GB3③=2\*GB3②=1\*GB3①C.=2\*GB3②=1\*GB3①=3\*GB3③D.無正確答案6.對(duì)于先序遍歷和后序遍歷結(jié)果相同的二叉樹為（B）。A.一般二叉樹B.只有根結(jié)點(diǎn)的二叉樹C.根結(jié)點(diǎn)無左孩子的二叉樹D.根結(jié)點(diǎn)無右孩子的二叉樹7.若圖的鄰接矩陣是對(duì)稱陣，則此圖必然為（B）。A.有向圖B.無向圖C.連通圖D.有向圖或無向圖8.關(guān)于哈夫曼樹，下列描述正確的是（D）。A.一定是二叉排序樹B.是一棵完全二叉樹C.是一棵平衡二叉樹D.以上三種說法都不對(duì)9.長(zhǎng)度為12的按關(guān)鍵字有序的待查找序列，采用順序存儲(chǔ)，若用二分查找，則在等概率情況下，查找成功的ASL是（A）。A.37/12B.62/13C.39/12D.49/1210.在數(shù)據(jù)管理技術(shù)的發(fā)展過程中，經(jīng)理了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。其中數(shù)據(jù)獨(dú)立性最高的階段是（A）。A.數(shù)據(jù)庫(kù)系統(tǒng)B.文件系統(tǒng)C.人工管理D.數(shù)據(jù)項(xiàng)管理11.下列有關(guān)數(shù)據(jù)庫(kù)的描述中，正確的是（C）。A.數(shù)據(jù)庫(kù)是一個(gè)DBF文件B.數(shù)據(jù)庫(kù)是一個(gè)關(guān)系C.數(shù)據(jù)庫(kù)是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集合D.數(shù)據(jù)庫(kù)是一組文件12.數(shù)據(jù)庫(kù)設(shè)計(jì)中，將E-R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型的過程屬于（C）。A.需求分析階段B.邏輯設(shè)計(jì)階段C.概念設(shè)計(jì)階段D.物理設(shè)計(jì)階段13.將E-R圖轉(zhuǎn)換到關(guān)系模式時(shí)，實(shí)體與聯(lián)系都可以表示成（B）。A.屬性B.關(guān)系C.鍵D.域二、填空題1.衡量算法的兩個(gè)主要指標(biāo)是時(shí)間復(fù)雜度和空間復(fù)雜度。2.線性表的順序存儲(chǔ)結(jié)構(gòu)通過數(shù)組下標(biāo)來反映數(shù)據(jù)元素之間的邏輯關(guān)系。3.鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表。進(jìn)行插入、刪除操作時(shí)，使用鏈表比使用順序存儲(chǔ)結(jié)構(gòu)的效率高。4.棧又稱為后進(jìn)先出（線性）表，隊(duì)列又稱為先進(jìn)先出（線性）表。5.二叉樹的第h層上最多含有的結(jié)點(diǎn)數(shù)為2h-1。6.高度為8的完全二叉樹至少有64個(gè)葉子結(jié)點(diǎn)。7.有向圖的鄰接矩陣不是對(duì)稱陣。8.圖的廣度優(yōu)先搜索算法中使用了隊(duì)（輔助數(shù)據(jù)結(jié)構(gòu)），以記錄正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。9.二叉排序樹的查找效率與二叉樹的高度有關(guān)，在待查序列全順序或全逆序情況下查找效率最低。10.衡量查找算法優(yōu)劣的指標(biāo)是平均查找長(zhǎng)度（ASL）。11.CQ[0]～CQ[8]為一循環(huán)隊(duì)列，初態(tài)front=rear=5，進(jìn)行下列操作：a,b,c,d入隊(duì)；a,b出隊(duì)，e,f,g,h,i,j,k,l,m入隊(duì)，這時(shí)隊(duì)的頭、尾指示器狀態(tài)為：front＝7，rear＝6。12.在以head為表頭指針的帶表頭結(jié)點(diǎn)的單鏈表和循環(huán)鏈表中，判斷鏈表為空的條件分別為head→next==NULL和__head==head→next13.對(duì)于一組關(guān)鍵字{41，62，34，67，89，54，76，22，93，8}進(jìn)行從小到大排序，寫出其快速排序第一趟（一個(gè)關(guān)鍵字到位為一趟）排序后的序列：8,22,34,41,89,54,76,67,93,62。14.二叉排序樹的查找——遞歸算法:boolFind(BTreeNode*BST,intitem){if(BST==NULL)returnfalse;可以使用SQL命令來操縱數(shù)據(jù)庫(kù)，也可將SQL命令嵌入高級(jí)語(yǔ)言（如C,Pascal,Java等）程序中使用。三、判斷題1.層次模型可以直接表示n:m聯(lián)系。（*）2.同一個(gè)關(guān)系的不同元組值可以相同。（*）3.SQL屬于關(guān)系數(shù)據(jù)庫(kù)語(yǔ)言。（√）四、綜合題1.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)什么是數(shù)據(jù)的物理結(jié)構(gòu)（略）2、編寫一個(gè)函數(shù)，把一個(gè)以整數(shù)作為結(jié)點(diǎn)的單鏈表轉(zhuǎn)換成數(shù)組。其中數(shù)組長(zhǎng)度要根據(jù)單鏈表長(zhǎng)度動(dòng)態(tài)建立，并編寫主函數(shù)驗(yàn)證函數(shù)正確性。（略）3.棧和隊(duì)列的邏輯結(jié)構(gòu)有何不同鏈棧和鏈隊(duì)列與普通單鏈表有何不同（略）4.循環(huán)隊(duì)列是如何實(shí)現(xiàn)的其隊(duì)空和隊(duì)滿的條件各是什么通過在邏輯上將順序隊(duì)看做首尾相接的結(jié)構(gòu)，來實(shí)現(xiàn)循環(huán)隊(duì)列?！?.二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和單鏈表有何異同點(diǎn)？相同點(diǎn)：都是鏈?zhǔn)酱鎯?chǔ)，都有數(shù)據(jù)域；不同點(diǎn)：前者有兩個(gè)指針域，后者只有一個(gè)指針域。6.什么是滿二叉樹，什么是完全二叉樹？（略）7.什么是平均查找長(zhǎng)度比較順序查找和折半查找的優(yōu)缺點(diǎn)（略）8.編寫一段程序，首先以學(xué)生信息為數(shù)據(jù)元素建立順序表，其中學(xué)生信息包括學(xué)號(hào)、姓名、籍貫、專業(yè)、班級(jí)，順序表按學(xué)號(hào)有序。程序可接收用戶查詢請(qǐng)求，其中按學(xué)號(hào)查詢用折半查找實(shí)現(xiàn)，按姓名、籍貫、班級(jí)查詢用順序查找實(shí)現(xiàn)。按姓名、籍貫、班級(jí)查詢時(shí)可能有多條滿足條件的記錄，這些記錄都應(yīng)顯示出來。（略）9.什么是排序處理同樣的元素集合時(shí)，排序和查找的算法復(fù)雜度有無差異，這種差異是如何形成的……處理同樣的元素集合時(shí)，排序和查找的算法復(fù)雜度有差異，這是由于，查找算法的主要操作時(shí)比較兩元素的關(guān)鍵字，其算法復(fù)雜度主要考察比較操作消耗的時(shí)間；而排序算法除比較操作外，移動(dòng)元素也是其主要操作，因此其算法復(fù)雜度主要考察比較和移動(dòng)兩種操作消耗的時(shí)間。10.閱讀以下算法并回答問題。LinkListmynote(LinkListL){請(qǐng)畫出下圖的鄰接矩陣和鄰接表。解：鄰接矩陣：鄰接表：12.已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECDFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。解：EDCBIHJGFA13.一個(gè)線性表為B=（12，23，45，57，20，3，78，31，15，36），設(shè)哈希表空間為H[0]～H[12]，哈希函數(shù)為H（key）=keymod13并用線性探測(cè)法解決沖突，請(qǐng)畫出哈希表，并計(jì)算等概率情況下的平均查找長(zhǎng)度。解：哈希表為：0123456789101112

78

153

57452031

2336121111114121上面最后一行為比較次數(shù)。平均查找長(zhǎng)度：ASL=（1+1+1+1+1+1+1+1+4+2）/10=14/10=14.假定允許每個(gè)倉(cāng)庫(kù)存放多個(gè)零件，每種零件也可在多個(gè)倉(cāng)庫(kù)中存放，而每個(gè)倉(cāng)庫(kù)中保存的零件都有庫(kù)存數(shù)量。倉(cāng)庫(kù)的屬性有：倉(cāng)庫(kù)號(hào)、面積、電話號(hào)碼；零件的屬性有：零件號(hào)、名稱、規(guī)格、單價(jià)。根據(jù)上述說明畫出E-R圖。解：（注：上圖中各實(shí)體、聯(lián)系均有各自的屬性，自行補(bǔ)充。）15.假定一臺(tái)機(jī)器可以由若干個(gè)工人操作，加工若干種零件，某個(gè)工人加工某種零件是在一臺(tái)機(jī)器上完成的這道工序，而一個(gè)零件需要多道工序才能完成。用E-R圖表示機(jī)器、零件和工人這三個(gè)實(shí)體之間的多對(duì)多聯(lián)系。解：16.假定有一個(gè)客戶訂貨系統(tǒng)，允許一個(gè)客戶一次（一張訂單）預(yù)訂多種商品，那么關(guān)系模式：訂單（訂單號(hào)、日期、客戶編號(hào)、客戶名、商品編碼、數(shù)量）屬于第幾范式為什么解：屬于第二范式。因?yàn)橹鲗傩詾橛唵翁?hào)，在此關(guān)系模式中，不存在部分函數(shù)依賴關(guān)系，但存在傳遞函數(shù)依賴關(guān)系。如：訂單號(hào)傳遞函數(shù)決定客戶名。17.下列關(guān)系模式分別屬于第幾范式為什么關(guān)系：R(X,Y,Z)，函數(shù)依賴：XYZ關(guān)系：R(X,Y,Z)，函數(shù)依賴：YZ;XZY關(guān)系：R(X,Y,Z)，函數(shù)依賴：YZ;YX;XYZ關(guān)系：R(X,Y,Z)，函數(shù)依賴：XY;XZ關(guān)系：R(W,X,Y,Z)，函數(shù)依賴：XZ;WXY解：（1）第三范式（2）第三范式（3）第二范