軟件設(shè)計(jì)師備考筆記

1、資料更新時(shí)間：2017年5月21軟件設(shè)討!1市知識(shí)框架其它知識(shí)1硬#出01緒論02計(jì)算機(jī)組成06信息.安全&體系結(jié)構(gòu)卜標(biāo)準(zhǔn)化10冬媒體軟件基5出03揮作系統(tǒng)-04數(shù)據(jù)庫(kù)系統(tǒng)l 05計(jì)算機(jī)網(wǎng)絡(luò)軟件設(shè)計(jì)&開發(fā)07數(shù)據(jù)結(jié)構(gòu)&算法 卜（jggisth吾言 11系統(tǒng)開發(fā)基礎(chǔ) 12面向?qū)ο蠹夹g(shù)下午綜合題i-。13數(shù)據(jù)流圖，14數(shù)據(jù)庫(kù)設(shè)計(jì)-015uml 建模數(shù)據(jù)皓構(gòu)與算法應(yīng)用q 17面向?qū)ο蟪绦蛟O(shè)計(jì)一、緒論 略二、計(jì)算機(jī)系統(tǒng)數(shù)據(jù)表示與校驗(yàn)碼1 .數(shù)據(jù)表示:原碼、反碼、補(bǔ)碼、移碼。 符號(hào)位0為正數(shù)，1為負(fù)數(shù)。兩正數(shù)/負(fù)數(shù)相加，符號(hào)位不對(duì)時(shí)即出現(xiàn)“溢出”2 .移碼:補(bǔ)碼 符號(hào)位取反。如果機(jī)器字長(zhǎng)為n,偏移量為2

2、n-1,則兇移=2n-1+兇補(bǔ)（x為整數(shù)）。兇移=1+x （x為小數(shù)）3.ieee754 :符號(hào)位（1位,0正1負(fù)）+階碼（8位,+127） +尾數(shù)（23位，小數(shù)點(diǎn)在最高位之后，隨后省略最高位） 。4 .浮點(diǎn)數(shù)加減:0操作數(shù)檢查，對(duì)階操作（小階變大階），尾數(shù)加減 （階碼用雙符號(hào)位，尾數(shù)用單符號(hào)位），結(jié)果規(guī)格 化，舍入處理（判定溢出）。5 .常用校驗(yàn)碼：奇偶校驗(yàn)碼（檢錯(cuò) ,1位糾錯(cuò)）、海明碼（檢錯(cuò),1位糾錯(cuò)）、循環(huán)冗余校驗(yàn)碼（crc）。校驗(yàn)碼越長(zhǎng)越精確6 .海明碼:奇偶校驗(yàn)的一種擴(kuò)充，采用多位校驗(yàn)碼的方式，不等式關(guān)系：2k- 1印+ k, k個(gè)校驗(yàn)碼，總共m + k個(gè)字符計(jì)算機(jī)系統(tǒng)硬件組成1 .

3、cpu的功能:程序控制、操作控制、時(shí)間控制、數(shù)據(jù)處理。2 .計(jì)算機(jī)系統(tǒng)組成示意圖：計(jì)機(jī)軟件系統(tǒng)硬件系統(tǒng)中央姓理中山cpu寄療器相內(nèi)值茴器控制總畿對(duì)不用易戶共透字;j _外rti鼾rti才 t-先分貴易于實(shí)現(xiàn)您的 共？把作業(yè)的 郵分裝入主 存請(qǐng)求介更系統(tǒng)請(qǐng)求段驅(qū)式系統(tǒng) 值求分段雜統(tǒng)3 .寄存器:指令寄存器ir用來存放當(dāng)前正在執(zhí)行的指令，對(duì)用戶是完全透明的。狀態(tài)寄存器用來存放計(jì)算結(jié)果的標(biāo)志 信息，如進(jìn)位標(biāo)志、溢出標(biāo)志等。通用寄存器可用于傳送和暫存數(shù)據(jù)，也可參與算術(shù)邏輯運(yùn)算，并保存運(yùn)算結(jié)果。4 .計(jì)算機(jī)體系結(jié)構(gòu)分類：?jiǎn)翁幚硐到y(tǒng),并行處理與多處理系統(tǒng)，分布式處理系統(tǒng)。5 .risc中的流水線技術(shù)：超流

4、水線技術(shù),超標(biāo)量技術(shù)，超長(zhǎng)指令字技術(shù)。6 .并治性的解決：陣列處理機(jī),并行處理機(jī)，多處理機(jī)。存儲(chǔ)系統(tǒng)1 .上存與 cache地土止映1寸方式：全相聯(lián)映射：將主存一個(gè)塊的地址與內(nèi)容一起存入cache中，拷貝靈活，但是比較器電路難設(shè)計(jì)實(shí)現(xiàn)；【沖突小】組相聯(lián)映射：主存塊放到哪個(gè)組是固定的，但是放到哪一行是靈活的，廣泛采用折中辦法；直接映射：一個(gè)主存塊只能拷貝到cache的特定行上去，硬件簡(jiǎn)單、成本低，但易沖突、效率降低；【沖突高】2 .虛擬存儲(chǔ)器: 頁式：頁表硬件小，查表速度快但不利于存儲(chǔ)保護(hù)； 段式：界限分明，便于程序的模塊化設(shè)計(jì)，易于編譯修改和保護(hù)，但主存利用率低，產(chǎn)生大量碎片，查表速度慢； 段

5、頁式：折中辦法，廣泛采用，但地址變換速度比較慢。3 .計(jì)算機(jī)與外設(shè)數(shù)據(jù)交換：無條件傳送,查詢方式傳送，中斷方式傳送，直接存儲(chǔ)器存取方式（dma）： cpu僅在過程開始和結(jié)束時(shí)有處理，過程中 dma占用系統(tǒng)總線傳送數(shù)據(jù)?！緄/o工作方式分類：程序控制、程序中斷、 dma】4 .多中斷處理辦法：多中斷信號(hào)線法,中斷軟件查詢法，菊花鏈法，總線仲裁法，中斷向量表法。指令系統(tǒng)1.指令的分類：數(shù)據(jù)傳輸類、運(yùn)算類、程序控制類、輸入 /輸出類、數(shù)據(jù)處理類。2.尋址方式:除了下表還有：基址尋址、變址尋址立即尋址指令的地址字段指出的不是操作數(shù)的地址，而是操作數(shù)本身直接尋址在指令格式的地址字段中直接指出操作數(shù)在內(nèi)存

6、的地址d間接尋址指令地址字段中的形式地址d不是操作數(shù)的真正地址，而是操作數(shù)地址的指示器，d單兀的內(nèi)容才是操作數(shù)的有效地址。兩次訪問內(nèi)存，影響指令執(zhí)行速度，現(xiàn)在已不大使用。不存器尋址操作數(shù)不放在內(nèi)存中，而在通用寄存器中。指令中給出的操作數(shù)地址不是內(nèi)存的地址單r號(hào)，而是 通用寄存器的編號(hào)。寄存器間接尋址指令格式中的寄存器內(nèi)容不是操作數(shù)，而是操作數(shù)的地址，該地址指明的操作數(shù)在內(nèi)存中。相對(duì)尋址操作數(shù)的有效地址=pc的內(nèi)容+指令格式中的形式地址do以pc的內(nèi)容為當(dāng)前指令的地址，“相對(duì)”尋址，是相對(duì)于當(dāng)前的指令地址而言的。（相對(duì)路徑尋址，d為偏移量）3.指令集白勺發(fā)展:cisc （complex inst

7、ruction set computer ）增強(qiáng)原有指令的功能，用更為復(fù)雜的新指令取而代之； risc （reduced instruction set computer）減少指令總數(shù)，精簡(jiǎn)指令功能，優(yōu)化編譯，降低復(fù)雜度。4.指令控制方式：順序方式,重疊方式，流水方式。總線結(jié)構(gòu)1 .總線分類:內(nèi)部總線：芯片的互連；系統(tǒng)總線： cpu,內(nèi)存，接口等的連接；外部總線：數(shù)據(jù)交換?？煽啃耘c系統(tǒng)性能評(píng)測(cè)2 .計(jì)算機(jī)可靠性：可靠性：串聯(lián)系統(tǒng)r=ri*r2,并聯(lián)系統(tǒng) r=1-（1-r1）*（ 1-r2）。平均無故障時(shí)間：串聯(lián)系統(tǒng)k=ki+k2,并聯(lián)系統(tǒng)k=1/k*（1 + 1/2）。3 .計(jì)算機(jī)系統(tǒng)性能評(píng)測(cè)

