二級(jí)c語(yǔ)言課件

1、全國(guó)計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)主講人：侯清蘭全國(guó)計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)主講人：侯清蘭公共基礎(chǔ)知識(shí)考試范圍單選2*10=20分，填空2*5=10分，共30分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計(jì)基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)公共基礎(chǔ)知識(shí)考試范圍單選2*10=20分，填空2*5=10分算法算法：解題方案的準(zhǔn)確而完整的描述。5個(gè)特性：有窮性：while(1); 確定性：int a=3,b,n; b=a*n;可行性:float a=15,b; b=a/0;有輸入：一個(gè)算法應(yīng)有零個(gè)或多個(gè)輸入。有輸出：一定要有一個(gè)或多個(gè)輸出。算法算法：解題方案的準(zhǔn)確而完整的描述。算法的特性算法的有窮性是指（ ）。 （2008年4月二

2、級(jí)C真題）A）算法程序的運(yùn)行時(shí)間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的C）算法程序的長(zhǎng)度是有限的 D）算法只能被有限的用戶使用A算法的特性算法的有窮性是指（ ）。 算法算法的時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量。算法的時(shí)間復(fù)雜度是指（ ）。(二級(jí)C真題)A）執(zhí)行算法程序所需要的時(shí)間 B）算法程序的長(zhǎng)度C）算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) D）算法程序中的指令數(shù)C算法C算 法算法的空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間。算法的空間復(fù)雜度是指（ ） （2009年9月二級(jí)C真題）A）算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間B）算法所處理的數(shù)據(jù)量C）算法程序中的語(yǔ)句或指令條數(shù)D）算法在執(zhí)行過(guò)程中

3、所需要的臨時(shí)工作單元數(shù)A算 法算法的空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間。A數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法=程序數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素的集合及數(shù)據(jù)元素之間的關(guān)系的集合 （a）集合結(jié)構(gòu) （b）線性結(jié)構(gòu) （c）樹(shù)型結(jié)構(gòu) （d）圖狀結(jié)構(gòu)一對(duì)一一對(duì)多多對(duì)多數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法=程序 （a）集合結(jié)構(gòu) （b）線性線性結(jié)構(gòu)線性表順序存儲(chǔ)：指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線性表的各元素 。12354a1anHa2線性表鏈?zhǔn)酱鎯?chǔ)：邏輯上相鄰的兩個(gè)數(shù)據(jù)元素物理上不一定相鄰 。注意：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)可以表示線性、非線性結(jié)構(gòu)線性結(jié)構(gòu)線性表順序存儲(chǔ)：指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)下列敘述中正

4、確的是（ ）（2008年9月二級(jí)C真題）A）順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的B）順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)C）順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間A順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)下列敘述中正確的是（ ）（2008年線性表?xiàng)：完?duì)列棧先進(jìn)后出表 。棧頂入棧出棧棧底a3a2 a1線性表?xiàng)：完?duì)列棧先進(jìn)后出表 。棧頂入棧出棧棧底a3a棧 一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E 依次入棧，然后再依次出棧，則元素出棧的順序是（ ）。 （2008年9月二級(jí)C真題）A）1

5、2345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA 假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)組(數(shù)組元素的下標(biāo)從0到49)作為棧的存儲(chǔ)空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30(數(shù)組下標(biāo))，則棧中具有 個(gè)元素。 （2009年3月二級(jí)C真題）B20棧 一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B隊(duì)列隊(duì)列先進(jìn)先出a1 a2 a3 a4 a5 入隊(duì)出隊(duì)65432110CBArearfront循環(huán)隊(duì)列：隊(duì)頭出、隊(duì)尾進(jìn)。隊(duì)頭標(biāo)志front指向隊(duì)頭元素的前一個(gè)；隊(duì)尾標(biāo)志rear指向最后一個(gè)元素。3E隊(duì)列

