二級C語音公共基礎知識-講義

1、第一章 數(shù)據(jù)結(jié)構(gòu)與算法算法算法:是指解題方案的準確而完整的描述。算法不等于程序，也不等于計算方法，程序的編制不可能優(yōu)于算法的設計。算法的基本特征:是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括:可行性；不允許有多義性；止，包括合理的執(zhí)行時間的含義；擁有足夠的情報。算法的基本要素:一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。算法的三種基本控制結(jié)構(gòu):順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法復雜度包括:算法時間復雜度和算法空間復雜度。算法時間復雜度是指執(zhí)行算法所需要的計算工作量。 算法空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間案例0.算法的有窮性是

2、指(D)A.算法只能被有限的用戶使用B.算法程序的長度是有限的C.算法程序所處理的數(shù)據(jù)量是有限的D.算法程序的運行時間是有限的案例1.下列敘述中正確的是(BG)一個算法的時間復雜度大，則其空間復雜度必定小算法的時間復雜度與空間復雜度沒有直接關(guān)系D.算法的時間復雜度與空間復雜度一定相關(guān)E.算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)F.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應的G.算法的時間復雜度是指執(zhí)行算法所需要的計算工作量棧及其基本運算棧是限定在一端進行插入與刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是

3、最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。棧的基本運算:二級VBC語言 VFPQQ 插入元素稱為入棧運算；2)刪除元素稱為退棧運算；2.1,2,3,A,B,C依次出棧，則元素出棧的順序是_(C,B,A,3,2,1)隊列及其基本運算隊列是指允許在一端(隊尾)(隊頭)進行刪除的線性(Rear)(front)指向排頭元素的前一個位置(隊頭)。隊列是“先進先出”或“后進后出”的線性表。隊列運算包括:入隊運算:從隊尾插入一個元素；退隊運算:從隊頭刪除一個元素。案例 3.下列與隊列結(jié)構(gòu)有關(guān)聯(lián)的是(A)A.先到先服務的作業(yè)調(diào)度B.函數(shù)的遞歸調(diào)用C.數(shù)組

4、元素的引用D.多重循環(huán)的執(zhí)行循環(huán)隊列及其運算:所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置， 形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針 rear front front rear 循環(huán)隊列中元素的個數(shù)=rear-front。案例4.下列敘述中正確的是(B)循環(huán)隊列有隊頭和隊尾兩個指針，因此循環(huán)隊列是非線性結(jié)構(gòu)循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定D.案例5.設循環(huán)隊列的存儲空間為初始狀態(tài)為front=rear=35. 現(xiàn)經(jīng)過一系列入隊與退隊運算后，front=15,rear=15,則循環(huán)隊列中的元素個數(shù)為(A)A.0或35B.15C.20D.1

5、6解析:循環(huán)隊列中的元素個數(shù)的計算方法是:隊尾-隊頭0，rear-front即為元素的個數(shù)。0，rear-front+空間容量 即為元素個數(shù)。二級VB C 語 言 VFPQQ:176424946400或空間容量。二叉樹及其基本性質(zhì)二叉樹是一種非線性結(jié)構(gòu)，它具有以下兩個特點:非空二叉樹只有一個根結(jié)點;0(葉結(jié)點)、1(只有一棵子樹)2(2棵子樹)。二叉樹考點 1:0的結(jié)點(即葉子結(jié)點)2個。葉子數(shù)(0)=2結(jié)點數(shù)+12:3:總結(jié)點數(shù)=2的結(jié)點數(shù)+1的結(jié)點數(shù)+0的結(jié)點數(shù)(葉子)6.71個，則該二叉樹的深度為(假設根結(jié)點在第1層) 。(7)案例7.一棵二叉樹共有25個結(jié)點，其中5個是葉子結(jié)點，則度為

6、1的結(jié)點數(shù)為_。(16)_解析:葉子結(jié)點數(shù)=2的結(jié)點數(shù)+15=？+124總結(jié)點數(shù)=2的結(jié)點數(shù)+1的結(jié)點數(shù)+0的結(jié)點數(shù)(葉子)25=4+？+5116二叉樹考點 4:二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種:前序遍歷:中序遍歷:后序遍歷:二級VBC語言 VFPQQ:1764249464案例 8. 對下列二叉樹進行前序遍歷的結(jié)果為 (ABDYECFXZ)線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的n(n0)個數(shù)據(jù)元素組成的一個有線性表可以為空表。線性表是一種存儲結(jié)構(gòu)，它的存儲方式:順序和鏈式。線性表的順序存儲結(jié)構(gòu)具有兩個基本特