8、常用方法：時(shí)鐘頻率,指令執(zhí)行速度，等效指令速度法，數(shù)據(jù)處理速率（pdr）。三、操作系統(tǒng)os基礎(chǔ)知識(shí)1作用:通過資源管理提高計(jì)算機(jī)系統(tǒng)的效率；改善人機(jī)界面，向用戶提供友好的工作環(huán)境2 .特征并發(fā)性、共享性、虛擬性、不確定性3 .功能:處理機(jī)管理、文件管理、存儲(chǔ)管理、設(shè)備管理、作業(yè)管理4 .類型；批處理操作系統(tǒng)（單道、多道）、分時(shí)操作系統(tǒng)（unix ,多路性、獨(dú)立性、交互性、及時(shí)性）、實(shí)時(shí)操作系統(tǒng) （快速響應(yīng)、有限交互、高可靠性）、網(wǎng)絡(luò)操作系統(tǒng)、分布式操作系統(tǒng)、微機(jī)操作系統(tǒng)、嵌入式操作系統(tǒng)處理機(jī)管理1 .程序并發(fā)執(zhí)行的特點(diǎn)：失去了程序封閉性,程序和機(jī)器的執(zhí)行程序的活動(dòng)不再一一對(duì)應(yīng)，并發(fā)程序間的相互

9、制約性2 .進(jìn)程的組成:程序、數(shù)據(jù)、 pcb3 .進(jìn)程的狀態(tài):新建、就緒、運(yùn)行、阻塞、終止4 .原語的特點(diǎn)：執(zhí)行時(shí)不能被分割,要么都做要么都不做。（原語由若干條機(jī)器指令組成）5 .進(jìn)程的同步：進(jìn)程間完成一項(xiàng)任務(wù)時(shí)直接發(fā)生相互作用的關(guān)系6 .進(jìn)程的互斥:系統(tǒng)中各進(jìn)程互斥使用臨界資源7 .信號(hào)量的意義：若 s=0,表示某資源的可用數(shù)；若 s0,其絕對(duì)值表示阻塞隊(duì)列中等待該資源的進(jìn)程數(shù)8 .pv操作（低級(jí)通訊方式）:p操作申請(qǐng)一個(gè)資源，v操作釋放一個(gè)資源9 .高級(jí)通訊方式：共享存儲(chǔ)模式,消息傳遞模式，管道通信10 .管翌：一些共享數(shù)據(jù)、一組能為并發(fā)進(jìn)程所執(zhí)行的、作用在共享數(shù)據(jù)上的操作的集合、初始代碼

10、、存取權(quán)。（管程是一種同步機(jī)制）11 進(jìn)程調(diào)度算法（可剝奪+不可剝奪）：先來先服務(wù)算法：主要用于宏觀調(diào)度；時(shí)間片輪轉(zhuǎn)：微觀調(diào)度，分時(shí)間片占用cpu;優(yōu)先級(jí)調(diào)度：根據(jù)優(yōu)先級(jí)（靜態(tài) +動(dòng)態(tài)）；多級(jí)反饋調(diào)度：分多個(gè)優(yōu)先級(jí)隊(duì)列前三中調(diào)度的綜合，先執(zhí)行新進(jìn)程12 .產(chǎn)牛死鎖的原因：競(jìng)爭(zhēng)資源:多道程序運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合理（算法low）13 .產(chǎn)牛死鎖的四個(gè)必要條件：互斥條件:請(qǐng)求保持條件；不可剝奪條件；環(huán)路條件（循環(huán)等待條件）14 .死鎖的處理：預(yù)防（破壞形成死鎖的4個(gè)必要條件。預(yù)先靜態(tài)分配：破壞“不可剝奪條件”。資源有序分配法:破壞“環(huán)路”條件）。避免（有序分配資源；銀行家算法：先計(jì)算資源需求最大

11、量和可分配量，如果分配資源后系統(tǒng)進(jìn)入不安全狀態(tài)則不予分配）。檢測(cè)（系統(tǒng)定時(shí)運(yùn)行死鎖檢測(cè)程序）。解除（資源剝奪/撤銷進(jìn)程）15 .安全狀態(tài):系統(tǒng)能按某種順序來為每個(gè)進(jìn)程分配其所需資源，使每個(gè)進(jìn)程都能順序完成16 .源存儲(chǔ)管理1 .存儲(chǔ)器管理：分配和回收主存空間、提高主存利用率、擴(kuò)充主存、有效保護(hù)主存信息2 .存儲(chǔ)器的的層次結(jié)構(gòu)：寄存器、caches主存、外存【讀寫速度越來越慢，單位空間價(jià)格越來越低】3 .地址重定位：將邏輯地址轉(zhuǎn)變成物理地址的過程。分類：靜態(tài)，動(dòng)態(tài)（程序運(yùn)行時(shí)完成轉(zhuǎn)換）4 .虛擬存儲(chǔ)頁面置換算法：最佳置換（以后最久不會(huì)被使用），先進(jìn)先出置換，最近最少未使用，最近未用5 .設(shè)備管理

12、的目標(biāo)：提高設(shè)備的利用率,為用戶提供方便統(tǒng)一的界面6 .磁盤調(diào)度算法（縮短平均尋道時(shí)間）：先來先月艮務(wù)，最短尋道時(shí)間優(yōu)先，掃描算法scan ,單向掃描調(diào)度 cscan文件管理文件:具有符號(hào)名的、在邏輯上具有完整意義的一組相關(guān)信息項(xiàng)的集合7 .文件系統(tǒng):操作系統(tǒng)中實(shí)現(xiàn)文件統(tǒng)一管理的、一組軟件和相關(guān)數(shù)據(jù)的集合，專門負(fù)責(zé)文件管理和存取文件信息8 .存儲(chǔ)管理方案示意圖：見上面9 .文件系統(tǒng)的安全：一類涉及到技術(shù)、管理、法律、道德和政治等問題；另一類涉及操作系統(tǒng)的安全機(jī)制10 文件系統(tǒng)的可靠性：轉(zhuǎn)儲(chǔ)和恢復(fù),日志文件，文件系統(tǒng)的一致性作業(yè)管理32 .作業(yè):系統(tǒng)為完成一個(gè)用戶的計(jì)算任務(wù)（或一次事物處理）所做

13、的工作總和33 .作業(yè)狀態(tài):提交，后備，執(zhí)行，完成34 .作業(yè)調(diào)度算法：先來先服務(wù),短作業(yè)優(yōu)先，響應(yīng)比高優(yōu)先，優(yōu)先級(jí)調(diào)度，均衡調(diào)度os實(shí)例35 .網(wǎng)絡(luò)操作系統(tǒng)：集中模式,客戶端 /服務(wù)器模式，對(duì)等模式36 .嵌入式操作系統(tǒng)：微型化,可定制，實(shí)時(shí)性，可靠性，易移植性37 .shell變量:用戶定義變量，系統(tǒng)定義變量，shell定義變量四、數(shù)據(jù)庫(kù)系統(tǒng)基本概念1 .數(shù)據(jù)庫(kù)系統(tǒng)：數(shù)據(jù)庫(kù),硬件，軟件，人員2 .dbms功能:數(shù)據(jù)庫(kù)建立、操作、運(yùn)行管理維護(hù)，數(shù)據(jù)定義、組織、存儲(chǔ)和管理，與其他軟件系統(tǒng)的通信功能等3 .dbms特征:數(shù)據(jù)結(jié)構(gòu)化且統(tǒng)一管理，有較高的數(shù)據(jù)獨(dú)立性，數(shù)據(jù)控制功能（數(shù)據(jù)庫(kù)的安全性保護(hù)、

14、數(shù)據(jù)的完整性、并發(fā)控制、故障恢復(fù)）4 .dbms分類:關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)（實(shí)體間的聯(lián)系用關(guān)系表示），面向?qū)ο蟮臄?shù)據(jù)庫(kù)系統(tǒng)（以對(duì)象形式對(duì)數(shù)據(jù)建模），對(duì)象關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)（在關(guān)系數(shù)據(jù)模型基礎(chǔ)上提供處理新的數(shù)據(jù)類型操作的能力）5數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)：集中式（數(shù)據(jù)、數(shù)據(jù)管理、數(shù)據(jù)庫(kù)功能等都集中在一起），分布式（物理上分布+邏輯上分布），c/s模式（客戶端負(fù)責(zé)數(shù)據(jù)表示服務(wù)、 服務(wù)器負(fù)責(zé)數(shù)據(jù)庫(kù)服務(wù)），并行結(jié)構(gòu)（多個(gè) cpu物理上連在一起處理）6數(shù)據(jù)庫(kù)的三級(jí)模式：外模式 （用戶與數(shù)據(jù)庫(kù)系統(tǒng)的接口， 用戶用到那部分?jǐn)?shù)據(jù)的描述）概念模式（數(shù)據(jù)庫(kù)中全部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述，只涉及型的描述而不涉及具體的值）內(nèi)模式（數(shù)

