二級(jí)公共基礎(chǔ)速學(xué)教程

1算法的復(fù)雜 數(shù)據(jù)結(jié) 邏輯結(jié)構(gòu)和結(jié) 線性結(jié)構(gòu)和非線性結(jié) 隊(duì) 鏈

二叉 二叉樹概念及其基本性 查 順序查 二分法查 排 2程序設(shè)計(jì)的方法與風(fēng) 結(jié)構(gòu)化程序設(shè)

面向?qū)ο蠓?3軟件工程基本概 軟件生命周 軟件設(shè) 軟件設(shè)計(jì)基本概 軟件設(shè)計(jì)的基本原

結(jié)構(gòu)化分析方 軟件測 軟件測試的目的和準(zhǔn) 軟件測試的方法和實(shí) 程序的調(diào) 4數(shù)據(jù)庫的基本概 數(shù)據(jù)庫系統(tǒng)的發(fā)展和基本特 數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié) 數(shù)據(jù)模型的基本概

關(guān)系模 關(guān)系代 數(shù)據(jù)庫設(shè)計(jì)與原 第1 數(shù)據(jù)結(jié)構(gòu)與算

表11。1-13②在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的關(guān)系，即數(shù)據(jù)的存③是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了數(shù)據(jù)元間的前后件關(guān)系，通常記為R。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成：B(D,R)例如，如果把一年四季看作一個(gè)數(shù)據(jù)結(jié)構(gòu)，則可表示成：B(D,R)D{春季,夏季,秋季,冬季}R{(春季,夏季),(夏季,秋季),(秋季,冬季由于數(shù)據(jù)元素在計(jì)算機(jī)空間中的位置關(guān)系可能與邏輯關(guān)系不同，因?yàn)榱吮硎敬娣旁谟?jì)算機(jī)空間中的各數(shù)據(jù)元間的邏輯關(guān)系（即前后件關(guān)系，在數(shù)據(jù)的結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元間的前后件關(guān)系的信息。元素ai的地址為：ADR(ai)ADR(a1)+(i1)k，ADR(a1)為第一個(gè)元素的地址，k代表每個(gè)元素占的字節(jié)數(shù)。棧3種：入棧、退棧與讀棧頂①入棧運(yùn)算：在棧頂位置插入一個(gè)新②退棧運(yùn)算：取出棧頂元素并賦給一個(gè)指定的變量③讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量隊(duì)列是只允許在一端進(jìn)行刪除，在另一端進(jìn)行插入的順序表，通常將允許刪除的這一端稱為隊(duì)頭允許插入的這一端稱為隊(duì)尾當(dāng)表中沒有元素時(shí)稱為空隊(duì)列。隊(duì)列的修改是依照先進(jìn)先出的原則進(jìn)行的，因此隊(duì)列也稱為先進(jìn)先出的線性表，或者后進(jìn)后出的線性表。例如：火車進(jìn)遂道，最先進(jìn)遂道的是火車頭，最后是火車尾而火車出遂道的時(shí)候也是火車頭先出，最后出的是火車尾有隊(duì)列：Q隊(duì)頭元素q1是最先入的元素，也是最先被刪除的元素。隊(duì)尾元素qn是進(jìn)先出”（FirstInFirstOut，簡FIFO）“后進(jìn)后出”（LastInLastOut，簡稱LILO）的線性表。隊(duì)列的順序結(jié)構(gòu)一般采用隊(duì)列循環(huán)的形式。循環(huán)隊(duì)列s0表示隊(duì)列空s1frontrear表示隊(duì)列滿。計(jì)算循環(huán)隊(duì)列的元素個(gè)數(shù)：“尾指針減頭指針”，線性單鏈表中，HEAD稱為頭指針，HEADNULL（0）①非空二叉②每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹和右子樹。例如，一個(gè)中的族譜關(guān)系如圖11所示：AB，C；BD，E；CF典型的二叉11詳細(xì)講解二叉樹的基本概念121-11-2件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。例如，在圖1-1中，結(jié)點(diǎn)D，E，F(xiàn)均為葉子結(jié)點(diǎn)度C1D，E，F(xiàn)0A1B，C2D，E，F(xiàn)3二叉樹具有以下幾個(gè)性質(zhì)性質(zhì)2：深度為m的二叉樹最多有2m1個(gè)結(jié)點(diǎn)。性3：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為性4n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1，其中[log2n]log2n的整數(shù)部第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m1個(gè)結(jié)點(diǎn)。的最大層次或?yàn)閜，或?yàn)閜+1。完全二叉樹具有以下兩個(gè)性質(zhì)性5n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1性6：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層次（每一層k1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父編號(hào)②若2k≤n，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)2k+1≤n，則編號(hào)k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)2k+1；否時(shí)，仍需先根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。例如，對(duì)圖11中樹時(shí)，仍然先遍歷左子樹，然后根結(jié)點(diǎn)，最后遍歷右子樹。例如，對(duì)圖11樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后根結(jié)點(diǎn)。例如，對(duì)圖11先從第1個(gè)元素21開始進(jìn)行比較，比較結(jié)果與要查找的數(shù)據(jù)不相等，接著2個(gè)元素46進(jìn)行比較，以此類推，當(dāng)進(jìn)行到與第4個(gè)元素比較時(shí)，它們1X與線性表的中間項(xiàng)比較步驟3：如果X小于中間項(xiàng)的值，則性表的前半部分以二分法繼續(xù)步驟4：如果X大于中間項(xiàng)的值，則性表的后半部分以二分法繼續(xù)38大于中間項(xiàng)30的值，則性表[38，46，47，70]中繼續(xù)查找；接著與中間項(xiàng)比較，即與第2個(gè)元素46相比較，38小于46，則性表[38]中繼續(xù)查找，