6、隊(duì)列先進(jìn)先出a1 a2 a3 a4 a5 入隊(duì)列對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是( )。 （2009年9月二級(jí)C真題）A）隊(duì)頭指針是固定不變的B）隊(duì)頭指針一定大于隊(duì)尾指針C）隊(duì)頭指針一定小于隊(duì)尾指針D）隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針設(shè)某循環(huán)隊(duì)列的容量為50，頭指針front=5（指向隊(duì)頭元素的前一位置），尾指針rear=29（指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有 個(gè)元素。（2008年4月二級(jí)C真題）24D隊(duì)列對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是( )。 二叉樹(shù)結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)。分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)稱為分

7、支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。一棵樹(shù)的結(jié)點(diǎn)除葉結(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。左孩子、右孩子、雙親、兄弟。祖先、子孫。結(jié)點(diǎn)的層數(shù)（深度）。規(guī)定樹(shù)的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1。ABCEDFIGH二叉樹(shù)結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。ABC二叉樹(shù)滿二叉樹(shù) 完全二叉樹(shù)ABCEDFIHKGJLMNOABCEDFIHGJ二叉樹(shù)滿二叉樹(shù) 二叉樹(shù)的性質(zhì)性質(zhì)1 一棵非空二叉樹(shù)的第k層上最多有2k1個(gè)結(jié)點(diǎn)（i1）。性質(zhì)2 一棵深度為k的二叉樹(shù)中，最多具有2k1個(gè)結(jié)點(diǎn)。性質(zhì)3 對(duì)于一棵非空的二叉樹(shù)，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有：n0n21。ABCED

8、FIGH二叉樹(shù)的性質(zhì)性質(zhì)1 一棵非空二叉樹(shù)的第k層上最多有2k1二叉樹(shù)特性例1：某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)以及3個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中共有 個(gè)結(jié)點(diǎn)。 （2009年9月二級(jí)C真題）【解析】：由性質(zhì)3可知葉子結(jié)點(diǎn)的個(gè)數(shù)是度為2的結(jié)點(diǎn)個(gè)數(shù)加1，即為6，又因?yàn)槎鏄?shù)只可能有度為0、度為1、度為2的結(jié)點(diǎn)，所以該二叉樹(shù)總結(jié)點(diǎn)的個(gè)數(shù)為63514。本題正確答案為14。例2：深度為5 的滿二叉樹(shù)有 個(gè)葉子結(jié)點(diǎn)（2008年4月二級(jí)C真題） 【解析】：由性質(zhì)1得滿二叉樹(shù)的第5層上有25-1個(gè)結(jié)點(diǎn)。本題的正確答案為16。二叉樹(shù)特性例1：某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)以及3個(gè)度為1的結(jié)二叉樹(shù)的遍歷前序 ：根左右；中序

9、：左根右； 后序：左右根ABDEFZYCX前：ABDEXCFYZ中：DBXEAYFZC后：DXEBYZFCA二叉樹(shù)的遍歷前序 ：根左右；中序：左根右； 后序：左右根AB已知一棵二叉樹(shù)前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹(shù)的后序遍歷為（ ） A）GEDHFBCA B）DGEBHFCA C）ABCDEFGH D）ACBFEDHG31已知一棵二叉樹(shù)的后序遍歷序列是dabec，中序遍歷序列是debac，則它的前序遍歷序列是（ ） Aacbed B. decab C. deabc D.cedbaBD已知一棵二叉樹(shù)前序遍歷和中序遍歷分別為ABDEGCFH和DB查找技術(shù) 比較

10、次數(shù) 時(shí)間復(fù)雜度順序查找 最壞 n O(n) 折半查找 最壞log2n O(log2n) 順序查找：從頭到尾一個(gè)一個(gè)找，可以用于順序表或鏈表。折半（二分、對(duì)分）查找：使用于有序的順序表，不適用于無(wú)序表和鏈表。下列敘述中正確的是A)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為nB)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n/2)C)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(log2n)D) 對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n log2n)A查找技術(shù) 排序技術(shù)交換類排序 比較次數(shù)冒泡排序 n(n-1)/2快速排序