15、據(jù)物理結(jié)構(gòu)和存儲(chǔ)方式的描述，數(shù)據(jù)在數(shù)據(jù)庫(kù)內(nèi)部的表示方式）7 .數(shù)據(jù)庫(kù)的兩級(jí)映像：外模式 /模式映像（外模式？概念模式），模式/內(nèi)模式映像（概念模式？?jī)?nèi)模式）；8 .數(shù)據(jù)的獨(dú)立性：物理獨(dú)立性（數(shù)據(jù)庫(kù)的內(nèi)模式改變時(shí)，數(shù)據(jù)的邏輯結(jié)構(gòu)不變），通過修改外模式？概念模式的映射完成。邏輯獨(dú)立性（用戶的應(yīng)用程序與數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)相互獨(dú)立），通過修改概念模式？?jī)?nèi)模式的映射完成。數(shù)據(jù)模型1.數(shù)據(jù)模型:實(shí)體類型及實(shí)體間聯(lián)系的模型?，F(xiàn)實(shí)世界一信息世界（形成概念）一機(jī)器世界（形成數(shù)據(jù)結(jié)構(gòu)模型）（1）概念數(shù)據(jù)模型（e-r實(shí)體聯(lián)系模型等）；（2）基本數(shù)據(jù)模型（層次模型：用樹型結(jié)構(gòu)表示數(shù)據(jù)間的聯(lián)系；網(wǎng)狀模型：用網(wǎng)絡(luò)結(jié)構(gòu)表示數(shù)

16、據(jù)間的聯(lián)系；關(guān) 系模型：用表格結(jié)構(gòu)表示實(shí)體間的聯(lián)系；面向?qū)ο竽Ｐ停簩?duì)象標(biāo)識(shí)+封裝+對(duì)象的屬性+類和類層次+繼承）關(guān)系模型中難懂的一些術(shù)語： 全鍵/碼:關(guān)系模型中所有屬性都是這個(gè)關(guān)系的關(guān)鍵字。（全碼：所有字段） 超鍵（超碼）:在關(guān)系模式中，能唯一標(biāo)識(shí)元組的屬性集。這個(gè)屬性集可能含有多余的屬性。 候選鍵/碼:能唯一標(biāo)識(shí)元組，且又不含有多余的屬性一個(gè)屬性集，即超鍵中刪除多余屬性剩下的屬性集。 主鍵/碼:候選鍵中選擇一個(gè)作為關(guān)系模式中用戶使用的候選鍵。 主屬性:包含在任何候選鍵中的屬性。非主屬性:不包含在任何候選鍵中的屬性。2 .數(shù)據(jù)模型三要素：數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)操作，數(shù)據(jù)的約束條件3 .e-r圖:實(shí)體（

17、矩形），聯(lián)系（菱形），屬性（橢圓形）4 .完整性約束：實(shí)體完整性（主鍵取值唯一且不空）；參照完整性（主鍵+外鍵保證表間關(guān)聯(lián)）；用戶自定義完整性關(guān)系代數(shù)1 .關(guān)系代數(shù)運(yùn)算：并,交，差，笛卡爾積，投影（兀垂直方向上運(yùn)算），選擇（。水平方向運(yùn)算），連接，除關(guān)系數(shù)據(jù)庫(kù)sql1.sql語言的特點(diǎn)：綜合統(tǒng)一,高度非過程化，面向集合的操作方式（自含式、嵌入式），語言簡(jiǎn)潔易學(xué)易用2.sql語言的組成：數(shù)據(jù)定義語言,交互式數(shù)據(jù)操縱語言，事務(wù)控制，嵌入式 sql和動(dòng)態(tài)sql,完整性，權(quán)限管理3 .數(shù)據(jù)定義:創(chuàng)建-creates,刪除-drop,修改-alter；表-table,視圖-viewas select,索

18、弓 i -indexon4 .查詢數(shù)據(jù): selectfromwheregroup byhavingorder by asc/desc5 .增、刪、改數(shù)據(jù)：insert intovalues（）delete from .where. updateset.=.where6 .授權(quán)、回u攵權(quán)限：granton.to.（with grant option）revokeon.from.7 .函數(shù)依賴：反映屬性間的聯(lián)系（x-y）;完全函數(shù)依賴：（學(xué)生id,所修課程id） 一成績(jī)；部分函數(shù)依賴：（學(xué)生id,所修課程id） 一學(xué)生姓名；平凡函數(shù)依賴：x-y且y包含于x;非平凡函數(shù)依賴：x-y且y不包含于x;

19、傳遞函數(shù)依賴：x-y , y-z關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化1.規(guī)范化:1nf:屬性不可再分2nf:消除非主屬性對(duì)碼的部分函數(shù)依賴；r關(guān)系模式屬于1nf,且每個(gè)非主屬性完全函數(shù)依賴r的候選鍵3nf:消除非主屬性對(duì)碼的傳遞函數(shù)依賴；r屬于1nf,且每個(gè)非主屬性都不傳遞依賴于r的候選鍵eg: 1nf職工信息表（職工號(hào)，姓名，級(jí)別，工資，學(xué)歷，畢業(yè)時(shí)間）1nf - 2nf職工表（職工號(hào)，姓名，級(jí)別，工資 ）職工學(xué)歷表（職工號(hào)，學(xué)歷，畢業(yè)時(shí)間）1nf - 3nf職工表（職工號(hào)，姓名，級(jí)別）職工學(xué)歷表（職工號(hào)，學(xué)歷，畢業(yè)時(shí)間）工資關(guān)系（級(jí)別，工資） 存在的傳遞性依賴：職工號(hào)一級(jí)別，級(jí)別一工資，形成“職工號(hào)一級(jí)別一

20、工資”表內(nèi)傳遞性依賴?！局洠?nf、3nf在1nf基礎(chǔ)上轉(zhuǎn)換得到。1nf所有屬性堆在一個(gè)表中；2nf較常用；3nf消除了傳遞函數(shù)依賴】2.1nf存在的問題：數(shù)據(jù)冗余、修改不一致、插入異常、刪除異常3.模式分解標(biāo)準(zhǔn)：無損連接.保持函數(shù)依賴數(shù)據(jù)庫(kù)的控制功能1 .事務(wù)的 acid 性質(zhì):原子性（atomicity ）, 一致性（consistency）,隔離性（isolation）,持久性（durability ）2 .事務(wù)管理：事務(wù)開始（begin transaction）,事務(wù)提交（commit）,事務(wù)回滾（rollback）3 .數(shù)據(jù)庫(kù)故障：事務(wù)內(nèi)部故障,系統(tǒng)故障，介質(zhì)故障，計(jì)算機(jī)病毒4 .

21、數(shù)據(jù)備份方法：靜態(tài)轉(zhuǎn)儲(chǔ)和動(dòng)態(tài)轉(zhuǎn)儲(chǔ),海量轉(zhuǎn)儲(chǔ)和增量轉(zhuǎn)儲(chǔ)，日志文件5 .數(shù)據(jù)恢復(fù)步驟：反向掃描文件日志,對(duì)事物的更新操作執(zhí)行逆操作，繼續(xù)反向掃描和更新，直到事務(wù)的開始標(biāo)志6 .并發(fā)控制的技術(shù)：封鎖（寫鎖、讀鎖）7 .數(shù)據(jù)不一致性：丟失修改,不可重復(fù)讀，讀臟數(shù)據(jù)五、計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)的基礎(chǔ)（internet）1.2（計(jì)算機(jī)技術(shù)+通信技術(shù)）：具有通信功能的單機(jī)系統(tǒng) 一具有通信功能的多機(jī)系統(tǒng)一以共享資源為目的的計(jì)算機(jī)網(wǎng)絡(luò) 一以局域網(wǎng)及因特網(wǎng)為支撐環(huán)境的分布式計(jì)算機(jī)系統(tǒng)2 .功加 數(shù)據(jù)通信，資源共享，負(fù)載均衡，高可靠性3 .分類:局域網(wǎng)（lan ： 10m1000m）,城域網(wǎng)（man ： 10km）,廣