7、點:線性表中所有元素所占的存儲空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。第i個結(jié)點的存儲地址。順序表的插入、刪除運算線性表的鏈式存儲結(jié)構(gòu)(線性鏈表)數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應于一個存儲單元，這種存儲單元稱為存儲結(jié)點， 簡稱結(jié)點。結(jié)點由兩部分組成:用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。指針域來確定的。鏈式存儲方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性結(jié)構(gòu)條件:有且只有一個根結(jié)點； 每一個結(jié)點最多有一個前件，也最多有一個后件。 二級VBC語言 VFPQQ:1764249464非線性結(jié)構(gòu):不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)

8、構(gòu)。案例9.下列敘述中正確的是(A)循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)循環(huán)隊列是非線性結(jié)構(gòu)C.D.循環(huán)隊列是隊列的一種鏈式存儲結(jié)構(gòu)解析:常見的線性結(jié)構(gòu)有:隊列、棧。非線性結(jié)構(gòu)有:樹、二叉樹案例10.下列敘述中正確的是(CE)線性表鏈式存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)所需要的存儲空間是相同的(不相同)線性表鏈式存儲結(jié)構(gòu)所需要的存儲空間一般要少于順序存儲結(jié)構(gòu)(多于)線性表鏈式存儲結(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)線性表鏈式存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)的存儲空間都是連續(xù)的線性表鏈式存儲結(jié)構(gòu)的存儲空間可以是連續(xù)的，也可以是不連續(xù)的排序排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即 是將無序的記錄序

9、列調(diào)整為有序記錄序列的一種操作。冒泡排序、快速排序、直接插入排序:n,則在最壞情況下，n(n-1)/2 堆排序:在最壞情況下，需要比較的次數(shù)為 nlog2n順序查找和二分查找順序查找又稱為順序搜索。順序查找一般是指在線性表中查找指定的元素下面兩種情況如果線性表為無序表(即表中元素排序是無序的)，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，都只能用順序查找即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用于順序查找按值非遞減排序(即從小到大，但允許相鄰元素值相等)。n在最壞情況下log2n次 ，n次。11.對長度為nn(n-1)/2的排序方法是(C)A.快速排序B.冒泡排序C.堆排序D.直接插入排序二級

10、VBC語言 VFPQQ:1764249464案例12.在長度為n的有序線性表中進行二分查找最壞情況下需要比較的數(shù)是(A)A.O(log2n)B.O(nlog2n)C.O(n2)D.O(n)13.10的線性表進行冒泡排序，最壞情況下需要比較的次(B)A.9B.45C.90D.10第二章 軟件工程基本概念計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件按功能分為應用軟件、系統(tǒng)軟件、支撐軟件(或工具軟件)。軟件危機主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。軟件周期:軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。軟件生命周期三個階段:軟件定義、軟件開發(fā)、運行維護，主要活動階段是: (1)可行性研究

11、與計劃制定；(2)需求分析； (3)軟件設計； (4)軟件實現(xiàn)； (5)軟件測試； (6)運行和維護。衡量軟件模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量標準。合。合性是指模塊間相互連接的緊密程度軟件測試軟件測試的目的:發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。軟件測試方法:靜態(tài)測試和動態(tài)測試。要通過人工進行。動態(tài)測試:是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法。 白盒測試:CAO有邏輯覆蓋、基本基路徑測試。黑盒測試:在黑盒測試方法中，設計測試用例的主要根據(jù)是程序外部功能。主要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。4個步驟進行:單元測試、集成測試、驗收測試(試)和系統(tǒng)測試。二級VB

