access公共基礎(chǔ)知識(shí)復(fù)習(xí)要點(diǎn)總(第一、二、三、四章)

1、公共基礎(chǔ)知識(shí)復(fù)習(xí)要點(diǎn)（橫線(xiàn)為要點(diǎn)） 第一章一、算法：1、基本概念：是解題方案的準(zhǔn)確而完整的描述。有可行性，確定性，有窮性，擁有足夠的情報(bào)四個(gè)基本特征。有數(shù)據(jù)對(duì)象的運(yùn)算和操作和算法的控制機(jī)構(gòu)?；镜倪\(yùn)算和操作包括算數(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。算法的控制機(jī)構(gòu)分為順序、選擇、循環(huán)三種基本結(jié)構(gòu)。2、復(fù)雜度：包括時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量用算法的基本運(yùn)算次數(shù)來(lái)度量?？臻g復(fù)雜度指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。二、數(shù)據(jù)結(jié)構(gòu)：1、數(shù)據(jù)邏輯結(jié)構(gòu)包含數(shù)據(jù)元素的信息和各數(shù)據(jù)元素之間的前后件關(guān)系。分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。線(xiàn)性結(jié)構(gòu)只有一個(gè)根節(jié)點(diǎn)，最多只有一個(gè)前件也最多有

2、一個(gè)后件。2、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)。 分為順序、鏈接，索引。不同的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)處理的效率是不同的。三、線(xiàn)性表及順序存儲(chǔ)結(jié)構(gòu)1、 線(xiàn)性表式最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。2、 順序存儲(chǔ)結(jié)構(gòu)有存儲(chǔ)空間是連續(xù)的和各數(shù)據(jù)元素在存儲(chǔ)空間中按邏輯順序依次存放的。3、 順序存儲(chǔ)結(jié)構(gòu)插入和刪除運(yùn)算不太方便，平均情況下要移動(dòng)一半的元素。順序存儲(chǔ)結(jié)構(gòu)適合小線(xiàn)性表和元素不常變動(dòng)的線(xiàn)性表，不適合元素經(jīng)常變動(dòng)的大線(xiàn)性表。四、棧和隊(duì)列1、棧限定在一端進(jìn)行插入和刪除的線(xiàn)性表。特點(diǎn)是先進(jìn)后出或后進(jìn)先出。2、隊(duì)列是允許在一端進(jìn)行插入而在另一端進(jìn)行刪除的線(xiàn)性表。特點(diǎn)是先進(jìn)先出或后

3、進(jìn)后出。3、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般是循環(huán)隊(duì)列的形式。4、循環(huán)隊(duì)列中元素個(gè)數(shù)計(jì)算公式。 尾指針頭指針時(shí) 尾指針-頭指針例如：容量為 15 的循環(huán)隊(duì)列中，頭指針為 6，尾指針為 9，循環(huán)隊(duì)列中共有（ ） 個(gè)元素。答:9-6=3尾指針頭指針時(shí) 尾指針-頭指針+容量.例如：容量為 15 的循環(huán)隊(duì)列中，頭指針為 6，尾指針為 3，循環(huán)隊(duì)列中共有（ ） 個(gè)元素。答:3-6+15=125、棧中元素個(gè)數(shù)的計(jì)算。棧頂-棧底+1例如：已知棧頂指針為 8，棧底指針為 1，棧中共有 8 個(gè)元素。五、線(xiàn)性鏈表1、線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線(xiàn)性鏈表。2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中存儲(chǔ)空間可以不連續(xù)，存儲(chǔ)順序與邏輯關(guān)系可以不一致。邏輯關(guān)

