1、計(jì)算機(jī)二級(jí)考點(diǎn)算法基本特征有窮性確定性可行性基本要素對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作算法的控制結(jié)構(gòu)設(shè)計(jì)的基本方法列舉法歸納法遞推法減半遞推回溯法復(fù)雜度時(shí)間復(fù)雜度即計(jì)算工作量，用基本運(yùn)算次數(shù)來(lái)度量：工作量=f(n)(其中n是問(wèn)題規(guī)模)空間復(fù)雜度程序所占空間輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間執(zhí)行過(guò)程中所需的額外空間數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)方式順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ).結(jié)構(gòu)分類非線性結(jié)構(gòu)樹(shù)基本概念：父節(jié)點(diǎn)、子節(jié)點(diǎn)（有后件）、葉子節(jié)點(diǎn)（無(wú)后件）、度、深度、 子樹(shù)二叉樹(shù)特點(diǎn)：可為空、最多兩子樹(shù)、左右次序不可顛倒?jié)M二叉樹(shù)&完全二叉樹(shù)（滿二叉樹(shù)一定是完全二叉樹(shù)；反之不一定）性質(zhì)：k層最多結(jié)點(diǎn)：2的（k-1）次幕

2、深度m的滿二叉樹(shù)結(jié)點(diǎn):2m-ln個(gè)結(jié)點(diǎn)的二叉樹(shù)深度k至少為（即完全二叉樹(shù)）：Iog2il+l|完全二叉樹(shù)n個(gè)結(jié)點(diǎn)，對(duì)編號(hào)k的結(jié)點(diǎn)有以下結(jié)論：-k=1,根結(jié)點(diǎn)，無(wú)父結(jié)點(diǎn)k1,父節(jié)點(diǎn)編號(hào)為INT（k/2）2k=n,編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k ；否則無(wú) 2k+1=n,則編號(hào)為岫勺右子結(jié)點(diǎn)編號(hào)為2k+1 ；否則無(wú)存儲(chǔ)結(jié)構(gòu)：通常使用鏈?zhǔn)蕉鏄?shù)的遍歷：（確定任意二者可確定唯一二叉樹(shù)）前 序 DLR 中序LDR后 序圖線性結(jié)構(gòu)線性表（有限序列）隊(duì)列（允許一端插入、一端刪除）S=0，循環(huán)隊(duì)列為空S=1，且front=rear 時(shí)，滿元素總數(shù)=（rear-front號(hào)性表總長(zhǎng)）線性表總長(zhǎng)列滿入隊(duì)（上溢）；列空

3、退隊(duì)（下溢）棧（特殊的線性表-射線性質(zhì)）棧底、棧頂LRD記憶作用插入刪除運(yùn)算不需移動(dòng)表中其他元素 棧頂指針動(dòng)態(tài)反應(yīng)變化查找技術(shù)下列公式中n表示線性表長(zhǎng)度n較小時(shí)，插入選擇排序n較大時(shí)，快速/堆排序n的初始狀態(tài)基本有序時(shí)，簡(jiǎn)單/冒泡排序順序查找適用無(wú)序排列和順序鏈?zhǔn)脚帕凶詈们闆r，查找次數(shù)1最壞情況，查找次數(shù)n平均情況，次數(shù)n/2，時(shí)間復(fù)雜度O(n)二分法查找(即折半查找)最壞情況比較次數(shù)：排序技術(shù)交換類排序法泡排序最壞情況：n/2遍從前往后掃描和n/2遍從后往前掃描，需比較n(n-1)/2次， 數(shù)量級(jí)為n的二次方快速排序法平均時(shí)間效率最高為：0(nlog2 n)最壞情況時(shí)間效率為：插入類排序法簡(jiǎn)

4、單插入排序法最好情況，比較n-1次，移動(dòng)0次最壞情況，比較n(n-1)/2次，移動(dòng)次數(shù)n(n-1)/2次平均比較次數(shù)和移動(dòng)次數(shù)都為口平方/4，時(shí)間復(fù)雜度為：希爾排序法效率與所選取的增量序列有關(guān)選擇類排序法單選擇排序法最壞情況下比較：n（n-1）/2次堆排序法堆：將元素順序組成一顆完全二叉樹(shù)，所有結(jié)點(diǎn)的值大于或等于（小于或等于）左右子結(jié)點(diǎn) 的值，我們稱大（?。└?。最壞情況，堆排序需要比較的次數(shù)為0(nlog2 n)程序設(shè)計(jì)指程序設(shè)計(jì)、編制、調(diào)試的方法和過(guò)程設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法原則：自頂向下、逐步求精、模塊化、限制使用goto語(yǔ)句基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)（分WHILE型和UN

