計算機二級office(基礎(chǔ)理論)

1、基礎(chǔ)理論第一章1、算法：是指解題方案的準(zhǔn)確而完整的描述 2、算法的基本特征：可行性、確定性、又窮性、擁有足夠的情報 3、算法設(shè)計基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法 4、算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度 5、用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量 6、數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究和討論一下三個方面的問題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu) （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的儲存關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu) （3）對數(shù)據(jù)結(jié)構(gòu)進行的運算 7、數(shù)據(jù)的邏輯結(jié)構(gòu)：是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合 8、數(shù)據(jù)結(jié)

2、構(gòu)應(yīng)包含（1）表示數(shù)據(jù)元素的信息（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系 9、所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反應(yīng)數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu) 10、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu) 11、根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型： 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 12、如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件 （1）有且只有一個根結(jié)點 （2）每一個結(jié)點最多有一個前件，也最多有一個后件 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表13、線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu) 14、非線性表有以下結(jié)構(gòu)特征 （1）有且只有一個根結(jié)點a1，它無前件 （2）有且只有一個終

3、結(jié)點An，它無后件 （3）除根結(jié)點與終結(jié)端外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件，線性表中結(jié)點的個數(shù)n稱為為線性表長度，當(dāng)n=0時，稱為空表 15線性表的順序存儲結(jié)構(gòu)具有兩個基本特點 （1）線性表中所有元素所占的存儲空間是連續(xù)的 （2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 16、順序表的插入、刪除運算 17、棧：是限定在一端進行插入與刪除的線性表 18、棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的，棧也被稱為“先進后出” 表 或“后進先出”表 19、棧中的個數(shù)=bottom-top+1 (用值大的減值小的再加一) Top=0表示棧空 top=m表示棧滿 支持

4、子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是棧。棧的基本運算有三種：入棧、退棧、與讀棧頂元素 20、隊列：是指允許在一端進行插入、而在另一端進行刪除的線性表 21、隊列稱為“先進先出”或“后進后出”的線性表 22、對列空與對列滿的條件：隊列空的條件為s=0，隊列滿的條件為s=1且ftont=rear23、入隊運算、是指在循環(huán)隊列的隊尾加入一個新元素 退隊運算、是指在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量 24、線性表的鏈?zhǔn)酱鎯κ浇Y(jié)構(gòu)稱為線性鏈表。25、（1）在線性鏈表中查找指定元素 （2）線性鏈表的插入、是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中插入一個新元素 （3）線性鏈表的刪除、是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中刪除包

5、含指定元素的結(jié)點 26、樹是一種簡單的非線性結(jié)構(gòu) 27、樹這種數(shù)據(jù)結(jié)構(gòu)的基本特征 （1）在樹結(jié)構(gòu)中每一個結(jié)點只有一個前件，稱為父結(jié)點沒有前件的結(jié)點只有一個，稱 為樹的根結(jié)點，簡稱為樹的根。 （2）在樹結(jié)構(gòu)中，每一個結(jié)點可以有多個后件，它們都稱為該結(jié)點的子結(jié)點。沒有后 件的結(jié)點稱為葉子結(jié)點 （3）在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。葉子結(jié)點的度為0在 樹中，所有結(jié)點中的最大的度稱為樹的度 28、樹的最大層次稱為樹的深度 29、在樹中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一顆子樹，葉子結(jié)點沒有子 樹 30、二叉樹，是一種很有用的非線性結(jié)構(gòu) 31、二叉樹的特點：（1）非空二叉

6、樹只有一個根結(jié)點 （2）每一個結(jié)點最多有兩顆子樹，每一個結(jié)點的度最大為2 32、二叉樹的基本性質(zhì)：（1）在二叉樹的第k層上，最多有2的k-1次方（k=1）個結(jié)點 （2）深度為m的二叉樹最多有2的m次方-1個結(jié)點（深度為m的 二叉樹是指二叉樹共有m層） （3）在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度 為2的結(jié)點多一個 （4）具有n個結(jié)點的二叉樹，其深度至少為【log2N】+1,其中【log2N】 表示取其整數(shù)部分 33、滿二叉樹與完全二叉樹（1）滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個 子結(jié)點 （2）完全二叉樹：除最后一層外，每一層上的結(jié)點樹均達到最 大值，在最后一層上只