12、C語言 VFPQQ:1764249464程序的調(diào)試程序調(diào)試的任務是診斷和改正程序中的錯誤，主要在開發(fā)階段進行。案例14.軟件詳細設計產(chǎn)生的圖如下:該圖是A.PAD圖B.E-R圖C.程序流程圖D.N-S圖第三章 數(shù)據(jù)庫設計基礎數(shù)據(jù)庫管理系統(tǒng):一種系統(tǒng)軟件，負責數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務等，是數(shù)據(jù)庫的核心。(1)數(shù)據(jù)定義語言:負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建； (2)數(shù)據(jù)操縱語言:負責數(shù)據(jù)的操縱，如查詢與增、刪、改等；(3)數(shù)據(jù)控制語言:負責數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復等。數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式:交互式命令(又稱自含型或

13、自主型 語言)宿主型語言(一般可嵌入某些宿主語言中)。數(shù)據(jù)庫管理員:對數(shù)據(jù)庫進行規(guī)劃、設計、維護、監(jiān)視等的專業(yè)管理人員。 數(shù)據(jù)庫系統(tǒng):由數(shù)據(jù)庫(數(shù)據(jù))、數(shù)據(jù)庫管理系統(tǒng)(軟件)、數(shù)據(jù)庫管理員(人 員)、硬件平臺(硬件)、軟件平臺(軟件)五個部分構(gòu)成的運行實體。數(shù)據(jù)庫應用系統(tǒng):由數(shù)據(jù)庫系統(tǒng)、應用軟件及應用界面三者組成。文件系統(tǒng)階段:管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段:為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。關(guān)系數(shù)據(jù)庫系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)的基本特點:數(shù)據(jù)的集成性 、數(shù)據(jù)的高共享性與低冗余性 、數(shù)據(jù)獨立性(物理獨立性與邏輯獨立性)、數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)庫系統(tǒng)的三級模式:二級VBC語言 VF

14、PQQ:1764249464概念模式:數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視；外模式:也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；內(nèi)模式:數(shù)據(jù)模型數(shù)據(jù)模型的概念:述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。E-R模型的基本概念(1)實體:現(xiàn)實世界中的事物； (2)屬性:事物的特性；(3)聯(lián)系:現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有一對一、一對多、多對聯(lián)系。案例15.若實體A和B是一對多的聯(lián)系，實體B和C是一對一的聯(lián)系，則實體A和C的聯(lián)系是 一間宿舍可住多個學生則實體宿舍和學生間的聯(lián)系是 。(一對多) 一對多)E-R模型三個基本概念之間的聯(lián)接關(guān)系:實體是概念世界中的

15、基本單位， E-R模型的圖示法:(1)(2)(3)聯(lián)系表示法。 個作為用戶使用的鍵稱主鍵AB的鍵，則稱該屬性集A的外鍵或外碼。關(guān)系中的數(shù)據(jù)約束:(1)實體完整性約束:約束關(guān)系的主鍵中屬性值不能為空值； (2)參照完全性約束:是關(guān)系之間的基本約束；(3)用戶定義的完整性約束:它反映了具體應用中數(shù)據(jù)的語義要求。關(guān)系代數(shù)論可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。關(guān)系模型的基本運算:(1) 插入 (2)刪除 (3)修改 (4)查詢(包括投影、選擇、笛卡爾積運算)二級VBC語言 VFPQQ:1764249464解析:-二級VBC語言 VFPQQ:1764249464R1選擇R2A

16、BCa1ABCa12b21c31ABCa12b21R1投影R2ABCa1ABCa12b21c31ABa1b2c3案例16.有三個關(guān)系R、S和T如下:(A)R和ST的操作是A.自然連接B.并C.投影D. 交 案例17.有三個關(guān)系R,S和T如下:R和ST的操作是A.并B.交C.投影D.選擇二級VBC語言 VFPQQ:1764249464案例18.有三個關(guān)系R,S和T如下:(D)R和ST的操作是A.選擇B.交C.并D.差案例19.有兩個關(guān)系R和S如下(A)R S的操作是A.選擇B.并C.自然連接D.投影案例20.有兩個關(guān)系R,S如下:(C)RS,則所使用的運算為A.連接B.插入C.投影D.選擇第四章

17、 程序設計基礎面向?qū)ο蠓椒ǖ闹饕獌?yōu)點:(2)穩(wěn)定性好；可重用(1)性好；易于開發(fā)大型軟件產(chǎn)品；二級VBC語言 VFPQQ:1764249464可維護性好。對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實 屬性和它可執(zhí)行的一組操作組成。對象是屬性和方法的封裝體。操作來改變。性。一個對象由對象名、屬性和操作三部分組成。對象的基本特點:標識惟一性，分類性，多態(tài)性，封裝性，模塊獨立性好。標識惟一性指對象是可區(qū)分的并且由對象的內(nèi)在本質(zhì)來區(qū)分而不是 描述來區(qū)分。分類性。指可以將具有相同屬性的操作的對象抽象成類(3)多態(tài)性。指同一個操作可以是不同對象的行為。(4)封裝性。信息隱蔽是通過對象的封裝性來實現(xiàn)的。(5)模塊獨立性好。消息是一個實例與另一個實例之間傳遞的信息。在面向?qū)ο蠓椒ㄖ校粋€對象請求另一個對象為其服務的方式是通過發(fā)送消 。繼承是指能夠直接獲得已有的性質(zhì)和特征而不必重復定義他們多個父類。類的繼