5、TIL型）軟件工程方法特點(diǎn)：邏輯實(shí)體，具抽象性沒(méi)有明顯制作過(guò)程不存在磨損、老化問(wèn)題軟件開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性復(fù)雜性高、成本昂貴軟件開(kāi)發(fā)涉及諸多社會(huì)因素軟件危機(jī)不能滿足軟件需求的增長(zhǎng)無(wú)法控制軟件的開(kāi)發(fā)成本和速度難以保證軟件質(zhì)量軟件不可維護(hù)或維護(hù)成本非常低軟件成本不斷提高軟件的開(kāi)發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求增長(zhǎng)軟件工程三要素：方法、工具、過(guò)程基本活動(dòng)：軟件規(guī)格說(shuō)明、軟件開(kāi)發(fā)、軟件確認(rèn)、軟件演進(jìn)軟件生命周期：包括軟件定義、開(kāi)發(fā)、運(yùn)行維護(hù)3過(guò)程提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用、退役的過(guò)程目標(biāo)：有效、可靠、可理解、可維護(hù)、可重用、可適應(yīng)、可移植、可追蹤、可操作性原則：抽象、信息隱蔽

6、、模塊化、局部化、確定性、一致性、完備性、可驗(yàn)證性 計(jì)算機(jī)輔助軟件工程（CASE）面向?qū)ο蠓椒?基本概念：對(duì)象：基本特點(diǎn)一一標(biāo)識(shí)唯一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性好類和實(shí)例消息繼承多態(tài)性方法優(yōu)點(diǎn)：與人類習(xí)慣的思維方法一致穩(wěn)定性好可重用性好易于開(kāi)發(fā)大型軟件產(chǎn)品可維護(hù)性好設(shè)計(jì)風(fēng)格編寫時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思維結(jié)構(gòu)化分析方法需求分析需求獲取、需求分析、編寫需求規(guī)格說(shuō)明書、需求評(píng)審需求分析方法結(jié)構(gòu)化分析方法常用工具：數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、判定樹(shù)、判定表面向?qū)ο蠓治龇椒ㄔO(shè)計(jì)方法面向數(shù)據(jù)流的設(shè)計(jì)方法：變換型（一條直鏈）、事務(wù)型（事務(wù)中心-支鏈）軟件測(cè)試技術(shù)與方法靜態(tài)/動(dòng)態(tài)測(cè)試

7、白盒測(cè)試邏輯覆蓋型語(yǔ)句路徑條件.判定判斷-條 件基本路徑測(cè) 試黑盒測(cè)試等價(jià)類劃分法 邊界值分析法 錯(cuò)誤推測(cè)法軟件測(cè)試的實(shí)施單元測(cè)試集成測(cè)試確認(rèn)測(cè)試（驗(yàn)收測(cè)試） 系統(tǒng)測(cè)試數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)基本概念描述事物的符號(hào)記錄據(jù)庫(kù)（DB）長(zhǎng)期儲(chǔ)存在計(jì)算機(jī)內(nèi)的、有組織的、可共享的數(shù)據(jù)集合；具有集成”與“共享”特點(diǎn)的數(shù)據(jù)據(jù)庫(kù)管理系統(tǒng)（DBMS）管理數(shù)據(jù)庫(kù)的機(jī)構(gòu)，是一個(gè)系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中數(shù)據(jù)的組織、操縱、維護(hù)、控制、保護(hù)以及 數(shù)據(jù)服務(wù)等。是數(shù)據(jù)庫(kù)系統(tǒng)的核心類型：文件管理系統(tǒng)、層次數(shù)據(jù)庫(kù)系統(tǒng)、網(wǎng)狀數(shù)據(jù)庫(kù)系統(tǒng)、關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)據(jù)庵時(shí)（DBS）引進(jìn)數(shù)據(jù)庫(kù)技術(shù)后的整個(gè)計(jì)算機(jī)系統(tǒng)，能實(shí)現(xiàn)有組織地、動(dòng)態(tài)地存儲(chǔ)大量相關(guān)數(shù)據(jù)，提供