4、系可以不一致。3、鏈?zhǔn)酱鎯?chǔ)方式既可以表示線(xiàn)性結(jié)構(gòu)，也可以表示非線(xiàn)性結(jié)構(gòu)。4、帶鏈的棧和帶鏈的隊(duì)列。六、樹(shù)與二叉樹(shù)1、樹(shù)：是一種簡(jiǎn)單的非線(xiàn)性結(jié)構(gòu)。沒(méi)有前件的節(jié)點(diǎn)叫根結(jié)點(diǎn)。沒(méi)有后件的節(jié)點(diǎn)叫葉子結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)擁有的后件個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。根結(jié)點(diǎn)在第 1 層，所有子結(jié)點(diǎn)在下一層，樹(shù)的最大層次稱(chēng)為數(shù)的深度。樹(shù)在計(jì)算機(jī)中用多重鏈表表示2、二叉樹(shù)：（1）基本性質(zhì)：性質(zhì) 1：第k 層上最多 21 個(gè)結(jié)點(diǎn)。例如：深度為 5 的滿(mǎn)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)是(16)個(gè)。答：求第 5 層節(jié)點(diǎn) 共 25-1=16 個(gè)性質(zhì) 2：深度為 m 的二叉樹(shù)最多有 21 個(gè)結(jié)點(diǎn)。性質(zhì) 3：度為 0 的節(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為 2

5、的節(jié)點(diǎn)多一個(gè)。例如，已知度為 2 的節(jié)點(diǎn) 50 個(gè)，求葉子結(jié)點(diǎn)數(shù)（51）已知葉子結(jié)點(diǎn) 50 個(gè)，度為 1 的節(jié)點(diǎn) 50 個(gè)，求總結(jié)點(diǎn)數(shù)（50+50+49=149個(gè)）性質(zhì) 4:：n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，深度至少為 n +12（2）滿(mǎn)二叉樹(shù)和完全二叉樹(shù)：滿(mǎn)二叉樹(shù)：每一層上的節(jié)點(diǎn)數(shù)達(dá)到最大值，第K 層上有 21 個(gè)節(jié)點(diǎn)，深度為m的滿(mǎn)二叉樹(shù)有 21 個(gè)節(jié)點(diǎn)。完全二叉樹(shù)：除最后一層外，每一層上的節(jié)點(diǎn)數(shù)達(dá)到最大值，最后一層缺右邊的若干節(jié)點(diǎn)。完全二叉樹(shù)中已知總結(jié)點(diǎn)求葉子結(jié)點(diǎn)公式：總結(jié)點(diǎn)/2例如：完全二叉樹(shù)共有 700 個(gè)結(jié)點(diǎn)，則有（350）個(gè)葉子結(jié)點(diǎn)，度為 2 的節(jié)點(diǎn)(349)個(gè)，度為 1 的節(jié)點(diǎn)（1）個(gè)完全二

6、叉樹(shù)共有 701 個(gè)結(jié)點(diǎn)，則有（351）個(gè)葉子結(jié)點(diǎn)，度為 2 的節(jié)點(diǎn)(350)個(gè)，度為 1 的節(jié)點(diǎn)（0）個(gè)二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二叉樹(shù)的遍歷。前序（根左右）中序（左根右） 后序（左右根）遍歷方法注意上課筆記。例 48 選擇第 7 題和填空第 3 題七、查找1、查找分為順序查找和二分法查找。2、二分法查找只適用于順序存儲(chǔ)的有序表。最壞情況下二分查找只需要比較順序查找比較 n 次。八、排序：1、冒泡排序法、簡(jiǎn)單插入排序法、簡(jiǎn)單選擇排序法德比較次數(shù)為 n(1)/2。2、希爾排序的比較次數(shù)為 n1.5n 次，23、堆排序的比較次數(shù)為 n 2 第二章一、程序設(shè)計(jì)方法與風(fēng)格。1、程序設(shè)計(jì)方法經(jīng)過(guò)了結(jié)構(gòu)化

7、程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。2、程序設(shè)計(jì)風(fēng)格：清晰第一，效率第二3、符號(hào)名的命名要具有實(shí)際含義，注釋分為序言性注釋和功能性注釋。二、結(jié)構(gòu)化程序設(shè)計(jì)1、原則：自頂向下、逐步求精、模塊化、限制使用語(yǔ)句。2、三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)（分支結(jié)構(gòu)）、重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)） 三、面向?qū)ο蟮某绦蛟O(shè)計(jì)1、面向?qū)ο蠓椒ㄒ呀?jīng)成為主流的軟件開(kāi)發(fā)方法。優(yōu)點(diǎn)：（1）與人類(lèi)習(xí)慣的思維方法一致（2）穩(wěn)定性好 （3）可重用性好（4）易于開(kāi)發(fā)大型軟件產(chǎn)品 （5）可維護(hù)性好2、基本概念：對(duì)象：表示客觀世界中的任何實(shí)體。對(duì)象的基本特點(diǎn)：標(biāo)示唯一性、分類(lèi)性、多態(tài)性、封裝性、模塊獨(dú)立性好。類(lèi)：具有共同屬性，共同方法的對(duì)象的

