計算機二級語言程序設(shè)計

1、計算機二級語言程序設(shè)計2017年計算機二級語言程序設(shè)計第一部分公共基礎(chǔ)部分知識歸納數(shù)據(jù)結(jié)構(gòu)與算法算法-一是一組嚴謹?shù)囟x運算順序的規(guī)則算法的基本要素是對數(shù)據(jù)對象的運算和操作，二是算法的 控制結(jié)構(gòu)算法設(shè)計基本方法-列舉法、歸納法、遞推、遞歸、減半 遞推算法的復雜度-包括時間復雜度和空間復雜度時間復雜度- - 執(zhí)行算法所需的計算工作量空間復雜度-一執(zhí)行算法所需的內(nèi)存空間數(shù)據(jù)結(jié)構(gòu)-相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。如春、夏、秋、冬；18、11、35、23、16。；父親、兒子、女兒等都是數(shù)據(jù)元素。 前件一-數(shù)據(jù)元素之間的關(guān)系，如父親是兒子和女兒的前件后件一一如 兒子是父親的后件結(jié)構(gòu)-指數(shù)據(jù)元素之間的前后件關(guān)

2、系數(shù)據(jù)的邏輯結(jié)構(gòu)一是指反映數(shù)據(jù)元素之間邏輯關(guān)系，而與它們在 計算機中的存儲位置無關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）-數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空 間中的存放形式，數(shù)據(jù)元素在計算機存儲空間的位置關(guān)系可能與邏 輯關(guān)系不同。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復雜程度，可將數(shù) 據(jù)結(jié)構(gòu)分兩類一-線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)（線性表）-滿足下列兩個條件有且只有一個根結(jié)點 每一個結(jié)點最多有一個前件和后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，否 則為非線性結(jié)構(gòu)。線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)元素之間的相 對位置是線性的，其存儲方式為順序存儲的，如數(shù)組棧-是限定在一端進行插入與刪除的線性表，一端封閉，另一

3、端開口，其操作原則是“先進后出”，棧的運算有入棧、退棧、讀 棧頂元素隊列-是指在一端進行插入（稱為隊尾）而在另一端進行刪 除（稱為隊頭）的線性表，其操作規(guī)則是“先進先出”，其運算有入 隊和退隊。樹-一是一種簡單的非線性結(jié)構(gòu)，而且是層次結(jié)構(gòu)，是倒立的大 樹，有根結(jié)點、父結(jié)點、子結(jié)點、葉子結(jié)點。根結(jié)點在第一層，一 個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度 稱為樹的度，樹的最大層次稱為樹的深度。二叉樹一- （1）非空二叉樹只有一個根結(jié)點每一個結(jié)點最多有 兩棵子樹（左子樹和右子樹），其存儲結(jié)構(gòu)為鏈式。二叉樹性質(zhì)一-（DK層上最多有2（1）個結(jié)點出深度為111的二 叉樹最多有2m-1個

4、結(jié)點（3）度為0的結(jié)點（葉子結(jié)點）比度為2的結(jié)點多一個（4）具有n個 結(jié)點的二叉樹，其深度至少為Log2n+1,其中Log2n表示對 Log2n取整滿二叉樹一-除最后一層外，其余層的結(jié)點都有兩個子結(jié)點完全二叉樹一-除最后一層外，每一層上的結(jié)點數(shù)均達到最大值, 在最后一層上只缺少右邊的若干結(jié)點，葉子結(jié)點只可能在層次最大 的兩層上出現(xiàn)。滿二叉樹是完全二叉樹，而完全二叉樹不是滿二叉 樹。完全二叉樹有兩個性質(zhì)：（1）具有n個結(jié)點的完全二叉樹的深度 為Log2n+1（2）二叉樹遍歷一-不重復地訪問各個結(jié)點。分為前序遍歷（DLR-根左 右）、中序遍歷（LDR-左根右）和后序遍歷（LRD-左右根）查找技術(shù)-

5、順序查找一一對于長度為n的有序線性表，查找時 需要比較n次二分法查找一一對于長度為n的有序線性表，查找時需要比較 log2n次排序技術(shù)-假設(shè)線性表的長度為n,則冒泡排序和簡單插 入排序的比較次數(shù)（時間復雜度）為n （n-1） /2;希爾排序的比較次數(shù)為0 （nl. 5）;簡單選擇排序的比較次數(shù)為n （n-l）/2;堆排序的比較次 數(shù)為0（nlog2n）.程序設(shè)計基礎(chǔ)結(jié)構(gòu)化程序設(shè)計的三種結(jié)構(gòu)-是順序、選擇和循環(huán)對象-表示 客觀世界的任何實體類-是具有共同屬性和方法的對象的集合實例-任何一個對象 都是其對應類的實例消息-一一個實例和另一個實例之間傳遞的信息繼承-是指直接獲得已有的性質(zhì)和特征，而不必

