全國計算機(jī)等級考試二級公共基礎(chǔ)知識復(fù)習(xí)提綱-文庫吧
2025-04-01 22:12 本頁面
【正文】 取 的整數(shù)部分 滿二叉樹與完全二叉樹 滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點?！ ?完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點。 下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹： 二叉樹的遍歷 ★★★★ 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種： (1)前序遍歷(DLR)：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。 (2)中序遍歷(LDR)：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。 (3)后序遍歷(LRD)：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點. 該二叉樹前序遍歷為:F C A D B E G H P 該二叉樹中序遍歷為:A C B D F E H G P 該二叉樹后序遍歷為:A B D C H P G E F 查找技術(shù) 查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 查找結(jié)果：（查找成功：找到；查找不成功：沒找到。） 平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。 查找分為: 順序查找 二分法查找對于長度為n的有序線性表，最壞情況只需比較次，而順序查找需要比較n次?！ ? 排序技術(shù) 排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。 交換類排序法（冒泡排序，快速排序） 插入類排序法（簡單插入排序，希爾排序） 選擇類排序法（簡單選擇排序，堆排序） 冒泡排序法,快速排序法,簡單插入排序法,簡單選擇排序法,最壞需要比較的次數(shù)為n(n1)/2 希爾排序,最壞需要比較的次數(shù)為 堆排序,最壞需要比較的次數(shù)為 2011年全國計算機(jī)等級考試二級公共基礎(chǔ)知識總結(jié)：第二章 程序設(shè)計設(shè)計方法和風(fēng)格 清晰第一、效率第二已成為當(dāng)今主導(dǎo)的程序設(shè)計風(fēng)格。 形成良好的程序設(shè)計風(fēng)格需注意： 源程序文檔化； 數(shù)據(jù)說明的方法； 語句的結(jié)構(gòu)； 輸入和輸出?！ ∽⑨尫中蜓孕宰⑨尯凸δ苄宰⑨尅?語句結(jié)構(gòu)清晰第一、效率第二。 結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計方法的四條原則是： 自頂向下； 逐步求精； 模塊化； 限制使用goto語句。 結(jié)構(gòu)化程序的基本結(jié)構(gòu)及特點： (1)順序結(jié)構(gòu)：一種簡單的程序設(shè)計，最基本、最常用的結(jié)構(gòu)； (2)選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列； (3)循環(huán)結(jié)構(gòu)：又稱重復(fù)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同或類似的程序段。 結(jié)構(gòu)化程序設(shè)計的特點：只有一個入口和出口 面向?qū)ο蟮某绦蛟O(shè)計 面向?qū)ο蠓椒ǖ膬?yōu)點： (1)與人類習(xí)慣的思維方法一致； (2)穩(wěn)定性好； (3)可重用性好； (4)易于開發(fā)大型軟件產(chǎn)品； (5)可維護(hù)性好。 對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實體，對象是實體的抽象。 面向?qū)ο蟮某绦蛟O(shè)計方法中，對象是由數(shù)據(jù)的容許的操作組成的封裝體，是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 操作描述了對象執(zhí)行的功能，是對象的動態(tài)屬性，操作也稱為方法或服務(wù)。 對象的基本特點： (1)標(biāo)識惟一性； (2)分類性； (3)多態(tài)性； (4)封裝性； (5)模塊獨立性好。 類是指具有共同屬性、共同方法的對象的集合。類是關(guān)于對象性質(zhì)的描述。類是對象的抽象，對象是其對應(yīng)類的一個實例。 消息是一個實例與另一個實例之間傳遞的信息。對象間的通信靠消息傳遞。它請求對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。 繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)，廣義指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。 繼承具有傳遞性，一個類實際上繼承了他上層的全部基類的特性。 繼承分單繼承和多重繼承。 多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。2011年全國計算機(jī)等級考試
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1