全國計算機二級 公共基礎高頻考點匯總

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

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

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

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

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

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

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

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

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

10、測試。程序調試的目的程序調試的目的是診斷和改正錯誤。軟件調試的方法：強行排錯法、回溯法、原因排除法。第四章第四章數(shù)據(jù)庫設計基礎數(shù)據(jù)庫設計基礎數(shù)據(jù)數(shù)據(jù)，描述事物的符號記錄。數(shù)據(jù)庫（DB）就是存放數(shù)據(jù)的倉庫。數(shù)據(jù)庫中的數(shù)據(jù)具有兩大特點：集成與共享。數(shù)據(jù)庫管理系統(tǒng)（數(shù)據(jù)庫管理系統(tǒng)（DBMS），目前流行的均為關系數(shù)據(jù)庫系統(tǒng)，數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心。數(shù)據(jù)的完整性與安全性的維護是數(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)、應用系統(tǒng)、數(shù)據(jù)庫管理員和用戶構成。數(shù)據(jù)庫應用系統(tǒng)（數(shù)據(jù)庫應用系統(tǒng)（DBAS），包括數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺、軟件平臺、應用軟件、應用界面7個部分。數(shù)據(jù)管理技術數(shù)據(jù)管理技術經歷了3個階段，人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。數(shù)據(jù)庫系統(tǒng)的基本特點數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)

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

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