C語言公共基礎(chǔ)知識知識點(diǎn)自己整理

1、第一章 數(shù)據(jù)結(jié)構(gòu)與算法1.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報(bào)。2.算法的有窮性是指算法程序的運(yùn)行時間是有限的。3.算法的時間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量（基本運(yùn)算次數(shù)）。 算法的空間復(fù)雜度：這個算法所需要的內(nèi)存空間。兩者之間沒有必然直接的聯(lián)系4. 程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、程序的控制結(jié)構(gòu)、所處理的數(shù)據(jù)量等有關(guān)。5.線性結(jié)構(gòu)的兩大條件：有且只有一個根節(jié)點(diǎn)；每一個結(jié)點(diǎn)最多只有一個前件，也最多有一個后件。6. 線性表的順序存儲結(jié)構(gòu)具備如下兩個基本特征：（）線性表中的所有元素所占的存儲空間是連續(xù)的；（）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的

2、。7. 棧是先進(jìn)后出的線性表。8. 隊(duì)列是先進(jìn)先出的線性表。9.棧和隊(duì)列都是線性結(jié)構(gòu)。10. 棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。11. 循環(huán)隊(duì)列中元素的個數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定。12. 樹是簡單的非線性結(jié)構(gòu)，所以二叉樹作為樹的一種也是一種非線性結(jié)構(gòu)。13. 循環(huán)隊(duì)列中的元素個數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動態(tài)變化。14. 由于入隊(duì)時尾指針向前追趕頭指針，出隊(duì)時頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時，頭尾指針均相等。15. 在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化。16. 循環(huán)隊(duì)列是隊(duì)列的一種

3、順序存儲結(jié)構(gòu)。17. 循環(huán)鏈表和雙向鏈表都是線性結(jié)構(gòu)。18. 線性鏈表中數(shù)據(jù)的插入和刪除都不需要移動表中的元素，只需改變結(jié)點(diǎn)的指針域即可。19. 線性鏈表中的各數(shù)據(jù)結(jié)點(diǎn)的存儲空間可以不連續(xù)，各數(shù)據(jù)元素的存儲順序與邏輯順序可以不一致。20. 鏈?zhǔn)酱鎯Y(jié)構(gòu)既可以針對線性結(jié)構(gòu)也可以針對非線性結(jié)構(gòu)。21. 順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的。22. 線性表（線性結(jié)構(gòu)）的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)。23. 棧支持子程序調(diào)用。棧是一種只能在一端進(jìn)行插入或刪除的線性表，在主程序調(diào)用子函數(shù)時要首先保存主程序當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子程序，最終把子程序的

4、執(zhí)行結(jié)果返回到主程序中調(diào)用子程序的位置，繼續(xù)向下執(zhí)行。24. 在任意一棵二叉樹中，度為0的葉子節(jié)點(diǎn)總是比度為2的節(jié)點(diǎn)多一個。25. 滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。26. 完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。27. 二叉樹的遍歷：1前序遍歷：訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹 2中序遍歷：中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹 3后序遍歷：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)28. 一顆二叉樹的前序遍歷序列為ABDGCFK，中序遍歷序?yàn)镈GBAFCK，則結(jié)點(diǎn)的后

5、序遍歷序序列為什么？后序應(yīng)該是GDBFKCA。中序：順序?yàn)樽蟾摇２⑶?，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。29.順序查找：最好情況：1次；最壞情況：n次；需要比較n/2次，復(fù)雜度為O(n)。 二分法查找：最壞情況：次；復(fù)雜度為30.排序中：最壞情況冒泡排序，簡單插入排序，簡單選擇排序，選擇排序的最壞情況時間都為而堆排序的最壞情況時間為冒泡排序，簡單插入排序，簡單選擇排序，選擇排序的最壞情況比較次數(shù)都為n(n-1)/2次而堆排序的最壞情況次數(shù)為次第二章 程序設(shè)計(jì)基礎(chǔ)1.結(jié)構(gòu)化程序設(shè)計(jì)的基本原則：自頂而下；逐步求精；模塊化；限制goto語句使用。2.結(jié)構(gòu)化程序所