8、集合。實(shí)例：指一個(gè)具體的對(duì)象。消息：一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。繼承：能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。多態(tài)：同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)。第三章一、軟件工程的基本概念：1、軟件包括程序、數(shù)據(jù)和文檔組成。2、軟件分為應(yīng)用軟件、系統(tǒng)軟件、支持軟件（工具軟件）3、軟件危機(jī)是成本、質(zhì)量、生產(chǎn)率的問(wèn)題。4、軟件工程三要素：方法、工具和過(guò)程。5、軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。6、軟件工程過(guò)程包括軟件規(guī)格說(shuō)明、軟件開(kāi)發(fā)、軟件確認(rèn)、軟件演進(jìn)。7、軟件生命周期分為軟件定義、軟件開(kāi)發(fā)、軟件運(yùn)行和維護(hù)三個(gè)大的階段。軟件定義分為：可行性研究和計(jì)

9、劃制定、需求分析。軟件開(kāi)發(fā)分為：概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試軟件運(yùn)行和維護(hù)分為：使用、維護(hù)、退役8、軟件工程內(nèi)容包括軟件開(kāi)發(fā)技術(shù)和軟件工程管理。9、軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可驗(yàn)證性。10、軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。二、結(jié)構(gòu)化分析方法：1、需求分析階段的工作：需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)、需求評(píng)審。2、面向數(shù)據(jù)流的分析方法（）、面向數(shù)據(jù)結(jié)構(gòu)的方法()面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法() 面向?qū)ο蟮姆治龇椒?)3、數(shù)據(jù)流圖（）：橢圓代表加工（轉(zhuǎn)換）、箭頭代表數(shù)據(jù)流、雙橫線(xiàn)代表存儲(chǔ)文件、矩形代表源、潭P67 面

10、的圖形。4、數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。三、結(jié)構(gòu)化設(shè)計(jì)方法：1、軟件設(shè)計(jì)是把軟件需求轉(zhuǎn)換為軟件表示的過(guò)程。2、從技術(shù)觀點(diǎn)看：軟件設(shè)計(jì)分為軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。3、從工程管理角度看：軟件設(shè)計(jì)分概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步。4、軟件設(shè)計(jì)的基本原理：（1）抽象（2）模塊化（3）信息隱蔽（4）模塊獨(dú)立性5、優(yōu)秀軟件設(shè)計(jì)要做到：高內(nèi)聚低偶合。6、概要設(shè)計(jì)的任務(wù)：設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)、編寫(xiě)概要設(shè)計(jì)文檔、概要設(shè)計(jì)文檔評(píng)審。7、結(jié)構(gòu)圖() P76 圖 3.88、數(shù)據(jù)流類(lèi)型有變換型和事務(wù)型兩種9、詳細(xì)設(shè)計(jì)為模塊實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)。10、程序流程圖 P81 圖 3.17圖

