廈門大學信科數據庫及數據結構試題

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

78

153

57452031

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