22、域網(wǎng)（wan : 100km 以上）4 .網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：總線型,星型，環(huán)型，樹型，分布式（無嚴(yán)格的布線規(guī)定和形狀，各節(jié)點(diǎn)有多條線路相連）5.osi七層參考模型：物理層（物理地傳送比特流） ，數(shù)據(jù)鏈路層（負(fù)責(zé)兩相鄰節(jié)點(diǎn)間無差錯(cuò)傳送以幀為單位的數(shù)據(jù)2005.11, arp,網(wǎng)絡(luò)層（提供端到端的交換網(wǎng)絡(luò)數(shù)據(jù)傳送功能），傳輸層（提供可靠的數(shù)據(jù)傳輸服務(wù)），會(huì)話層（提供會(huì)話管理服務(wù)），表示層（提供格式化的表示和轉(zhuǎn)換數(shù)據(jù)服務(wù)） ，應(yīng)用層（提供網(wǎng)絡(luò)與用戶應(yīng)用軟件之間的接口服務(wù)） 網(wǎng)絡(luò)互聯(lián)軟硬件1 .網(wǎng)絡(luò)百連設(shè)備： 中繼器，物理層上實(shí)現(xiàn)局域網(wǎng)網(wǎng)段互連，用于擴(kuò)展局域網(wǎng)網(wǎng)段長(zhǎng)度 集線器，特殊的多路中繼器，有信號(hào)放大

23、功能，并便于網(wǎng)絡(luò)維護(hù) 網(wǎng)橋，工作在數(shù)據(jù)鏈路層，用于連接兩個(gè)局域網(wǎng)網(wǎng)段 交換機(jī)，按每一個(gè)包中的macm址相對(duì)簡(jiǎn)單地決策信息轉(zhuǎn)發(fā) 路由器，網(wǎng)絡(luò)層異構(gòu)互連，連接多個(gè)邏輯上分開的網(wǎng)絡(luò) 網(wǎng)關(guān)，在兩個(gè)不同類型協(xié)議的網(wǎng)絡(luò)系統(tǒng)之間進(jìn)行通信2 .網(wǎng)絡(luò)傳輸介質(zhì)：有線介質(zhì)（雙絞線，同軸電纜：直接傳輸數(shù)字信號(hào)，光纖：傳輸光信號(hào)、需信號(hào)轉(zhuǎn)換）；無線介質(zhì)（微波：利用無線電波傳輸，紅外線：傳輸紅外光信號(hào)，激光：傳激光信號(hào)，衛(wèi)星通信：傳輸電磁波信號(hào)）3 .局域網(wǎng)組成部件：服務(wù)器（文件 /打印/通信服務(wù)器），客戶端（用戶與網(wǎng)絡(luò)應(yīng)用接口設(shè)備），網(wǎng)絡(luò)設(shè)備（網(wǎng)卡，收發(fā)器，中繼器，集中器，網(wǎng)橋，路由器等），通信介質(zhì)（數(shù)據(jù)的傳輸媒體），

24、網(wǎng)絡(luò)軟件（底層協(xié)議軟件、網(wǎng)絡(luò)os等）網(wǎng)絡(luò)的標(biāo)準(zhǔn)與協(xié)議協(xié)議:規(guī)定通信時(shí)的數(shù)據(jù)格式、數(shù)據(jù)傳送時(shí)序以及相應(yīng)的控制信息和應(yīng)答信號(hào)等內(nèi)容2 .網(wǎng)絡(luò)的標(biāo)準(zhǔn):電信標(biāo)準(zhǔn)，國(guó)際標(biāo)準(zhǔn)（ieee標(biāo)準(zhǔn)等），internet標(biāo)準(zhǔn)（自發(fā)標(biāo)準(zhǔn)非政府干預(yù)）3 .決定局域網(wǎng)特性的主要技術(shù)：傳輸介質(zhì)（傳輸數(shù)據(jù)），拓?fù)浣Y(jié)構(gòu)（連接各種設(shè)備），介質(zhì)訪問控制方法（共享資源）4 .局域網(wǎng)協(xié)議：lan模型（物理層，數(shù)據(jù)鏈路層：邏輯鏈路控制子層、介質(zhì)訪問控制）；以太網(wǎng)（csma/cd技術(shù)：邊發(fā)送邊接收、時(shí)刻偵聽信道）；令牌環(huán)網(wǎng)（適用于環(huán)型網(wǎng)絡(luò)結(jié)構(gòu)的分布式介質(zhì)訪問控制：廣播發(fā)送令牌、目標(biāo)站進(jìn)行處理）；fddi （類似令牌環(huán)網(wǎng)協(xié)議、光纖作為傳輸介

25、質(zhì)）5 .廣域網(wǎng)協(xié)議：點(diǎn)對(duì)點(diǎn)協(xié)議（ppp:主要用于撥號(hào)上網(wǎng)，建立點(diǎn)對(duì)點(diǎn)連接發(fā)送數(shù)據(jù)）；數(shù)字用戶線（xdsl:不對(duì)稱數(shù)字用戶線adsl ,甚高速數(shù)字用戶線 vdsl）;數(shù)字專線（電信數(shù)字?jǐn)?shù)據(jù)網(wǎng)固定專線，電信鋪設(shè)）；幀中繼（在用戶網(wǎng)絡(luò)接口之間提供用戶信息流的雙向傳送，并保持順序不變）；異步傳輸模式（atm :面向分組的快速分組交換模式，使用異步時(shí)分復(fù)用技術(shù)）；x.25協(xié)議（在本地?cái)?shù)據(jù)終端設(shè)備和遠(yuǎn)程數(shù)據(jù)終端設(shè)備之間提供一個(gè)全雙工、同步的透明信道）6 .tcp/ip協(xié)議簇特性：邏輯編址,路由選擇，域名解析，錯(cuò)誤檢測(cè)，流量控制7 . tcp/ip模型立用層ftptelnetsmtpnfssnmp網(wǎng)關(guān)專輸

26、層tcpudp網(wǎng)絡(luò)層picmparp （地址解析協(xié)議）rarp :路由器、三層交換機(jī)致?lián)溌穼觘thernet ieee802.3 fdiditoken-ring/ieee802.5arcnetppp/slip網(wǎng)橋、交換機(jī)物理層中繼器、集線器internet及應(yīng)用internet地址格式：域名格式，ip地址格式2.解決ip地址短缺問題：長(zhǎng)期（使用 ipv6）,短期（使用網(wǎng)絡(luò)地址翻譯技術(shù)nat：在子網(wǎng)內(nèi)部使用局部地址，外部使用少量的全局地址，通過路由器進(jìn)行內(nèi)部地址和外部地址的轉(zhuǎn)換）3.ipv6 : 16個(gè)字節(jié)的ip地址長(zhǎng)度（40個(gè)字節(jié)的首部長(zhǎng)度？）4.服務(wù)端口： 0 1023公共端口； 1024

27、 65535注冊(cè)登記端口5.internet高層協(xié)議及其端口：udpdns: 53;tcpftp 數(shù)據(jù)連接：20,控制連接：21; telnet: 23; smtp: 25; hiip: 80; pop3: 110;發(fā) smtp 收 smtp+pop3六、信息安全1 .信息安全5要素:機(jī)密性，完整性，可用性，可控性，可審查性。2 .加密技術(shù)：對(duì)稱加密（私人密鑰加密）：數(shù)據(jù)加密標(biāo)準(zhǔn)（des） +三重des + rc-5 +國(guó)際數(shù)據(jù)加密算法 （idea） +高級(jí)加密標(biāo)準(zhǔn)（aes）。非對(duì)稱加密（公開密鑰加密，比如rsa算法）：加密模型+認(rèn)證模型。3 .pki: 一種遵循既定標(biāo)準(zhǔn)的密鑰管理平臺(tái)，能夠?yàn)?/p>

