全國計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)匯總-在線瀏覽
2025-08-06 20:33本頁面
【正文】 隊(duì)列運(yùn)算包括：(1) 入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素； (2) 退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。循環(huán)隊(duì)列s=0表示隊(duì)列空；s=1且front=rear表示隊(duì)列滿。 樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu)，其所有元素之間具有明顯的層次特性。沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。樹的最大層次稱為樹的深度。滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹有2m1個(gè)結(jié)點(diǎn)。二叉樹基本性質(zhì)：(1)在二叉樹的第k層上，最多有2k1(k≥1)個(gè)結(jié)點(diǎn)；(2)深度為m的二叉樹最多有2m1個(gè)結(jié)點(diǎn)；(3)度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)；(4)具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分(5) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1；(6) 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。補(bǔ)充：增加度為1的結(jié)點(diǎn)不會(huì)影響二叉樹的葉子結(jié)點(diǎn)數(shù)，每增加一個(gè)度為2的結(jié)點(diǎn)便會(huì)增加一個(gè)葉子結(jié)點(diǎn)，沒有度為2的結(jié)點(diǎn)時(shí)葉子結(jié)點(diǎn)數(shù)為1。二叉樹存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹與完全二叉樹可以按層序進(jìn)行順序存儲(chǔ)。最左邊的結(jié)點(diǎn)最先遍歷，最右邊的結(jié)點(diǎn)最后遍歷）（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)。先訪問整棵二叉樹的根結(jié)點(diǎn)A，然后再先序遍歷左子樹T1；在訪問T1時(shí)，也以先序遍歷原則，先訪問T1的根結(jié)點(diǎn)B，然后再先序遍歷T1的左子樹T11；在訪問T11時(shí)，也以先序遍歷原則，先訪問T11的根結(jié)點(diǎn)D，然后再先序遍歷T11的左子樹。由于T11的右子樹只有I結(jié)點(diǎn)，故訪問此結(jié)點(diǎn)后T11的右子樹的先序遍歷結(jié)束。先序遍歷完T1子樹后，接著先序遍歷根結(jié)點(diǎn)A的右子樹T2。訪問各個(gè)結(jié)點(diǎn)的順序?yàn)椋篐DIBEAFCG2) 后序遍歷：先后序遍歷左子樹，然后再后序遍歷右子樹，最后再訪問根結(jié)點(diǎn)。下面樹的先序、中序、后續(xù)遍歷的結(jié)果依次為__ abdcef _、 bdaecf _、_ dbefcaacbdef一棵二叉樹如圖所示，它的中序遍歷的結(jié)果為（ B ）A、abdgcefh B、dgbaechf C、gdbehfca D、abcdefghacbfdegh小結(jié)：邏輯結(jié)構(gòu)可分為線性表和非線性表。鏈?zhǔn)叫陀校壕€性鏈表，帶鏈的棧，帶鏈的隊(duì)列，循環(huán)鏈表等。 查找技術(shù)只能使用順序查找的兩種情況：（1）線性表為無序表，不管是順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)；（2）表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即使是有序線性表。 排序技術(shù)排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。插入類排序法：（1）簡單插入排序法，最壞情況需要n(n1)/2次比較； (2) 希爾排序法，最壞情況需要O()次比較。相比以上幾種(除希爾排序法外)，堆排序法的時(shí)間復(fù)雜度最小。形成良好的程序設(shè)計(jì)風(fēng)格需注意：(詳見書P27)源程序文檔化； 數(shù)據(jù)說明的方法； 語句的結(jié)構(gòu)； 輸入和輸出。 語句結(jié)構(gòu)清晰第一、效率第二。（1）自頂向下。不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。對(duì)復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化。一個(gè)復(fù)雜問題，肯定是由若干稍簡單的問題構(gòu)成。（4）限制使用goto語句。結(jié)構(gòu)化程序設(shè)計(jì)的特點(diǎn)：只有一個(gè)入口和出口 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)的首次提出以60年代末挪威奧斯陸大學(xué)和挪威計(jì)算機(jī)中心研制的SIMULA語言為標(biāo)志。對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象。屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過執(zhí)行對(duì)象的操作來改變。對(duì)象的基本特點(diǎn)：（1）標(biāo)識(shí)惟一性。 （2）分類性。 （3）多態(tài)性。 （4）封裝性。對(duì)象的內(nèi)部，即處理能力的實(shí)行和內(nèi)部狀態(tài)，對(duì)外是不可見的。*：信息隱蔽是通過對(duì)象的封裝性來實(shí)現(xiàn)的。對(duì)象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對(duì)象是以數(shù)據(jù)為中心的，操作圍繞對(duì)其數(shù)據(jù)所需做的處理來設(shè)置，沒有無關(guān)的操作。類是指具有共同屬性、共同方法的對(duì)象的集合。類是對(duì)象的抽象，對(duì)象是其對(duì)應(yīng)類的一個(gè)實(shí)例。對(duì)象間的通信靠消息傳遞。消息的組成包括：（1）接收消息的對(duì)象的名稱； （2）消息標(biāo)識(shí)符，也稱消息名； （3）零個(gè)或多個(gè)參數(shù)。繼承具有傳遞性，一個(gè)類實(shí)際上繼承了他上層的全部基類的特性。單繼承指一個(gè)類只允許有一個(gè)父類，即類等級(jí)為樹形結(jié)構(gòu)；多重繼承指一個(gè)類允許有多個(gè)父類。軟件的特點(diǎn)包括：（1）軟件是一種邏輯實(shí)體，具有抽象性；（2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；（3）軟件在運(yùn)行、使用期間不存在磨損、老化問題；（4）軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；（5）軟件復(fù)雜性高，成本昂貴；（6）軟件開發(fā)涉及諸多的社會(huì)因素。軟件危機(jī)主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。簡單的說就是使軟件走向工程化。軟件工程包括3個(gè)要素：方法、工具和過程。軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。軟件工程的目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。軟件開發(fā)環(huán)境或軟件工程環(huán)境是指全面支持軟件開發(fā)全過程的軟件工具的集合。軟件管理學(xué)包括人員組織、進(jìn)度安排、質(zhì)量保證、配置管理、項(xiàng)目計(jì)劃等。 結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。需求分析，對(duì)待開發(fā)軟件提出的需求分析并給出詳細(xì)的定義。需求分析方法有：（1）結(jié)構(gòu)化需求分析方法； ①面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法（ISD）；②面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法（SA）；③面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法（DSSD）；（2）面向?qū)ο蟮姆治龅姆椒ǎ∣OA）。結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。（1）數(shù)據(jù)流圖（DFD圖）：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能建模。②數(shù)據(jù)流——箭頭，沿箭頭方向傳遞數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。④源、潭——方框，表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。（4）判定表：與判定樹相似，當(dāng)數(shù)據(jù)流圖中的加工要依賴于多個(gè)邏輯條件的取值，即完成該加工的一組動(dòng)作是由于某一組條件取值的組合而引發(fā)的，使用判定表描述比較適宜。 結(jié)構(gòu)化設(shè)計(jì)方法軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。系統(tǒng)設(shè)計(jì)人員和程序設(shè)計(jì)人員應(yīng)該在反復(fù)理解軟件需求的基礎(chǔ)上，給出軟件結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程。從技術(shù)觀點(diǎn)來看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。②數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。④過程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述。軟件設(shè)計(jì)的一般過程：軟件設(shè)計(jì)
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1