6、要求的基本結(jié)構(gòu)：順序結(jié)構(gòu)；選擇（分支）結(jié)構(gòu)；重復(fù)（循環(huán)）結(jié)構(gòu)。3.對象的基本特點(diǎn)：標(biāo)識唯一性；分類性；多態(tài)性；封裝性；模塊獨(dú)立性好。4. 對象之間進(jìn)行通信的構(gòu)造叫做消息。5.對象的多態(tài)性是指同一個操作可以是不同對象的行為，導(dǎo)致完全不同的行為。6. 對象不一定必須有繼承性。7. 繼承是面向?qū)ο蟮姆椒ǖ囊粋€主要特征。8. 繼承是指類之間共享屬性和操作的機(jī)制。第三章 軟件工程基礎(chǔ)1. 軟件指的是計(jì)算機(jī)系統(tǒng)中與硬件相互依賴的另一部分，包括程序、數(shù)據(jù)和有關(guān)的文檔。2. 軟件生命周期是指軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。3.軟件的生命周期有三大階段： 一軟件定義期：問題定義；可行性研究；

7、需求分析。 二軟件開發(fā)期：軟件設(shè)計(jì)（概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)）；軟件實(shí)現(xiàn)；軟件測試。 三運(yùn)行維護(hù)期：運(yùn)行和維護(hù)。4.需求分析階段的主要工作：需求獲?。恍枨蠓治?；編寫需求規(guī)格說明書；需求評審。5.需求分析階段（結(jié)構(gòu)化分析方法）常用的工具：數(shù)據(jù)流圖（DFD）；數(shù)據(jù)字典（DD）；判定表；判定樹；6. 數(shù)據(jù)字典（DD）是結(jié)構(gòu)化分析的核心。7. 軟件需求規(guī)格說明書有以下幾個方面的作用：便于用戶、開發(fā)人員進(jìn)行理解和交流； 反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)；作為確認(rèn)測試和驗(yàn)收的依據(jù)。8.軟件設(shè)計(jì)中常用的工具：圖形工具：程序流程圖；N-S圖；PAD圖；HIPO。 表格工具：判定表。語言工具：P

8、DL（偽碼）。9. 在數(shù)據(jù)流圖（DFD）中，用標(biāo)有名字的箭頭表示數(shù)據(jù)流。在程序流程圖中，用標(biāo)有名字的箭頭表示控制流。10. 軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程，測試要以查找錯誤為中心，而不是為了演示軟件的正確功能。不是為了評估軟件或改正錯誤。11.軟件測試方法： 一靜態(tài)測試和動態(tài)測試； 二黑盒測試和白盒測試； 白盒測試：邏輯覆蓋測試（語句，路徑，判定，條件覆蓋）；基本路徑測試。 黑盒測試：等價類劃分法；邊界值分析法；錯誤推測法。12.白盒測試又稱為結(jié)構(gòu)測試或者邏輯驅(qū)動測試。（注重內(nèi)部邏輯結(jié)構(gòu)和信息）13.黑盒測試又稱功能測試或者數(shù)據(jù)驅(qū)動測試。（注重測試軟件的功能）14.軟件測試的實(shí)施過程：

9、單元測試；集成測試；確認(rèn)（驗(yàn)收）測試；系統(tǒng)測試。15.程序調(diào)試的目的是在測試發(fā)現(xiàn)錯誤后排除錯誤的過程。16.軟件調(diào)試的方法：強(qiáng)行排錯法；回溯法；原因排除法（二分法；歸納法；演繹法）。第四章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)1. 數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫的機(jī)構(gòu)，它是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。是一種在操作系統(tǒng)之上的系統(tǒng)軟件。2.數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心。3.數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)語言：數(shù)據(jù)定義語言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建。 數(shù)據(jù)操縱語言：負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢與增，刪，改等操作。數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)的完整性。安全性的定義與檢查以及并發(fā)控制

