此文檔收集于網絡，僅供學習與交流，如有侵權請聯系網站刪除第一章 數據結構與算法1.算法算法:是指解題方案的準確而完整的描述。算法不等于程序，也不等于計算方法，程序的編制不可能優于算法的設計。 算法的基本特征:是一組嚴謹地定義運算順序的規則，每一個規則都是有效的，是明確的，此順序將在有限的次數下終止。特征包括: (1)可行性； (2)確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性； (3)有窮性，算法必須能在有限的時間內做完，即能在執行有限個步驟后終止，包括合理的執行時間的含義； (4)擁有足夠的情報。 算法的基本要素:一是對數據對象的運算和操作；二是算法的控制結構。算法的三種基本控制結構:順序結構、選擇結構、循環結構。算法復雜度包括:算法時間復雜度和算法空間復雜度。算法時間復雜度是指執行算法所需要的計算工作量。算法空間復雜度是指執行這個算法所需要的內存空間。 案例0.算法的有窮性是指 (D)A.算法只能被有限的用戶使用B.算法程序的長度是有限的C.算法程序所處理的數據量是有限的D.算法程序的運行時間是有限的案例1.下列敘述中正確的是 (BG) A.一個算法的時間復雜度大，則其空間復雜度必定小B.算法的時間復雜度與空間復雜度沒有直接關系C.一個算法的空間復雜度大，則其時間復雜度也必定大D.算法的時間復雜度與空間復雜度一定相關E.算法的效率只與問題的規模有關，而與數據的存儲結構無關F.數據的邏輯結構與存儲結構是一一對應的G.算法的時間復雜度是指執行算法所需要的計算工作量2.棧及其基本運算 棧是限定在一端進行插入與刪除運算的線性表。 在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數據的。 棧的基本運算:1) 插入元素稱為入棧運算；2)刪除元素稱為退棧運算；案例2.一個棧的初始狀態為空。先將元素1,2,3,A,B,C依次入棧，然后再依次出棧，則元素出棧的順序是_ _ (C,B,A,3,2,1)3.隊列及其基本運算 隊列是指允許在一端(隊尾)進入插入，而在另一端(隊頭)進行刪除的線性表。尾指針(Rear)指向隊尾元素，頭指針(front)指向排頭元素的前一個位置(隊頭)。 隊列是“先進先出”或“后進后出”的線性表。 隊列運算包括:1)入隊運算:從隊尾插入一個元素；2)退隊運算:從隊頭刪除一個元素。案例3.下列與隊列結構有關聯的是 (A)A.先到先服務的作業調度B.函數的遞歸調用C.數組元素的引用D.多重循環的執行4.循環隊列及其運算:所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。 循環隊列中元素的個數=rear-front。 案例4.下列敘述中正確的是 (B)A.循環隊列有隊頭和隊尾兩個指針，因此循環隊列是非線性結構B.循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定C.在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況D.在循環隊列中，只需要隊頭指針就能反映隊列中元素的動態變化情況案例5.設循環隊列的存儲空間為Q(1:35)，初始狀態為front=rear=35.現經過一系列入隊與退隊運算后， front=15, rear=15,則循環隊列中的元素個數為 (A)A.0或35 B.15C.20D.16解析:循環隊列中的元素個數的計算方法是:隊尾-隊頭1.如果大于0，rear-front 即為元素的個數。2.如果小于0，rear-front+空間容量 即為元素個數。3.如果等于0，元素個數為0或空間容量。5.二叉樹及其基本性質 二叉樹是一種非線性結構，它具有以下兩個特點:1)非空二叉樹只有一個根結點;2)每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。 根據二叉樹的概念可知，二叉樹的度可以為0(葉結點)、1(只有一棵子 樹)或2(有2棵子樹)。 二叉樹考點1:在任意一棵二叉樹中，度數為0的結點(即葉子結點)總比度為2的結點多一個。葉子數(度為0)=度為2結點數+1二叉樹考點2: 二叉樹的深度即二叉樹的層次數二叉樹考點3:總結點數=度為2的結點數+度為1的結點數+度為0的結點數(葉子)案例6.某二叉樹共有7個結點，其中葉子結點只有1個，則該二叉樹的深度為(假設根結點在第1層) _ 。 (7)案例7.一棵二叉樹共有25個結點，其中5個是葉子結點，則度為1的結點數為_ _ 。 (16)_解析:葉子結點數=度為2的結點數+1 5 = ？ +1求得度為2的結點數為4 總結點數=度為2的結點數+度為1的結點數+度為0的結點數(葉子) 25 =4 + ？ +5求得度為1的結點數為16二叉樹考點4:二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種: (1)前序遍歷:若二叉樹為空，則結束返回。否則:首先訪問根結點，然后遍歷 左子樹，最后遍歷右子樹。 (2)中序遍歷:若二叉樹為空，則結束返回。否則:首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。 (3)后序遍歷:若二叉樹為空，則結束返回。否則:首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。案例8. 對下列二叉樹進行前序遍歷的結果為_ _ (ABDYECFXZ)6.線性表由一組數據元素構成，數據元素的位置只取決于自己的序號，元素之間的相對位置是線性的稱為線性表。線性表是由n(n0)個數據元素組成的一個有限序列，表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數據元素的個數稱為線性表的長度。線性表可以為空表。 線性表是一種存儲結構，它的存儲方式:順序和鏈式。 線性表的順序存儲結構具有兩個基本特點:(1)線性表中所有元素所占的存儲空間是連續的；(2)線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。 由此可以看出，在線性表的順序存儲結構中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定第i個結點的存儲地址。 順序表的插入、刪除運算線性表的鏈式存儲結構(線性鏈表) 數據結構中的每一個結點對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。 結點由兩部分組成:(1)用于存儲數據元素值，稱為數據域；(2)用于存放指針，稱為指針域，用于指向前一個或后一個結點。 在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。 鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。 線性結構條件: (1)有且只有一個根結點； (2)每一個結點最多有一個前件，也最多有一個后件。 非線性結構:不滿足線性結構條件的數據結構。 案例9.下列敘述中正確的是 (A)A.循環隊列是隊列的一種順序存儲結構B.循環隊列是非線性結構 C.循環隊列是一種邏輯結構 D.循環隊列是隊列的一種鏈式存儲結構解析:常見的線性結構有:隊列、棧。非線性結構有:樹、二叉樹 案例10.下列敘述中正確的是 (CE)A.線性表鏈式存儲結構與順序存儲結構所需要的存儲空間是相同的 (不相同)B.線性表鏈式存儲結構所需要的存儲空間一般要少于順序存儲結構 (多于)C.線性表鏈式存儲結構所需要的存儲空間一般要多于順序存儲結構D.線性表鏈式存儲結構與順序存儲結構的存儲空間都是連續的E.線性表鏈式存儲結構的存儲空間可以是連續的，也可以是不連續的7.排序排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調整為有序記錄序列的一種操作。冒泡排序、快速排序、直接插入排序:假設線性表的長度為n,則在最壞情況下，需要比較的次數為n(n-1)/2堆排序:在最壞情況下，需要比較的次數為nlog2n8.順序查找和二分查找順序查找又稱為順序搜索。順序查找一般是指在線性表中查找指定的元素下面兩種情況1.如果線性表為無序表(即表中元素排序是無序的)，則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找2.即使是有序線性表，如果采用鏈式存儲結構，也只能用于順序查找二分查找只適用于順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排序(即從小到大，但允許相鄰元素值相等)。當有序線性表為順序存儲時才能采用二分查找，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次 ，而順序查找需要比較n次。案例11.對長度為n的線性表排序，在最壞情況下，比較次數不是n(n-1)/2的排序方法是 (C)A.快速排序 B.冒泡排序C.堆排序 D.直接插入排序案例12.在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數是 (A)A.O(log2n) B.O(nlog2n)C.O(n2)D.O(n)案例13.對長度為10的線性表進行冒泡排序，最壞情況下需要比較的次(B)A.9 B.45C.90D.10第二章 軟件工程基本概念1.計算機軟件是包括程序、數據及相關文檔的完整集合。 軟件按功能分為應用軟件、系統軟件、支撐軟件(或工具軟件)。 軟件危機主要表現在成本、質量、生產率等問題。 軟件周期:軟件產品從提出、實現、使用維護到停止使用退役的過程。 軟件生命周期三個階段:軟件定義、軟件開發、運行維護，主要活動階段是: (1)可行性研究與計劃制定；(2)需求分析； (3)軟件設計；(4)軟件實現；(5)軟件測試；(6)運行和維護。 衡量軟件模塊獨立性使用耦合性和內聚性兩個定性的度量標準。 在程序結構中各模塊的內聚性越強，則耦合性越弱。優秀軟件應高內聚，低耦合。 內聚性是指一個模塊內部各個元素間彼此結合的緊密程度耦合性是指模塊間相互連接的緊密程度2.軟件測試 軟件測試的目的:發現錯誤而執行程序的過程。 軟件測試方法:靜態測試和動態測試。 靜態測試包括代碼檢查、靜態結構分析、代碼質量度量。不實際運行軟件，主要通過人工進行。 動態測試:是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法。 白盒測試:在程序內部進行，主要用于完成軟件內部CAO作的驗證。主要方法有邏輯覆蓋、基本基路徑測試。 黑盒測試:在黑盒測試方法中，設計測試用例的主要根據是程序外部功能。主要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。 軟件測試過程一般按4個步驟進行:單元測試、集成測試、驗收測試(確認測試)和系統測試。 3.程序的調試 程序調試的任務是診斷和改正程序中的錯誤，主要在開發階段進行。 案例14.軟件詳細設計產生的圖如下: (C)該圖是A.PAD圖B.E-R圖C.程序流程圖D.N-S圖第三章 數據庫設計基礎1.數據庫系統的基本概念 數據庫管理系統:一種系統軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護和數據服務等，是數據庫的核心。 (1)數據定義語言:負責數據的模式定義與數據的物理存取構建； (2)數據操縱語言:負責數據的操縱，如查詢與增、刪、改等； (3)數據控制語言:負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等。 數據語言按其使用方式具有兩種結構形式:交互式命令(又稱自含型或自主型語言)宿主型語言(一般可嵌入某些宿主語言中)。 數據庫管理員:對數據庫進行規劃、設計、維護、監視等的專業管理人員。 數據庫系統:由數據庫(數據)、數據庫管理系統(軟件)、數據庫管理員(人員)、硬件平臺(硬件)、軟件平臺(軟件)五個部分構成的運行實體。 數據庫應用系統:由數據庫系統、應用軟件及應用界面三者組成。文件系統階段:提供了簡單的數據共享與數據管理能力，但是它無法提供完整的、統一的、管理和數據共享的能力。層次數據庫與網狀數據庫系統階段:為統一與共享數據提供了有力支撐。 關系數據庫系統階段 數據庫系統的基本特點:數據的集成性 、數據的高共享性與低冗余性 、數據獨立性(物理獨立性與邏輯獨立性)、數據統一管理與控制。 2.數據庫系統的三級模式: (1)概念模式:數據庫系統中全局數據邏輯結構的描述，全體用戶公共數據視圖； (2)外模式:也稱子模式與用戶模式。是用戶的數據視圖，也就是用戶所見到的數據模式； (3)內模式:又稱物理模式，它給出了數據庫物理存儲結構與物理存取方法。 數據模型 數據模型的概念:是數據特征的抽象，從抽象層次上描述了系統的靜態特征、動態行為和約束條件，為數據庫系統的信息表與操作提供一個抽象的框架。描述了數據結構、數據操作及數據約束。 E-R模型的基本概念 (1)實體:現實世界中的事物； (2)屬性:事物的特性； (3)聯系:現實世界中事物間的關系。實體集的關系有一對一、一對多、多對多的聯系。 案例15.若實體A和B是一對多的聯系，實體B和C是一對一的聯系，則實體A和C的聯系是_。一間宿舍可住多個學生，則實體宿舍和學生之間的聯系是_。 (一對多) (一對多)E-R模型三個基本概念之間的聯接關系:實體是概念世界中的基本單位，屬性有屬性域，每個實體可取屬性域內的值。一個實體的所有屬性值叫元組。 E-R模型的圖示法:(1)實體集表示法； (2)屬性表法； (3)聯系表示法。 在二維表中凡能唯一標識元組的最小屬性稱為鍵或碼。從所有侯選健中選取一個作為用戶使用的鍵稱主鍵。表A中的某屬性是某表B的鍵，則稱該屬性集為A的外鍵或外碼。 關系中的數據約束: (1)實體完整性約束:約束關系的主鍵中屬性值不能為空值； (2)參照完全性約束:是關系之間的基本約束； (3)用戶定義的完整性約束:它反映了具體應用中數據的語義要求。 3.關系代數 關系數據庫系統的特點之一是它建立在數據理論的基礎之上，有很多數據理論可以表示關系模型的數據操作，其中最為著名的是關系代數與關系演算。 關系模型的基本運算: (1) 插入 (2)刪除 (3)修改 (4)查詢(包括投影、選擇、笛卡爾積運算) 解析: -R1 選擇 R2 ABABCa12b21Ca12 b21c31ABa1b2c3R1 投影 R2 ABCa12 b21c31案例16.有三個關系R、S和T如下: (A)則由關系R和S得到關系T的操作是A.自然連接B.并C.投影D.交案例17.有三個關系R,S 和T如下: (A)則由關系R和S得到關系T的操作是A.并B.交C.投影D.選擇案例18.有三個關系R,S 和T如下: (D)則由關系R和S得到關系T的操作是A.選擇B.交C.并D.差案例19.有兩個關系R和S如下 (A)則由關系R 得到關系S的操作是A.選擇B.并C.自然連接D.投影案例20.有兩個關系R,S如下: (C)由關系R通過運算得到關系S,則所使用的運算為A.連接B.插入C.投影D.選擇第四章 程序設計基礎1.面向對象的程序設計和結構化程序設計面向對象方法的主要優點: (1)與人類習慣的思維方法一致； (2)穩定性好； (3)可重用(注釋1) 性好； (4)易于開發大型軟件產品； (5)可維護性好。 對象是面向對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象是實體的抽象。面向對象的程序設計方法中的對象是系統中用來描述客觀事物的一個實體，是構成系統的一個