8、數(shù)據(jù)處 理和信息資源共享的便利手段。包含數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)管理系統(tǒng)包含數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)技術(shù)數(shù)據(jù)管理發(fā)展階段：人工管理、文件系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)階段 未來(lái)數(shù)據(jù)庫(kù)應(yīng)支持：數(shù)據(jù)、對(duì)象、知識(shí)管理基本特征：面向?qū)ο蠡咎攸c(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)獨(dú)立性高：包括物理獨(dú)立和邏輯獨(dú)立數(shù)據(jù)統(tǒng)一管理與控制數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)三級(jí)模式結(jié)構(gòu)：概念模式：全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)內(nèi)模式：數(shù)據(jù)物理結(jié)構(gòu)和存儲(chǔ)方式的描述，數(shù)據(jù)庫(kù)內(nèi)部的表示方式夕卜模式：子模式/用戶模式，用戶的數(shù)據(jù)視圖兩級(jí)映射：夕卜模式/概念模式的映射；內(nèi)模式/概念模式的映射數(shù)據(jù)模型基本概念：抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件三個(gè)要素：數(shù)據(jù)結(jié)構(gòu)

9、、數(shù)據(jù)操作、數(shù)據(jù)約束概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型有層次模式、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ偷葘哟文Ｐ途W(wǎng)狀模型關(guān)系模型名詞：關(guān)系、屬性、元組（記錄）、值域、候選碼、主鍵（主碼）、夕卜鍵（外碼）數(shù)據(jù)操作：數(shù)據(jù)查詢、刪除、插入、修改完整性約束：實(shí)體、參照、用戶定義物理數(shù)據(jù)模型E-R模型 （實(shí)體聯(lián)系模型）實(shí)體、聯(lián)系、屬性關(guān)系代數(shù)基本運(yùn)算投影運(yùn)算選擇運(yùn)算笛卡兒積擴(kuò)充運(yùn)算交除（笛卡爾積的逆運(yùn)算） 連接與自然連接數(shù)據(jù)庫(kù)管理數(shù)據(jù)庫(kù)的建立、調(diào)整、重組、數(shù)據(jù)恢復(fù)、監(jiān)控計(jì)算基礎(chǔ)知識(shí)概述1946，美國(guó)賓夕法尼亞大學(xué)，電子數(shù)字積分計(jì)算機(jī)（ENIAC）莫克利、埃克特：新型電子離散變量自動(dòng)計(jì)算機(jī)（EDVAC）馮諾依曼：“現(xiàn)代

10、電子計(jì)算機(jī)之父”提出二進(jìn)制、存儲(chǔ)程序概念計(jì)算機(jī)必須由輸入、存儲(chǔ)、運(yùn)算、控制、輸出五大部分計(jì)算機(jī)輔助技術(shù)*計(jì)算機(jī)輔助設(shè)計(jì)（CAD）硬計(jì)算機(jī)輔助制造（CAM）計(jì)算機(jī)輔助測(cè)試（CAT）計(jì)算機(jī)輔助教學(xué)（CAI）嵌入式系統(tǒng)單個(gè)程序?qū)崿F(xiàn)整個(gè)控制邏輯。是一個(gè)控制程序存儲(chǔ)在ROM中的嵌入式處理器控制面板，若手表、 微波爐、錄像機(jī)、汽車等計(jì)算機(jī)類型巨型機(jī)大型通用機(jī)微型機(jī)個(gè)人計(jì)算機(jī)工作站服務(wù)器未來(lái)計(jì)算機(jī)目標(biāo)：巨型化、微型化、網(wǎng)絡(luò)化、智能化新一代計(jì)算機(jī)種類：模糊計(jì)算機(jī)、生物計(jì)算機(jī)、光子計(jì)算機(jī)、量子計(jì)算機(jī)、超導(dǎo) 計(jì)算機(jī)電子商務(wù)企業(yè)對(duì)企業(yè)（B2B）企業(yè)對(duì)消費(fèi)者（B2C）消費(fèi)者對(duì)消費(fèi)者（C2C）非商務(wù)的電子商務(wù)（No-b

11、usiness EC）企業(yè)內(nèi)的電子商務(wù)（Intrabusiness EC）數(shù)據(jù)/信息數(shù)據(jù)經(jīng)過(guò)處理之后產(chǎn)生的結(jié)果為信息輸入-模/數(shù)（A/D）-數(shù)/模（D/A）-輸 出數(shù)據(jù)單位位字節(jié)（8位）.字長(zhǎng)（8位、16位、32位、64位.）字符編碼西文字符的二進(jìn)制編碼ASCLL漢字的編碼漢字輸入碼（夕卜部碼、夕卜碼）：音碼、形碼、數(shù)字碼、混合碼 漢字機(jī)內(nèi)碼（漢字內(nèi)部碼、內(nèi)碼）漢字字形碼和漢字字庫(kù)：點(diǎn)陣碼計(jì)算機(jī)的硬件系統(tǒng)運(yùn)算器（ALU）控制器（CU ）指令寄存器IR、程序計(jì)數(shù)器PC、指令譯碼器ID、操作控制器* OC 存儲(chǔ)器（Memory ）內(nèi)存：隨機(jī)存儲(chǔ)器RAM和只讀存儲(chǔ)器（ROM ）高速緩沖器Cache存

