C語言公共基礎(chǔ)知識知識點

第一章數(shù)據(jù)結(jié)構(gòu)及算法.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報。.算法的有窮性是指算法程序的運行時間是有限的。.算法的時間困難度:執(zhí)行算法所須要的計算工作量(基本運算次數(shù))。算法的空間困難度:這個算法所須要的內(nèi)存空間。兩者之間沒有必定干脆的聯(lián)系.程序執(zhí)行的效率及數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、程序的限制結(jié)構(gòu)、ffi處理的數(shù)據(jù)量等有關(guān)。.線性結(jié)構(gòu)的兩大條件：有且只有一個根節(jié)點；每一個結(jié)點最多只有一個前件，也最多有一個后件。.線性表的依次存儲結(jié)構(gòu)具備如下兩個基本特征:(1)線性表中的全部元素所占的存儲空間是連續(xù)的;(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯依次依次存放的。.棧是先進后出的線性表。.隊列是先進先出的線性表。.棧和隊列都是線性結(jié)構(gòu)。.棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最終才能被刪除的元素。.循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同確定。.樹是簡潔的非線性結(jié)構(gòu)，所以二叉樹作為樹的一種也是一種非線性結(jié)構(gòu)。.循環(huán)隊列中的元素個數(shù)隨隊頭指針及隊尾指針的變更而動態(tài)變更。.由于入隊時尾指針向前追逐頭指針，出隊時頭指針向前追逐尾指針，故隊空和隊滿時,頭尾指針均相等。.在棧中，棧底指針不變,棧中元素隨棧頂指針的變更而動態(tài)變更。.循環(huán)隊列是隊列的一種依次存儲結(jié)構(gòu)。.循環(huán)鏈表和雙向鏈表都是線性結(jié)構(gòu)。.線性鏈表中數(shù)據(jù)的插入和刪除都不須要移動表中的元素,只需變更結(jié)點的指針域即可。.線性鏈表中的各數(shù)據(jù)結(jié)點的存儲空間可以不連續(xù),各數(shù)據(jù)元素的存儲依次及邏輯依次可以不一樣。.鏈?zhǔn)酱鎯Y(jié)構(gòu)既可以針對線性結(jié)構(gòu)也可以針對非線性結(jié)構(gòu)。.依次存儲結(jié)構(gòu)的存儲確定是連續(xù)的,鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不愿定是連續(xù)的。.線性表(線性結(jié)構(gòu))的鏈?zhǔn)酱鎯Y(jié)構(gòu)所須要的存儲空間一般要多于依次存儲結(jié)構(gòu)。.棧支持子程序調(diào)用。棧是一種只能在一端進行插入或刪除的線性表，在主程序調(diào)用子函數(shù)時要首先保存主程序當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子程序，最終把子程序的執(zhí)行結(jié)果返回到主程序中調(diào)用子程序的位置，接著向下執(zhí)行。.在隨意一棵二叉樹中，度為0的葉子節(jié)點總是比度為2的節(jié)點多一個。.滿二叉樹是指這樣的一種二叉樹：除最終一層外，每一層上的全部結(jié)點都有兩個子結(jié)點。26.完全二叉樹是指這樣的二叉樹：除最終一層外，每一層上的結(jié)點數(shù)均達到最大值；在最終一層上只缺少右邊的若干結(jié)點。2312)(13)(14)(15,4) (58)(9)(10)(1110)11滿二叉樹完全二叉樹2312)(13)(14)(15,4) (58)(9)(10)(1110)11滿二叉樹27.二叉樹的遍歷：.前序遍歷：①訪問根結(jié)點；②前序遍歷左子樹;③前序遍歷右子樹.中序遍歷：①中序遍歷左子樹;②訪問根結(jié)點；③中序遍歷右子樹.后序遍歷：①后序遍歷左子樹;②后序遍歷右子樹;③訪問根結(jié)點.一顆二叉樹的前序遍歷序列為ABDGCFK,中序遍歷序為DGBAFCK,則結(jié)點的后序遍歷序序列為什么？后序應(yīng)當(dāng)是GDBFKCA。中序：依次為左根右。并且，在遍歷左、右子樹時,照舊先遍歷左子樹，然后訪問根結(jié)點，最終遍歷右子樹。.依次查找：最好狀況：1次；最壞狀況：n次；須要比較n/2次，困難度為0(n)o二分法查找：最壞狀況：log2n次；困難度為.排序中:最壞狀況冒泡排序，簡潔插入排序，簡潔選擇排序，選擇排序的最壞狀況時間都為而堆排序的最壞狀況時間為0(〃］。用〃.)冒泡排序，簡潔插入排序，簡潔選擇排序，選擇排序的最壞狀況比較次數(shù)都為n(n-l)/2次而堆排序的最壞狀況次數(shù)為nlog2n次其次章程序設(shè)計基礎(chǔ).結(jié)構(gòu)化程序設(shè)計的基本原則：自頂而下；逐步求精；模塊化；限制got。語句運用。.結(jié)構(gòu)化程序所要求的基本結(jié)構(gòu)：依次結(jié)構(gòu)；選擇（分支）結(jié)構(gòu)；重復(fù)（循環(huán)）結(jié)構(gòu)。.對象的基本特點：標(biāo)識唯一性；分類性；多態(tài)性；封裝性；模塊獨立性好。.對象之間進行通信的構(gòu)造叫做消息。.對象的多態(tài)性是指同一個操作可以是不同對象的行為,導(dǎo)致完全不同的行為。.對象不愿定必需有繼承性。.繼承是面對對象的方法的一個主要特征。.繼承是指類之間共享屬性和操作的機制。第三章軟件工程基礎(chǔ)L軟件指的是計算機系統(tǒng)中及硬件相互依靠的另一部分，包括程序、數(shù)據(jù)和有關(guān)的文檔。.軟件生命周期是指軟件產(chǎn)品從提出、實現(xiàn)、運用維護到停止運用退役的過程。.軟件的生命周期有三大階段：.軟件定義期：問題定義;可行性探討;需求分析。.軟件開發(fā)期：軟件設(shè)計（概要設(shè)計和詳細設(shè)計）；軟件實現(xiàn);軟件測試。.運行維護期：運行和維護。.需求分析階段的主要工作：需求獲得;需求分析;編寫需求規(guī)格說明書;需求評審。.需求分析階段（結(jié)構(gòu)化分析方法）常用的工具：數(shù)據(jù)流圖（DFD）；數(shù)據(jù)字典（DD）；判定表;判定樹;.數(shù)據(jù)字典（DD）是結(jié)構(gòu)化分析的核心。.軟件需求規(guī)格說明書有以下幾個方面的作用：①便于用戶、開發(fā)人員進行理解和溝通；②反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)；③作為確認測試和驗收的依據(jù)。.軟件設(shè)計中常用的工具：①圖形工具：程序流程圖;N-S圖;PAD圖;HIPOo②表格工具：判定表。③語言工具：PDL（偽碼）。.在數(shù)據(jù)流圖（DFD）中,用標(biāo)出名字的箭頭表示數(shù)據(jù)流。在程序流程圖中,用標(biāo)出名字的箭頭表示限制流。.軟件測試是為了發(fā)覺錯誤而執(zhí)行程序的過程,測試要以查找錯誤為中心，而不是為了演示軟件的正確功能。不是為了評估軟件或改正錯誤。n.軟件測試方法：.靜態(tài)測試和動態(tài)測試；.黑盒測試和白盒測試；①白盒測試：邏輯覆蓋測試（語句，路徑，判定，條件覆蓋）;基本路徑測試。②黑盒測試：等價類劃分法;邊界值分析法;錯誤推想法。.白盒測試又稱為結(jié)構(gòu)測試或者邏輯驅(qū)動測試。（留意內(nèi)部邏輯結(jié)構(gòu)和信息）.黑盒測試又稱功能測試或者數(shù)據(jù)驅(qū)動測試。（留意測試軟件的功能）.軟件測試的實施過程：單元測試;集成測試;確認（驗收）測試;系統(tǒng)測試。.程序調(diào)試的目的是在測試發(fā)覺錯誤后解除錯誤的過程。.軟件調(diào)試的方法：強行排錯法;回溯法;緣由解除法（二分法；歸納法；演繹法）。第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)1.數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫的機構(gòu),它是一種系統(tǒng)軟件，負責(zé)數(shù)據(jù)庫中數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、限制及愛惜和數(shù)據(jù)服務(wù)等。是一種在操作系統(tǒng)之上的系統(tǒng)軟件。送據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心。.數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)語言：①數(shù)據(jù)定義語言：負責(zé)數(shù)據(jù)的模式定義及數(shù)據(jù)的物理存取構(gòu)建。②數(shù)據(jù)操縱語言：負責(zé)數(shù)據(jù)的操縱，包括查詢及增，冊，改等操作。③數(shù)據(jù)限制語言：負責(zé)數(shù)據(jù)的完整性。平安性的定義及檢查以及并發(fā)限制，故障復(fù)原等功能。.數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫,數(shù)據(jù)庫管理系統(tǒng),數(shù)據(jù)庫管理員,硬件,軟件平臺組成。.數(shù)據(jù)庫系統(tǒng)的特點：數(shù)據(jù)集成性;數(shù)據(jù)高共享低冗雜;數(shù)據(jù)獨立性高;數(shù)據(jù)統(tǒng)一管理和限制（平安性，完整性，并發(fā)限制）。.數(shù)據(jù)庫應(yīng)用系統(tǒng)中的核心問題是數(shù)據(jù)庫的設(shè)計。.數(shù)據(jù)庫系統(tǒng)的三級模式結(jié)構(gòu)：①概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述,全體用戶公共數(shù)據(jù)視圖。②外模式：也稱子模式或用戶模式,它是用戶的數(shù)據(jù)視圖,給出了每個用戶的局部數(shù)據(jù)描述。③內(nèi)模式：又稱物理模式,它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)及物理存取方法。.一個數(shù)據(jù)庫只有一個概念模式和一個內(nèi)模式,有多個外模式。.數(shù)據(jù)庫系統(tǒng)的兩級映射：外模式/概念模式的映射和概念模式/內(nèi)模式的映射。.當(dāng)概念模式變更時，只需變更外模式/概念模式的映射,不需變更外模式,保證了數(shù)據(jù)的邏輯獨立性。當(dāng)內(nèi)模式變更時，只需變更概念模式/內(nèi)模式的映射,不需變更概念模式,保證了數(shù)據(jù)的物理獨立性。.E-R模型的基本概念：實體；W;聯(lián)系。.E-R圖中：矩形表示實體集,橢圓形表示屬性,菱形表示聯(lián)系。.層次模型:用樹形結(jié)構(gòu)表示實體及其之間聯(lián)系的模型。.網(wǎng)狀模型:用網(wǎng)狀結(jié)構(gòu)表示實體機器之間聯(lián)系的模型。.關(guān)系模型:用二維表來表示關(guān)系。.二維表中的一列稱為屬性;一行稱為元組。.有表示公司和職員及工作的三張表，職員可在多家公司兼職。其中公司C（公司號，公司名，地址，注冊資本，法人代表，員工數(shù)），職員S（職員號，姓名，性別，年齡，學(xué)歷），工作W（公司號，職員號，工資），則表W的鍵（碼）為A）公司號，職員號B）職員號，工資0職員號D）公司號，職員號，工資參考答案：A【解析】由于職員可以再多加公司兼職，表W的鍵（碼）應(yīng)為公司關(guān)系和職員關(guān)系的主碼，即公司號和職員號。.投影：從關(guān)系模式中指定若干個屬拄組成的新的關(guān)系。也就是垂直分解。.選擇：從關(guān)系中找出滿足給定條件的無組的操作。也就是水平抽取。.自然連接：一種特殊的等值連接，它要求兩個關(guān)系中進行比較的重量必需是相同的屬性組，并且在結(jié)果中把重復(fù)的屬性列去掉。而等值連接并不去掉重復(fù)的屬性列。.數(shù)據(jù)庫設(shè)計的步驟：1、需求分析階段：了解用戶的數(shù)據(jù)需求、處理需求、平安性及完整性要求；2、概念設(shè)計階段：通過數(shù)據(jù)抽象，設(shè)計系統(tǒng)概念模型，一般為E-R模型;3、邏輯設(shè)計階段：設(shè)計系統(tǒng)的模式和外模式，將E-R圖向關(guān)系數(shù)據(jù)模型轉(zhuǎn)換;4、物理設(shè)計階段：設(shè)計數(shù)據(jù)的存儲結(jié)構(gòu)和存取方法，如索引的設(shè)計；5、系統(tǒng)實施：組織數(shù)據(jù)入庫、編制應(yīng)用程序、試運行；6、運行維護：系統(tǒng)投入運行，長期的維護工作。22.在需求分析階段建立數(shù)據(jù)字典。上機練習(xí)中的題目：1.SQL語言又稱為結(jié)構(gòu)化