全國計算機等級考試二級公共基礎知識點總結

1、秋風清，秋月明，落葉聚還散，寒鴉棲復驚。1、算法是指解決方案的準確而完整的描述2、算法的四個基本特性：可行性確定性有窮性擁有足夠的情報3、算法有兩個基本的要素組成：一、數(shù)據(jù)對象的運算和操作二、算法的控制結構4、計算機中的基本操作算術運算邏輯運算關系運算數(shù)據(jù)運算5、算法的控制結構給出了算法的基本框架，不僅決定了算法中各操作的執(zhí)行順序， 而且也直接反應了算法的設計是否符合結構化的原則。一個算法都可以用順序、選 擇、循環(huán)3鐘基本控制結構組成6、算法的復雜度主要包括時間復雜度和空間復雜度7、算法的時間復雜度是執(zhí)行算法所需要的計算工作量。他不僅應該與使用的計算機、程序設計語言及程序編制者無關， 而且應該

2、與算法實現(xiàn)過程中的許多細節(jié)無關。8算法的空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。9、如果一個數(shù)據(jù)結構中沒有一個數(shù)據(jù)元素，則稱該數(shù)據(jù)結構為空的數(shù)據(jù)結構。10、根據(jù)數(shù)據(jù)結構中個數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結構分為 線性結構和非線性結構11、 如果一個非空的數(shù)據(jù)結構滿足 1、有且只有一個根結點；2、每一個結點最多 有一個前件，也最多有一個后件，則稱該數(shù)據(jù)結構為線性結構。線性結構又稱線性12、13、14、在一個線性結構中插入或刪除任何一個結點后還是線性結構。在計算機中存放線性表，一種最簡單的方法是順序存儲。、線性表的順序存儲結構具有兩個基本的特點：一、線性表中所有元素所占的存儲空間

3、是連續(xù)的。二、線性表中各數(shù)據(jù)在存儲空間中是按邏輯順序依次存放的。I大風起分云飛揚15、 線性表的插入運算和刪除運算P8-916、棧是一種特殊的線性表，其插入和刪除只能在表的一端進行。17、在棧中允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的一端稱為棧底， 棧的修改原則是先進后出或后進先出。18、 入棧運算：1、首先將棧頂指針進1,然后將新元素入到棧頂指針指向的位置。19、 退棧預算：首先將棧頂元素賦予一個指定的變量，然后將棧頂指針退1。20、隊列：是指允許在一端進行插入、而在另一端進行刪除的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為排頭。隊列又稱 先進先出 或 后進后出的線性 表，

4、體現(xiàn)了“先來先服務的原則”21、隊列的順序存儲結構一般采用循環(huán)隊列的形式。即將隊列的存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供列隊循環(huán)使用。22、線性表的順序存儲結構具有簡單、運算方便等優(yōu)點。但是對于大的線性表，特 別是元素變動頻繁的大線性表不宜采用順序的存儲結構，二是采用鏈式存儲結構23、 鏈式存儲結構中，要求每個結點有兩部分組成：一用于存放數(shù)據(jù)元素值，稱 為數(shù)據(jù)域。另一部分用于存放指針，稱為指針域。其中指針用于指向該結點的前一 個或后一個結點。24、在鏈式存儲結構中的存儲空間可以不連續(xù)，各數(shù)據(jù)結點的存儲結構與數(shù)據(jù)之間 的邏輯關系可以不一致，而數(shù)據(jù)元素之間的邏輯關系是由指

5、針域來確定的。鏈式存 儲方式既可以用于表示線性結構，也可以表示非線性結構25、線性鏈表：線性表的鏈式存儲結構稱為線性鏈表。26、樹：樹是一種簡單的非線性結構。在樹結構中，每一個結點只有一個前件，稱 為父結點，沒有前結點的只有1個，稱為根結點，簡稱為樹的根。每一個結點可以 有多個后件，他們都稱為子結點。27、二叉樹是一種重要的非線性結構。二叉樹具有兩個特點：非空二叉樹只有一個根結點。每個結點最多有兩顆子樹，且分別稱為該結點的左子樹與右子樹。28、在二叉樹的第K層上，最多有2k-1（k>=1）個結點29、深度為M的二叉樹最多有2m-1個結點。深度為M的二叉樹是指二叉樹共有 M 層。30、在任