12、取速度（單位ns ）、存儲(chǔ)容.量外存：硬盤、USB閃存驅(qū)動(dòng)器、光盤倍速：?jiǎn)伪端贋榛鶞?zhǔn)15kbps硬盤容量=磁頭數(shù)*柱面數(shù)*磁道扇區(qū)數(shù)*每個(gè)扇區(qū)的字節(jié)數(shù)輸入/輸出設(shè)備（I/O）輸入設(shè)備：鼠標(biāo)鍵盤、攝像頭、掃描儀、光筆手寫輸入板、游戲桿 輸出設(shè)備：像素與點(diǎn)距、分辨率、顯存顯存容量=圖形分辨率*色彩分辨率/8計(jì)算機(jī)軟件系統(tǒng)概念.程序程序設(shè)計(jì)語(yǔ)言：1.機(jī)器語(yǔ)言；2 .匯編語(yǔ)言；3 .高級(jí)語(yǔ)言進(jìn)程與線程：進(jìn)程=程序+執(zhí)行進(jìn)程是正在運(yùn)行的程序?qū)嶓w；線程是進(jìn)程中的實(shí)體內(nèi)核態(tài)和用戶態(tài) 計(jì)算機(jī)軟件系統(tǒng)及其組成軟件系統(tǒng)：操作系統(tǒng)（核心，Windows. Linux、UNIX ）、語(yǔ)言處理系統(tǒng)、數(shù) 據(jù)庫(kù)管理系統(tǒng)、系

13、統(tǒng)輔助處理程序應(yīng)用軟件：辦公室軟件套裝、多媒體處理軟件、Internet具軟件多媒體技術(shù)基礎(chǔ)知識(shí)多媒體含義：1.傳播信息的載體；2.存儲(chǔ)信息的載體多媒體特征：實(shí)時(shí)性、集成性、交互性、多樣性/L二多媒體數(shù)字化：*聲音：音頻數(shù)據(jù)量（B）=采樣時(shí)間（s ） *采樣頻率（Hz ） *量化位數(shù)（b ） *聲 道數(shù)/8 ；文件格式：WAVE （拓展名 WAV ）、MOD （ MOD、ST3、XT、S3M、 FAR ）、MPEG-3 （ MP3 ）、Real Audio （ RA ）、Creative Musical Format （ CMF ）、CD Audio （ CDA ）、MIDI （ MID ）文

14、件種類：WAV、VOC、MIDI、RMI、PCM、 AIF圖像：靜態(tài)圖像的數(shù)字化圖像的文件格式：BMP、TIFF、JPEG、GIF、PSD、PDF視頻文件格式:AVI、WMV、MPEG、Real Video （ or RealMedia ）多媒體數(shù)據(jù)壓縮無(wú)損壓縮：行程編碼、霍夫曼編碼、算數(shù)編碼、LZW壓縮編碼有損壓縮：預(yù)測(cè)編碼、變換編碼、基于模型編碼、分形編碼、矢量量化編碼計(jì)算機(jī)病毒特征：繁殖性、破壞性、傳染性、潛伏性、隱蔽性、可觸發(fā)性-分類：-引導(dǎo)區(qū)病毒通過(guò)軟盤在操作系統(tǒng)中傳播文件型病毒是文件感染者，也稱寄生病毒。運(yùn)行在計(jì)算機(jī)存儲(chǔ)器中混合型病毒具有引導(dǎo)區(qū)病毒和文件型病毒兩者特點(diǎn)宏病毒用BASIC語(yǔ)言編寫的寄存在O ice文檔上的宏代碼網(wǎng)絡(luò)病毒留駐型病毒非留駐型病毒.Internet基礎(chǔ)及應(yīng)用計(jì)算機(jī)網(wǎng)絡(luò)的基本概念功能：數(shù)據(jù)通信、資源共享、計(jì)算機(jī)系統(tǒng)可靠性和可用性提高、實(shí)現(xiàn)分布式處理、綜合信息服務(wù)網(wǎng)絡(luò)分類：局域網(wǎng)、城域網(wǎng)、廣域網(wǎng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分類：總線型拓?fù)浣Y(jié)構(gòu)、星型拓?fù)浣Y(jié)構(gòu)、環(huán)形