計算機二級公共基礎知模板-文庫吧
2025-04-29 03:46 本頁面
【正文】 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。二叉樹的特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。二叉樹的基本性質(zhì)：（1）在二叉樹的第k層上，最多有2k1(k≥1)個結(jié)點；（2）深度為m的二叉樹最多有2m1個結(jié)點；（3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個；（4）具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分；（5）具有n個結(jié)點的完全二叉樹的深度為[log2n]+1；（6）設完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，….n給結(jié)點進行編號（k=1,2….n），有以下結(jié)論：①若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k1，則該結(jié)點的父結(jié)點編號為INT(k/2)；②若2k≤n，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）；③若2k+1≤n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k層上有2k1個結(jié)點深度為m的滿二叉樹有2m1個結(jié)點。完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。二叉樹存儲結(jié)構(gòu)采用鏈式存儲結(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。二叉樹的遍歷：（1）前序遍歷（DLR），首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點。1．7 查找技術(shù)順序查找的使用情況：（1）線性表為無序表；（2）表采用鏈式存儲結(jié)構(gòu)。二分法查找只適用于順序存儲的有序表，對于長度為n的有序線性表，最壞情況只需比較log2n次。1．8 排序技術(shù)排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。交換類排序法：（1）冒泡排序法，需要比較的次數(shù)為n(n1)/2；（2）快速排序法。插入類排序法：（1）簡單插入排序法，最壞情況需要n(n1)/2次比較；（2）希爾排序法，最壞情況需要O()次比較。選擇類排序法：（1）簡單選擇排序法,最壞情況需要n(n1)/2次比較；（2）堆排序法，最壞情況需要O(nlog2n)次比較。第2章 程序設計基礎2．1 程序設計設計方法和風格如何形成良好的程序設計風格源程序文檔化； 數(shù)據(jù)說明的方法；語句的結(jié)構(gòu)； 輸入和輸出。注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清晰第一、效率第二。2．2 結(jié)構(gòu)化程序設計結(jié)構(gòu)化程序設計方法的四條原則是：1. 自頂向下；2. 逐步求精；；。結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點：（1）順序結(jié)構(gòu)：一種簡單的程序設計，最基本、最常用的結(jié)構(gòu)；（2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應該選擇哪一條分支來執(zhí)行相應的語句序列；（3）重復結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復執(zhí)行某一相同程序段。2．3 面向?qū)ο蟮某绦蛟O計面向?qū)ο蟮某绦蛟O計：以60年代末挪威奧斯陸大學和挪威計算機中心研制的SIMULA語言為標志。面向?qū)ο蠓椒ǖ膬?yōu)點：（1）與人類習慣的思維方法一致；（2）穩(wěn)定性好；（3）可重用性好；（4）易于開發(fā)大型軟件產(chǎn)品；（5）可維護性好。對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實體，對象是實體的抽象。面向?qū)ο蟮某绦蛟O計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務。對象的基本特點：（1）標識惟一性；（2）分類性；（3）多態(tài)性；（4）封裝性；（5）模塊獨立性好。類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應類的一個實例。消息是一個實例與另一個實例之間
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1