第一章資料結構與演算法
1.1演算法
1.1.1演算法：是指解題方****而完整的描述。
演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。
a演算法的基本特徵：是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，是明確的，此順序將在有限的次數下終止。特徵包括：
（1）可行性；
（2）確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性；
（3）有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止，包括合理的執行時間的含義； （4）擁有足夠的情報。
b演算法的基本要素：一是對資料物件的運算和操作；二是演算法的控制結構。
指令系統：乙個計算機系統能執行的所有指令的集合。 計算機可以執行的基本操作是以指令的形式描述的。
基本的運算和操作包括：算術運算、邏輯運算、關係運算、資料傳輸。
演算法的控制結構：順序結構、選擇結構、迴圈結構。 演算法中各操作之間的執行順序稱為演算法的控制結構。
c演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。
1.1.2演算法複雜度：演算法時間複雜度和演算法空間複雜度。
演算法時間複雜度是指執行演算法所需要的計算工作量。
演算法空間複雜度是指執行這個演算法所需要的記憶體空間。
1.2資料結構的基本概念
1.2.1資料結構研究的三個方面：
（1）資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構；
（2）在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構；
（3）對各種資料結構進行的運算。
資料結構是指反映資料元素之間關係的資料元素集合的表示。
資料處理，是指對資料集合中的各元素以各種方式進行運算，包括插入、刪除、查詢、更改等運算，也包括對資料元素進行分析。
a資料的邏輯結構包含： （1）表示資料元素的資訊；
2）表示各資料元素之間的前後件關係。
資料元素之間的前後件關係是指它們的邏輯關係，而與它們在計算機中的儲存位置無關。
資料的邏輯結構，是指反映資料元素之間邏輯關係的資料結構。
b資料的儲存結構有順序、鏈結、索引等。
1.2.2線性結構（又稱線性表）條件： （1）有且只有乙個根結點；
2）每乙個結點最多有乙個前件，也最多有乙個後件。
非線性結構：不滿足線性結構條件的資料結構。
1.3線性表及其順序儲存結構
1.3.1線性表由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。資料元素**性表中的位置只取決於它們自己的序號，即資料元素之間的相對位置是線性的。
非空線性表的結構特徵：
（1）且只有乙個根結點a1，它無前件；
（2）有且只有乙個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。
1.3.2線性表的順序儲存結構具有以下兩個基本特點：
（1）線性表中所有元素的所佔的儲存空間是連續的；
（2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
ai的儲存位址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
1.3.3順序表的運算：插入、刪除。（詳見17--19頁）
1.4棧和佇列
1.4.1棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。
棧按照「先進後出」（filo）或「後進先出」（lifo）組織資料，棧具有記憶作用。用top指示棧頂位置，用bottom指向棧底。
棧的基本運算：（1）入棧運算是指在棧頂位置插入乙個元素；（2）退棧運算是指取出棧頂元素並賦給乙個指定的變數；（3）讀棧頂元素是將棧頂元素賦給乙個指定的變數，此時棧頂指標無變化。
1.4.2★佇列是指允許在一端（隊尾）進行插入，而在另一端（隊頭）進行刪除的線性表。
允許插入的一端稱為隊尾，尾指標（rear）指向隊尾元素，即尾指標總是指向最後被插入的元素；允許刪除的一端稱為排頭，排頭指標（front）指向排頭元素的前乙個位置。
佇列是「先進行出」（fifo）或「後進後出」（lilo）的線性表。
佇列運算包括（1）入隊運算：在迴圈佇列的隊尾加入乙個新元素；（2）退隊運算：在迴圈佇列的排頭位置推出乙個元素並賦給制定的變數。
迴圈佇列：s=0表示佇列空，s=1且front=rear表示佇列滿 （詳見21--23頁）
1.5線性鍊錶
1.5.1假設資料結構中的每乙個資料結點對應於乙個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
結點由兩部分組成：（1）用於存放資料元素值，稱為資料域；（2）用於存放指標，稱為指標域，用於指向該結點的前乙個或後乙個結點。
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
線性鍊錶，head指向線性鍊錶中第乙個資料元素的結點，稱為頭指標；線性鍊錶最後乙個結點的指標域為空(用null或0表示)，表示鍊錶終止，head=null（或0）稱為空表。如果是兩指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點，這種的線性鍊錶稱為雙向鍊錶。
1.5.2線性鍊錶的基本運算：查詢、插入、刪除。
1.6樹與二叉樹
1.6.1樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。 上端結點是前件，下端結點是後件。
在樹結構中，每乙個結點只有乙個前件，稱為父結點，沒有前件的結點只有乙個，稱為樹的根結點，簡稱樹的根。每乙個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，乙個結點所擁有的後件的個數稱為該結點的度，葉子結點的度為0。所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
1.6.2二叉樹的特點：（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.6.3二叉樹儲存結構採用鏈式儲存結構，對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。
由於二叉樹的儲存結構中每乙個儲存結點有兩個指標域，因此二叉樹的鏈式儲存結構也稱為二叉鍊錶。
1.6.4二叉樹的遍歷是指不重複地訪問二叉樹中的所有結點：
（1）前序遍歷（dlr）：訪問根結點；前序遍歷左子樹；前序遍歷右子樹。
（2）中序遍歷（ldr）：中序遍歷左子樹；訪問根結點；中序遍歷右子樹。
（3）後序遍歷（lrd）：後序遍歷左子樹；後序遍歷右子樹；訪問根結點。
1.7查詢技術
1.7.1順序查詢的使用情況： （1）線性表為無序表；
2）表採用鏈式儲存結構。
1.7.2二分法查詢只適用於順序儲存的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次，而順序查詢需要比較n次。
1.8排序技術
排序是指將乙個無序序列整理成按值非遞減順序排列的有序序列。
1.8.1交換類排序法：（1）氣泡排序法，最壞情況需要比較的次數為n(n-1)/2；（2）快速排序法。
1.8.2插入類排序法：
（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；（2）希爾排序法，最壞情況需要o(n1.5)次比較。 插入排序是指將無序序列中的各元素一次插入到已經有序的線性表中。
1.8.3選擇類排序法：（1）簡單選擇排序法, 最壞情況需要n(n-1)/2次比較；（2）堆排序法，最壞情況需要o(nlog2n)次比較。
第二章程式設計基礎
2.1程式設計方法與風格
當今主導的程式設計風格：清晰第一，效率第二
注重和考慮的因素：（1）源程式文件化 （2）資料說明的方法 （3）語句的結構 （4）輸入和輸出
2.2結構化程式設計
2.2.1結構化程式設計的原則：（1）自頂而下（2）逐步求精（3）模組化（4）限制使用goto語句
2.2.2結構化程式設計的基本結構：（1）順序結構（2）選擇結構（3）重複結構
2.2.3結構化程式設計注意把握如下要素：
（1）使用程式語言中的順序、選擇、迴圈等有限的控制結構表示程式的控制邏輯；
（2）選用的控制結構只准許有乙個入口和乙個出口；
（3）程式語句組成容易識別的塊，每塊只有乙個入口和乙個出口；
（4）複雜結構應該用巢狀的基本控制結構進行組合巢狀來實現；
（5）語言中所沒有的控制結構，應該採用前後一致的方法來模擬；
（6）嚴格控制goto語句的使用。
2.3物件導向的程式設計
2.3.1以simula語言為標誌，物件導向方法的基本要點首次在simula語言中得到了表達和實現。
物件導向方法的優點：（1）與人類習慣的思維方法一致（2）穩定性好（3）可重用性好（4）易於開發大型軟體產品（5）可維護性好
2.3.2a物件可以用來表示客觀世界中的任何實體。
物件導向的程式設計方法中設計的物件是系統中用來描述客觀食物的乙個實體，是構成系統的乙個基本單位，它由一組表示其靜態特徵的屬性和它可執行的一組操作組成。
屬性即物件所包含的資訊，它在設計物件時確定，一般只能通過執行物件的操作來改變。
物件的基本特點：（1）標識唯一性（2）分類性（3）多型性（4）封裝性
b類是具有共同屬性、共同方法的物件的集合。類是物件的抽象，它描述了屬於該物件型別的所有物件的性質，而乙個物件則是其對應類的乙個例項。
c訊息是乙個例項與另乙個例項之間傳遞的資訊，它請求物件執行某一處理或回答某一要求的資訊，它統一了資料流和控制流。
訊息的組成：（1）接收訊息的物件的名稱；（2）訊息識別符號；（3）零個或多個引數。
d繼承是使用已有的類定義作為基礎建立新類的定義技術。
繼承分為單繼承與多重繼承。單繼承是指，乙個類只允許由乙個分類，即類等級為樹形結構。多重繼承是指，乙個類允許有多個父類。
e多型性是指物件根據所接受的訊息而做出動作，同樣的訊息被不同的物件接受時可導致完全不同的行動。
第三章軟體工程基礎
3.1 軟體工程基本概念
3.1.1計算機軟體是包括程式、資料及相關文件的完整集合。
軟體的特點包括：
（1）軟體是一種邏輯實體，而不是物理實體，具有抽象性；
（2）軟體的生產與硬體不同，它沒有明顯的製作過程；
（3）軟體在執行、使用期間不存在磨損、老化問題；
（4）軟體的開發、執行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟體移植的問題；
（5）軟體複雜性高，成本昂貴；
（6）軟體開發涉及諸多的社會因素。
軟體按功能分為應用軟體、系統軟體、支撐軟體（或工具軟體）。
3.1.2軟體危機主要表現在成本、質量、生產率等問題。
軟體工程是應用於計算機軟體的定義、開發和維護的一整套方法、工具、文件、實踐標準和工序。
軟體工程包括3個要素：方法、工具和過程。方法是完成軟體工程專案的技術手段；工具支援軟體的開發、管理、文件生成；過程支援軟體開發的各個環節的控制、管理。
3.1.3軟體工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動，包含4種基本活動：
（1）p（plan）——軟體規格說明；
（2）d(do)——軟體開發；
（3）c(check)——軟體確認；
（4）a(action)——軟體演進。
軟體生命週期：軟體產品從提出、實現、使用維護到停止使用退役的過程。
軟體生命週期三個階段:軟體定義、軟體開發、執行維護，主要活動階段是：
（1）可行性研究與計畫制定； （2）需求分析； （3）軟體設計； （4）軟體實現； （5）軟體測試； （6）執行和維護。
3.1.4軟體工程的目標和與原則：
目標：在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足使用者需求的產品。
基本目標：付出較低的開發成本；達到要求的軟體功能；取得較好的軟體效能；開發軟體易於移植；需要較低的費用；能按時完成開發，及時交付使用。
基本原則：抽象、資訊隱蔽、模組化、區域性化、確定性、一致性、完備性和可驗證性。
軟體工程的理論和技術性研究的內容主要包括：軟體開發技術和軟體工程管理。
軟體開發技術包括：軟體開發方法學、開發過程、開發工具和軟體工程環境。
軟體工程管理包括：軟體管理學、軟體工程經濟學、軟體心理學等內容。
軟體管理學包括人員組織、進度安排、質量保證、配置管理、專案計畫等。
軟體工程經濟學是研究軟體開發中成本的估算、成本效益分析的方法和技術，用經濟學的基本原理來研究軟體工程開發中的經濟效益問題。
二級C公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 演算法 是一組有窮指令集，是解題方 而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所...
二級C 公共基礎知識
黑體為正確答案 1 下列敘述中正確的是 a 資料庫是乙個獨立的系統，不需要作業系統的支援 b 資料庫設計是指設計資料庫管理系統 c 資料庫技術的根本目標是要解決資料共享的問題 d 資料庫系統中，資料的物理結構必須與邏輯結構一致 2 下面敘述正確的是 a 演算法的執行效率與資料的儲存結構無關 b 演算...
二級C語言公共基礎知識總結
公共基礎知識總結 第一章資料結構與演算法 1.1 演算法 演算法 是指解題方 而完整的描述。演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。演算法的基本特徵 是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，是明確的，此順序將在有限的次數下終止。特徵包括 1 可行性 2 確...