全國計算機(jī)二級 公共基礎(chǔ)高頻考點(diǎn)匯總

1、第一章第一章數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法算法算法是一組有窮的指令集，通俗地說就是計算機(jī)解題的過程。算法有四個基本特征算法有四個基本特征：確定性、有窮性、可行性、擁有足夠的情報。算法的組成要素算法的組成要素：對數(shù)據(jù)對象的運(yùn)算和操作（算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸操作）、控制結(jié)構(gòu)（算法一般由順序、選擇、循環(huán)三種基本結(jié)構(gòu)組合而成）。算法的復(fù)雜度算法的復(fù)雜度(復(fù)雜度的高低體現(xiàn)在運(yùn)行該算法時所需占用計算機(jī)資源的多少)：算法的時間復(fù)雜度是指

2、執(zhí)行算法所需要的計算工作量，即基本運(yùn)算次數(shù)；算法的空間復(fù)雜度是指執(zhí)行算法所需要的內(nèi)存空間。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。前后件關(guān)系是數(shù)據(jù)元素之間最基本的關(guān)系。依據(jù)視點(diǎn)不同，數(shù)據(jù)結(jié)構(gòu)可以分為數(shù)據(jù)的邏輯結(jié)構(gòu)（它是面向問題的，與所使用的計算機(jī)無關(guān)）和存儲結(jié)構(gòu)（也稱物理結(jié)構(gòu)，它是面向計算機(jī)的，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示）。依據(jù)數(shù)據(jù)元素之間的關(guān)系，數(shù)據(jù)結(jié)構(gòu)一般分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)（也稱線性表）：線性結(jié)構(gòu)（也稱

3、線性表）：非空的數(shù)據(jù)結(jié)構(gòu)、有且只有一個根結(jié)點(diǎn)、每一個結(jié)點(diǎn)最多有一個前件（也最多有一個后件）。線性表的順序存儲結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系相鄰的結(jié)點(diǎn)物理位置上也相鄰。鏈表的優(yōu)點(diǎn)鏈表的優(yōu)點(diǎn)是在進(jìn)行插入和刪除運(yùn)算時，只需要改變指針即可，不需要移動元素，當(dāng)存儲空間不足時，可以動態(tài)為其分配內(nèi)存空間，所以不必估計存儲空間的大小。順序表可以隨機(jī)訪問任意一個結(jié)點(diǎn)，而鏈表必須從第一個數(shù)據(jù)結(jié)點(diǎn)出發(fā)，逐一查找每個結(jié)點(diǎn)。順序存儲結(jié)構(gòu)的插入運(yùn)算：順序存儲結(jié)構(gòu)的插入運(yùn)算：

4、在順序表第i個位置上插入一個值，就要先把第i個元素（包括i）之后的所有元素依次向后移動一個位置，然后再插入，最后長度加1.順序存儲結(jié)構(gòu)的刪除運(yùn)算：順序存儲結(jié)構(gòu)的刪除運(yùn)算：要刪除第i個表項(xiàng)，則必須把第i個元素（不包括i）之后的所有元素依次向前移動一個位置，把第i個表項(xiàng)覆蓋掉，最后長度減1.棧是一種后進(jìn)先出（先進(jìn)后出）的線性表，具有記憶功能。棧的基本運(yùn)算棧的基本運(yùn)算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元

5、素等，對棧的操作都是在棧頂進(jìn)行的。列隊列隊只允許在表的一端插入（隊尾），而在另一端刪除（隊頭），是一種先進(jìn)先出（后進(jìn)后出）的線性表。棧和隊列的共同點(diǎn)：都是操作受限的線性表，只允許在表的端點(diǎn)處進(jìn)行操作。樹（非線性結(jié)構(gòu)）對于任意的一棵非空樹都具有兩個特性：有且只有一個根結(jié)點(diǎn)；當(dāng)n（結(jié)點(diǎn)）1時，除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m(m0)個互不相交的有限集。結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹棵數(shù)。度為0的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。樹的度：樹中所有結(jié)點(diǎn)的度的最大值。樹的

6、深度則為所處層次最大的那個結(jié)點(diǎn)的層次?？偨Y(jié)點(diǎn)數(shù)=總度數(shù)1（一棵樹中每個結(jié)點(diǎn)的度樹之和與邊的條數(shù)相等）二叉樹的基本性質(zhì)：二叉樹的基本性質(zhì)：在二叉樹的第k層上，最多有2的k1次方個結(jié)點(diǎn)；深度為m的二叉樹最多有2的m次方1個結(jié)點(diǎn)；任意二叉樹中，度為度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總比度為的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個結(jié)點(diǎn)多一個；具有n個結(jié)點(diǎn)的二叉樹，其深度不小于[log2n]1(“[]”取整)滿二叉樹滿二叉樹就是每一層上的所有結(jié)點(diǎn)數(shù)都到達(dá)最

7、大值；完全二叉樹：具有n個結(jié)點(diǎn)的完全二叉樹的深度為[log以2為底n的對數(shù)]1；完全二叉樹中度為1的結(jié)點(diǎn)數(shù)為0或1；二叉樹的編歷二叉樹的編歷如果二叉樹為空，則執(zhí)行空操作；前序遍歷：訪問根結(jié)點(diǎn)，前序遍歷左子樹，前序遍歷右子樹中序遍歷：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹后序遍歷：后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點(diǎn)。(層層分左右根層層分左右根)框表示源、潭。建立數(shù)據(jù)流圖的步驟一般分三步：由外向內(nèi)、自頂向下、逐層分解。軟件設(shè)計軟