28、所有網(wǎng)絡(luò)應(yīng)用提供加密和數(shù)字簽名等密碼服務(wù)及所必需的密鑰和證 書管理體系，必須具有權(quán)威認(rèn)證機(jī)構(gòu)、數(shù)字證書庫(kù)、密鑰備份和恢復(fù)系統(tǒng)、證書作廢系統(tǒng)、應(yīng)用接口。4 .網(wǎng)絡(luò)安全的威脅：被攻擊的目標(biāo)（計(jì)算機(jī)存儲(chǔ)著國(guó)家、機(jī)構(gòu)、組織的秘密信息或個(gè)人的隱私）；軟件規(guī)模的膨脹容易使系統(tǒng)存在缺陷；信息傳輸?shù)陌踩源嬖陔[患；網(wǎng)絡(luò)協(xié)議本身的漏洞也會(huì)引發(fā)安全問題5 .網(wǎng)絡(luò)安全:運(yùn)行系統(tǒng)安全，信息系統(tǒng)的安全，信息傳播的安全，信息內(nèi)容的安全6 .網(wǎng)絡(luò)的安全威脅：物理威脅,網(wǎng)絡(luò)攻擊，身份鑒別，編程威脅，系統(tǒng)漏洞7 .網(wǎng)絡(luò)的信息安全：信息的存儲(chǔ)安全（用戶的標(biāo)識(shí)與驗(yàn)證，用戶存取權(quán)限限制，系統(tǒng)安全監(jiān)控，計(jì)算機(jī)病毒防治，數(shù)據(jù)的加密，計(jì)算

29、機(jī)網(wǎng)絡(luò)安全）；信息的傳輸安全（鏈路加密，節(jié)點(diǎn)加密，端到端加密）8 .防火墻:建立在內(nèi)外網(wǎng)絡(luò)邊界的過濾封鎖機(jī)制，防止不良數(shù)據(jù)包進(jìn)出被保護(hù)的內(nèi)部網(wǎng)絡(luò)9 .防火墻的分類：包過濾型（直接轉(zhuǎn)發(fā)報(bào)文，對(duì)用戶透明），應(yīng)用代理網(wǎng)關(guān)型（通過服務(wù)器建立連接），狀態(tài)檢測(cè)型（建立狀態(tài)連接表，跟蹤檢測(cè)每一個(gè)會(huì)話狀態(tài)）10 .典型防火墻的體系結(jié)構(gòu)：網(wǎng)絡(luò)級(jí)（包過濾，狀態(tài)檢測(cè)）；應(yīng)用級(jí)（雙穴主機(jī)，屏蔽主機(jī)，屏蔽子網(wǎng)）。 包過濾路由器（在網(wǎng)絡(luò)層對(duì)進(jìn)出內(nèi)部網(wǎng)絡(luò)所有信息進(jìn)行分析限制）； 雙宿主主機(jī)（代理服務(wù)器軟件在雙宿主主機(jī)上運(yùn)行，每一個(gè)接口連接不同網(wǎng)段）； 被屏蔽主機(jī)（由過濾路由器和應(yīng)用網(wǎng)管組成，包過濾+代理服務(wù)，內(nèi)網(wǎng)和外網(wǎng)雙重

30、保障）； 被屏蔽子網(wǎng)（由兩個(gè)包過濾路由器和一個(gè)應(yīng)用網(wǎng)關(guān)組成，最安全的防火墻系統(tǒng)）11.安全需求分類：物理線路安全（機(jī)房）、網(wǎng)絡(luò)安全（入侵卞測(cè)）、系統(tǒng)安全（漏洞補(bǔ)?。?、應(yīng)用安全（數(shù)據(jù)庫(kù)）2015.5七、數(shù)據(jù)結(jié)構(gòu)&算法基礎(chǔ)數(shù)組與線性表1 .數(shù)據(jù)結(jié)構(gòu):數(shù)據(jù)元素的集合及元素間的相互關(guān)系和構(gòu)造方法2 .線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ),鏈?zhǔn)酱鎯?chǔ)3 .單鏈表節(jié)點(diǎn):typedef struct nodeint data; struct node *link;node,*linklist;4 .雙向鏈表:每個(gè)節(jié)點(diǎn)有兩個(gè)指針，分別指出直接前驅(qū)和直接后繼5 .循環(huán)鏈表:尾節(jié)點(diǎn)指針指向第一個(gè)節(jié)點(diǎn)/頭節(jié)點(diǎn)6 .靜態(tài)鏈表:借

31、助數(shù)組來描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7 .崔:filo。初始化 initstack（s）;判空 stackempty（s）;入棧 push（s,x）;出棧 pop（s）;讀棧頂 top（s）-順序 + 鏈?zhǔn)酱鎯?chǔ)8 .隊(duì)列:fifo,尾入頭出。初始化 initqueue（q）;判空empty（q）;入隊(duì)enqueue（q,x）;出隊(duì)dequeue（q）;讀隊(duì)頭元 素frontque（q）-順序存儲(chǔ)+鏈?zhǔn)酱鎯?chǔ)9 .由：僅由字符構(gòu)成的有限序列，是取值范圍受限的線性表-串的模式匹配 kmp算法10 .數(shù)組:定長(zhǎng)線性表在維數(shù)上的擴(kuò)張，一般不做插入刪除運(yùn)算11 .矩陣:特殊矩陣（元素分布有一定的規(guī)律：對(duì)稱矩陣

32、、三角矩陣、對(duì)角矩陣） ；稀疏矩陣（非零元素遠(yuǎn)少于零元素且分布無規(guī)律，用三元組存儲(chǔ)（行號(hào)，列號(hào)，值）12 .廣義表:n個(gè)表元素組成的有限序列（表中有表），是線性表的推廣。通常使用遞歸形式進(jìn)行定義。eg: ls1=（a, （b, c）, （d, e）。表頭（表中第一個(gè)元素）；表尾（表中除去表頭剩下的部分）基本操作：取表頭 head（ls1）=a,取表尾 tail（ls1）= （b, c）, （d, e）樹與二叉樹1 .批：遞歸的，元素之間有明顯的層次關(guān)系2 .二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：typedef struct bitnodeint data; struct bitnode *lchild, *r

33、child;bitnode, *bitree;3 .完全二叉樹：滿二叉樹最后少一些葉子。（應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)，一般二叉樹則應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）4 .二叉樹的遍歷：先序遍歷，中序遍歷，后序遍歷，層序遍歷（利用隊(duì)列，每次出同一層的節(jié)點(diǎn)時(shí)進(jìn)他們的子節(jié)點(diǎn)層）5 .線索二叉樹:加上線索（直接前驅(qū)和直接后繼）的二叉樹6 .最優(yōu)二叉樹（哈夫曼樹）:一類帶權(quán)路徑長(zhǎng)度最短的樹7 .樹的存儲(chǔ)結(jié)構(gòu)：雙親表示法（順序存儲(chǔ)）；孩子表示法（鏈?zhǔn)酱鎯?chǔ)）；孩子兄弟表示法（鏈?zhǔn)酱鎯?chǔ)，左孩子、右兄弟）8 .二叉排序樹:左子樹上所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值，右子樹上所有節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值9 .平衡二叉樹（avl樹）：左子樹和右子

34、樹高度之差的絕對(duì)值不超過110.b_樹（m階）：每個(gè)節(jié)點(diǎn)子樹個(gè)數(shù)=m ,根節(jié)點(diǎn)子樹個(gè)數(shù)=0或=2,其他節(jié)點(diǎn)子樹個(gè)數(shù) =0或=m/211 .哈希表（hash table,散列表）:通過哈希函數(shù)得到記錄的存儲(chǔ)地址；定長(zhǎng)按一定函數(shù)規(guī)律存放數(shù)據(jù)；哈希地址+關(guān)鍵字12 .構(gòu)造哈希函數(shù)：直接定址法,數(shù)字分析法，平方取中法，折疊法，隨機(jī)數(shù)法，除留余數(shù)法13 .哈希表解決沖突辦法：開放定址法,鏈地址法，再哈希法，建立公共溢出區(qū)。圖1 .圖：一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)數(shù)目沒有任何限制。（帶權(quán)網(wǎng)：邊帶權(quán)值的圖）2 .圖的表示:g=（v , e）; v:頂點(diǎn)的集合；e：邊的集合3 .相關(guān)概念:圖（完全圖，路徑圖，

35、子圖，網(wǎng)圖）； 無向圖（度，連通，連通分量）；有向圖（強(qiáng)連通，強(qiáng)連通分量，出 /入度）4 .圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣（n行、n歹u）,鄰接鏈表（n個(gè)頭節(jié)點(diǎn)，2*e個(gè)鄰接節(jié)點(diǎn)）5 .圖的遍歷：深度優(yōu)先搜索dfs,廣度優(yōu)先搜索 bfs6 .牛成樹:極小連通子圖，針對(duì)連通圖7 .最小牛成樹算法（權(quán)值之和最小的牛成樹）:布魯姆算法（在相鄰邊的基礎(chǔ)上求最小，與邊數(shù)無關(guān)，適于邊稠密的 網(wǎng)）；克魯斯科爾算法（在不構(gòu)成環(huán)的基礎(chǔ)上找最小邊直至連通，與頂點(diǎn)數(shù)無關(guān)，適于邊稀疏的網(wǎng)）8 .aov網(wǎng):有向圖中頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)間的優(yōu)先關(guān)系9 .拓?fù)渑判?將 aov網(wǎng)中所有頂點(diǎn)按優(yōu)先順序排成一個(gè)線性序列的過程1o

