【正文】 維來分析源程序代碼和排錯，是主要的設(shè)計手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。 第四章數(shù)據(jù)庫 基礎(chǔ) 4． 1 數(shù)據(jù)庫系統(tǒng)的基本概念 數(shù)據(jù)：實際上就是描述事物的符號 記錄。而數(shù)據(jù)的值給出了符合定型的值，如整型值 15。 數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點。 數(shù)據(jù)庫管理系統(tǒng)功能： （ 1）數(shù)據(jù)模式定義：即為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架； （ 2）數(shù)據(jù)存取的物理構(gòu)建 ：為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段； （ 3）數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫的數(shù)據(jù)提供方便，如查詢、插入、修改、刪除等以及簡單的算術(shù)運(yùn)算及統(tǒng)計； （ 4）數(shù)據(jù)的完整性、安生性定義與檢查； （ 5）數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)； （ 6）數(shù)據(jù)的服務(wù)：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。 數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令 (又稱自含型或自主型語言 )宿主型語言（一般可嵌入某些宿主語言中）。 數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運(yùn)行實體。 文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無法提供完整的、統(tǒng) 一的、管理和數(shù)據(jù)共享的能力。 關(guān)系數(shù)據(jù)庫系統(tǒng)階段 數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性 、數(shù)據(jù)的高共享性與低冗余性 、數(shù)據(jù)獨立性（物理獨立性與邏輯獨立性）、數(shù)據(jù)統(tǒng)一管理與控制。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式； （ 3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。 數(shù)據(jù)模型 數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表與操作提供一個抽象的框架。 ER 模型的基本概念 （ 1）實體：現(xiàn)實世界中的事物； （ 2）屬性：事物的特性； （ 3）聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。 ER 模型三個基本概念之間的聯(lián)接關(guān)系：實體是概念世界中的基本單位，屬性有屬性域，每 個實體可取屬性域內(nèi)的值。 ER 模型的圖示法：（ 1）實體集表示法； （ 2）屬性表法； （ 3）聯(lián)系表示法。 從圖論上看，網(wǎng)狀模型是一個不加任何條件限制的無向圖。一個二維表就是一個關(guān)系。從所有侯選健中選取一個作為用戶使用的鍵稱主鍵。 關(guān)系中的數(shù)據(jù)約束： （ 1）實體完整性約束：約束關(guān)系的主鍵中屬性值不能為空值； （ 2）參照完全性約束：是關(guān)系之間的基本約束； （ 3）用戶定義的完整性約束：它反映了具體應(yīng)用中數(shù)據(jù)的語義要求。 關(guān)系模型的基本運(yùn)算： （ 1）插入 （ 2）刪除 (3)修改 （ 4）查詢（包括投影、選擇、笛卡爾積運(yùn)算） 數(shù)據(jù)庫設(shè)計與 管理 數(shù)據(jù)庫設(shè)計是數(shù)據(jù)應(yīng)用的核心。 數(shù)據(jù)庫的生命周期：需求分析階段、概念設(shè)計階段、邏輯設(shè)計階段、物理設(shè)計階段、編碼階段、測試階段、運(yùn)行階段、進(jìn)一步修改階段。結(jié)構(gòu)化分析（簡稱 SA）方法用自頂向下、逐層分解的方式分析系統(tǒng)。對數(shù)據(jù)庫設(shè)計來講，數(shù)據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。 數(shù)據(jù)庫概念設(shè)計的目的是分析數(shù)據(jù)內(nèi)在語義關(guān)系。 設(shè)計方法： ER 模型與視圖集成。 視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約束沖突。 關(guān)系視圖的主要作用 ： （ 1）提供數(shù)據(jù)邏輯獨立性； （ 2）能適應(yīng)用戶對數(shù)據(jù)的不同需求； （ 3）有一定數(shù)據(jù)保密功能。一般 RDBMS中留給用戶參與物理設(shè)計的內(nèi)容大致有索引設(shè)計、集成簇設(shè)計和分區(qū)設(shè)計。 公共基礎(chǔ)知識考題匯編 1． 1 數(shù)據(jù)結(jié)構(gòu)與算法 一、選擇題 （ 1）下列敘述中正確的是 A）程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān) B）程序執(zhí)行效率只取決于程序的控制結(jié)構(gòu) C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量 D）以上三種說法都不對 （ 2）下列敘述中正確的是 A）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的 B）由于計算機(jī)存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu) C）程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu) D）以上三種說法都不對 （ 3）冒泡排序在最壞情況下的比較次數(shù)是 A） n(n+1)/2 B） nlog2n C） n(n1)/2 D） n/2 （ 4）一棵二叉樹中共有 70個葉子結(jié)點與 80個度為 1 的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為 A） 219 B） 221 C） 229 D） 231 （ 5）下列敘述中正確的是 A）算法的效率只是與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B）算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量 C）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲是一一對應(yīng)的 D）算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān) （ 6）下列對隊例的敘述正確的是 A）隊列屬于非線性表 B）隊列按“先進(jìn)后出”原則組織數(shù)據(jù) C）隊列在隊尾刪除數(shù)據(jù) D）隊列按“先進(jìn)先出”原則組織數(shù)據(jù) （ 7）對右圖二叉樹進(jìn)行前序遍歷的結(jié)果為 A） DYBEAFCZX B） YDEBFZXCA C） ABDYECFXZ D） ABCDEFXYZ （ 8）某二叉樹中有 n 個度為 2 的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為 A） n+1 B） n1 C） 2n D） n/2 （ 9）下列敘述中正確的是 A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大 B）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小 C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小 A B C D E F X Y Z 選擇題第（ 7）題圖 D）上述三種說法都不對 （ 10）在長度為 64 的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為 A） 63 B） 64 C） 6 D） 7 （ 11）對右圖二叉樹進(jìn)行中序遍歷的結(jié)果是 A） ACBDFEG B） ACBDFGE C） ABDCGEF D） FCADBEG （ 12）按照“后進(jìn)先出”原則組織數(shù)據(jù)結(jié)構(gòu)是 A）隊列 B）棧 C）雙向鏈表 D）二叉樹 （ 13）下列敘述中正確的是 A）線性鏈表層是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) B）棧與隊列是非線性結(jié)構(gòu) C）雙向鏈表是非線性結(jié)構(gòu) D）只有根結(jié)點的二叉樹是線性結(jié)構(gòu) （ 14）對右圖二叉樹進(jìn)行后 序遍歷的結(jié)果為 A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA （ 15）在深度為 7 的滿二叉樹中，葉子結(jié)點的個數(shù)為 A） 32 B） 31 C） 64 D） 63 （ 16）下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是 A）順序存儲的有序線性表 B）線性鏈表 C）二叉鏈表 D）有序線性鏈表 （ 17）下列關(guān)于棧的描述正確的是 A）在棧中只能插入元素而不能刪除元素 B）在棧中只能刪除元素而不能插入元素 C）棧是特殊的線性表，只能在一端插入成刪除元素 D）棧是特殊的線性表，只能在一端插入 元素，而在另一端刪除元素 （ 18）下列敘述中正確的是 A）一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu) B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 C）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響處理的效率 （ 19）數(shù)據(jù)的存儲結(jié)構(gòu)是指 A）存儲在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的存儲空間量 C）數(shù)據(jù)在計算機(jī)中的順序存儲方式 D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示 （ 20）下列關(guān)于棧的描述中錯誤的是 A）棧是先進(jìn)后出 的線性表 B）棧只能順序存儲 C）棧具有記憶作用 D）對棧的插入與刪除操作中，不需要改變棧底指針 （ 21）對于長度為 n 的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是 A）冒泡排序為 n/2 B）冒泡排序為 n C）快速排序為 n D）快速排序為 n(n1)/2 （ 22）對長度為 n 的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是 A） log2n B） n/2 C） n D） n+1 （ 23）下列對于線性鏈表的描述中正確的是 A）存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的 B）存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面 C）存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面 D）存儲空間必須連續(xù)，且各元素的存儲順序是任意的 二、填空題 A B C E E F 選擇題第（ 14）題圖 F C E A D G B 選擇題第（ 11）題圖 （ 1）線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 （ 2）對下列二叉地進(jìn)行中序遍歷的結(jié)果為 [2] 。 （ 4）按“先進(jìn)后出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 [4] 。 （ 6）對長度為 10 的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為 （ 6） 。 （ 8）一棵二叉樹第六層（根結(jié)點為第一層）的結(jié)點數(shù)最多為 [8] 個。 （ 10）某二叉樹中度為 2 的結(jié)點有 18個，則該二叉樹中有 [10] 個葉子結(jié)點。 1． 1． 3 全真試題訓(xùn)練 一、選擇 題 （ 1）長度為 10的順序表的首地址是從 1023 開始的，順序表中的每個元素的長度為 2，在第 4 個元素前面插入一個元素和刪除第 7 個元素后，順序表的總長度還是不變。則 T 中的葉子結(jié)點數(shù)為 A） 8 B） 7 C） 6 D） 5 （ 21）具有 8 個結(jié)點的完全二叉樹中編號為 4 的結(jié)點的右子結(jié)點的編號為 A） 8 B） 9 C）無此結(jié)點 D） 8 或是 9 （ 22）通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序的排序方法是 A）冒泡排序法 B）簡單選擇排序法 C）簡單插入排序法 D）希爾排序法 （ 23）快速排序法屬于 A）選擇類排序法 B）交換類排序法 C）插入類排序法 D）歸并類排序法 （ 24）對長度為 n 的線性表進(jìn)行推排序的時間復(fù)雜度是 A） O(n) B） O(nlog2n) C） O(n2) D） O() 二、填空題 （ 1）假如剛開始時棧為空，依次有‘ A’，‘ B’，‘ C’，‘ D’四個元素入棧，此時棧底指針指向元素 [1] ，棧頂指針值為 [2] （假設(shè)每個元素的長度為 1）。 （ 2）在一個容量為 15 的循環(huán)險旬中，若頭指針 front=6, 尾指針 rear=4，則該循環(huán)隊列中共有 [5]個元素；若頭指針 front=4，尾指針 rear=6，則該循環(huán)隊列中共有 [6] 個元素；若頭指針 front=6，尾指針 rear=6，則該循環(huán)隊列中共有 [7] 個元素。 （ 4）請寫出用二分查找法在有序順序表（ 1， 2， 3， 4， 6， 8， 9， 11）中查找 3 的比較序列 [9] 。 （ 6）請寫出用冒泡排序法對序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）進(jìn)行第一遍掃描后的中間結(jié)果是 [11] 。 （ 8）請寫出用簡單選擇排序法對序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）進(jìn)行第一遍掃描后的中間結(jié)果是 [13] 。 （ 10）在一般的計算機(jī)系統(tǒng)中，有算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和 [15] 四類基本的操作和運(yùn)算。 （ 12）算法必須能在有限的時間內(nèi)完成，即算法必須能在執(zhí)行有限個步驟之后終止，這是算法的 [17] 特征。 （ 14）算法中各操作之間的執(zhí)行順序稱為 （ 19） 。 （ 15）一個算法一般都可以用 [23] 、 [24] 、 [25] 三種控制結(jié)構(gòu)組合完成。 （ 17）通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系，這是算法設(shè)計基本方法中的 [27] 。 （ 19）將一個復(fù)雜的問題歸結(jié)為若干個簡單的問題，然后將這些較簡單的問題再歸結(jié)為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題的問題為止，這是算法設(shè)計基本方法中的 [29] 。如果算法 P 調(diào)用另一個算法 Q，而算法 Q 又調(diào)用算法 P，則稱為 [31] 。 （ 21）通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探，這是算法設(shè)計基本方法中的 [33] 。 （ 23）表示數(shù)據(jù)結(jié)構(gòu)的兩種方法是 [38] 和 [39] 。 （ 25）在長度為 n 的順序存儲結(jié)構(gòu)的線性表中，插入（或刪除）一個元素，在平均情況下需要移動表中的 [44] 個元素，在最壞情況下需要 移動表中的 [45] 個元素。 （ 27）樹是一種簡單的 [47] （線性 /非線性）結(jié)構(gòu)，在樹中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的 [48] 特征。 （ 29）具有 16 個結(jié)點的完全二叉樹的深度為 [50] 。 （ 31）以下排序技術(shù)中屬于交換類排序法的有 [56] ，屬于插入類排序法的有 [57] ，屬于選擇類排序法的有 [58] 。冒泡排序 V. 快速排序 1． 1． 4 歷屆最新考題與全真試題