6、意一顆二叉樹中，度為0的結點（即葉子結點）總比度為2的結點多一個。31、具有N個結點的二叉樹，其深度至少為log2n+1,32、滿二叉樹，除了最后一層外，每一層上的所有結點都有兩個子結點的二叉樹為滿二叉樹。即深度為K的滿二叉樹，其第K層上有2k-1個結點，且深度為M的滿 二叉樹共有2M-1個結點。33、在計算機中，二叉樹通常采用鏈式存儲結構。與線性鏈表類似，用于存儲二叉 樹中各元素的存儲結點也有兩部分組成：數(shù)據(jù)域和指針域。34、二叉樹的遍歷可以分為三種：前序遍歷中序遍歷后序遍歷35、前序遍歷：首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。36、中序遍歷：首先遍歷左子樹，然后訪問根結點，最后遍

7、歷右子樹。37、后序遍歷：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。38、順序查找：又稱順序搜索，一般指在線性表中查找指定元素。對于大的線性表來說，順序查找效率很低。但在以下兩種情況只能用順序查找：1、如果線性表是無序的（即表中的元素是無序的），則不管是順序存儲結構還是鏈式存儲結構， 都只 能順序查找。2、即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。39、二分法查找：二分法查找只能用于順序存儲的有序表。對于長度為N的有序線性表，在最壞的情況下，二分查找只需要比較log2n次，而順序查找則需要比較N次。40、交換類排序法：是指借助數(shù)據(jù)元素之間的相互交換進行排序的一種方法。包括

8、冒泡排序法和 快速排序法。41、冒泡排序法：一種最簡單的交換類排序方法，它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。假設線性表的長度為N,則在最壞的情況下，冒泡排序需要經(jīng)過N/2遍從前往后的掃描和N/2遍從后往前的掃描，需要的比較次數(shù)為n(n-1)/2.但一 般情況下要小于這個工作量。42、快速排序法：是一種交換類的排序方法，但由于它比冒泡排序法的速度快，因 此稱為快速排序法。43、插入類排序法包括簡單插入類排序法希爾排序法44、簡單插入排序法的效率與冒泡排序法相同。在最壞的情況下需要n(n-1)/2次比較45、希爾排序的效率與所選取的增量序列有關。在最壞的情況下，希爾排序所需要 的比較次

9、數(shù)為0( n1.5)46、選擇類排序法包括簡單選擇排序法和堆排序法47、簡單排序法在最壞的情況下需要比較N(n-1)/2次48、堆排序法在最壞情況下需要比較 0( nlog2n)49、就程序設計方法和技術的發(fā)展而言，主要經(jīng)過了結構化程序設計和面向?qū)ο蟮?程序設計兩個階段。50、面向?qū)ο笤O計的主要優(yōu)點是：與人類習慣的思維方法一致；穩(wěn)定性好；可重用 性好；易于開發(fā)大型軟件產(chǎn)品；可維護性好。51、清晰第一，效率第二的論點已經(jīng)成為當今主導的程序設計風格。52、結構化程序?qū)嶋H方法的主要原則為自頂向下，逐步求精，模塊化，限制使用GOTO語句53、結構化程序語言僅使用順序、選擇、重復3鐘基本控制結構就足以表

10、達出各種其他形式的程序設計方法。54、順序就夠是一種簡單的程序設計結構，它是最基本、最常用的結構。55、選擇結構又稱為分支結構，它包括簡單選擇結構和分支選擇結構。56、重復結構又稱為循環(huán)結構。在程序設計語言中，重復結構對應兩類循環(huán)語句， 對先判斷后執(zhí)行循環(huán)體的稱為當型循環(huán)結構。對先執(zhí)行循環(huán)體后判斷的稱為直到型 循環(huán)結構。即直到型循環(huán)至少執(zhí)行一次運算。57、遵循結構化程序的設計原則，按結構化程序設計方法設計出的程序具有明顯的 特點。一、程序結構良好、易讀、易理解、易維護。二、可以提高編程工作的效率， 降低軟件開發(fā)成本。58、 對象是面向?qū)ο蠓椒ㄖ凶罨镜酶拍睢ο缶哂幸韵碌囊恍┗咎攸c：1、標識

