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

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

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

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

結(jié)構(gòu)化分析方 軟件測 軟件測試的目的和準(zhǔn) 軟件測試的方法和實 程序的調(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è)計與原 第1 數(shù)據(jù)結(jié)構(gòu)與算

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

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