7、缺少右邊的若干結(jié)點 34、完全二叉樹的性質(zhì)：（1）具有m個結(jié)點的完全二叉樹的深度為【log2N】+1 （2）設(shè)完全二叉樹共有n個結(jié)點 35、計算機中二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 36、二叉樹的遍歷：是指不重復(fù)地訪問二叉樹中的所有結(jié)點 （1）前序遍歷（2）中序遍歷（3）后序遍歷37、二分法查找只適用于順序存儲的有序表。二分法查找只需要比較log2N次而順序查找需要比較n次 38、交換類排序法：冒泡排序法、快速排序法 39、插入類排序法：簡單插入排序法、希爾排序法 40、選擇類排序法：簡單選擇排序法、堆排序法 第二章 1、注釋一般分為序言性注釋、功能性注釋 2、結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為

8、自項而下、逐步求精、模塊化、限制使用語 句 3、面向?qū)ο蠓椒ǖ膬?yōu)點（1）與人類習(xí)慣的思維方法一（2）穩(wěn)定性好(3)可重用性好（4）易于開發(fā)大型軟件產(chǎn)品（5）可維護性好4、對象的基本特點：標(biāo)志唯一性、分類性、多態(tài)性、封裝性、模塊獨立性好 5、將屬性、操作相似的對象歸為類 類是對象的抽象 6、消息：對象與對象之間的傳遞形式稱為消息 7、繼承：是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們 第三章 1、計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔 的完整集合 2、軟件的特點：（1）軟件是一種邏輯實體，而不是物理實體，具有抽象性 （2）軟件的生產(chǎn)與硬件不同他沒有明

9、顯的制作過程 （3）軟件在運行、使用期間不存在磨損、老化問題（4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性受計算機系統(tǒng)的限制導(dǎo)致 了軟件移植問題 （5）軟件復(fù)雜性高，成本昂貴 （6）軟件開發(fā)涉及諸多的社會因素 2、軟件工程概念的出現(xiàn)源自軟件危機 3、軟件危機主要表現(xiàn)在 （1）軟件需求的增長得不到滿足（2）軟件開發(fā)成本和進度無法控制（3）軟件質(zhì)量難以保證（4）軟件不可維護或維護程度非常低（5）軟件的成本不斷提高（6）軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長 4、軟件工程3要素，方法、工具、過程 5、軟件生命周期，軟件定義、軟件開發(fā)、軟件運行 6、軟件生命周期的主要活動階段，（1）可行性

10、研究與計劃制定（2）需求分析（3）軟件設(shè)計（4）軟件實現(xiàn)（5）軟件測試（6）運行和維護 7、軟件工程的原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、和可驗證性 8、軟件開發(fā)環(huán)境：是全面支持軟件開發(fā)全過程的軟件工具集合 9、需求分析階段的工作（1）需求獲取（2）需求分析（3）編寫需求規(guī)格說明書（4）需求評審 10、需求分析方法（1）結(jié)構(gòu)化分析方法（2）面向?qū)ο蟮姆治龇椒?1、數(shù)據(jù)流圖主要圖形元素：（橢圓）加工轉(zhuǎn)換 （箭頭）數(shù)據(jù)流 （兩條橫線）存儲文件 （長方形）源，潭12、數(shù)據(jù)字典、是結(jié)構(gòu)化分析方法的核心，數(shù)據(jù)字典是對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表以及精確的嚴(yán)格的定

