計算機二級公共基礎(chǔ)知模板-wenkub
2023-05-29 03:46:47 本頁面
【正文】 二分法查找只適用于順序存儲的有序表，對于長度為n的有序線性表，最壞情況只需比較log2n次。完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。二叉樹的特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點，右指針（Rlink）指向后件結(jié)點。循環(huán)隊列：s=0表示隊列空，s=1且front=rear表示隊列滿1．5 線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。 （詳見1416頁）1．4 棧和隊列棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。結(jié)點個數(shù)n稱為線性表的長度，當(dāng)n=0時，稱為空表。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止?；具\算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。1．3 線性表及其順序存儲結(jié)構(gòu)線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：（1）線性表中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。Rear指針指向隊尾，front指針指向隊頭。結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。線性鏈表的基本運算：查找、插入、刪除。沒有后件的結(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）設(shè)完全二叉樹共有n個結(jié)點。二叉樹存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。1．8 排序技術(shù)排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。第2章 程序設(shè)計基礎(chǔ)2．1 程序設(shè)計設(shè)計方法和風(fēng)格如何形成良好的程序設(shè)計風(fēng)格源程序文檔化； 數(shù)據(jù)說明的方法；語句的結(jié)構(gòu)； 輸入和輸出。2．3 面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蟮某绦蛟O(shè)計：以60年代末挪威奧斯陸大學(xué)和挪威計算機中心研制的SIMULA語言為標(biāo)志。屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。消息是一個實例與另一個實例之間傳遞的信息。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動，包含4種基本活動：（1）P軟件規(guī)格說明；（2）D軟件開發(fā)；（3）C軟件確認(rèn)；（4）A軟件演進?；灸繕?biāo)：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能按時完成開發(fā)，及時交付使用。軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟學(xué)、軟件心理學(xué)等內(nèi)容。需求分析方法有（1）結(jié)構(gòu)化需求分析方法；（2）面向?qū)ο蟮姆治龅姆椒?。?shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能建模。數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。從
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1