8、件設(shè)計（是確定系統(tǒng)的物理模型），是將需求準(zhǔn)確地轉(zhuǎn)化為軟件產(chǎn)品或系統(tǒng)的唯一途徑。軟件設(shè)計的基本原理軟件設(shè)計的基本原理：模塊化、抽象、信息隱藏和局部化、模塊獨(dú)立性（與耦合性（模塊之間）成反比，與內(nèi)聚性（模塊內(nèi)）成正比）。在設(shè)計中應(yīng)該力求松散耦合，避免緊密耦合。內(nèi)聚性越強(qiáng)，則耦合性越弱，高質(zhì)量的軟件設(shè)計，應(yīng)盡量做到高內(nèi)聚，低耦合，有利于提高模塊的獨(dú)立性。典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。好的軟件設(shè)計結(jié)構(gòu)通常頂層高扇出，中間扇出較少，底層

9、高扇入。軟件測試軟件測試，測試的根本目的是盡可能地發(fā)現(xiàn)并排除軟件中隱藏的錯誤。一個好的程序測試用例能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯誤；一個成功的程序測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤。軟件測試的方法軟件測試的方法，按是否需要執(zhí)行被測軟件分為靜態(tài)和動態(tài)測試，按功能則分為黑盒（功能、數(shù)據(jù)驅(qū)動測試）和白盒測試（結(jié)構(gòu)、邏輯測試），黑盒測試的主要方法有等價類劃分法、邊界值分析法、錯誤推測法。軟件測試過程分為4個步驟：單元測試、集成測試、驗(yàn)收（確認(rèn)）測試和系統(tǒng)

10、測試。程序調(diào)試的目的程序調(diào)試的目的是診斷和改正錯誤。軟件調(diào)試的方法：強(qiáng)行排錯法、回溯法、原因排除法。第四章第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)數(shù)據(jù)，描述事物的符號記錄。數(shù)據(jù)庫（DB）就是存放數(shù)據(jù)的倉庫。數(shù)據(jù)庫中的數(shù)據(jù)具有兩大特點(diǎn)：集成與共享。數(shù)據(jù)庫管理系統(tǒng)（數(shù)據(jù)庫管理系統(tǒng)（DBMS），目前流行的均為關(guān)系數(shù)據(jù)庫系統(tǒng)，數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心。數(shù)據(jù)的完整性與安全性的維護(hù)是數(shù)據(jù)庫管理系統(tǒng)的基本功能。數(shù)據(jù)管理系統(tǒng)的數(shù)據(jù)語言有三種數(shù)據(jù)管

11、理系統(tǒng)的數(shù)據(jù)語言有三種：數(shù)據(jù)定義語言（DDL）、數(shù)據(jù)操縱語言（DML）、數(shù)據(jù)控制語言（DCL）。數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)，由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用系統(tǒng)、數(shù)據(jù)庫管理員和用戶構(gòu)成。數(shù)據(jù)庫應(yīng)用系統(tǒng)（數(shù)據(jù)庫應(yīng)用系統(tǒng)（DBAS），包括數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺、軟件平臺、應(yīng)用軟件、應(yīng)用界面7個部分。數(shù)據(jù)管理技術(shù)數(shù)據(jù)管理技術(shù)經(jīng)歷了3個階段，人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)：數(shù)

12、據(jù)的高集成性、髙共享性與低冗余性、高獨(dú)立性。物理獨(dú)立性，存儲結(jié)構(gòu)改變時，其邏輯結(jié)構(gòu)可以不變，且基于邏輯結(jié)構(gòu)的應(yīng)用程序也無須改變；邏輯獨(dú)立性，數(shù)據(jù)的邏輯結(jié)構(gòu)改變了，用戶的應(yīng)用程序可以不變。三級模式和兩級映射三級模式和兩級映射：內(nèi)模式、概念模式、外模式；外模式概念模式映射、概念模式內(nèi)模式映射。概念模式是全體用戶的公共數(shù)據(jù)視圖，外模式是用戶的數(shù)據(jù)視圖，內(nèi)模式是數(shù)據(jù)物理結(jié)構(gòu)和存儲方式的描述。數(shù)據(jù)庫技術(shù)的根本目的是解決數(shù)據(jù)共享的問題。數(shù)據(jù)模型數(shù)據(jù)

13、模型通常由數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和完整性約束組成。數(shù)據(jù)模型分為概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型3類。鍵（碼）能夠唯一標(biāo)識實(shí)體的屬性集。主鍵，表中能夠唯一確定一個元組的屬性值，如學(xué)號。兩個實(shí)體集之間的聯(lián)系兩個實(shí)體集之間的聯(lián)系有三種：一對一、一對多、多對多。在ER圖中，實(shí)體用矩形表示，屬性用橢圓形表示，聯(lián)系用菱形表示。邏輯數(shù)據(jù)模型邏輯數(shù)據(jù)模型分為四種：層次、網(wǎng)狀、關(guān)系模型和面向?qū)ο竽Ｐ?。（前兩種為非關(guān)系及格式化模型）層次模型層次模型，有