11、 的唯一性。2、分類性。3、多態(tài)性。、4、封裝性。5、模塊獨立性好。59、類：將屬性、操作相似的對象歸為類。即類是具有共同屬性、共同方法的對象的集合。60、 消息：一個消息有三部分組成：1、接受消息的對象名稱、2、消息標識符3、零 個或多個參數(shù)。61、在面向?qū)ο蠓椒ㄖ?，實現(xiàn)信息隱蔽是依靠對象的封裝。62、程序中添加的必要注釋：程序的代碼要層次分明，清晰明了，滿足視覺要求。注釋一般分為序言性注釋和功能性注釋。序言性注釋通常位于程序的開頭部分，他 給出了程序的整體說明。功能性注釋一般嵌在源程序體之中，主要描述其后的語句 或程序。63、 從程序行文角度，編寫程序源代碼應該注意源程序文檔化、程序的語句

12、結構、 數(shù)據(jù)的說明和輸入輸出等方面的要求。64、衡量模塊的獨立程度使用耦合性和內(nèi)聚性兩個度量標準。模塊的內(nèi)聚程度越高I 大風起分云飛揚越獨立，耦合程序越低越獨立。65、繼承性是面向?qū)ο蟮姆椒ǖ囊粋€主要特性。繼承是使用已有的類定義作為基礎 建立新類的定義技術。已有的類可以當作基類來引用，新類相應的可當做派生類來 引用。這種層次結構系統(tǒng)的一個重要性質(zhì)是繼承性，一個類直接繼承其父類的描述 或特性，子類自動的共享基類中定義的數(shù)據(jù)和方法。66、通常，將軟件產(chǎn)品從提出、實行、使用維護到停止使用退役的過程稱為軟件的 生命周期。軟件生存期一般包括可行性研究與需求分析、設計、實現(xiàn)、測試、交付 使用以及維護等活動

13、。67、軟件工程的概念出現(xiàn)源自 軟件危機。而軟件危機歸結為成本、質(zhì)量、生產(chǎn)率 的問題。68、 軟件工程是建立并使用完善的工程化原則。軟件工程主要包括3個要素：方法、 工具、過程。69、軟件工程的核心思想是把軟件產(chǎn)品看做是一個工程產(chǎn)品來處理。70、 軟件工程的原則： 抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。71、結構化分析方法是結構化程序設計理論在軟件需求分析階段的運用。72、結構化分析方法的實質(zhì)：著眼于數(shù)據(jù)流、自頂向下、逐層分解、建立系統(tǒng)的流程。以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。73、數(shù)據(jù)流圖 從數(shù)據(jù)傳遞和加工的角度來刻畫數(shù)據(jù)流從輸入到輸出的移動變換

14、過 程。74、數(shù)據(jù)字典是結構化分析方法的核心。數(shù)據(jù)字典是對所有與系統(tǒng)相關的數(shù)據(jù)元素 的一個有組織的列表，具有精確、嚴格的定義，使得用戶和系統(tǒng)分析員對于輸入、 存儲成分和中間的計算結構有共同的理解。符號含義示例及說明=被定義為+與X=a+b表示X由a和b組成| 或X=a|b 表示X由a或b組成 重復X=a表示X由0個或多個a組成m n重復X=2a5表示X中最少出現(xiàn)2次a，最多 出現(xiàn)5次a , 5 > 2為重復次數(shù)的上下 限r(nóng)”一 - （）可選X= ( a )表示a可在X中出現(xiàn)，也可不出現(xiàn)數(shù)據(jù)元素X= “ a ”表示X是取值為字符a的數(shù)據(jù)兒糸連接符X=19表示X可取1到9中的任意一個值* *注釋*a*表示a為說明或注釋75、 表 4-6數(shù)據(jù)字典中采用的符號76、判定樹和判定表77、軟件需求規(guī)格說明書是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之78、軟件需求規(guī)格說明書的作用。1、便于用戶、開發(fā)人員進行理解和交流。2、反映出用戶問題的結構?？梢宰鳛檐浖_發(fā)工具的基礎和依據(jù)。3、作為確認測試和驗 收的依據(jù)。79、有關軟件設計的基本內(nèi)