二級(jí)C語(yǔ)音公共基礎(chǔ)知識(shí)-講義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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