36、aoe網(wǎng):有向圖中有向邊表示活動(dòng)，邊上的權(quán)值表示該活動(dòng)持續(xù)的時(shí)間11 .關(guān)鍵路徑:從源點(diǎn)到匯點(diǎn)的路徑中長(zhǎng)度最長(zhǎng)的12 .最短路徑:從源點(diǎn)到其余各頂點(diǎn)的最短路徑-迪杰斯克拉算法算法基礎(chǔ)1 .算法的特性：有窮性,確定性，可行性，輸入（可以沒有），輸出（至少一個(gè)）2 .算法的表示方法：自然語言,流程圖，程序設(shè)計(jì)語言，偽代碼查找與排序1 .平均查找長(zhǎng)度：關(guān)鍵字和給定值進(jìn)行過比較的記錄個(gè)數(shù)的平均值2 .靜態(tài)查找方法：順序查找;折半查找；分塊查找3 .動(dòng)態(tài)查找:二叉排序樹（二叉查找樹）。表結(jié)構(gòu)本身在查找過程中是動(dòng)態(tài)生成的4 .哈希查找:用散列表來存儲(chǔ)和查找，0（1）5 .簡(jiǎn)單排序:時(shí)間復(fù)雜度 0（n2）,

37、空間復(fù)雜度0（1）直接插入排序。插入第i個(gè)時(shí)，前i-1個(gè)已排序好。若元素基本有序，時(shí)間復(fù)雜度為0（n）簡(jiǎn)單選擇排序。第i個(gè)依次與后面每個(gè)元素比較排序，每次循環(huán)確定一個(gè)極值，不穩(wěn)定冒泡排序。相鄰兩個(gè)比較排序，每次循環(huán)確定一個(gè)極值6.高端內(nèi)部排序: 希爾排序。增量分組法。先將整體分割的序列分別進(jìn)行直接插入排序；再對(duì)整個(gè)序列直接插入排序一次 堆排序。建立初始堆輸出并刪除堆頂關(guān)鍵字，再建立新堆得到新的關(guān)鍵字依次輸出快速排序?！皹休S”。將整個(gè)記錄分割成兩部分，兩個(gè)指針分別指向?qū)?yīng)部分的兩端，往中間移動(dòng)比較排序，遞歸 歸并排序。將若干個(gè)有序序列合并為新的有序序列。先分組排序，再將組數(shù)逐漸減小，最終到整體排

38、序 基數(shù)排序。按組成關(guān)鍵字的各個(gè)數(shù)位的值進(jìn)行排序類別持序方法時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性平均情況最好情況最壞情況輔助存儲(chǔ)入序-插產(chǎn)直接插入5嘮5嘮0(1)穩(wěn)定shell排序o(nlcxn)5嶗0(1)不穩(wěn)定擇序 選排直接選擇3吟5嶗。解）0(1)不穩(wěn)定堆摔序ociilog?n)cxnkjgn)ofnlogjn)0(1)不穩(wěn)定(捌序冒泡排序3庶）cxn)5%51)穩(wěn)定快速排序o(nl臉 n)w)ex血唯m不穩(wěn)定婦并排序o(nlcjg?n)o(nlcg?n)o(nlog?n)o(n)穩(wěn)定基數(shù)排序。（如 0）。(儀r+n)o(rd-n)穩(wěn)定注;塔敷排洋的星條屢中，代表關(guān)健享的基歌.d代表長(zhǎng)建，n代表兼

39、稷字的個(gè)毅.常用算法1 .遞歸算法求0:展開法（將等式依次展開）；代換法（用所猜測(cè)的值代替函數(shù)的解）；遞歸樹法；主方法；2 .分治法:將一個(gè)難以直接解決的大問題分解成一些規(guī)模較小的小問題各個(gè)擊破。步驟：分解，求解，合并3 .動(dòng)態(tài)規(guī)劃法（將待求解問題分解成若干子問題分別求解,再根據(jù)子問題的解得到原問題的解；分解得到的子問題往往 不是獨(dú)立的）：找出最優(yōu)解性質(zhì)并刻畫其結(jié)構(gòu)特性；遞歸地定義最優(yōu)解的值；以自底向上的方式求出最優(yōu)值；根據(jù)最 優(yōu)值構(gòu)造最優(yōu)解。顯著特征是滿足最優(yōu)性原理，即原問題的最優(yōu)解包含其子問題的最優(yōu)解。4 .貪心算法（僅根據(jù)當(dāng)前已有信息做出選擇,重點(diǎn)考慮局部最優(yōu)以達(dá)到全局最優(yōu)）：最優(yōu)子結(jié)構(gòu)

40、；貪心選擇性質(zhì)5 .回溯法（以深度優(yōu)先的方式系統(tǒng)地搜索問題）:定義問題的解空間；確定解空間結(jié)構(gòu)；深度優(yōu)先的方式搜索解空間6 .分支限界法（以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間）:隊(duì)列式分支限界法；優(yōu)先隊(duì)列式分支限界法7 .算法補(bǔ)充:迭代法、窮舉搜索法、遞推法（分支界限法和回溯法都是對(duì)窮舉法的改進(jìn)）8 .概率算法（把隨機(jī)性的選擇加入到算法中,允許較小概率的錯(cuò)誤來提高運(yùn)行效率）：數(shù)值概率算法；蒙特卡羅算法；拉斯維加斯算法；舍伍德算法9 .近似算法衡量標(biāo)準(zhǔn)：算法的時(shí)間復(fù)雜度;解的近似程度。（放棄求最優(yōu)解，而用近似最優(yōu)解代替）10 .np完全性理論:研究計(jì)算問題難易以及一類特殊的難解問題的理論1

41、1 .p類問題:能夠以 0（nk）的時(shí)間運(yùn)行一個(gè)確定性算法得到準(zhǔn)確答案12 .np類問題:能夠以 0（nk）的時(shí)間運(yùn)行一個(gè)不確定性算法得到準(zhǔn)確答案13 .np完全問題：能夠證明用多項(xiàng)式時(shí)間的確定性算法得到準(zhǔn)確答案常用算法典型應(yīng)用補(bǔ)充描述分治法歸并排序、快速排序貪心法最小生成樹、單點(diǎn)起最短路徑（布魯斯卡爾，迪杰斯特拉）、哈夫曼算法“溯法n皇后問題2015.5、走迷宮問題,態(tài)規(guī)劃算法最優(yōu)二叉樹、圖中每對(duì)節(jié)點(diǎn)間最短路徑、背包算法、lcs最長(zhǎng)公共子序列問題金支界限法分支界限技術(shù)求解分配問題八、程序語言基礎(chǔ)知識(shí)程序語言概述1 .編程語言之間的翻譯形式：匯編,解釋，編譯。2 .程序設(shè)計(jì)語言的定義：語法.語

42、義，語用。3程序語言的分類：命令式程序設(shè)計(jì)語言:fortran, pascal, c語言；面向?qū)ο蟮某绦蛟O(shè)計(jì)語言（ smaltalk ,c+, java）;函數(shù)式程序設(shè)計(jì)語言（lisp）;邏輯型程序設(shè)計(jì)語言（ prolog）。4 .程序語言的基本成分：數(shù)據(jù),運(yùn)算，控制，傳輸。5 .匯編語言源程序：指令語句,偽指令語句，宏指令語句。6 .匯編程序:將匯編語言所編寫的源程序翻譯成機(jī)器指令程序。語言處理程序1編譯過程:源程序一詞法分析一語法分析一語義分析一生成中間代碼一代碼優(yōu)化一生成目標(biāo)代碼一目標(biāo)代碼。（全每個(gè)階段都有符號(hào)表管理、出錯(cuò)處理）2 .解釋程序:分析部分：詞法分析、語法分析、語義分析一中間

43、代碼;解釋部分：解釋執(zhí)行中間代碼。3 .中間代碼的表示：逆波蘭式（后綴表達(dá)式）、四元式、三元式、樹。共同特征：代碼的方式與具體的機(jī)器無關(guān)。4 .編譯與解釋方式的比較：前者效率高;后者更具有靈活性和可移植性。5 .程序錯(cuò)誤:靜態(tài)錯(cuò)誤，出現(xiàn)在編譯階段，分為：語法錯(cuò)誤和靜態(tài)語義錯(cuò)誤。動(dòng)態(tài)語義錯(cuò)誤，發(fā)生在運(yùn)行階段。文法和有限自動(dòng)機(jī)1 .狀態(tài)轉(zhuǎn)換圖的表示習(xí)慣：初始 /非終止?fàn)顟B(tài)用表示，終止?fàn)顟B(tài)*2 .正規(guī)式（正規(guī)表達(dá)式）、正規(guī)集： 或r|s, l（r） u l（s）;連接r s, l（r）l（s）; 閉包r , （l（r）3 .有限自動(dòng)機(jī):確定性有限自動(dòng)機(jī) （dfa）只能進(jìn)入唯一狀態(tài)；不確定性有限自動(dòng)機(jī)