11、log2n 插入類排序直接插入排序 n(n-1)/2希爾排序 n1.5選擇類排序簡(jiǎn)單選擇排序 n(n-1)/2堆排序 nlog2n 下列排序方法中，最壞情況下比較次數(shù)最少的是_。 （2008年9月二級(jí)C真題）冒泡排序 簡(jiǎn)單選擇排序 直接插入排序 堆排序D排序技術(shù)交換類排序 比較次數(shù)下列排序程序設(shè)計(jì)基礎(chǔ)（記住基礎(chǔ)概念）1、結(jié)構(gòu)化程序設(shè)計(jì)原則：自頂向下，逐步求精，模塊化，限制使用 goto 語(yǔ)句。標(biāo)準(zhǔn)：清晰第一、效率第二3大基本結(jié)構(gòu)：順序、選擇、循環(huán)2、面向?qū)ο蟪绦蛟O(shè)計(jì)（略）程序設(shè)計(jì)基礎(chǔ)（記住基礎(chǔ)概念）1、結(jié)構(gòu)化程序設(shè)計(jì)軟件工程軟件、軟件危機(jī)、軟件工程的定義軟件生命周期：可行性研究、需求分析、軟件

12、設(shè)計(jì)、軟件實(shí)現(xiàn)、軟件測(cè)試、運(yùn)行和維護(hù)軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完整性、可驗(yàn)證性結(jié)構(gòu)化分析常用工具：數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典(DD)等模塊獨(dú)立化：內(nèi)聚性模塊內(nèi)的緊密程度 耦合性模塊間的緊密程度軟件工程軟件、軟件危機(jī)、軟件工程的定義軟件測(cè)試軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試白盒測(cè)試結(jié)構(gòu)測(cè)試、邏輯驅(qū)動(dòng)測(cè)試 方法邏輯覆蓋、基本路徑測(cè)試等黑盒測(cè)試功能測(cè)試、數(shù)據(jù)驅(qū)動(dòng)測(cè)試 方法等價(jià)劃分法、邊界值分析法、因果法等軟件測(cè)試的實(shí)施：?jiǎn)卧獪y(cè)試、集成測(cè)試、確認(rèn)測(cè)試、系統(tǒng)測(cè)試程序的調(diào)試軟件測(cè)試軟件測(cè)試方法：數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)概念：數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)等數(shù)據(jù)庫(kù)系統(tǒng)的三

13、級(jí)模式：概念模式（唯一）、外模式（多個(gè)）、內(nèi)模式（唯一）E-R模型：實(shí)體（長(zhǎng)方形）、聯(lián)系（橢圓）、屬性（菱形）課程教師參考書(shū)講授編號(hào)姓名職稱實(shí)體與實(shí)體之間：一對(duì)一一對(duì)多多對(duì)多屬性中關(guān)鍵屬性（關(guān)鍵字）：編號(hào)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)概念：數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)關(guān)系模型：二維表SSnSdSa2001001200100220010032001004張浩然李一明王偉趙堅(jiān)強(qiáng)CPCPEEEE18191820元組/記錄屬性關(guān)系模型：二維表SSnSdSa2001001張浩然CP18關(guān)系運(yùn)算（重點(diǎn)）并 RUS 差：R-S交RS 笛卡爾積：RSRABCa1b1c1a1b2c2a2b2c1SABCa1b2c2a1b3c2a2b2c1RSR.AR.BR.CS.AS.BS.Ca1b1c1a1b2c2a1b1c1a1b3c2a1b1c1a2b2c1a1b2c2a1b2c2a1b2c2a1b3c2a1b2c2a2b2c1a2b2c1a1b2c2a2b2c1a1b3c2a2b2c1a2b2c1關(guān)系運(yùn)算（重點(diǎn)）并 RUS 專門的關(guān)系運(yùn)算投影：挑選出關(guān)系表中的列（屬性）選擇：挑選出關(guān)系表中的行（元組）有兩個(gè)關(guān)系R和T如下：R TABCa12b22c32d32ABCc32d32則由關(guān)系R得到關(guān)