11、：避免了流程圖的隨意性和靈活性。圖 問(wèn)題分析圖結(jié)構(gòu)化的英語(yǔ)和偽碼。四、軟件測(cè)試：1、軟件測(cè)試成本占總成本的 40%以上。2、軟件測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤。3、軟件測(cè)試的準(zhǔn)則：（1）所有測(cè)試都應(yīng)追溯到需求。（2）嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試的隨意性。（3）充分注意測(cè)試中的群集現(xiàn)象（4）程序員應(yīng)避免檢查自己的程序。（5）窮舉測(cè)試不可能（6）妥善保存測(cè)試計(jì)劃、測(cè)試用例、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告。這個(gè)一般是選擇題哪一個(gè)是錯(cuò)誤的。4、軟件測(cè)試從是否執(zhí)行軟件的角度測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。按功能分為白盒測(cè)試和黑盒測(cè)試白盒測(cè)試（結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試）：看成打開(kāi)的盒子，利用內(nèi)部邏輯結(jié)構(gòu)選擇測(cè)試用例。主要方法有邏輯

12、覆蓋和基本路徑測(cè)試黑盒測(cè)試（功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試）：不考慮內(nèi)部邏輯結(jié)構(gòu)，主要用于軟件確認(rèn)測(cè)試。主要方法有等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖5、軟件測(cè)試分單元測(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（確認(rèn)測(cè)試）、系統(tǒng)測(cè)試 4 個(gè)步驟。6、驅(qū)動(dòng)模塊是被測(cè)模塊的主程序，樁模塊是一個(gè)模擬子程序。7、確認(rèn)測(cè)試是驗(yàn)證是否滿(mǎn)足需求規(guī)格說(shuō)明中的需求。主要用黑盒測(cè)試方法。五、程序調(diào)試1、程序調(diào)試是診斷和改正程序中的錯(cuò)誤。2、程序調(diào)試的步驟：（1）錯(cuò)誤定位 （2）修改設(shè)計(jì)和代碼排除錯(cuò)誤 （3）進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。第四章一、數(shù)據(jù)庫(kù)系統(tǒng)基本概念：1、數(shù)據(jù)是描述事物的符號(hào)記錄。2、數(shù)據(jù)庫(kù)（）是數(shù)據(jù)的集合，有集

13、成和共享的特點(diǎn)。3、數(shù)據(jù)庫(kù)管理系統(tǒng)()是數(shù)據(jù)庫(kù)系統(tǒng)的核心，它是一種系統(tǒng)軟件。4、數(shù)據(jù)定義語(yǔ)言()、數(shù)據(jù)操縱語(yǔ)言()、數(shù)據(jù)控制語(yǔ)言()5、上面的數(shù)據(jù)語(yǔ)言按使用方式分為交互式語(yǔ)言和宿主型語(yǔ)言。6、嚴(yán)格意義的包括、2、。小型數(shù)據(jù)庫(kù)有 和。7、數(shù)據(jù)庫(kù)管理員()的工作是（1）數(shù)據(jù)庫(kù)設(shè)計(jì) （2）數(shù)據(jù)庫(kù)維護(hù) （3）改善系統(tǒng)性能，提高系統(tǒng)效率。8、數(shù)據(jù)庫(kù)系統(tǒng)（）由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、硬件平臺(tái)和軟件平臺(tái)五部分組成硬件平臺(tái)包括計(jì)算機(jī)和網(wǎng)絡(luò)。網(wǎng)絡(luò)數(shù)據(jù)庫(kù)系統(tǒng)結(jié)構(gòu)形式以客戶(hù)機(jī)/服務(wù)器（）和瀏覽器/服務(wù)器（）方式為主。軟件平臺(tái)包括操作系統(tǒng)：（包括）和兩種數(shù)據(jù)庫(kù)系統(tǒng)開(kāi)發(fā)工具：可視化開(kāi)發(fā)工具、和9、數(shù)據(jù)庫(kù)應(yīng)

14、用系統(tǒng)由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件和應(yīng)用界面組成。10、數(shù)據(jù)庫(kù)系統(tǒng)發(fā)展經(jīng)歷了人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫(kù)系統(tǒng)階段11、數(shù)據(jù)庫(kù)系統(tǒng)基本特點(diǎn)：（1）數(shù)據(jù)集成性（2）數(shù)據(jù)的高共享性和低冗于性。（3）數(shù)據(jù)獨(dú)立性（4）數(shù)據(jù)統(tǒng)一管理和控制12、數(shù)據(jù)獨(dú)立性分為物理獨(dú)立性和邏輯獨(dú)立性?xún)杉?jí)。物理獨(dú)立性：是物理結(jié)構(gòu)的改變不影響邏輯結(jié)構(gòu)，不會(huì)引起應(yīng)用程序的變化。邏輯獨(dú)立性：總體邏輯結(jié)構(gòu)的改變不不會(huì)引起應(yīng)用程序的變化。13、數(shù)據(jù)庫(kù)系統(tǒng)三級(jí)模式。概念模式:是全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述是全體用戶(hù)的公共數(shù)據(jù)視圖。外模式：用戶(hù)的數(shù)據(jù)視圖。內(nèi)模式：數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)和物理存取方法。14、數(shù)據(jù)庫(kù)系統(tǒng)兩級(jí)映射。概念模式到內(nèi)模式的映射：

