計算機二級考公共基礎知識的內容並不多，但是一分都不能少。下面本站小編為大家整理了相關計算機二級公共基礎知識內容，希望大家喜歡。
資料結構與演算法
1 演算法
演算法：是指解題方案准確而完整的描述。
演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。
演算法的基本特徵：是一組嚴謹地定義運算順序的規則，每一個規則都是有效的，是明確的，此順序將在有限的次數下終止。特徵包括：
(1)可行性;
(2)確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性;
(3)有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止，包括合理的執行時間的含義;
(4)擁有足夠的情報。
演算法的基本要素：一是對資料物件的運算和操作;二是演算法的控制結構。
指令系統：一個計算機系統能執行的所有指令的集合。
基本運算和操作包括：算術運算、邏輯運算、關係運算、資料傳輸。
演算法的控制結構：順序結構、選擇結構、迴圈結構。
演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。
演算法複雜度：演算法時間複雜度和演算法空間複雜度。
演算法時間複雜度是指執行演算法所需要的計算工作量。
演算法空間複雜度是指執行這個演算法所需要的記憶體空間。
2 資料結構的基本基本概念
資料結構研究的三個方面：
(1)資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構;
(2)在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構;
(3)對各種資料結構進行的運算。
資料結構是指相互有關聯的資料元素的集合。
資料的邏輯結構包含：
(1)表示資料元素的資訊;
(2)表示各資料元素之間的前後件關係。
資料的儲存結構有順序、連結、索引等。
線性結構條件：
(1)有且只有一個根結點;
(2)每一個結點最多有一個前件，也最多有一個後件。
非線性結構：不滿足線性結構條件的資料結構。
3 線性表及其順序儲存結構
線性表由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。
非空線性表的結構特徵：
(1)且只有一個根結點a1，它無前件;
(2)有且只有一個終端結點an，它無後件;
(3)除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。
線性表的順序儲存結構具有以下兩個基本特點：
(1)線性表中所有元素的所佔的儲存空間是連續的;
(2)線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
ai的儲存地址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第一個元素的地址，k代表每個元素佔的位元組數。
順序表的運算：插入、刪除。 (詳見14--16頁)
4 棧和佇列
棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。
棧按照“先進後出”(filo)或“後進先出”(lifo)組織資料，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。
棧的基本運算：(1)插入元素稱為入棧運算;(2)刪除元素稱為退棧運算;(3)讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指標無變化。
佇列是指允許在一端(隊尾)進入插入，而在另一端(隊頭)進行刪除的線性表。rear指標指向隊尾，front指標指向隊頭。
佇列是“先進行出”(fifo)或“後進後出”(lilo)的線性表。
佇列運算包括(1)入隊運算：從隊尾插入一個元素;(2)退隊運算：從隊頭刪除一個元素。
迴圈佇列：s=0表示佇列空，s=1且front=rear表示佇列滿
5 線性連結串列
資料結構中的每一個結點對應於一個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
結點由兩部分組成：(1)用於儲存資料元素值，稱為資料域;(2)用於存放指標，稱為指標域，用於指向前一個或後一個結點。
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
線性連結串列，head稱為頭指標，head=null(或0)稱為空表，如果是兩指標：左指標(llink)指向前件結點，右指標(rlink)指向後件結點。
線性連結串列的基本運算：查詢、插入、刪除。
6 樹與二叉樹
樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點：(1)非空二叉樹只有一個根結點;(2)每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質：
(1)在二叉樹的第k層上，最多有2k-1(k≥1)個結點;
(2)深度為m的二叉樹最多有2m-1個結點;
(3)度為0的結點(即葉子結點)總是比度為2的結點多一個;
(4)具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分;
(5)具有n個結點的完全二叉樹的深度為[log2n]+1;
(6)設完全二叉樹共有n個結點。如果從根結點開始，按層序(每一層從左到右)用自然數1，2，….n給結點進行編號(k=1,2….n)，有以下結論：
①若k=1，則該結點為根結點，它沒有父結點;若k>1，則該結點的父結點編號為int(k/2);
②若2k≤n，則編號為k的結點的左子結點編號為2k;否則該結點無左子結點(也無右子結點);
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1;否則該結點無右子結點。
滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。
二叉樹儲存結構採用鏈式儲存結構，對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。
二叉樹的遍歷：
(1)前序遍歷(dlr)，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹;
(2)中序遍歷(ldr)，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹;
(3)後序遍歷(lrd)首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。
7 查詢技術
順序查詢的使用情況：
(1)線性表為無序表;
(2)表採用鏈式儲存結構。
二分法查詢只適用於順序儲存的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次。
8 排序技術
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。
交換類排序法：(1)氣泡排序法，需要比較的次數為n(n-1)/2; (2)快速排序法。
插入類排序法：(1)簡單插入排序法，最壞情況需要n(n-1)/2次比較;(2)希爾排序法，最壞情況需要o(n1.5)次比較。
選擇類排序法：(1)簡單選擇排序法,
最壞情況需要n(n-1)/2次比較;(2)堆排序法，最壞情況需要o(nlog2n)次比較。
1.1 演算法
演算法：是解題方案准確而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。
(1)確定性，演算法中每一步驟都必須有明確定義，不允許有模稜兩可的解釋，不允許有多義性;
(2)有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止;
(3)可行性，演算法原則上能夠精確地執行;
(4)擁有足夠的情報。
演算法效率的度量—演算法複雜度：演算法時間複雜度和演算法空間複雜度。★★★
演算法時間複雜度：指執行演算法所需要的計算工作量。即演算法執行過程中所需要的基本運算次數。
演算法空間複雜度：指執行這個演算法所需要的記憶體空間。
1.2 資料結構的基本概念
資料結構：指相互有關聯的資料元素的集合。
資料結構研究的三個方面：
(1)資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構;
(2)在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構;
(3)對各種資料結構進行的運算。
線性結構的條件，(一個非空資料結構)：
(1)有且只有一個根結點; (2)每一個結點最多有一個前件，也最多有一個後件。
非線性結構：不滿足線性結構條件的資料結構。
1.3 線性表及其順序儲存結構
線性表的順序儲存結構具有以下兩個基本特點：
(1)線性表中所有元素所佔的儲存空間是連續的;
(2)線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
順序表的運算：查詢、插入、刪除。
1.4線性連結串列
資料結構中的每一個結點對應於一個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
結點由兩部分組成：
(1) 用於儲存資料元素值，稱為資料域;
(2) 用於存放指標，稱為指標域，用於指向前一個或後一個結點。
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
線性連結串列的基本運算：查詢、插入、刪除。
1.5棧和佇列★★★★
棧：限定在一端進行插入與刪除的線性表。
其允許插入與刪除的一端稱為棧頂，用指標top表示棧頂位置。
不允許插入與刪除的另一端稱為棧底，用指標bottom表示棧底。
棧按照“先進後出”(FILO)或“後進先出”(LIFO)組織資料，棧具有記憶作用。
棧的儲存方式有順序儲存和鏈式儲存。
棧的基本運算：
(1) 入棧運算，在棧頂位置插入元素;
(2) 退棧運算，刪除元素(取出棧頂元素並賦給一個指定的變數);
(3) 讀棧頂元素，將棧頂元素賦給一個指定的變數，此時指標無變化。
佇列：指允許在一端(隊尾)進入插入，而在另一端(隊頭)進行刪除的線性表。
用rear指標指向隊尾，用front指標指向隊頭元素的前一個位置。
佇列是“先進先出”(FIFO)或“後進後出”(LILO)的線性表。
佇列運算：
(1) 入隊運算：從隊尾插入一個元素;
(2) 退隊運算：從隊頭刪除一個元素;
計算迴圈佇列的元素個數：
“尾指標減頭指標”，若為負數，再加其容量即可。
即:
當 尾指標-頭指標>0 時,尾指標-頭指標
當 尾指標-頭指標<0 時,尾指標-頭指標+容量
計算棧的個數:
棧底 –棧頂 +1
1.6 樹與二叉樹 ★★★★★
1、樹的基本概念
樹是一種簡單的非線性結構，其所有元素之間具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點。
沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。
每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度。 來源：考試大
所有結點中最大的度稱為樹的度。
樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
滿足下列兩個特點的樹,即為二叉樹
(1) 非空二叉樹只有一個根結點;
(2) 每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹基本性質：★★★★
性質1 在二叉樹的第k層上，最多有 個結點。
性質2 深度為m的二叉樹最多有個 個結點。
性質3 在任意一棵二叉樹中，度數為0的結點(即葉子結點)總比度為2的結點多一個。
性質4 具有n個結點的二叉樹，其深度至少為 ，其中 表示取 的整數部分
3、滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。
完全二叉樹：除最後一層外，每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。
下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：
4、二叉樹的遍歷 ★★★★
二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
(1)前序遍歷(DLR)：若二叉樹為空，則結束返回。否則：首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹;並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
(2)中序遍歷(LDR)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹;並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
(3)後序遍歷(LRD)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點.
該二叉樹前序遍歷為:F C A D B E G H P
該二叉樹中序遍歷為:A C B D F E H G P
該二叉樹後序遍歷為:A B D C H P G E F
1.7 查詢技術
查詢：根據給定的某個值，在查詢表中確定一個其關鍵字等於給定值的資料元素。
查詢結果：(查詢成功：找到;查詢不成功：沒找到。)
平均查詢長度：查詢過程中關鍵字和給定值比較的平均次數。
查詢分為: 順序查詢 二分法查詢對於長度為n的有序線性表，最壞情況只需比較 次，而順序查詢需要比較n次。
1.8 排序技術
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。
1、交換類排序法(氣泡排序，快速排序)
2、插入類排序法(簡單插入排序，希爾排序)
3、選擇類排序法(簡單選擇排序，堆排序)
氣泡排序法,快速排序法,簡單插入排序法,簡單選擇排序法,最壞需要比較的次數為n(n-1)/2
希爾排序,最壞需要比較的次數為
堆排序,最壞需要比較的次數為
2.1 程式設計設計方法和風格
"清晰第一、效率第二"已成為當今主導的程式設計風格。
形成良好的程式設計風格需注意：
1、源程式文件化;
2、資料說明的方法;
3、語句的結構;
4、輸入和輸出。
註釋分序言性註釋和功能性註釋。 語句結構清晰第一、效率第二。
2.2 結構化程式設計
結構化程式設計方法的四條原則是：
1、自頂向下;
2、逐步求精;
3、模組化;
4、限制使用goto語句。
3.1 軟體工程基本概念
1、軟體的相關概念
計算機軟體是包括程式、資料及相關文件的完整集合。
軟體的特點包括：1)軟體是一種邏輯實體，而不是物理實體，具有抽象性;2)軟體的生產與硬體不同，它沒有明顯的製作過程;3)軟體在執行、使用期間不 存在磨損、老化問題;4)軟體的開發、執行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟體移植的問題;5)軟體複雜性高，成本昂貴;6)軟體 開發涉及諸多的社會因素。
2、軟體危機與軟體工程
軟體工程源自軟體危機。所謂軟體危機是泛指在計算機軟體的開發和維護過程中所遇到的一系列嚴重問題。
軟體工程的主要思想是將工程化原則運用到軟體開發過程，它包括3個要素：方法、工具和過程。方法是完成軟體工程專案的技術手段;工具是支援軟體的開發、管理、文件生成;過程支援軟體開發的各個環節的控制、管理。
軟體工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。
3、軟體生命週期
軟體生命週期：軟體產品從提出、實現、使用維護到停止使用退役的過程。
軟體生命週期分為軟體定義、軟體開發及軟體執行維護三個階段：
1)軟體定義階段：包括制定計劃和需求分析。
制定計劃：確定總目標;可行性研究;探討解決方案;制定開發計劃。
需求分析：對待開發軟體提出的需求進行分析並給出詳細的定義。
2)軟體開發階段：
軟體設計：分為概要設計和詳細設計兩個部分。
軟體實現：把軟體設計轉換成計算機可以接受的程式程式碼。
軟體測試：在設計測試用例的基礎上檢驗軟體的各個組成部分。
3)軟體執行維護階段：軟體投入執行，並在使用中不斷地維護，進行必要的擴充和刪改。
4、軟體工程的目標和與原則
(1)軟體工程目標：在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、
可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足使用者需求的產品。
(2)軟體工程需要達到的基本目標應是：付出較低的開發成本;達到要求的軟體功能;取得較好的軟體效能;開發的軟體易於移植;需要較低的維護費用;能按時完成開發，及時交付使用。
(3)軟體工程原則：抽象、資訊隱蔽、模組化、區域性化、確定性、一致性、完備性和可驗證性。
1)抽象： 2)資訊隱蔽： 3)模組化：4)區域性化：5)確定性： 6)一致性：7)完備性： 8)可驗證性：
3.2 結構化分析方法
1、需求分析
需求分析方法有：1)結構化需求分析方法;2)面向物件的分析方法。
2、結構化分析方法
結構化分析方法是結構化程式設計理論在軟體需求分析階段的應用。
結構化分析方法的實質：著眼於資料流，自頂向下，逐層分解，建立系統的處理流程，以資料流圖和資料字典為主要工具，建立系統的邏輯模型。
結構化分析的常用工具：1)資料流圖(DFD);2)資料字典(DD);3)判定樹;4)判定表。
資料流圖的基本圖形元素：
加工(轉換)：輸入資料經加工變換產生輸出。
資料流：沿箭頭方向傳送資料的通道，一般在旁邊標註資料流名。
儲存檔案(資料來源)：表示處理過程中存放各種資料的檔案。
源，潭：表示系統和環境的介面，屬系統之外的實體。
3.3 結構化設計方法
1、軟體設計的基礎
從技術觀點來看，軟體設計包括軟體結構設計、資料設計、介面設計、過程設計。
從工程角度來看，軟體設計分兩步完成，即概要設計和詳細設計。
概要設計：又稱結構設計，將軟體需求轉化為軟體體系結構，確定系統級介面、全域性資料結構或資料庫模式。
詳細設計：確定每個模組的實現演算法和區域性資料結構，用適當方法表示演算法和資料結構的細節。
軟體設計的基本原理包括：抽象、模組化、資訊隱蔽和模組獨立性。
1)抽象。抽象是一種思維工具，就是把事物本質的共同特性提取出來而不考慮其他細節。
2)模組化。解決一個複雜問題時自頂向下逐步把軟體系統劃分成一個個較小的、相對獨立但又不相互關聯的模組的過程。
3)資訊隱蔽。每個模組的實施細節對於其他模組來說是隱蔽的。
4)模組獨立性。軟體系統中每個模組只涉及軟體要求的具體的子功能，而和軟體系統中其他的模組的介面是簡單的。
*：模組分解的主要指導思想是資訊隱蔽和模組獨立性。
模組的耦合性和內聚性是衡量軟體的模組獨立性的兩個定性指標。
內聚性：是一個模組內部各個元素間彼此結合的緊密程度的度量。
*：按內聚性由弱到強排列，內聚可以分為以下幾種：偶然內聚、邏輯內聚、時間內聚、過程內聚、通訊內聚、順序內聚及功能內聚。
耦合性：是模組間互相連線的緊密程度的度量。
*：按耦合性由高到低排列，耦合可以分為以下幾種：內容耦合、公共耦合、外部耦合、控制耦合、標記耦合、資料耦合以及非直接耦合。
一個設計良好的軟體系統應具有高內聚、低耦合的特徵。
在結構化程式設計中，模組劃分的原則是：模組內具有高內聚度，模組間具有低耦合度。
2、總體設計(概要設計)和詳細設計
(1)總體設計(概要設計)
軟體概要設計的基本任務是：1)設計軟體系統結構;2)資料結構及資料庫設計;3)編寫概要設計文件;4)概要設計文件評審。
常用的軟體結構設計工具是結構圖，也稱程式結構圖。程式結構圖的基本圖符：
模組用一個矩形表示，箭頭表示模組間的呼叫關係。在結構圖中還可以用帶註釋的箭頭表示模組呼叫過程中來回傳遞的資訊。還可用帶實心圓的箭頭表示傳遞的是控制資訊，空心圓箭心表示傳遞的是資料資訊。
(2)詳細設計
詳細設計是為軟體結構圖中的每一個模組確定實現演算法和區域性資料結構，用某種選定的表達工具表示演算法和資料結構的細節。
常用的過程設計(即詳細設計)工具有以下幾種：
圖形工具：程式流程圖、N-S(方盒圖)、PAD(問題分析圖)和HIPO(層次圖+輸入/處理/輸出圖)。
表格工具：判定表。
語言工具：PDL(偽碼)
3.4 軟體測試
1、軟體測試定義：使用人工或自動手段來執行或測定某個系統的過程，其目的在於檢驗它是否滿足規定的需求或是弄清預期結果與實際結果之間的差別。
軟體測試的目的：儘可能地多發現程式中的錯誤，不能也不可能證明程式沒有錯誤。軟體測試的關鍵是設計測試用例，一個好的測試用例能找到迄今為止尚未發現的錯誤。
2、軟體測試方法：靜態測試和動態測試。
靜態測試：包括程式碼檢查、靜態結構分析、程式碼質量度量。不實際執行軟體，主要通過人工進行。
動態測試：是基於計算機的測試，主要包括白盒測試方法和黑盒測試方法。
(1)白盒測試
白盒測試方法也稱為結構測試或邏輯驅動測試。它是根據軟體產品的內部工作過程，檢查內部成分，以確認每種內部操作符合設計規格要求。
白盒測試的基本原則：保證所測模組中每一獨立路徑至少執行一次;保證所測模組所有判斷的每一分支至少執行一次;保證所測模組每一迴圈都在邊界條件和一般條件下至少各執行一次;驗證所有內部資料結構的有效性。
*：白盒測試法的測試用例是根據程式的內部邏輯來設計的，主要用軟體的單元測試，主要方法有邏輯覆蓋、基本路徑測試等。
A、邏輯覆蓋。邏輯覆蓋泛指一系列以程式內部的邏輯結構為基礎的測試用例設計技術。通常程式中的邏輯表示有判斷、分支、條件等幾種表示方法。
語句覆蓋：選擇足夠的測試用例，使得程式中每一個語句至少都能被執行一次。
路徑覆蓋：執行足夠的測試用例，使程式中所有的可能的路徑都至少經歷一次。
判定覆蓋：使設計的測試用例保證程式中每個判斷的每個取值分支(T或F)至少經歷一次。
條件覆蓋：設計的測試用例保證程式中每個判斷的每個條件的可能取值至少執行一次。
判斷-條件覆蓋：設計足夠的測試用例，使判斷中每個條件的所有可能取值至少執行一次，同時每個判斷的所有可能取值分支至少執行一次。
*：邏輯覆蓋的強度依次是：語句覆蓋<路徑覆蓋<判定覆蓋<條件覆蓋<判斷-條件覆蓋。
B、基本路徑測試。其思想和步驟是，根據軟體過程性描述中的控制流程確定程式的環路複雜性度量，用此度量定義基本路徑集合，並由此匯出一組測試用例，對每一條獨立執行路徑進行測試。
(2)黑盒測試
黑盒測試方法也稱為功能測試或資料驅動測試。黑盒測試是對軟體已經實現的功能是否滿足需求進行測試和驗證。
黑盒測試主要診斷功能不對或遺漏、介面錯誤、資料結構或外部資料庫訪問錯誤、效能錯誤、初始化和終止條件錯誤。
黑盒測試不關心程式內部的邏輯，只是根據程式的功能說明來設計測試用例，主要方法有等價類劃分法、邊界值分析法、錯誤推測法等，主要用軟體的確認測試。
3、軟體測試過程一般按4個步驟進行：單元測試、整合測試、確認測試和系統測試。
3.5 程式的除錯
程式除錯的任務是診斷和改正程式中的錯誤，主要在開發階段進行，除錯程式應該由編制源程式的程式設計師來完成。
程式除錯的基本步驟：(1)錯誤定位;(2)糾正錯誤;(3)迴歸測試。
軟體的除錯後要進行迴歸測試，防止引進新的錯誤。
軟體除錯可分為靜態除錯和動態除錯。靜態除錯主要是指通過人的思維來分析源程式程式碼和排錯，是主要的除錯手段，而動態除錯是輔助靜態除錯。
對軟體主要的除錯方法可以採用：
(1)強行排錯法。
(2)回溯法。
(3)原因排除法。
結構化程式的基本結構及特點：
(1)順序結構：一種簡單的程式設計，最基本、最常用的結構;
(2)選擇結構：又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執行相應的語句序列;
(3)迴圈結構：又稱重複結構，可根據給定條件，判斷是否需要重複執行某一相同或類似的程式段。
結構化程式設計的特點：只有一個入口和出口
2.3 面向物件的程式設計
面向物件方法的優點：
(1)與人類習慣的思維方法一致;
(2)穩定性好;
(3)可重用性好;
(4)易於開發大型軟體產品;
(5)可維護性好。
物件是面向物件方法中最基本的概念，可以用來表示客觀世界中的任何實體，物件是實體的抽象。
面向物件的程式設計方法中，物件是由資料的容許的操作組成的封裝體，是系統中用來描述客觀事物的一個實體，是構成系統的一個基本單位，由一組表示其靜態特徵的屬性和它可執行的一組操作組成。
操作描述了物件執行的功能，是物件的動態屬性，操作也稱為方法或服務。
物件的基本特點：
(1)標識惟一性;
(2)分類性;
(3)多型性;
(4)封裝性;
(5)模組獨立性好。
類是指具有共同屬性、共同方法的物件的集合。類是關於物件性質的描述。類是物件的抽象，物件是其對應類的一個例項。
訊息是一個例項與另一個例項之間傳遞的資訊。物件間的通訊靠訊息傳遞。它請求物件執行某一處理或回答某一要求的資訊，它統一了資料流和控制流。
繼承是使用已有的類定義作為基礎建立新類的定義技術，廣義指能夠直接獲得已有的性質和特徵，而不必重複定義他們。
繼承具有傳遞性，一個類實際上繼承了他上層的全部基類的特性。
繼承分單繼承和多重繼承。
多型性是指同樣的訊息被不同的物件接受時可導致完全不同的行動的現象。
4.1 資料庫系統的基本概念
1、資料、資料庫、資料管理系統
(1)資料
(2)資料庫(DB)
(3)資料庫管理系統(DBMS)：一種系統軟體，負責資料庫中的資料組織、資料操縱、資料維護、控制及保護和資料服務等，是資料庫的核心。
資料庫管理系統功能：
1)資料模式定義
2)資料存取的物理構建
3)資料操縱
4)資料的完整性、安生性定義與檢查
5)資料庫的併發控制與故障恢復
6)資料的服務
資料庫技術的根本目標是解決資料的共享問題。
2、資料庫系統的發展
資料庫管理髮展至今已經歷了三個階段：人工管理階段、檔案系統階段和資料庫系統階段。
3、資料庫系統的基本特點
(1)資料的高整合性。
(2)資料的高共享性與低冗餘性。
(3)資料獨立性：
資料獨立性一般分為物理獨立性與邏輯獨立性兩級。
物理獨立性：物理獨立性即是資料的物理結構(包括儲存結構，存取方式等)的改變，如儲存裝置的更換、物理儲存的更換、存取方式改變等都不影響資料庫的邏輯結構，從而不致引起應用程式的變化。
邏輯獨立性：資料庫總體邏輯結構的改變，如修改資料模式、增加新的資料型別、改變資料間聯絡等，不需要相應修改應用程式，這就是資料的邏輯獨立性。
(4)資料統一管理與控制。
4、資料庫系統的內部結構體系
(1)資料庫系統的三級模式：
1)概念模式：資料庫系統中全域性資料邏輯結構的描述，是全體使用者(應用)公共資料檢視。
2)外模式：也稱子模式或使用者模式，它是使用者的資料檢視，也就是使用者所見到的資料模式，它由概念模式推導而出。
3)內模式：又稱物理模式，它給出了資料庫物理儲存結構與物理存取方法。內模式的物理性主要體現在作業系統及檔案級上，它還未深入到裝置級上(如磁碟及磁碟操作)。內模式對一般使用者是透明的，但它的設計直接影響資料庫的效能。
(2)資料庫系統的兩級對映：
1)概念模式/內模式的對映：實現了概念模式到內模式之間的相互轉換。當資料庫的儲存結構發生變化時，通過修改相應的概念模式/內模式的對映，使得資料庫的邏輯模式不變，其外模式不變，應用程式不用修改，從而保證資料具有很高的物理獨立性。
2)外模式/概念模式的對映：實現了外模式到概念模式之間的相互轉換。當邏輯模式發生變化時，通過修改相應的外模式/邏輯模式對映，使得使用者所使用的那部分外模式不變，從而應用程式不必修改，保證資料具有較高的邏輯獨立性。
4.2 資料模型
1、資料模型
2、實體聯絡模型及E-R圖
E-R模型的圖示法：
1)實體集：用矩形表示。
2)屬性：用橢圓形表示。
3)聯絡：用菱形表示。
4)實體集與屬性間的聯接關係：用無向線段表示。
5)實體集與聯絡間的聯接關係：用無向線段表示。
3、資料庫管理系統常見的資料模型有層次模型、網狀模型和關係模型三種。
4.3 關係代數
1、關係的資料結構
關係是由若干個不同的元組所組成，因此關係可視為元組的集合。n元關係是一個n元有序組的集合。
關係模型的基本運算：1)插入;2)刪除;3)修改;4)查詢(包括投影、選擇、笛卡爾積運算)。
2、關係操縱
關係模型的資料操縱即是建立在關係上的資料操縱，一般有查詢、增加、刪除和修改四種操作。
3、集合運算及選擇、投影、連線運算
(1)並(∪)：關係R和S具有相同的關係模式，R和S的並是由屬於R或屬於S的元組構成的集合。
(2)差(-)：關係R和S具有相同的關係模式，R和S的差是由屬於R但不屬於S的元組構成的集合。
(3)交(∩)：關係R和S具有相同的關係模式，R和S的交是由屬於R且屬於S的元組構成的集合。
(4)廣義笛卡爾積(×)：設關係R和S的屬性個數分別為n、m，則R和S的廣義笛卡爾
積是一個有(n+m)列的元組的集合。每個元組的前n列來自R的一個元組，後m列來自S的一個元組，記為R×S。
*：根據笛卡爾積的定義：有n元關係R及m元關係S，它們分別有p、q個元組，則關係R與S經笛卡爾積記為R×S，該關係是一個n+m元關係，元組個數是p×q，由R與S的有序組組合而成。
例：有兩個關係R和S，分別進行並、差、交和廣義笛卡爾積運算。
(5)在關係型資料庫管理系統中，基本的關係運算有選擇、投影與聯接三種操作：
1)選擇：選擇指的是從二維關係表的全部記錄中，把那些符合指定條件的記錄挑出來。
2)投影：投影是從所有欄位中選取一部分欄位及其值進行操作，它是一種縱向操作。
3)聯接：聯接將兩個關係模式拼接成一個更寬的關係模式，生成的新關係中包含滿足聯接條件的元組。
4.4 資料庫設計方法和步驟
(1)資料庫設計階段包括：需求分析、概念分析、邏輯設計、物理設計。
(2)資料庫設計的每個階段都有各自的任務：
1)需求分析階段：這是資料庫設計的第一個階段，任務主要是收集和分析資料，這一階段收集到的基礎資料和資料流圖是下一步設計概念結構的基礎。
2)概念設計階段：分析資料間內在語義關聯，在此基礎上建立一個數據的抽象模型，即形成E-R圖。
3)邏輯設計階段：將E-R圖轉換成指定RDBMS中的關係模式。
4)物理設計階段：對資料庫內部物理結構作調整並選擇合理的存取路徑，以提高資料庫訪問速度及有效利用儲存空間。
全國計算機等級考試二級公共基礎知識複習題一、選擇題(在下列各題的A)、 B)、 C)、D)四個選項中，只有一個選項是正確的，請將正確選項填塗在答題卡相應位置上。)
1.1 資料結構作為計算機的一門學科，主要研究資料的邏輯結構、對各種資料結構進行的運算，以及
A)資料的儲存結構 B)計算方法 C)資料映象 D)邏輯儲存
正確答案: A
1.2 資料處理的最小單位是
A)資料 B)資料元素 C)資料項 D)資料結構
正確答案: C
1.3 根據資料結構中各資料元素之間前後件關係的複雜程度，一般將資料結構分成
A)動態結構和靜態結構 B)緊湊結構和非緊湊結構 C)線性結構和非線性結構 D)內部結構和外部結構
正確答案: C
1.4 資料結構中，與所使用的計算機無關的是資料的
A)儲存結構
正確答案: C
1.5 在計算機中，演算法是指
A)加工方法 B)解題方案准確而完整的描述 C)排序方法 D)查詢方法
正確答案: B
1.6 演算法分析的目的是
A)找出資料結構的合理性 B)找出演算法中輸入和輸出之間的關係 C)分析演算法的易懂性和可靠性 D)分析演算法的效率以求改進
正確答案: D
1.7 演算法的時間複雜度是指
A)執行演算法程式所需要的時間 B)演算法程式的長度 C)演算法執行過程中所需要的.基本運算次數 D)演算法程式中的指令條數
正確答案: C
1.8 演算法的空間複雜度是指
A)演算法程式的長度 B)演算法程式中的指令條數 C)演算法程式所佔的儲存空間 D)執行過程中所需要的儲存空間
正確答案: D
1.9 連結串列不具有的特點是
A)不必事先估計儲存空間 B)可隨機訪問任一元素
C)插入刪除不需要移動元素 D)所需空間與線性表長度成正比
正確答案: B
1.10 用連結串列表示線性表的優點是
A)便於隨機存取 B)花費的儲存空間較順序儲存少
C)便於插入和刪除操作 D)資料元素的物理順序與邏輯順序相同
正確答案: C
1.11 下列敘述中正確的是
A)線性表是線性結構 B)棧與佇列是非線性結構 C)線性連結串列是非線性結構 D)二叉樹是線性結構
正確答案: A
1.12 線性表的順序儲存結構和線性表的鏈式儲存結構分別是
A)順序存取的儲存結構、順序存取的儲存結構 B)隨機存取的儲存結構、順序存取的儲存結構
C)隨機存取的儲存結構、隨機存取的儲存結構 D)任意存取的儲存結構、任意存取的儲存結構
正確答案: B
1.13 線性表L=(a1,a2,a3,…ai，…an)，下列說法正確的是
A)每個元素都有一個直接前件和直接後件 B)線性表中至少要有一個元素
C)表中諸元素的排列順序必須是由小到大或由大到小
D)除第一個元素和最後一個元素外，其餘每個元素都有一個且只有一個直接前件和直接後件
正確答案: D
1.14 在單鏈表中，增加頭結點的目的是
A)方便運算的實現 B)使單鏈表至少有一個結點
C)標識表結點中首結點的位置 D)說明單鏈表是線性表的鏈式儲存實現
正確答案: A
1.15 非空的迴圈單鏈表head的尾結點(由p所指向)，滿足
A)p->next==NULL B)p==NULL C)p->next=head D)p=head
正確答案: C
1.16 迴圈連結串列的主要優點是
A)不再需要頭指標了 B)從表中任一結點出發都能訪問到整個連結串列
C)在進行插入、刪除運算時，能更好的保證連結串列不斷開 D)已知某個結點的位置後，能夠容易的找到它的直接前件
正確答案: B
1.17 下列資料結構中，按先進後出原則組織資料的是
A)線性連結串列 B)棧 C)迴圈連結串列 D)順序表
正確答案: B
1.18 棧和佇列的共同特點是
A)都是先進先出 B)都是先進後出 C)只允許在端點處插入和刪除元素 D)沒有共同點
正確答案: C
1.19 如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是
A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2 D)任意順序
正確答案: B
1.20 棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是
A)ABCED B)DCBEA C)DBCEA D)CDABE
正確答案: B
1.21 棧通常採用的兩種儲存結構是
A線性儲存結構和連結串列儲存結構 B雜湊方式和索引方式 C連結串列儲存結構和陣列 D)線性儲存結構和非線性儲存結構
正確答案: A
1.22 串的長度是
A)串中不同字元的個數 B串中不同字母的個數 C串中所含字元的個數且字元個數大於零 D)串中所含字元的個數
正確答案: D
1.23 樹是結點的集合，它的根結點數目是
A)有且只有1 B)1或多於1 C)0或1 D)至少2
正確答案: A
1.24 設有下列二叉樹：對此二叉樹前序遍歷的結果為
A)ZBTYCPXA B)ATBZXCYP C)ZBTACYXP D)ATBZXCPY
正確答案: B
1.25 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的後序遍歷為
A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG
正確答案: B
1.26 已知二叉樹後序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是
A)acbed B)decab C)deabc D)cedba
正確答案: D
1.27 具有3個結點的二叉樹有
A)2種形態 B)4種形態 C)7種形態 D)5種形態
正確答案: D
1.28 在深度為5的滿二叉樹中，葉子結點的個數為
A)32 B)31 C)16 D)15
正確答案: B
1.29 設一棵二叉樹中有3個葉子結點，有8個度為1的結點，則該二叉樹中總的結點數為
A)12 B)13 C)14 D)15
正確答案: B
1.30 n個頂點的強連通圖的邊數至少有
A)n-1 B)n(n-1) C)n D)n+1
正確答案: C
1.31 假設線性表的長度為n，則在最壞情況下，氣泡排序需要的比較次數為
A)log2n B)n2 C)O(n1.5) D)n(n-1)/2
正確答案: D
1.32 已知資料表A中每個元素距其最終位置不遠，為節省時間，應採用的演算法是
A)堆排序 B)直接插入排序 C)快速排序 D)直接選擇排序
正確答案: B
1.33 最簡單的交換排序方法是
A)快速排序 B)選擇排序 C)堆排序 D)氣泡排序
正確答案: D
1.34 在下列幾種排序方法中，要求記憶體量最大的是
A)插入排序 B)選擇排序 C)快速排序 D)歸併排序
正確答案: D
1.35 程式設計語言的基本成分是資料成分、運算成分、控制成分和
A)物件成分 B)變數成分 C)語句成分 D)傳輸成分
正確答案: D
1.36 結構化程式設計的3種結構是
A)順序結構、選擇結構、轉移結構 B)分支結構、等價結構、迴圈結構
C)多分支結構、賦值結構、等價結構 D)順序結構、選擇結構、迴圈結構
正確答案: D
1.37 在設計程式時，應採納的原則之一是
A)不限制goto語句的使用 B)減少或取消註解行 C)程式越短越好 D)程式結構應有助於讀者理解
正確答案: D
1.38 對建立良好的程式設計風格，下面描述正確的是
A程式應簡單、清晰、可讀性好 B符號名的命名只要符合語法 C充分考慮程式的執行效率 D程式的註釋可有可無
正確答案: A
1.39 下列敘述中，不屬於結構化程式設計方法的主要原則的是
A)自頂向下 B)由底向上 C)模組化 D)限制使用goto語句
正確答案: B
1.40 結構化程式設計主要強調的是
A)程式的規模 B)程式的效率 C)程式設計語言的先進性 D)程式易讀性
正確答案: D
1.41 在結構化程式設計思想提出之前，在程式設計中曾強調程式的效率，現在，與程式的效率相比，人們更重視程式的
A)安全性 B)一致性 C)可理解性 D)合理性
正確答案: C
1.42 一些重要的程式語言(如C語言和Pascal語言)允許過程的遞迴呼叫。而實現遞迴呼叫中的儲存分配通常用
A)棧 B)堆 C)陣列 D)連結串列
正確答案: A
1.43 以下不屬於物件的基本特點的是
A)分類性 B)多型性 C)繼承性 D)封裝性
正確答案: C
1.44 下列不屬於軟體工程的3個要素的是
A)工具 B)過程 C)方法 D)環境
正確答案: D
1.45 開發大型軟體時，產生困難的根本原因是
A)大系統的複雜性
B)人員知識不足 C)客觀世界千變萬化 D)時間緊、任務重
正確答案: A
1.46 下面不屬於軟體設計原則的是
A)抽象 B)模組化 C)自底向上 D)資訊隱蔽
正確答案: C
1.47 軟體工程的理論和技術性研究的內容主要包括軟體開發技術和
A)消除軟體危機 B)軟體工程管理 C)程式設計自動化 D)實現軟體可重用
正確答案: B
1.48 開發軟體所需高成本和產品的低質量之間有著尖銳的矛盾，這種現象稱作
A)軟體投機 B)軟體危機 C)軟體工程 D)軟體產生
正確答案: B
1.49 軟體工程的出現是由於
A)程式設計方法學的影響 B)軟體產業化的需要 C)軟體危機的出現 D)計算機的發展
正確答案: C
1.50 下列不屬於結構化分析的常用工具的是 A)資料流圖 B)資料字典 C)判定樹 D)PAD圖
正確答案: A
1.51 資料流圖用於抽象描述一個軟體的邏輯模型，資料流圖由一些特定的圖符構成。下列圖符名標識的圖符不屬於資料流圖合法圖符的是
A)控制流 B)加工 C)資料儲存 D)源和潭
正確答案: A
1.52 在資料流圖(DF
D)中，帶有名字的箭頭表示
A)模組之間的呼叫關係 B)程式的組成成分 C)控制程式的執行順序 D)資料的流向
正確答案: D
1.53 在結構化設計方法中，生成的結構圖(S
C)中，帶有箭頭的連線表示
A)模組之間的呼叫關係 B)程式的組成成分 C)控制程式的執行順序 D)資料的流向
正確答案: A
1.54 為了避免流程圖在描述程式邏輯時的靈活性，提出了用方框圖來代替傳統的程式流程圖，通常也把這種圖稱為
A)PAD圖 B)N-S圖 C)結構圖 D)資料流圖
正確答案: B
1.55 模組獨立性是軟體模組化所提出的要求，衡量模組獨立性的度量標準則是模組的
A)抽象和資訊隱蔽 B)區域性化和封裝化 C)內聚性和耦合性 D)啟用機制和控制方法
正確答案: C
1.56 下列選項中，不屬於模組間耦合的是
A)資料耦合 B)同構耦合 C)異構耦合 D)公用耦合
正確答案: C
1.57 軟體開發的結構化生命週期方法將軟體生命週期劃分成
A)定義、開發、執行維護 B)設計階段、程式設計階段、測試階段
C)總體設計、詳細設計、程式設計除錯 D)需求分析、功能定義、系統設計
正確答案: A
1.58 需求分析階段的任務是確定
A)軟體開發方法 B)軟體開發工具 C)軟體開發費用 D)軟體系統功能
正確答案: D
1.59 需求分析中開發人員要從使用者那裡瞭解
A)軟體做什麼 B)使用者使用介面 C)輸入的資訊 D)軟體的規模
正確答案: A
1.60 下列敘述中，不屬於軟體需求規格說明書的作用的是
A)便於使用者、開發人員進行理解和交流 B)反映出使用者問題的結構，可以作為軟體開發工作的基礎和依據
C)作為確認測試和驗收的依據 D)便於開發人員進行需求分析
正確答案: D
1.61 在軟體生產過程中，需求資訊的給出是
A)程式設計師 B)專案管理者 C)軟體分析設計人員 D)軟體使用者
正確答案: D
1.62 軟體設計包括軟體的結構、資料介面和過程設計，其中軟體的過程設計是指
A)模組間的關係 B)系統結構部件轉換成軟體的過程描述 C)軟體層次結構 D)軟體開發過程
正確答案: B
1.63 開發軟體時對提高開發人員工作效率至關重要的是
A)作業系統的資源管理功能 B)先進的軟體開發工具和環境 C)程式人員的數量 D)計算機的並行處理能力
正確答案: B
1.64 在軟體測試設計中，軟體測試的主要目的是
A)實驗性執行軟體 B)證明軟體正確 C)找出軟體中全部錯誤 D)發現軟體錯誤而執行程式
正確答案: D
1.65 下列敘述中，不屬於測試的特徵的是
A)測試的挑剔性 B)完全測試的不可能性 C)測試的可靠性 D)測試的經濟性
正確答案: C
1.66 為了提高測試的效率，應該
A)隨機選取測試資料 B)取一切可能的輸入資料作為測試資料 C)在完成編碼以後制定軟體的測試計劃
D)集中對付那些錯誤群集的程式
正確答案: D
1.67 軟體開發離不開系統環境資源的支援，其中必要的測試資料屬於
A)硬體資源 B)通訊資源 C)支援軟體 D)輔助資源
正確答案: D
1.68 完全不考慮程式的內部結構和內部特徵，而只是根據程式功能匯出測試用例的測試方法是
A)黑箱測試法 B)白箱測試法 C)錯誤推測法 D)安裝測試法
正確答案: A
1.69 在軟體工程中，白箱測試法可用於測試程式的內部結構。此方法將程式看做是
A)路徑的集合 B)迴圈的集合 C)目標的集合 D)地址的集合
正確答案: A
1.70 下列不屬於軟體除錯技術的是
A)強行排錯法 B)整合測試法 C)回溯法 D)原因排除法
正確答案: B
1.71 檢查軟體產品是否符合需求定義的過程稱為
A)確認測試 B)整合測試 C)驗證測試 D)驗收測試
正確答案: A
1.72 軟體生命週期中所花費用最多的階段是
A)詳細設計 B)軟體編碼 C)軟體測試 D)軟體維護
正確答案: D
1.73 軟體複雜性度量的引數包括
A)效率 B)規模 C)完整性 D)容錯性
正確答案: B
1.74 在資料管理技術的發展過程中，經歷了人工管理階段、檔案系統階段和資料庫系統階段。其中資料獨立性最高的階段是
A)資料庫系統 B)檔案系統 C)人工管理 D)資料項管理
正確答案: A
1.75 在資料管理技術發展過程中，檔案系統與資料庫系統的主要區別是資料庫系統具有
A)特定的資料模型 B)資料無冗餘 C)資料可共享 D)專門的資料管理軟體
正確答案: A
1.76 相對於資料庫系統，檔案系統的主要缺陷有資料關聯差、資料不一致性和
A)可重用性差 B)安全性差 C)非永續性 D)冗餘性
正確答案: D
1.77 下列說法中，不屬於資料模型所描述的內容的是
A)資料結構 B)資料操作 C)資料查詢 D)資料約束
正確答案: C
1.78 下列有關資料庫的描述，正確的是
A)資料庫是一個DBF檔案 B)資料庫是一個關係 C)資料庫是一個結構化的資料集合 D)資料庫是一組檔案
正確答案: C
1.79 下列有關資料庫的描述，正確的是
A)資料處理是將資訊轉化為資料的過程 B)資料的物理獨立性是指當資料的邏輯結構改變時，資料的儲存結構不變
C)關係中的每一列稱為元組，一個元組就是一個欄位
D)如果一個關係中的屬性或屬性組並非該關係的關鍵字，但它是另一個關係的關鍵字，則稱其為本關係的外關鍵字
正確答案: D
1.80 應用資料庫的主要目的是
A)解決資料保密問題 B)解決資料完整性問題 C)解決資料共享問題 D)解決資料量大的問題
正確答案: C
1.81 資料庫設計包括兩個方面的設計內容，它們是
A)概念設計和邏輯設計 B)模式設計和內模式設計 C)內模式設計和物理設計 D)結構特性設計和行為特性設計
正確答案: A
1.82 下述關於資料庫系統的敘述中正確的是
A)資料庫系統減少了資料冗餘 B)資料庫系統避免了一切冗餘
C)資料庫系統中資料的一致性是指資料型別一致 D)資料庫系統比檔案系統能管理更多的資料
正確答案: B
1.83 資料庫系統的核心是
A)資料庫 B)資料庫管理系統 C)模擬模型 D)軟體工程
正確答案: B
1.84 為使用者與資料庫系統提供介面的語言是
A)高階語言 B)資料描述語言(DDL) C)資料操縱語言(DML) D)組合語言
正確答案: C
1.85 資料庫、資料庫系統和資料庫管理系統之間的關係是
A)資料庫包括資料庫系統和資料庫管理系統 B)資料庫系統包括資料庫和資料庫管理系統
C)資料庫管理系統包括資料庫和資料庫系統 D)3者沒有明顯的包含關係
正確答案: B
1.86 分散式資料庫系統不具有的特點是
A)資料分佈性和邏輯整體性 B)位置透明性和複製透明性 C)分佈性 D)資料冗餘
正確答案: D
1.87 資料庫管理系統DBMS中用來定義模式、內模式和外模式的語言為
A)C B)Basic C)DDL D)DML
正確答案: C
1.88 單個使用者使用的資料檢視的描述稱為
A)外模式 B)概念模式 C)內模式 D)儲存模式
正確答案: A
1.89 索引屬於
A)模式 B)內模式 C)外模式 D)概念模式
正確答案: B
1.90 在資料庫設計中，將E-R圖轉換成關係資料模型的過程屬於
A)需求分析階段 B)邏輯設計階段 C)概念設計階段 D)物理設計階段
正確答案: B
1.91 實體是資訊世界中廣泛使用的一個術語，它用於表示
A)有生命的事物 B)無生命的事物 C)實際存在的事物 D)一切事物
正確答案: C
1.92 將E-R圖轉換到關係模式時，實體與聯絡都可以表示成
A)屬性 B)關係 C)鍵 D)域
正確答案: B
1.93 下列敘述中，正確的是
A)用E-R圖能夠表示實體集間一對一的聯絡、一對多的聯絡和多對多的聯絡 B)用E-R圖只能表示實體集之間一對一的聯絡
C)用E-R圖只能表示實體集之間一對多的聯絡 D)用E-R圖表示的概念資料模型只能轉換為關係資料模型
正確答案: C
1.94 一個關係中屬性個數為1時，稱此關係為
A)對應關係 B)單一關係 C)一元關係 D)二元關係
正確答案: C
1.95 下列關係模型中，能使經運算後得到的新關係中屬性個數多於原來關係中屬性個數的是
A)選擇 B)連線 C)投影 D)並
正確答案: B
1.96 下列資料模型中，具有堅實理論基礎的是
A)層次模型 B)網狀模型 C)關係模型 D)以上3個都是
正確答案: C
1.97 關係模型允許定義3類資料約束，下列不屬於資料約束的是
A)實體完整性約束 B)參照完整性約束 C)域完整性約束 D)使用者自定義的完整性約束
正確答案: C
1.98 “年齡在18～25之間”這種約束是屬於資料庫當中的
A)原子性措施 B)一致性措施 C)完整性措施 D)安全性措施
正確答案: C
1.99 關係表中的每一橫行稱為一個
A)元組 B)欄位 C)屬性 D)碼
正確答案: A
1.100 SQL語言又稱為
A)結構化定義語言 B)結構化控制語言 C)結構化查詢語言 D)結構化操縱語言
正確答案: C
1.101 下列SQL語句中，用於修改表結構的是
A)ALTER B)CREATE C)UPDATE D)INSERT
正確答案: A
1.102 NULL是指
A)0 B)空格 C)未知的值或無任何值 D)空字串
正確答案: C
1.103 資料庫的故障恢復一般是由
A)資料流圖完成的 B)資料字典完成的 C)DBA完成的 D)PAD圖完成的
正確答案: C
二、填空題(請將每一個空的正確答案寫在答題卡相應序號後。)
1.104 演算法的基本特徵是可行性、確定性、 【1】 和擁有足夠的情報。
正確答案: 有窮性
1.105 資料結構分為邏輯結構與儲存結構，線性連結串列屬於 【2】 。
正確答案: 儲存結構
1.106 資料的邏輯結構有線性結構和 【3】 兩大類。
正確答案: 非線性結構
1.107 在演算法正確的前提下，評價一個演算法的兩個標準是 【4】 。
正確答案: 時間複雜度和空間複雜度
1.108 演算法的工作量大小和實現演算法所需的儲存單元多少分別稱為演算法的 【5】 。
正確答案: 時間複雜度和空間複雜度
1.109 順序儲存方法是把邏輯上相鄰的結點儲存在物理位置 【6】 的儲存單元中。
正確答案: 相鄰
1.110 長度為n的順序儲存線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數為【7】 。
正確答案: n/2
1.111 棧和佇列通常採用的儲存結構是 【8】 。
正確答案: 鏈式儲存和順序儲存
1.112 當迴圈佇列非空且隊尾指標等於隊頭指標時，說明迴圈佇列已滿，不能進行入隊運算。這種情況稱為【9】 。
正確答案: 上溢
1.113 若串s="MathTypes"，則其子串的數目是【10】 。
正確答案: 46
1.114 在樹形結構中，樹根結點沒有 【11】 。
正確答案: 前件
1.115 在長度為n的有序線性表中進行二分查詢。最壞的情況下，需要的比較次數為【12】 。
正確答案: log2n
1.116 排序是計算機程式設計中的一種重要操作，常見的排序方法有插入排序、 【13】和選擇排序等。
正確答案: 交換排序
1.117 氣泡排序演算法在最好的情況下的元素交換次數為 【14】 。
正確答案: 0
1.118 在最壞情況下，堆排序需要比較的次數為 【15】 。
正確答案: O(nlog2n)
1.119 Jackson結構化程式設計方法是英國的son提出的，它是一種面向【16】 的設計方法。
正確答案: 資料結構
1.120 面向物件的模型中，最基本的概念是物件和 【17】 。
正確答案: 類
1.121 類是一個支援整合的抽象資料型別，而物件是類的 【18】 。
正確答案: 例項
1.122 在面向物件的程式設計中，類描述的是具有相似性質的一組 【19】 。
正確答案: 物件
1.123 可以把具有相同屬性的一些不同物件歸類，稱為 【20】 。
正確答案: 物件類
1.124 在面向物件方法中，類之間共享屬性和操作的機制稱為 【21】 。
正確答案: 繼承
1.125 一個類可以從直接或間接的祖先中繼承所有屬性和方法。採用這個方法提高了軟體的【22】 。
正確答案: 可重用性
1.126 在面向物件的設計中，用來請求物件執行某一處理或回答某些資訊的要求稱為【23】。
正確答案: 訊息
1.127 【24】 是一種資訊隱蔽技術，目的在於將物件的使用者和物件的設計者分開。
正確答案: 封裝
1.128 將代數式 Z=x2+y2a+b 轉換成程式設計中的表示式為 【25】。
正確答案: SQR(x^2+y^2)/(a+b)
1.129 在程式設計階段應該採取 【26】 和逐步求精的方法，把一個模組的功能逐步分解，細化為一系列具體的步驟，進而用某種程式設計語言寫成程式。
正確答案: 自頂而下
1.130 軟體危機出現於60年代末，為了解決軟體危機，人們提出了 【27】 的原理來設計軟體，這就是軟體工程誕生的基礎。
正確答案: 軟體工程學
1.131 軟體工程包括3個要素，分別為方法、工具和 【28】 。
正確答案: 過程
1.132 軟體工程研究的內容主要包括： 【29】 技術和軟體工程管理。
正確答案: 軟體開發
1.133 軟體開發環境是全面支援軟體開發全過程的 【30】 集合。
正確答案: 軟體工具
1.134 通常，將軟體產品從提出、實現、使用維護到停止使用退役的過程稱為 【31】。
正確答案: 軟體生命週期
1.135 軟體結構是以 【32】 為基礎而組成的一種控制層次結構。
正確答案: 模組
1.136 軟體設計模組化的目的是 【33】 。
正確答案: 降低複雜性
1.137 耦合和內聚是評價模組獨立性的兩個主要標準，其中 【34】 反映了模組內各成分之間的聯絡。
正確答案: 內聚
1.138 資料模型按不同應用層次分成3種類型，它們是概念資料模型、 【35】 和物理資料模型。
正確答案: 邏輯資料模型
1.139 資料流圖的型別有 【36】 和事務型。
正確答案: 變換型
1.140 為了便於對照檢查，測試用例應由輸入資料和預期的 【37】 兩部分組成。
正確答案: 輸出結果
1.141 常用的黑箱測試有等價分類法、 【38】 、因果圖法和錯誤推測法4種。
正確答案: 邊值分析法
1.142 測試的目的是暴露錯誤，評價程式的可靠性;而 【39】 的目的是發現錯誤的位置並改正錯誤。
正確答案: 除錯
1.143 軟體維護活動包括以下幾類：改正性維護、適應性維護、 【40】 維護和預防性維護。
正確答案: 完善性
1.144 資料庫管理系統常見的資料模型有層次模型、網狀模型和 【41】 3種。
正確答案: 關係模型
1.145 用樹型結構表示實體型別及實體間聯絡的資料模型稱為 【42】 。
正確答案: 層次模型
1.146 在關係模型中，把資料看成一個二維表，每一個二維表稱為一個 【43】 。
正確答案: 關係
1.147 關係操作的特點是 【44】 操作。
正確答案: 集合
1.148 【45】 是從二維表列的方向進行的運算。
正確答案: 關係運算
1.149 一個專案具有一個專案主管，一個專案主管可管理多個專案，則實體"專案主管"與實體"專案"的聯絡屬於【46】 的聯絡。
正確答案: 一對多 或 1:N
1.150 資料庫設計分為以下6個設計階段：需求分析階段、 【47】 、邏輯設計階段、物理設計階段、實施階段、執行和維護階段。
正確答案: 資料庫概念設計階段
1.151 【48】 是資料庫設計的核心。
正確答案: 資料模型
1.152 資料庫系統階段的資料具有較高獨立性，資料獨立性包括物理獨立性和 【49】兩個含義。
正確答案: 邏輯獨立性
1.153 當資料的物理結構(儲存結構、存取方式等)改變時，不影響資料庫的邏輯結構，從而不致引起應用程式的變化，這是指資料的【50】 。
正確答案: 物理獨立性
1.154 關係資料庫的關係演算語言是以 【51】 為基礎的DML語言。
正確答案: 謂詞演算
1.155 關鍵字ASC和DESC分別表示 【52】 的含義。
正確答案: 升序排列和降序排列
1.156 資料庫保護分為：安全性控制、 【53】 、併發性控制和資料的恢復。
正確答案: 完整性控制
1.157 由關係資料庫系統支援的完整性約束是指 【54】 和參照完整性。
正確答案: 實體完整性