在的情況下，冒泡排序需要比較次數(shù)為n(n1)/2①簡單插入排序法，情況需要n(n1)/2次比較①簡單選擇排序法，情況需要n(n1)/2次比較第2 程序設(shè)計(jì)基②③上對(duì)程序的結(jié)構(gòu)一目了然表21。2-1和輸入和輸輸入輸出比較簡單，這里就不作介紹模塊化和限制使用goto語句。①自頂向上：先考慮整體，再考慮細(xì)節(jié)；先考慮全局目標(biāo)，再考慮局部②逐步求精：對(duì)復(fù)雜問題應(yīng)設(shè)計(jì)一些子目標(biāo)作為過渡，逐步細(xì)化：把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的限制使goto語句：在程序開發(fā)過程中要限制使goto語句普通的結(jié)構(gòu)形式，按照程序中的語句行的先后支結(jié)構(gòu)，它包括簡單選擇和多分支循環(huán)結(jié)構(gòu)：根據(jù)給定的條件，判斷是否要重復(fù)執(zhí)行某一相同的或類似的通常把對(duì)象的操作也稱為方法或服務(wù)第3 軟件工程基表3- 軟件工3個(gè)要素：方法、工323-2軟件生命周期分為3個(gè)時(shí)期共8個(gè)階段，軟件定義期：包括問題定義、可行性研究和需求3個(gè)階段軟件開發(fā)期：包括概要設(shè)計(jì)、詳細(xì)4個(gè)階段運(yùn)行期：即運(yùn)行階段軟件生命周期各個(gè)階段的活動(dòng)可以有重復(fù)，執(zhí)行時(shí)也可以有迭代，如圖33-131中的軟件生命周期各階段的主要任務(wù)333-3①結(jié)構(gòu)設(shè)計(jì)定義軟件系統(tǒng)各主要部接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何①概要設(shè)計(jì)將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)、確定系統(tǒng)級(jí)接口、全局?jǐn)?shù)據(jù)②詳細(xì)設(shè)計(jì)確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算抽模塊獨(dú)立數(shù)據(jù)流圖數(shù)據(jù)字典數(shù)據(jù)字典中有4種類型的條目：數(shù)據(jù)流、數(shù)據(jù)項(xiàng)、數(shù)據(jù)和加工所有測試都應(yīng)追溯到用戶需求充分注意測試中的群集現(xiàn)象①靜態(tài)測試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。其中代碼檢查分為代碼、代碼走查、桌面檢查、靜態(tài)分析等具體形式；②動(dòng)態(tài)測試。靜態(tài)測試不實(shí)際運(yùn)行軟件，主要通過人工進(jìn)行分析。動(dòng)態(tài)測①白盒測試。白盒測試是把程序看成裝在一只透明的白盒子里，測試者完②黑盒測試。黑盒測試是把程序看成一只黑盒子，測試者完全不了解，或軟4個(gè)步驟，即單元測試、集成測試、驗(yàn)收測試和系統(tǒng)測試。單元測試是對(duì)軟件設(shè)計(jì)的最小單位模塊（程序單元）進(jìn)行正確性檢驗(yàn)測說明確認(rèn)的標(biāo)準(zhǔn)從錯(cuò)誤的外部表現(xiàn)形式入手，研究有關(guān)部分的程序，確定程②修改設(shè)計(jì)和代碼，以排進(jìn)行回歸測試，防止引進(jìn)新主要的調(diào)試方法有：強(qiáng)行排錯(cuò)法、回溯法和原因排除法3第4 數(shù)據(jù)庫設(shè)計(jì)基關(guān)于數(shù)據(jù)管理三個(gè)階段中的軟硬件背景及處理特點(diǎn)，簡單概414-1人具有高度的物理獨(dú)立性和①物理獨(dú)立性：當(dāng)數(shù)據(jù)的物理結(jié)構(gòu)（包括結(jié)構(gòu)、存取方式等）改變時(shí)，如設(shè)備的更換、物理的更換、存取方式改變等，應(yīng)用程序都不用改變。型分為型。數(shù)據(jù)模424-2③碼：惟一標(biāo)識(shí)實(shí)體的屬性集稱為碼ER模ERER②屬性表示法：在ER圖中用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬③ER圖中用菱形表示聯(lián)系，菱形內(nèi)寫上聯(lián)系名屬性：二維表中垂直方向的列稱為屬性，每一列有一個(gè)屬性名用戶使用的鍵稱為主鍵或主碼。表A中的某屬性集是某表B的鍵，則稱該屬值A(chǔ)的外鍵或外碼關(guān)系模型采用二維表來表示，二維7個(gè)性質(zhì)①二維表中元組個(gè)數(shù)是有限 元組個(gè)數(shù)有限性②二維表中元組均不相 元組的惟一性③二維表中元組的次序可以任意交 元組