15、實(shí)現(xiàn)數(shù)據(jù)的物理獨(dú)立性。外模式到概念模式的映射：實(shí)現(xiàn)數(shù)據(jù)的邏輯獨(dú)立性。二、數(shù)據(jù)模型：1、數(shù)據(jù)模型描述的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操縱、數(shù)據(jù)約束。2、數(shù)據(jù)模型按不同的應(yīng)用層次分為三種類(lèi)型：概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型、物理數(shù)據(jù)模型。3、概念模型是模型（實(shí)體聯(lián)系模型）4、實(shí)體：現(xiàn)實(shí)世界中的事物可以抽象為實(shí)體。屬性：現(xiàn)實(shí)世界中的事物具有的一些特性。5、實(shí)體的聯(lián)系分為：兩個(gè)實(shí)體間的聯(lián)系、多個(gè)實(shí)體間的聯(lián)系、一個(gè)實(shí)體集內(nèi)部的聯(lián)系。6、兩個(gè)實(shí)體間的聯(lián)系分為一對(duì)一、一對(duì)多、多對(duì)多。要任給兩個(gè)實(shí)體，能夠判斷聯(lián)系。7、圖中矩形表示實(shí)體、橢圓表示屬性、菱形表示聯(lián)系。8、層次模型的基本結(jié)構(gòu)是樹(shù)型結(jié)構(gòu)，網(wǎng)狀模型是無(wú)向圖、關(guān)系模型

16、是二維表。9、二維表中唯一標(biāo)識(shí)元組的最小屬性集稱(chēng)為該表的鍵或碼。二維表中可能有若干個(gè)鍵，稱(chēng)為候選碼或候選鍵。從二維表的若干個(gè)候選鍵中選取一個(gè)用戶(hù)使用的鍵就是主鍵。表 A 中的屬性集是表 B 的鍵就稱(chēng)該屬性集是 A 的外鍵。表示信息的空缺。10、關(guān)系操縱有查詢(xún)、增加、刪除和修改四種操作。11、關(guān)系中的數(shù)據(jù)約束分為（ 1）實(shí)體完整性約束 （2）參照完整性約束 （3）用戶(hù)定義的完整性約束三、關(guān)系代數(shù)：1、基本運(yùn)算（1）插入 RR（2）刪除 (3) 修改 （）R投影 (R)(5)選擇 (R)2、集合運(yùn)算12,F（1）笛卡爾積：P120 表 4.4（2）交 P121 表 4.5（3）除：P121 表 4.6 表 4.7（4）連接 P123 表 4.8自然連接：P123 表 4.9這個(gè)知識(shí)點(diǎn)要理