全國計算機(jī)二級vb公共基礎(chǔ)知識總結(jié)-wenkub
2023-06-15 04:30:37 本頁面
【正文】 也以先序遍歷原則，先訪問T1的根結(jié)點B，然后再先序遍歷T1的左子樹T11；在訪問T11時，也以先序遍歷原則，先訪問T11的根結(jié)點D，然后再先序遍歷T11的左子樹?！ 、?基本性質(zhì)： a) 在二叉樹的第k層上，最多有2k1(k≥1)個結(jié)點； b) 深度為m的二叉樹最多有2m1個結(jié)點； c) 度為0的結(jié)點（即葉子結(jié)點）=度為2的結(jié)點數(shù)+1； d) 二叉樹總結(jié)點數(shù)=度為0的結(jié)點數(shù)+度為1的結(jié)點數(shù)+度為2的結(jié)點數(shù) e) 具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分 f) 具有n個結(jié)點的完全二叉樹的深度為[log2n]+1； g) 完全二叉樹中度為1的節(jié)點只可能是0或1個 補(bǔ)充：增加度為1的結(jié)點不會影響二叉樹的葉子結(jié)點數(shù)，每增加一個度為2的結(jié)點便會增加一個葉子結(jié)點，沒有度為2的結(jié)點時葉子結(jié)點數(shù)為1?！、?樹的最大層次稱為樹的深度?！ 、?沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。 ?、?隊列運(yùn)算包括： a) 入隊運(yùn)算：從隊尾插入一個元素； b) 退隊運(yùn)算：從隊頭刪除一個元素?！、?棧的基本運(yùn)算： a) 入棧運(yùn)算，在棧頂位置插入元素； b) 退棧運(yùn)算，刪除元素(取出棧頂元素并賦給一個指定的變量)； c) 讀棧頂元素，將棧頂元素賦給一個指定的變量，此時指針無變化?！ 、?棧頂位置用指針top表示?！〗Y(jié)點由兩部分組成： a) 用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域； b) 用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點?！ 。ò锤髟刂g前后件關(guān)系的復(fù)雜度劃分）：?。?）線性結(jié)構(gòu)的條件：①有且只有一個根結(jié)點； ②每一個結(jié)點最多有一個前件，也最多有一個后件?！。?）算法空間復(fù)雜度：指執(zhí)行這個算法所需要的內(nèi)存空間。?。毫信e法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。 ?。阂皇菍?shù)據(jù)對象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。公共基礎(chǔ)知識 二級公共基礎(chǔ)知識總結(jié)(30分：10選擇+5填空) 第一章 數(shù)據(jù)結(jié)構(gòu)與算法 一． 算法 ?。菏墙忸}方案的準(zhǔn)確而完整的描述?！。阂粋€計算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合?！。ㄋ惴ㄐ实亩攘浚。?）算法時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量。包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間。?。?）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)?！ 镌阪?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。棧底位置用指針bottom表示。 ⑥ 棧的元素個數(shù)=bottomtop+1 ?。?）隊列?、?指允許在一端（隊尾）進(jìn)入插入，而在另一端（隊頭）進(jìn)行刪除的線性表?！、?隊列的順序存儲結(jié)構(gòu)一般采用隊列循環(huán)的形式?！ 、?每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點?！ 。?）二叉樹 ?、?特點： a) 非空二叉樹只有一個根結(jié)點； b) 每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹?！ 、?二叉樹存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進(jìn)行順序存儲。由于此時T11的左子樹只有H結(jié)點，所以訪問H結(jié)點，T11的左子樹先序遍歷結(jié)束，根據(jù)先序遍歷的原則，進(jìn)行先序遍歷T11的右子樹。先序遍歷完T2后，該二叉樹的所有結(jié)點都已經(jīng)訪問過，各結(jié)點被訪問的順序為：ABDHIECFG ?。?）中序遍歷： 先中序遍歷左子樹，然后再訪問根結(jié)點，最后再中序遍歷右子樹。 線性表包括棧、隊列，其存儲方式為順序存儲、鏈?zhǔn)酱鎯??！ 铩锒址ú檎抑贿m用于順序存儲的有序表，對于長度為n的有序線性表，最壞情況只需比較log2n次，而順序查找需要比較n次。 2. 形成良好的程序設(shè)計風(fēng)格需注意： ?。?） 源程序文檔化； （2） 數(shù)據(jù)說明的次序要規(guī)范化； ?。?）語句的結(jié)構(gòu)應(yīng)該簡單直接，不要為提高效率而復(fù)雜化； （4）輸入數(shù)據(jù)前要有提示信息和輸出信息符合規(guī)范?！?. 基本工具：程序流程圖，NS圖 4. 特點：只有一個入口和出口 三． 面向?qū)ο蟮某绦蛟O(shè)計（主要考慮的是提高軟件的可重用性） 1. 面向?qū)ο蟮某绦蛟O(shè)計的首次提出以60年代末挪威奧斯陸大學(xué)和挪威計算機(jī)中心研制的SIMULA語言為標(biāo)志?！ 卫^承指一個類只允許有一個父類，即類等級為樹形結(jié)構(gòu)；多重繼承指一個類允許有多個父類?！ 〔僮髅枋隽藢ο髨?zhí)行的功能，是對象的動態(tài)屬性，操作也稱為方法或服務(wù)。對象間的通信靠消息傳遞?！?. 軟件按功能分為： 應(yīng)用軟件：教務(wù)管理系統(tǒng) 系統(tǒng)軟件：操作系統(tǒng) 支撐軟件(或工具軟件)：編譯軟件，匯編軟件 3. 軟件危機(jī)主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題?！》秩齻€階段：（1）定義階段：可行性研究與計劃制定；需求分析 ?。?）開發(fā)階段：軟件設(shè)計（概要設(shè)計和詳細(xì)設(shè)計）；軟件實現(xiàn)；軟件測試 （3）維護(hù)階段：運(yùn)行和維護(hù) 二．需求分析?。盒枨螳@取，需求分析，編寫需求規(guī)格說明書
公司管理相關(guān)推薦
鄂ICP備17016276號-1