44、（nfa）可以進(jìn)入任意狀態(tài)；九、標(biāo)準(zhǔn)化和軟件知識(shí)產(chǎn)權(quán)標(biāo)準(zhǔn)化基礎(chǔ)知識(shí)1標(biāo)準(zhǔn):對(duì)重復(fù)性事務(wù)和概念所做的統(tǒng)一規(guī)定2 .標(biāo)準(zhǔn)化對(duì)象:具體對(duì)象（需要指定標(biāo)準(zhǔn)的具體事務(wù)）；總體對(duì)象（各種具體對(duì)象的全體所構(gòu)成的整體）3 .標(biāo)準(zhǔn)化活動(dòng)過程：制定 一實(shí)施一更新（周期不超過 5年，2005.11）4標(biāo)準(zhǔn)的分類：根據(jù)適用范圍（國(guó)際標(biāo)準(zhǔn)，國(guó)家標(biāo)準(zhǔn)，區(qū)域標(biāo)準(zhǔn)，行業(yè)標(biāo)準(zhǔn)，企業(yè)標(biāo)準(zhǔn)，項(xiàng)目規(guī)范）；根據(jù)標(biāo)準(zhǔn)的性質(zhì)（技術(shù)標(biāo)準(zhǔn)，管理標(biāo)準(zhǔn)，工作標(biāo)準(zhǔn)）；根據(jù)標(biāo)準(zhǔn)化的對(duì)象和作用 （基礎(chǔ)標(biāo)準(zhǔn)，產(chǎn)品標(biāo)準(zhǔn)，方法標(biāo)準(zhǔn)，安全標(biāo)準(zhǔn)，衛(wèi)生標(biāo)準(zhǔn)，環(huán)境保護(hù)標(biāo)準(zhǔn)，服務(wù)標(biāo)準(zhǔn)）；根據(jù)法律的約束性（強(qiáng)制性標(biāo)準(zhǔn)，推薦性標(biāo)準(zhǔn)）5 .信息技術(shù)標(biāo)準(zhǔn)化：信息編碼標(biāo)準(zhǔn)化（如

45、ascii碼）；漢字編碼標(biāo)準(zhǔn)化（如 gb2312）;軟件工程標(biāo)準(zhǔn)化（基礎(chǔ)標(biāo)準(zhǔn)，開發(fā)標(biāo)準(zhǔn)，文檔標(biāo)準(zhǔn)，管理標(biāo)準(zhǔn)）6 .權(quán)威國(guó)際標(biāo)準(zhǔn)化組織：國(guó)際標(biāo)準(zhǔn)化組織（ iso）;國(guó)際電工委員會(huì)（iec）知識(shí)產(chǎn)權(quán)基礎(chǔ)知識(shí)1知識(shí)產(chǎn)權(quán):人們基于自己的智力活動(dòng)創(chuàng)造的成果和經(jīng)營(yíng)管理活動(dòng)中的經(jīng)驗(yàn)、知識(shí)，而依法享有的權(quán)利2知識(shí)產(chǎn)權(quán)的分類二工業(yè)產(chǎn)權(quán)（專利、實(shí)用新型、工業(yè)品外觀設(shè)計(jì)、商標(biāo)、服務(wù)標(biāo)記、廠商名稱、產(chǎn)地標(biāo)記、原產(chǎn)品名 稱、制止不正當(dāng)競(jìng)爭(zhēng)等）；著作權(quán)（也叫版權(quán)，不需登記或標(biāo)注版權(quán)標(biāo)志就能得到保護(hù)2005.11）3 .知識(shí)產(chǎn)權(quán)的特點(diǎn)：4形性,雙重性，確認(rèn)性，獨(dú)占性，地域性，時(shí)間性4 .知識(shí)產(chǎn)權(quán)保護(hù)權(quán)限：客體類型權(quán)利類型保

46、護(hù)期限公民作品署名權(quán)、修改權(quán)、保護(hù)作品完整權(quán)沒有限制發(fā)表權(quán)、使用權(quán)和獲得報(bào)酬權(quán)作者終生及其死亡后的 50年（第50年的12月31日）單位作品發(fā)表權(quán)、使用權(quán)和獲得報(bào)酬權(quán)50年（首次發(fā)表后的第 50年的12月31日），若其間 未發(fā)表，不受保護(hù)公民軟件產(chǎn)品署名權(quán)、修改權(quán)沒有限制發(fā)表權(quán)、復(fù)制權(quán)、發(fā)行權(quán)、出租權(quán)、信息網(wǎng)絡(luò)傳播 權(quán)、翻譯權(quán)、使用許可權(quán)、獲得報(bào)酬權(quán)、轉(zhuǎn)讓權(quán)作者終生及其死亡后的 50年（第50年的12月31 日）。對(duì)于合作開發(fā)的，則以最后死亡的作者為準(zhǔn)單位軟件產(chǎn)品發(fā)表權(quán)、復(fù)制權(quán)、發(fā)行權(quán)、出租權(quán)、信息網(wǎng)絡(luò)傳播 權(quán)、翻譯權(quán)、使用許可權(quán)、獲得報(bào)酬權(quán)、轉(zhuǎn)讓權(quán)著作權(quán)的保護(hù)期為 50年（首次發(fā)表后的第 5

47、0年的12 月31日），若50年內(nèi)未發(fā)表的，/、予保護(hù)注冊(cè)商標(biāo)有效期10年（若注冊(cè)人死亡或倒閉 1年后，未轉(zhuǎn)移則 可注銷。期滿后6個(gè)月內(nèi)必須續(xù)注）發(fā)明專利權(quán)保護(hù)期為20年（從申請(qǐng)日開始）實(shí)用新型和外觀設(shè)計(jì)專利權(quán)保護(hù)期為10年（從申請(qǐng)日開始）商業(yè)秘密不確定，公開后公眾可用5.知識(shí)產(chǎn)權(quán)人確定方法：情況說明判斷說明歸屬作職利用單位的物質(zhì)技術(shù)條件進(jìn)行創(chuàng)作，并由單位承擔(dān)責(zé)任的除署名權(quán)外，其他著作權(quán)歸單位品務(wù)有合同約定，具著作權(quán)屬于單位除署名權(quán)外，其他著作權(quán)歸單位作其他作者擁有著作權(quán)，單位有權(quán)在業(yè)務(wù)范圍內(nèi)品優(yōu)先使用軟職屬于本職工作中明確規(guī)定的開發(fā)目標(biāo)單位享有著作權(quán)件不 乍 品屬于從事本職工作活動(dòng)的結(jié)果使用

48、了單位資金、專用設(shè)備、未公開的傳息等物質(zhì)、技術(shù)條件， 并由單位或組織承擔(dān)責(zé)任的軟件作 品、托創(chuàng)作有合同約定，著作權(quán)歸委托方委托方合同中未約定著作權(quán)歸屬軟 件合作“發(fā)只進(jìn)行組織、提供咨詢意見、物質(zhì)條件或者進(jìn)行其他輔助工作/、學(xué)有著作權(quán)共同創(chuàng)作的共同享有，按人頭比例成果可分割的，可 分開申請(qǐng)商標(biāo)誰先申請(qǐng)誰擁有（除知名商標(biāo)的非法搶注）；同時(shí)申請(qǐng)，則根據(jù)誰先使用（需提供證據(jù)）； 無法提供證據(jù)，協(xié)商歸屬，無效時(shí)使用抽簽（但不可不確定）；誰先申請(qǐng)誰擁有；誰先使用誰擁有；同時(shí)申請(qǐng)則協(xié)商歸屬，但不能夠同時(shí)駁回雙方的專利申請(qǐng)；6 .計(jì)算機(jī)軟件著作權(quán)受保護(hù)條件：獨(dú)立創(chuàng)作,可被感知，邏輯合理7 .計(jì)算機(jī)軟件著作權(quán)的