10、，故障恢復(fù)等功能。4.數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫管理員，硬件，軟件平臺組成。5.數(shù)據(jù)庫系統(tǒng)的特點(diǎn)：數(shù)據(jù)集成性；數(shù)據(jù)高共享低冗雜；數(shù)據(jù)獨(dú)立性高；數(shù)據(jù)統(tǒng)一管理和控制（安全性，完整性，并發(fā)控制）。6.數(shù)據(jù)庫應(yīng)用系統(tǒng)中的核心問題是數(shù)據(jù)庫的設(shè)計(jì)。7.數(shù)據(jù)庫系統(tǒng)的三級模式結(jié)構(gòu)：概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖。 外模式：也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，給出了每個用戶的局部數(shù)據(jù)描述。內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。8.一個數(shù)據(jù)庫只有一個概念模式和一個內(nèi)模式，有多個外模式。9.數(shù)據(jù)庫系統(tǒng)的兩級映射：外模式/概念模式的映

11、射和概念模式/內(nèi)模式的映射。10.當(dāng)概念模式改變時，只需改變外模式/概念模式的映射，不需改變外模式，保證了數(shù)據(jù)的邏輯獨(dú)立性。 當(dāng)內(nèi)模式改變時，只需改變概念模式/內(nèi)模式的映射，不需改變概念模式，保證了數(shù)據(jù)的物理獨(dú)立性。11.E-R模型的基本概念：實(shí)體；屬性；聯(lián)系。12.E-R圖中：矩形表示實(shí)體集，橢圓形表示屬性，菱形表示聯(lián)系。13.層次模型：用樹形結(jié)構(gòu)表示實(shí)體及其之間聯(lián)系的模型。14.網(wǎng)狀模型：用網(wǎng)狀結(jié)構(gòu)表示實(shí)體機(jī)器之間聯(lián)系的模型。15.關(guān)系模型：用二維表來表示關(guān)系。16.二維表中的一列稱為屬性；一行稱為元組。17. 有表示公司和職員及工作的三張表，職員可在多家公司兼職。其中公司C（公司號，公司

12、名，地址，注冊資本，法人代表，員工數(shù)），職員S（職員號，姓名，性別，年齡，學(xué)歷），工作W（公司號，職員號，工資），則表W的鍵（碼）為A) 公司號，職員號B) 職員號，工資C) 職員號D) 公司號，職員號，工資 參考答案：A【解析】由于職員可以再多加公司兼職，表W的鍵（碼）應(yīng)為公司關(guān)系和職員關(guān)系的主碼，即公司號和職員號。18.投影：從關(guān)系模式中指定若干個屬性組成的新的關(guān)系。也就是垂直分解。19.選擇：從關(guān)系中找出滿足給定條件的元組的操作。也就是水平抽取。20.自然連接：一種特殊的等值連接，它要求兩個關(guān)系中進(jìn)行比較的分量必須是相同的屬性組，并且在結(jié)果中把重復(fù)的屬性列去掉。而等值連接并不去掉重復(fù)的屬性列。21數(shù)據(jù)庫設(shè)計(jì)的步驟： 1、需求分析階段：了解用戶的數(shù)據(jù)需求、處理需求、安全性及完整性要求；2、概念設(shè)計(jì)階段：通過數(shù)據(jù)抽象，設(shè)計(jì)系統(tǒng)概念模型，一般為E-R模型；3、邏輯設(shè)計(jì)階段：設(shè)計(jì)系統(tǒng)的模式和外模式，將E-R圖向關(guān)系數(shù)據(jù)模型轉(zhuǎn)換；4、物理設(shè)計(jì)階段：設(shè)計(jì)數(shù)據(jù)的存儲結(jié)構(gòu)和存取方法，如索引的設(shè)計(jì)； 5、系統(tǒng)實(shí)施：組織數(shù)據(jù)入庫、編制應(yīng)用程序、試運(yùn)行；6、運(yùn)行維護(hù)：系統(tǒng)投入運(yùn)行，長期的維護(hù)工作。22.在需求分析階段建立數(shù)據(jù)字典。上機(jī)練習(xí)中的題目：1.SQL語言又稱為結(jié)構(gòu)化查詢語言。（U4）2.