11、義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解 13、軟件需求規(guī)格說明書的作用是（1）便于用戶、開發(fā)人員進行理解和交流 （2）反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù) （3）作為確認測試和驗收的依據(jù) 14、軟件設(shè)計的重要性和地位概括為以下幾點 （1）軟件開發(fā)階段（設(shè)計、編碼、測試）占據(jù)軟件項目開發(fā)總成本絕大部分，是在軟件開發(fā)中形成質(zhì)量的關(guān)鍵環(huán)節(jié)（2）軟件設(shè)計是開發(fā)階段最重要的步驟，是將需求準(zhǔn)確的轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑 （3）軟件設(shè)計作出的決策，最終影響軟件實現(xiàn)的成敗 （4）設(shè)計是軟件工程和軟件維護的基礎(chǔ) 15、衡量軟件的模塊獨立性使用耦合

12、性和內(nèi)聚性兩個定性的度量標(biāo)準(zhǔn) 16、軟件概要設(shè)計的基本任務(wù)是（1）設(shè)計軟件系統(tǒng)結(jié)構(gòu)（2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計 （3）編寫概要設(shè)計文檔（4）概要設(shè)計文檔評審 17、典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型 18、常見的過程設(shè)計工具有（1）圖形工具：程序流程圖（2）表格工具：判定表（3）語言工具：PDL（偽碼） 19、軟件測試的目的、發(fā)現(xiàn)錯誤 20、軟件測試方法：若從是否需要執(zhí)行被測軟件的角度，可分為靜態(tài)測試和動態(tài)測試 若按照功能劃分為白盒測試和黑盒測試 21、靜態(tài)測試不實際運行軟件，主要通過人工進行，動態(tài)測試是基于計算機的測試 22、白盒測試的主要方法有邏輯覆蓋、基本路徑測試 23、黑盒測試方法主

13、要有等價類劃分法、邊界分析法、錯誤推測法、因果圖，主要用于軟件確認測試 24、軟件測試過程：單元測試、集成測試、驗收測試（確認測試）、系統(tǒng)測試 25、系統(tǒng)測試的具體實施一般包括：功能測試、性能測試、操作測試、配置測試、外部接口測試、安全性測試 26、程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤 第四章 1、數(shù)據(jù)實際上就是描述事物的符號記錄 2、數(shù)據(jù)庫是數(shù)據(jù)的集合 3、數(shù)據(jù)庫管理系統(tǒng)DBMS、數(shù)據(jù)定義語言DDL、數(shù)據(jù)操縱語言DML、數(shù)據(jù)控制語言DCL 4、數(shù)據(jù)庫管理員的主要工作：數(shù)據(jù)庫設(shè)計、數(shù)據(jù)庫維護、改善系統(tǒng)性能 5、數(shù)據(jù)管理發(fā)展至今經(jīng)歷了三個階段：人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫系統(tǒng)階段 6、數(shù)

14、據(jù)庫系統(tǒng)具有以下特點：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性、數(shù)據(jù)獨立性、數(shù)據(jù)統(tǒng)一管理與控制（數(shù)據(jù)的完整性檢查、數(shù)據(jù)的安全性保護、并發(fā)控制） 7、數(shù)據(jù)庫系統(tǒng)的三級模式：概念模式、外模式、內(nèi)模式 8、數(shù)據(jù)庫系統(tǒng)的兩級映射：概念模式到內(nèi)模式的映射、外模式到概念模式的映射9、數(shù)據(jù)模型描述內(nèi)容有三個部分：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作、數(shù)據(jù)約束 10、E-R模型可以用一種非常直觀的圖的形式表示，稱為E-R圖 11、層次模型是最早發(fā)展起來的數(shù)據(jù)庫模型。網(wǎng)狀模型是一個不加任何條件限制的無向圖 12、二維表一般滿足七個性質(zhì)：元組個數(shù)有限性、元組的唯一性、元組的次序無關(guān)性、元組分量的原子性、屬性名惟一性、屬性的次序無關(guān)性、分量值域的同一性 13、