49、權(quán)利：人身權(quán)（發(fā)表權(quán)，署名權(quán)）；著作財(cái)產(chǎn)權(quán)（使用權(quán)，復(fù)制權(quán)，修改權(quán)，發(fā)行權(quán)，翻譯權(quán),注釋權(quán)，信息網(wǎng)絡(luò)傳播權(quán)，出租權(quán)，使用許可權(quán)，獲得報(bào)酬權(quán)，轉(zhuǎn)讓權(quán)）8 .軟件經(jīng)濟(jì)權(quán)利的許可使用：獨(dú)占許可使用,獨(dú)家許可使用，普通許可使用，法定許可使用，強(qiáng)制許可使用；9 .計(jì)算機(jī)軟件著作權(quán)特點(diǎn)：技術(shù)性,依賴性，多樣性，運(yùn)行性10 .軟件著作權(quán)侵權(quán)的法律責(zé)任：民事責(zé)任,行政責(zé)任，刑事責(zé)任11 .商業(yè)秘密:部位公眾所知的、能為權(quán)利人帶來經(jīng)濟(jì)利益、具有實(shí)用性并經(jīng)權(quán)利人采取保密措施的技術(shù)信息和經(jīng)營(yíng)信息；包括經(jīng)營(yíng)秘密和技術(shù)秘密12 .商業(yè)秘密的構(gòu)成條件：未公開性,實(shí)用性，保密性13 .授予專利權(quán)的條件：新穎性,創(chuàng)造性，實(shí)用

50、性14 .軟件企業(yè)應(yīng)建立的合同規(guī)范：勞動(dòng)合同關(guān)系,軟件開發(fā)合同，軟件許可使用（或轉(zhuǎn)讓）合同十、多媒體多媒體基本概念1.媒蟲 感覺媒體（使人產(chǎn)生感覺的媒體），表示媒體（傳輸感覺媒體的中介），表現(xiàn)媒體（進(jìn)行信息輸入和輸出的媒 體，表現(xiàn)或獲取信息；鼠鍵、顯示器），存儲(chǔ)媒體（存儲(chǔ)表示媒體的物理介質(zhì)），傳輸媒體（傳輸表示媒體的物理介質(zhì)）2多媒體的特性：多樣性,集成性，交互性，非線性，實(shí)時(shí)性，信息使用的方便性，信息結(jié)構(gòu)的動(dòng)態(tài)性3虛擬現(xiàn)實(shí):運(yùn)用計(jì)算機(jī)對(duì)現(xiàn)實(shí)世界進(jìn)行全面仿真，創(chuàng)建與現(xiàn)實(shí)社會(huì)類似的環(huán)境，通過多種傳感設(shè)備使用戶“投入到該 環(huán)境中”，實(shí)現(xiàn)用戶與該環(huán)境直接進(jìn)行自然交互4.虛擬現(xiàn)實(shí)技術(shù)的特征：多感知（聽

51、覺感知、力覺感知、觸覺感知、運(yùn)動(dòng)感知、味覺感知、嗅覺感知），沉浸（用戶感受到的模擬環(huán)境的真實(shí)程度），交互（用戶對(duì)模擬環(huán)境內(nèi)物體的可操作程度，從環(huán)境得到反饋的自然程度）5虛擬現(xiàn)實(shí)的分類：桌面虛擬現(xiàn)實(shí),完全沉浸的虛擬現(xiàn)實(shí)，增強(qiáng)現(xiàn)實(shí)性的虛擬現(xiàn)實(shí)，分布式虛擬現(xiàn)實(shí)尸日1 .聲音感覺的三個(gè)指標(biāo)：音量,音調(diào)，音色2 .聲音信號(hào)的數(shù)字化：采木量化，編碼。 a? d互轉(zhuǎn)3 .數(shù)字語音的數(shù)據(jù)壓縮方法：波形編碼,參數(shù)編碼，混合編碼4 .聲音合成:語音合成（發(fā)音參數(shù)合成、聲道模型參數(shù)合成、波形編輯合成），音樂合成5 .midi （ musical instrument digital interface ,樂器數(shù)字接

52、口）：數(shù)字音樂的國(guó)際標(biāo)準(zhǔn)圖形和圖像1 .色彩三要素：亮度,色調(diào)，色飽和度2 .彩色空間:rgb , cmy , yuv等3 .圖形數(shù)據(jù)表示形式：矢量圖形（用數(shù)學(xué)的方式描述圖像），位圖圖像（用像素點(diǎn)來描述的圖）4 .圖像的屬i生:分辨率，圖像深度，真彩色和偽彩色5 .圖像的數(shù)據(jù)量：圖像的總像素 *圖像深度/86 .數(shù)據(jù)壓縮:有損壓縮（壓縮過程中損失一定信息），無損壓縮（行程長(zhǎng)度編碼，增量調(diào)制編碼，霍夫曼編碼）7 .多媒體數(shù)據(jù)壓縮編碼標(biāo)準(zhǔn)：jpeg, mpeg, h.261 （mpeg1:mp3 , mpeg2:dvd , mpeg7:多媒體內(nèi)容描述接口）動(dòng)畫和視頻1 .動(dòng)畫:實(shí)時(shí)動(dòng)畫（用各種算法

53、來實(shí)現(xiàn)運(yùn)動(dòng)物體的運(yùn)動(dòng)控制），矢量動(dòng)畫（由矢量圖衍生出的動(dòng)畫形式），二維動(dòng)畫（對(duì)傳統(tǒng)動(dòng)畫的一個(gè)改進(jìn)），三維動(dòng)畫（根據(jù)三維數(shù)據(jù)模型）2 .彩魚審視制式： ntsc 制，pal 制，secam 制 yuv、yiq、ycbcr3數(shù)字視頻標(biāo)準(zhǔn)：采樣頻率,分辨率，數(shù)據(jù)量多媒體網(wǎng)絡(luò)1 .超文本（將文本中遇到的一些相關(guān)內(nèi)容通過鏈接組織在一起）三要素：節(jié)點(diǎn)，鏈，網(wǎng)絡(luò)2 .超媒體:用超文本方式組織和處理多媒體信息3 .流媒體:在網(wǎng)絡(luò)中使用流式傳輸技術(shù)的連續(xù)時(shí)基載體。信息經(jīng)過壓縮后放到專用流服務(wù)器上，邊下載，邊看/聽4 .多媒體計(jì)算機(jī)硬件系統(tǒng)：音頻卡,視頻卡，光盤驅(qū)動(dòng)器，掃描儀，光學(xué)字符閱讀器，觸摸屏，數(shù)字化儀，操

54、縱桿，繪圖儀、投影儀和激光視盤播放器5 .多媒體計(jì)算機(jī)軟件系統(tǒng)：多媒體操作系統(tǒng),多媒體應(yīng)用軟件的開發(fā)工具，多媒體應(yīng)用軟件十一、系統(tǒng)開發(fā)基礎(chǔ)軟件工程基礎(chǔ)1.軟件工程：指應(yīng)用計(jì)算機(jī)科學(xué)、數(shù)學(xué)及管理科學(xué)等原理，以工程化的原則和方法來解決軟件工程的問題。目的是提高 軟件生產(chǎn)率，提高軟件質(zhì)量，降低軟件成本。2軟件生存周期：可行性分析與項(xiàng)目開發(fā)計(jì)劃、需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測(cè)試、維護(hù)3 .軟件生存周期模型：瀑布模型（按順序階段性開發(fā)），演化模型（先構(gòu)造一個(gè)初始版本再不斷改進(jìn)），螺旋模型（制定計(jì)劃、風(fēng)險(xiǎn)分析、實(shí)施工程、用戶評(píng)估） ，噴泉模型（重視用戶需求，允許各步驟交叉進(jìn)行） 瀑布模型：嚴(yán)格遵循

55、軟件生命周期各階段的固定順序，強(qiáng)調(diào)早期計(jì)劃及需求調(diào)查，但缺乏靈活性。 演化模型（快速原型模型）：在用戶的基本需求上，快速構(gòu)造出初始可運(yùn)行版本。減少因需求不明確的風(fēng)險(xiǎn)。 螺旋模型：綜合了瀑布模型和演化模型的優(yōu)點(diǎn)。分為4個(gè)流程：制定計(jì)劃、風(fēng)險(xiǎn)分析、實(shí)施工程、客戶評(píng)價(jià)。 噴泉模型（water fountain model ）:主要用于描述面向?qū)ο蟮拈_發(fā)過程。體現(xiàn)了面向?qū)ο箝_發(fā)過程的迭代和無間隙特征。無間隙：指在開發(fā)活動(dòng)（如分析、設(shè)計(jì)、編碼）之間不存在明顯的邊界。 v模型（v model）:傳統(tǒng)瀑布模型的變形，強(qiáng)調(diào)測(cè)試過程應(yīng)如何與分析、設(shè)計(jì)等過程相關(guān)聯(lián)。 增量模型（incremental model）:增量模