6、重復定義它們。 例如子類繼承父類結(jié)構(gòu)化程序設(shè)計主要強調(diào)-程序的易讀性良好的程序設(shè)計風格是一-程序應簡單、清晰、可讀性好在面向 對象方法中，一個對象請求另一個對象為其服務(wù)的方式是通過發(fā)送 （消息）來實現(xiàn)的信息隱蔽的概念與（模塊獨立性）概念直接相關(guān)（任何對象都具有 繼承性）這句話是錯誤的注釋分為（序言性注釋）和（功能性注釋）在面向?qū)ο蠓椒ㄖ?，信息隱蔽是通過對象的（封裝性）來實現(xiàn)的類 是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的（實例）在面向?qū)ο?方法中，類之間共享屬性和操作的機制稱為（繼承）第三章軟件工程基礎(chǔ)軟件生命周期-軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用 退役的過程。分為軟件定義、軟件開發(fā)、

7、軟件運行維護三個階段。軟件生命周期的主要活動階段-可行性分析、需求分析、軟件 設(shè)計、軟件實現(xiàn)、軟件測試、運行和維護。常見的需求分析方法一-（1）結(jié)構(gòu)化分析方法-主要包括面向數(shù) 據(jù)流的結(jié)構(gòu)化分析方法SA;面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法JSD;面向 數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法DSSD。（2）面向?qū)ο蟮姆治龇?法00A結(jié)構(gòu)化分析方法工具（1）數(shù)據(jù)流圖DFD,記住DFD圖的幾個符號：（2）數(shù)據(jù)字典DD（3） 判定樹（4）判定表程序結(jié)構(gòu)圖（SC）, N-S圖，問題分析圖（PAD）程序流程圖（PFD）的 幾個符號：軟件測試-黑盒測試：功能測試白盒測試：內(nèi)部結(jié)構(gòu)測試，窮舉路徑測試習題3在軟件生命周期

8、中，能準確地判斷軟件系統(tǒng)必須做什么和必須具 備哪些功能的階段是（需求分析）軟件工程的3個要素（工具），（過 程），（方法）檢查軟件產(chǎn)品是否符合需求定義的過程稱為（確認測試）軟件設(shè)計 原則是（抽象）、（模塊化）、（信息隱蔽）需求分析常用的工具是（DFD）在結(jié)構(gòu)化方法中，軟件功能分解屬于（總體設(shè)計）階段軟件測試的 目的是（改正錯誤）軟件需求分析階段可分為四個方面（需求獲?。?、（需求分析）、 （編寫需求格式說明）、（需求評審）軟件是（程序）、（數(shù)據(jù)）、（文檔） 的集合Jakson方法是一中面向（數(shù)據(jù)流）的結(jié)構(gòu)化方法軟件工程研究的內(nèi) 容包括（軟件開發(fā)技術(shù)）、（軟件工程管理）數(shù)據(jù)流圖的類型有（交換型）、

9、 （事務(wù)型）軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的（軟件工具）集合第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)（一）數(shù)據(jù)庫-DB;數(shù)據(jù)庫管理系統(tǒng)-DBMS;數(shù)據(jù)庫管理員-DBA;數(shù) 據(jù)庫系統(tǒng)一-DBS;數(shù)據(jù)庫應用系統(tǒng)-DBAS數(shù)據(jù)模型所描述的內(nèi)容分三個部分（數(shù)據(jù)結(jié)構(gòu)）、（數(shù)據(jù)操作）、 （數(shù)據(jù)約束）邏輯數(shù)據(jù)模型分（層次模型）、（網(wǎng)狀模型）、（關(guān)系模型）、（面向 對象模型）E-R模型-實體關(guān)系模型，主要由實體、屬性、聯(lián)系組成，聯(lián) 系分：1對1, 1對多，多對多；以二維表為基本結(jié)構(gòu)所建立的模型稱為關(guān)系模型，關(guān)系模型采用 二維表來表示，簡稱表，由行和列組成，行稱為元組或記錄，列稱 為字段主鍵一-唯一標識一個記錄的字段外鍵一-

10、一個表的字段是其 他表的主鍵在數(shù)據(jù)管理技術(shù)的發(fā)展過程中，經(jīng)歷了人工管理階段、文件系統(tǒng) 階段、數(shù)據(jù)庫系統(tǒng)階段，其中數(shù)據(jù)獨立性最高的階段是（數(shù)據(jù)庫系統(tǒng)） 數(shù)據(jù)庫系統(tǒng)減少了（數(shù)據(jù)冗余）；數(shù)據(jù)庫系統(tǒng)的核心是（數(shù)據(jù)庫管理系 統(tǒng)）用樹型結(jié)構(gòu)來表示實體間聯(lián)系的模型稱為（層次模型）關(guān)系表中的 每一行稱為（元組）關(guān)系數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)的專門關(guān)系運算包括（選擇）、（投影）、 （連接）在關(guān)系數(shù)據(jù)庫中，用來表示實體之間聯(lián)系的是（二維表）數(shù)據(jù)庫設(shè) 計包括兩方面的設(shè)計內(nèi)容（概念設(shè)計）、（邏輯設(shè)計）將E-R圖轉(zhuǎn)換到 關(guān)系模式時，實體與聯(lián)系都可以表示成（關(guān)系）一個項目具有一個項目主管，一個項目主管可以管理多個項目， 則實體“項目主管”與“項目”的聯(lián)系屬于（一對多）數(shù)據(jù)獨立性分為邏輯獨立性和物理獨立性，當數(shù)據(jù)的存儲結(jié)構(gòu)改 變時，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應用程序不必 修改，稱為（