【正文】 其中表示實體聯(lián)系的是_________框。在關(guān)系元組的分量中允許出現(xiàn)空值(Null Value)以表示信息空缺。 在關(guān)系模型中的一個重要概念是鍵(Key)或碼。 滿足下面7個性質(zhì)的二維表稱為關(guān)系(Relation)： 1) 元組個數(shù)有限性：二維表中元組個數(shù)是有限的。每個屬性有一個取值范圍，稱為值域(Domain)。下圖表示student與course間有多對多聯(lián)系： 兩個實體集間聯(lián)系叫二元聯(lián)系，多個實體集間聯(lián)系叫多元聯(lián)系。在ER圖中我們分別用下面不同的幾何圖形表示ER模型中的三個概念與兩個聯(lián)接關(guān)系。在概念世界中聯(lián)系反映了實體集間的一定關(guān)系。實體：現(xiàn)實世界中的事物可以抽象成為實體。數(shù)據(jù)操縱語言(DML)：負責數(shù)據(jù)的操縱，包括查詢及增、刪、改等操作。答案：程序4. 對軟件設(shè)計的最小單位(模塊或程序單元)進行的測試通常為_______測試。習題：（一）選擇題(單選)1. 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。所以，黑盒測試是在軟件接口處進行，完成功能驗證。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認每種內(nèi)部操作符合設(shè)計規(guī)格要求。軟件測試的目的：是發(fā)現(xiàn)錯誤。原則上講，模塊化設(shè)計總是希望模塊間的耦合表現(xiàn)為非直接耦合方式。衡量軟件的模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量標準。判定樹判定表結(jié)構(gòu)化設(shè)計方法常見的過程設(shè)計工具：圖形工具：程序流程圖，NS圖，PAD圖(問題分析圖)，HIPO表格工具：判定表。軟件由兩部分組成：一是機器可執(zhí)行的程序和數(shù)據(jù)；二是機器不可執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關(guān)的文檔。習題：（一）選擇題(單選)1. 下列敘述中正確的是( D )A）棧是“先進先出”的線性表B）隊列是“先進后出”的線性表C）循環(huán)隊列是非線性結(jié)構(gòu)D）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈式存儲結(jié)構(gòu)2. 下列關(guān)于棧的敘述中正確的是( A )A) 棧頂元素最先被刪除 B) 棧頂元素最后才能被刪除C) 棧底元素永遠不能被刪除 D) 以上三種說法都不對3. 下列敘述中正確的是( B )A) 有一個以上根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)B) 只有一個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)C) 循環(huán)鏈表是非線性結(jié)構(gòu)D) 雙向鏈表是非線性結(jié)構(gòu)4. 支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是( A )A) 棧 B) 樹 C) 隊列 D) 二叉樹5. 某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是( C )A）10 B）8 C）6 D）4提示：在任意二叉樹中，若度為0的結(jié)點(即葉子結(jié)點)的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則：n0= n2+1 即 n0(葉子結(jié)點數(shù))=5+1=66. 某二叉樹共有7個結(jié)點，其中葉子結(jié)點只有1個，則該二叉樹的深度為(假設(shè)根結(jié)點在第一層)( D )A) 3 B) 4 C) 6 D)77. 下列排序方法中，最壞情況下比較次數(shù)最少的是( D )A）冒泡排序 B）簡單選擇排序 C）直接插入排序 D）堆排序8. 下列敘述中正確的是( A )A) 對長度為n的有序鏈表進行查找，最壞的情況下需要的比較次數(shù)為nB) 對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為（n/2）C) 對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為(log2n)D) 對長度為n的有序鏈表進行對分查找，最壞的情況下需要的比較次數(shù)為(nlog2n)(二) 填空題1. 假設(shè)用一個長度為50的數(shù)組（數(shù)組元素的下標從0到49）作為棧的存儲空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49,top=30(數(shù)組下標)，則棧中具有________個元素。算法的時間復雜度為O(n2)。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，后面子表中的所有元素均不小于T。在本節(jié)所介紹的排序方法中，其排序的對象一般認為是順序存儲的線性表，在程序設(shè)計語言中就是一維數(shù)組。通常是指有序表中的元素按值升序排列(非遞減有序排列)。對于無序表(即表中的元素的排列是無序的)和鏈式存儲結(jié)構(gòu)的線性表(有序的和無序的)，只能用順序查找。查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。在遍歷左、右子樹時，仍然先遍歷其左子樹，然后訪問子樹的根結(jié)點，最后遍歷其右子樹。③ 遍歷右子樹(假設(shè)用R表示)。2) 如果2in，則結(jié)點i無左子結(jié)點，顯然也沒有右子結(jié)點，是葉子結(jié)點。在完全二叉樹中，若某個結(jié)點沒有左子結(jié)點，則它一定沒有右子結(jié)點，即該結(jié)點必是葉子結(jié)點。② 二叉樹中的每個結(jié)點，最多有兩棵子樹，分另稱為該結(jié)點的左子樹與右子樹。在樹形結(jié)構(gòu)中一般按如下原則分層：1) 根結(jié)點在第1層。結(jié)點的度：在樹形結(jié)構(gòu)中，一個結(jié)點所擁有的后繼個數(shù)稱為該結(jié)點的度。參見下面的圖形：樹形結(jié)構(gòu)的基本特征及基本術(shù)語：以下圖為例：樹的根：在樹形結(jié)構(gòu)中，沒有前驅(qū)的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱為樹的根。隊列是指只允許在表的一端插入元素、在另一端刪除元素的線性表。棧和隊列本質(zhì)上也是線性表，只是它們的操作受到了限制。ai(i=1,2, …,n)：為表的元素，也稱為線性表中的一個結(jié)點。注：某個元素直接相鄰的前一個元素稱為此元素的前驅(qū)、直接相鄰的后一個元素稱為此元素的后繼。也就是將所有存儲結(jié)點相繼存入在一個連續(xù)相鄰的存儲區(qū)里?！?算法的空間復雜度：算法的空間復雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式?！魯?shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素相互之間的關(guān)系，稱為結(jié)構(gòu)。數(shù)據(jù)的鏈式存儲方式：是在存儲每個結(jié)點信息的同時，增加一個指針來表示結(jié)點間的邏輯關(guān)系。非線性結(jié)構(gòu)的邏輯特征：在一個非空的數(shù)據(jù)結(jié)構(gòu)中，某數(shù)據(jù)元素可能有多于一個前驅(qū)或后繼。它可以是一個數(shù)、一個字符、一個字符串，也可以是一條記錄，還可以是復雜的數(shù)據(jù)對象。棧是限定僅在表尾進行插入和刪除操作的線性表。允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。如：上圖中的“R”。如：上圖中根結(jié)點R的度是4；結(jié)點T的度是3；結(jié)點P、Q、D、O、Y、W的度都為1。2) 其余結(jié)點的層數(shù)等于其父結(jié)點的層數(shù)加1。當一個結(jié)點即沒有左子樹也沒有右子樹時，該結(jié)點就是葉子結(jié)點。(3) 二叉樹的性質(zhì)假設(shè)定義根結(jié)點的層數(shù)為1(注意：有些資料中規(guī)定根結(jié)點的層數(shù)為0)。如果2i≤n，則結(jié)點i的左子結(jié)點是編號為2i的結(jié)點。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。即，中序遍歷是指訪問所有的根結(jié)點(包括子樹的根結(jié)點)都在遍歷其左子樹之后、在遍歷其右子樹之前。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。順序查找的優(yōu)點：算法簡單而適用范圍廣。二分查找不能用于鏈式存儲結(jié)構(gòu)的線性表。 這里的排序算法，都是針對升序排序。 如果對分割后的各子表再按上述原則進行分割，并且這種分割過程可以一直做下去，隨著對各子表不斷地進行分割，劃分出的子表會越來越多(一次只能對一個子表進行再分割處理)，直到所有子表中的元素都排好序為止，則此時的線性表就變成了有序表。(2) 希爾排序 希爾排序的基本思想：請查看相關(guān)資料。 答案：202. 一個隊列的初始狀態(tài)為空。軟件的分類 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件(或工具軟件)。語言工具：PDL(偽碼)軟件設(shè)計的基本原理 1) 抽象：是一種思維