C二級考試輔導(dǎo).ppt

1、C二級考試輔導(dǎo),2,C二級考試輔導(dǎo),一上機(jī)部分 二筆試部分 三關(guān)于考試,3,一上機(jī)部分,題型：填充題、改錯(cuò)題、編程題 滿分：100分 考試時(shí)間：90分鐘,4,一上機(jī)部分,知識分布：字符串、數(shù)組、典型算法、函數(shù)、語法、指針、遞歸、結(jié)構(gòu)鏈表、文件,5,語法,知識點(diǎn)主要集中在教材前3章 題型主要是改錯(cuò)題，還有少量填充題,6,語法,例1：純粹語法錯(cuò)誤，與上下文無關(guān),7,語法,例2：純粹語法錯(cuò)誤，與上下文無關(guān),8,語法,例3：純粹語法錯(cuò)誤，與上下文無關(guān),9,語法,例4：純粹語法錯(cuò)誤，與上下文無關(guān),10,語法,例5：純粹語法錯(cuò)誤，與上下文無關(guān),11,語法,例6：基本語法知識，與上下文關(guān)系不大,12,語法,

2、練習(xí)： 59, 08,13,數(shù)組,知識點(diǎn)主要集中在教材第6章前4節(jié) 三種題型都有，編程題居多，出現(xiàn)概率僅次于字符串,14,一維數(shù)組,例1：一維數(shù)組遍歷,15,一維數(shù)組,例2：一維數(shù)組遍歷,16,一維數(shù)組,例3：產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定）,17,一維數(shù)組,例4：產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定）,18,一維數(shù)組,例5：產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定）,19,一維數(shù)組,例6：產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定）,20,一維數(shù)組,例7：一維數(shù)組遍歷；產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定）,21,一維數(shù)組,例8：一維數(shù)組遍歷；產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定）,22,一維數(shù)組,例9：查找數(shù)組元素；刪除數(shù)組元素,23,一維

3、數(shù)組,例10：折半查找數(shù)組元素,24,二維數(shù)組,例11：二維數(shù)組遍歷,25,二維數(shù)組,例12：二維數(shù)組遍歷,26,二維數(shù)組,例13：二維數(shù)組遍歷,27,二維數(shù)組,例14：二維數(shù)組遍歷,28,二維數(shù)組,例15：二維數(shù)組遍歷,29,數(shù)組,練習(xí)： 61,f65,p55,30,字符串,知識點(diǎn)主要集中在教材第6章第5節(jié) 三種題型都有，出現(xiàn)概率最高,31,字符串,例1：字符串遍歷,32,字符串,例2：字符串遍歷,33,字符串,例3：字符串遍歷；產(chǎn)生新字符串(個(gè)數(shù)不確定),34,字符串,例4：字符串遍歷；產(chǎn)生新字符串(個(gè)數(shù)不確定),35,字符串,例5：字符串遍歷；產(chǎn)生新字符串(個(gè)數(shù)不確定),36,字符串,例

4、6：字符串遍歷；產(chǎn)生新字符串（個(gè)數(shù)不確定）,37,字符串,例7：字符串遍歷；插入字符,38,字符串,例8：字符串遍歷；數(shù)制轉(zhuǎn)換,39,字符串,例9：二個(gè)字符串同時(shí)遍歷,40,字符串,例10：查找字符,41,字符串,例11：查找字符,42,字符串,例12：查找字符；刪除指定字符,43,字符串,例13：查找字符；刪除指定字符,44,字符串,例14：插入字符,45,字符串,例15：查找子串,46,字符串,例16：查找子串,47,字符串,例17：查找子串；替換子串（同長度）,48,字符串,例18：字符排序,49,字符串,例19：字符串排序,50,字符串,例20：統(tǒng)計(jì)單詞數(shù),51,字符串,例21：回文數(shù)

5、,52,字符串,例22：逆序,53,字符串,例23：逆序;兩串交叉合并,54,字符串,練習(xí)： 63,31,p25,m28,m24,p24,p29,f11,55,典型算法,知識點(diǎn)主要集中在教材第5-7章 三種題型都有，出現(xiàn)概率僅次于字符串和數(shù)組,56,典型算法,例1：階乘,57,典型算法,例2：階乘,58,典型算法,例3：判斷閏年,59,典型算法,例4：判別素?cái)?shù),60,典型算法,例5：判別素?cái)?shù),61,典型算法,例6：判斷一個(gè)數(shù)是否為回文數(shù),62,典型算法,例7：數(shù)制轉(zhuǎn)換,63,典型算法,例8：冒泡排序,64,典型算法,例9：選擇排序,65,典型算法,例10：級數(shù)求和,66,典型算法,例11：檢索

6、數(shù)據(jù),67,典型算法,例12：簡單迭代方法求方程實(shí)根,68,典型算法,例13：二分法求方程根,69,典型算法,練習(xí)： 21,60,13,11,55,20,22,70,函數(shù),知識點(diǎn)主要集中在教材第7章 幾乎所有考題都涉及函數(shù)，專門考函數(shù)的不多,71,函數(shù),例1：交換兩個(gè)數(shù),72,函數(shù),例2：統(tǒng)計(jì)字母個(gè)數(shù),73,函數(shù),例3：檢索數(shù)據(jù),74,函數(shù),練習(xí)： 20,23,75,遞歸,知識點(diǎn)主要集中在教材第7章7.4.2 考題不多，幾乎都屬于典型算法,76,遞歸,例1：階乘,77,遞歸,例2：斐波納契數(shù)列：0、1、1、2、3、5、8、13、21,78,遞歸,例3：最小公倍數(shù),79,遞歸,練習(xí)： m53,m

7、23,80,指針,知識點(diǎn)主要集中在教材第8章前5節(jié) 很多考題都涉及指針，其知識點(diǎn)與字符串、數(shù)組相關(guān),81,指針,例1：指針變量作為函數(shù)參數(shù),82,指針,例2：指針變量作為函數(shù)參數(shù),83,指針,例3：指針數(shù)組與數(shù)組指針,84,結(jié)構(gòu)鏈表,知識點(diǎn)主要集中在教材第9章前4節(jié) 考題不是很多，變化不大，難度也不大,85,結(jié)構(gòu)鏈表,例1：結(jié)構(gòu);產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定),86,結(jié)構(gòu)鏈表,例2：創(chuàng)建隊(duì)式鏈表；創(chuàng)建棧式鏈表,87,結(jié)構(gòu)鏈表,例3：鏈表遍歷,88,結(jié)構(gòu)鏈表,練習(xí)： m21,f53,p54,89,文件,知識點(diǎn)主要集中在教材第10章第2、3節(jié) 考題非常少，變化不大，難度也不大,90,文件,例1：文

8、件操作,91,文件,例2：文件操作,92,一維數(shù)組遍歷,for(i=0;in;i+) ai ,93,二維數(shù)組遍歷,for(i=0;in;i+) for(j=0;jm;j+) aij ,94,產(chǎn)生一維數(shù)組(元素個(gè)數(shù)不確定）,n=0; for(.) bn+=. n,95,查找數(shù)組元素,for(i=0;ai!=x,96,刪除數(shù)組元素,for(i=m;in-1;i+) ai=ai+1; n-1,97,字符串遍歷,使用字符數(shù)組： for(i=0;si;i+) si ,已知字符串長度為n: for(i=0;in;i+) si ,使用字符指針： while(*p) *p p+; ,使用字符指針： for(p

9、=s;*p;p+) *p ,98,兩個(gè)字符串同時(shí)遍歷,使用字符指針： while(*p|*q) *p*q if(*p)p+; if(*q)q+; ,使用字符指針： while(*p ,99,產(chǎn)生新字符串(個(gè)數(shù)不確定）,n=0; for(.) bn+=. bn=0;,100,查找字符,使用字符指針： while(*p if(*p=ch) .,101,查找子串,while(*s1) p=s1;r=s2; while(*r) if(*p=*r) p+;r+; else break; if(*r=0). s1+;,while(*s1) p=s1;r=s2; while(*r,102,替換子串（同長度）

10、,while(*s1) p=s1;r=s2; while(*r) if(*p=*r) p+;r+ else break; if(*r=0). s1+;,if(*r=0) p=s1;r=s3; while(*r) *p=*r; p+;r+ ,103,兩串交叉合并,while(*s1|*s2) if(*s1) *s3=*s1;s1+;s3+; if(*s2) *s3=*s2;s2+;s3+; *s3=0;,104,判別素?cái)?shù),f=1; for(i=2;ix;i+) if(x%i=0) f=0;break;,105,冒泡排序,for(i=0;iaj+1) t=aj; aj=aj+1; aj+1=t;

11、,106,選擇排序,for(i=0;iaj) t=ai; ai=aj; aj=t; ,107,級數(shù)求和,s=0.0;t=.;n=1; . while(t.) s=.; t=.; n+; ,108,二分法求方程根,109,創(chuàng)建棧式鏈表,創(chuàng)建棧式鏈表的算法步驟： 建空表：head=NULL; 創(chuàng)建新結(jié)點(diǎn)：p=(*)mallco(); 給新結(jié)點(diǎn)數(shù)據(jù)域賦值 新結(jié)點(diǎn)進(jìn)棧：p-next=head;head=p; 重復(fù)第2步到第4步若干次,110,創(chuàng)建隊(duì)式鏈表,創(chuàng)建隊(duì)列式鏈表的算法步驟： 創(chuàng)建首結(jié)點(diǎn)，并對數(shù)據(jù)域賦值：head=(*)malloc(); 對末結(jié)點(diǎn)指針last初始化：last=head; 開辟后

12、續(xù)新結(jié)點(diǎn)：p=(*)malloc(); 新結(jié)點(diǎn)插入表尾：last-next=p; last指針后移至末結(jié)點(diǎn)：last=p; 重復(fù)第3步到第5步若干次 終止鏈表的延伸：last-next=NULL;,111,鏈表遍歷,字符串遍歷： while(*p) *p p+; ,鏈表遍歷： while(p) p-data p=p-next; ,112,文件操作,fopen(“文件名”,”使用方式”); fclose(文件指針); fputc(ch,fp); ch=fgetc(fp); fputs(str,fp); fgets(str,n,fp); fscanf(文件指針,格式說明,輸入列表); fprint

13、f(文件指針,格式說明,輸出列表);,113,二筆試部分,題型：選擇題、填充題 滿分：100分 考試時(shí)間：90分鐘,114,第1章 數(shù)據(jù)結(jié)構(gòu)與算法,算法 數(shù)據(jù)結(jié)構(gòu)的基本概念 線性表 棧和隊(duì)列 線性鏈表 樹與二叉樹 查找技術(shù) 排序技術(shù),115,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科,主要研究和討論以下三個(gè)方面的問題:數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu);在對數(shù)據(jù)進(jìn)行處理時(shí),各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系,即數(shù)據(jù)的存儲結(jié)構(gòu);對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。,116,數(shù)據(jù)結(jié)構(gòu),例： 數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科,主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算,以及 數(shù)據(jù)的存儲結(jié)構(gòu)

14、計(jì)算方法 數(shù)據(jù)映像 邏輯存儲,117,算法,算法具有5個(gè)特性: 有窮性 確定性 可行性 輸入 輸出,118,算法,例： 算法的有窮性是指 算法程序的運(yùn)行時(shí)間是有限的 算法程序所處理的數(shù)據(jù)量是有限的 算法程序的長度是有限的 算法只能被有限的用戶使用,119,算法,例： 在算法的5個(gè)特性中，算法必須能在執(zhí)行有限個(gè)步驟之后終止指的是算法的【2】性。,120,算法,例： 算法中,對需要執(zhí)行的每一步操作,必須給出清楚、嚴(yán)格的規(guī)定。這屬于算法的 正當(dāng)性 可行性 確定性 有窮性,121,算法,算法的復(fù)雜度主要包括算法的時(shí)間復(fù)雜度和空間復(fù)雜度。所謂算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量,即算法執(zhí)行過程

15、中所需要的基本運(yùn)算的次數(shù);算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。,122,算法,例： 算法的復(fù)雜度主要包括【1】復(fù)雜度和空間復(fù)雜度。,123,算法,例： 算法的時(shí)間復(fù)雜度是指 執(zhí)行算法程序所需要的時(shí)間 算法程序的長度 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) 算法程序中的指令條數(shù),124,算法,例： 算法的空間復(fù)雜度是指 算法程序的長度 算法程序中的指令條數(shù) 算法程序所占的存儲空間 執(zhí)行算法需要的內(nèi)存空間,125,算法,例： 算法的【1】是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。,126,算法,例： 下列敘述中正確的是 一個(gè)算法的空間復(fù)雜度大,則其時(shí)間復(fù)雜度也必定大 一個(gè)算法的空間復(fù)雜度大,

16、則其時(shí)間復(fù)雜度必定小 一個(gè)算法的時(shí)間復(fù)雜度大,則其空間復(fù)雜度必定小 上述三種說法都不對,127,算法,例： 下面敘述正確的是 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) 算法的空間復(fù)雜度是指算法程序中指令(或語句)的條數(shù) 算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止 以上三種描述都不對,128,算法,例： 對長度為n的線性表進(jìn)行順序查找,在最壞情況下所需要的比較次數(shù)為 log2n n/2 n n+1,129,數(shù)據(jù)結(jié)構(gòu)的基本概念,數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)存儲空

17、間中的存放形式。,130,數(shù)據(jù)結(jié)構(gòu)的基本概念,數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。,131,數(shù)據(jù)結(jié)構(gòu)的基本概念,根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后間關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表。所以線性表、棧與隊(duì)列、線性鏈表都是線性結(jié)構(gòu)，而樹是非線性結(jié)構(gòu)。,132,數(shù)據(jù)結(jié)構(gòu)的基本概念,例： 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的【5】結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。,133,數(shù)據(jù)結(jié)構(gòu)的基本概念,例： 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和【3】兩大類。,13

18、4,數(shù)據(jù)結(jié)構(gòu)的基本概念,例： 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu),帶鏈的隊(duì)列屬于【2】,135,數(shù)據(jù)結(jié)構(gòu)的基本概念,例： 數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 存儲結(jié)構(gòu) 物理結(jié)構(gòu) 邏輯結(jié)構(gòu) 物理和存儲結(jié)構(gòu),136,數(shù)據(jù)結(jié)構(gòu)的基本概念,例： 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的 存儲結(jié)構(gòu)存儲結(jié)構(gòu) 存儲實(shí)現(xiàn) 邏輯結(jié)構(gòu) 運(yùn)算實(shí)現(xiàn),137,數(shù)據(jù)結(jié)構(gòu)的基本概念,例： 下面數(shù)據(jù)結(jié)構(gòu)中，屬于非線性的是 線性表 樹 隊(duì)列 堆棧,138,數(shù)據(jù)結(jié)構(gòu)的基本概念,例： 下列敘述中正確的是 線性表是線性結(jié)構(gòu) 棧與隊(duì)列是非線性結(jié)構(gòu) 線性鏈表是非線性結(jié)構(gòu) 二叉樹是線性結(jié)構(gòu),139,線性表,例： 線性

19、表L=(a1,a2,a3,ai,an),下列說法正確的是 隊(duì)列每個(gè)元素都有一個(gè)直接前件和直接后件 線性表中至少要有一個(gè)元素 表中諸元素的排列順序必須是由小到大或由大到小 除第一個(gè)元素和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件,140,線性表,例： 長度為n的順序存儲線性表中,當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí),插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為【5】,141,棧和隊(duì)列,例： 下列數(shù)據(jù)結(jié)構(gòu)中,按先進(jìn)后出原則組織數(shù)據(jù)的是 隊(duì)列線性鏈表 棧 循環(huán)鏈表 順序表,142,棧和隊(duì)列,例： 按照“先進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 隊(duì)列 棧 雙向鏈表 二叉樹,143,棧和隊(duì)列,

20、例： 按先進(jìn)后出原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是【4】,144,棧和隊(duì)列,例： 棧通常采用的兩種存儲結(jié)構(gòu)是 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 散列方式和索引方式 鏈表存儲結(jié)構(gòu)和數(shù)組 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu),145,棧和隊(duì)列,例： 棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是 ABCED DCBEA DBCEA CDABE,146,棧和隊(duì)列,例： 如果進(jìn)棧序列為e1,e2,e3,e4,則可能的出棧序列是 e3,e1,e4,e2 e2,e4,e3,e1 e3,e4,e1,e2 任意順序,147,棧和隊(duì)列,例： 棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)

21、元素E入棧前，棧中元素可以出棧，則出棧序列可能是【1】,148,棧和隊(duì)列,例： 通常元素進(jìn)棧的操作是【2】。,149,棧和隊(duì)列,例： 下列關(guān)于隊(duì)列的敘述中正確的是 在隊(duì)列中只能插入數(shù)據(jù) 在隊(duì)列中只能刪除數(shù)據(jù) 隊(duì)列是先進(jìn)先出的線性表 隊(duì)列是先進(jìn)后出的線性表,150,棧和隊(duì)列,例： 棧和隊(duì)列的共同點(diǎn)是 都是先進(jìn)后出 都是先進(jìn)先出 只允許在端點(diǎn)處插入和刪除元素 沒有共同點(diǎn),151,棧和隊(duì)列,在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置直至隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。,152

22、,棧和隊(duì)列,入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作:首先將隊(duì)尾指針進(jìn)一(即rear=rear+1),并當(dāng)rear=m+1時(shí),置rear=1;然后將新元素插入隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空(s=1)且隊(duì)尾指針等于隊(duì)頭指針時(shí),說明循環(huán)隊(duì)列已滿,不能進(jìn)行入隊(duì)運(yùn)算,這種情況稱為上溢。,153,棧和隊(duì)列,例： 下列敘述中正確的是 循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu) 在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況 在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況 循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定的,154,棧

23、和隊(duì)列,例： 線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊(duì)列是一種特殊的線性表,循環(huán)隊(duì)列是隊(duì)列的【3】存儲結(jié)構(gòu)。,155,棧和隊(duì)列,例： 設(shè)某循環(huán)隊(duì)列的容量為50,頭指針front=5(指向隊(duì)頭元素的前一位置),尾指針rear=29(指向隊(duì)尾元素),則該循環(huán)隊(duì)列中共有【3】個(gè)元素。,156,棧和隊(duì)列,例： 設(shè)某循環(huán)隊(duì)列的容量為50，如果頭指針front=45（指向隊(duì)頭元素的前一位置），尾指針rear=10（指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有【2】個(gè)元素。,157,棧和隊(duì)列,例： 當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí),說明循環(huán)隊(duì)列已滿,不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為【3】。,158,

24、線性鏈表,例： 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu),線性鏈表屬于【3】,159,線性鏈表,例： 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu),160,線性鏈表,例： 下列對于線性鏈表的描述中正確的是 存儲空間不一定是連續(xù)的，且各元素的存儲順序是任意的 存儲空間不一定是連續(xù)的，且前件元素一定存儲在后件元素的前面 存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面 存儲空間必須連續(xù)，且各元素的存儲順序是任意的,161,線性鏈表,例： 以下

25、關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的敘述中，哪一條是不正確的 結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲密度小于順序存儲結(jié)構(gòu) 邏輯上相鄰的結(jié)點(diǎn)物理上不必相鄰 可以通過計(jì)算直接確定第I個(gè)結(jié)點(diǎn)的存儲地址 插入、刪除運(yùn)算操作方便，不必移動(dòng)結(jié)點(diǎn),162,樹與二叉樹,在任意一棵二叉樹中,度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。,163,樹與二叉樹,完全二叉樹的葉子結(jié)點(diǎn)總數(shù)是：int(n+1)/2)。其中n為結(jié)點(diǎn)總數(shù)，int表示取整。,164,樹與二叉樹,滿二叉樹是指除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)葉子結(jié)點(diǎn)。在滿二叉樹中,層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值,即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn),且深度為m的滿二叉樹

26、有2m-1個(gè)結(jié)點(diǎn)。,165,樹與二叉樹,例： 樹是結(jié)點(diǎn)的集合,它的根結(jié)點(diǎn)數(shù)目是 有且只有1 1或多于1 0或1 至少2,166,樹與二叉樹,例： 在下列關(guān)于二叉樹的敘述中,正確的一項(xiàng)是 在二叉樹中,任何一個(gè)結(jié)點(diǎn)的度都是2 二叉樹的度為2 在二叉樹中至少有一個(gè)結(jié)點(diǎn)的度是2 一棵二叉樹的度可以小于2,167,樹與二叉樹,例： 具有3個(gè)結(jié)點(diǎn)的二叉樹有 2種形態(tài) 4種形態(tài) 7種形態(tài) 5種形態(tài),168,樹與二叉樹,例： 在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有【2】,169,樹與二叉樹,例： 某二叉樹中度為2的結(jié)點(diǎn)有18個(gè),則該二叉樹中有【2】個(gè)葉子結(jié)點(diǎn)。,170,樹與二叉樹,例： 某二叉樹中度為2的結(jié)點(diǎn)有n個(gè),則該

27、二叉樹中有【4】個(gè)葉子結(jié)點(diǎn)。,171,樹與二叉樹,例： 一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn),則該二叉樹中的總結(jié)點(diǎn)數(shù)為 219 221 229 231,172,樹與二叉樹,例： 設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn),則在該二叉樹中有【1】個(gè)葉子結(jié)點(diǎn)。,173,樹與二叉樹,例： 在深度為5的滿二叉樹中,葉子結(jié)點(diǎn)的個(gè)數(shù)為 32 31 16 15,174,樹與二叉樹,例： 深度為 5的二叉樹最多有【2】個(gè)結(jié)點(diǎn)。,175,樹與二叉樹,例： 在深度為7的滿二叉樹中,度為2的結(jié)點(diǎn)個(gè)數(shù)為【1】,176,樹與二叉樹,所謂二叉樹的前序遍歷(DLR)是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這3者中,首先

28、訪問根結(jié)點(diǎn),然后遍歷左子樹,最后遍歷右子樹,并且,在遍歷左右子樹時(shí),上述規(guī)則同樣適用,即“根-左-右”。,177,樹與二叉樹,所謂中序遍歷(LDR)是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。,178,樹與二叉樹,例： 已知二叉樹后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是 acbed decab deabc cedba,179,樹與二叉樹,例： 若某二叉樹的前序遍歷訪問順序是abdgcefh,中序遍歷訪問順序是dgbaechf,則其后序遍歷

29、的結(jié)點(diǎn)訪問順序是 bdgcefha gdbecfha bdgaechf gdbehfca,180,樹與二叉樹,例： 已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是【3】。,181,樹與二叉樹,例： 設(shè)有下列二叉樹，對此二叉樹前序遍歷的結(jié)果為 ZBTYCPXA ATBZXCYP ZBTACYXP ATBZXCPY,182,樹與二叉樹,例： 設(shè)有下列二叉樹,對此二叉樹中序遍歷的結(jié)果為【3】。,183,查找技術(shù),順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下： 從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則

30、表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失敗）。,184,查找技術(shù),二分法查找只適用于順序存儲的有序表。設(shè)有序線性表的長度為n，被查元素為x，則二分查找的方法如下： 將x 與線性表的中間項(xiàng)進(jìn)行比較，若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束；若x 小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；若x大于中間項(xiàng)的值 ，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。這個(gè)過程一直進(jìn)行到查找成功或子表長度為 0（說明線性表中沒有這個(gè)元素）為止。,185,查找技術(shù),對于長度為 n 的

31、有序線性表，在最壞情況下，二分查找只需要比較 log 2 n次 ，而順序查找需要比較 n 次。,186,查找技術(shù),例： 在長度為64的有序線性表中進(jìn)行順序查找,最壞情況下需要比較的次數(shù)為 63 64 6 7,187,查找技術(shù),例： 對線性表進(jìn)行二分法檢索，其前提條件是 線性表以順序方式存儲，并按關(guān)鍵碼值排好序 線性表以順序方式存儲，并按關(guān)鍵碼的檢索頻率排好序 線性表以鏈接方式存儲，并按關(guān)鍵碼值排好序 線性表以鏈接方式存儲，并按關(guān)鍵碼的檢索頻率排好序,188,查找技術(shù),例： 二分法查找僅適用于這樣的表：表中的記錄必須【3】，其存儲結(jié)構(gòu)必須是順序存儲。,189,查找技術(shù),例： 在長度為n的有序線性

32、表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是 O(n) O(n2) O(log2n) O(nlog2n),190,查找技術(shù),例： 設(shè)有一個(gè)已按各元素的值排好序的順序表（長度大于2），現(xiàn)分別用順序查找法和二分查找法查找與給定值k相等的元素，比較次數(shù)分別是s和b，在查找不成功的情況下，s和b的關(guān)系是 s= b s b s =b,191,排序技術(shù),在最壞情況下,快速排序、冒泡排序和直接插入排序需要的比較次數(shù)都為n(n-1)/2,堆排序需要的比較次數(shù)為nlog2n,192,排序技術(shù),例： 排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，常見的排序方法有插入排序、【5】和選擇排序等。,193,排序技術(shù),例： 假設(shè)

33、線性表的長度為n,則在最壞情況下,冒泡排序需要的比較次數(shù)為 log2n n2 O(n1.5) n(n-1)/2,194,排序技術(shù),例： 在最壞情況下，堆排序需要比較的次數(shù)為【2】,195,排序技術(shù),例： 對長度為n的線性表排序,在最壞情況下,比較次數(shù)不是n(n-1)/2的排序方法是 快速排序 冒泡排序 直接插入排序 堆排序,196,排序技術(shù),例： 用快速排序法對下列關(guān)鍵字序列進(jìn)行排序，速度最慢的是 7， 11，19，23，25，27，32 27，25，32，19，23，7，11 3， 11，19，32，27，25，7 123，27，7，19，11，25，32 ,197,第2章 程序設(shè)計(jì)基礎(chǔ),程

34、序設(shè)計(jì)方法與風(fēng)格 結(jié)構(gòu)化程序設(shè)計(jì) 面向?qū)ο蟮某绦蛟O(shè)計(jì),198,程序設(shè)計(jì)方法與風(fēng)格,當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格是清晰第一,效率第二的觀點(diǎn)。,199,程序設(shè)計(jì)方法與風(fēng)格,例： 下列敘述中,不符合良好程序設(shè)計(jì)風(fēng)格要求的是 程序的效率第一,清晰第二 程序的可讀性好 程序中要有必要的注釋 輸入數(shù)據(jù)前要有提示信息,200,程序設(shè)計(jì)方法與風(fēng)格,例： 結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是 程序的規(guī)模 程序的效率 程序設(shè)計(jì)語言的先進(jìn)性 程序易讀性,201,程序設(shè)計(jì)方法與風(fēng)格,例： 在設(shè)計(jì)程序時(shí),應(yīng)采納的原則之一是 不限制goto語句的使用 減少或取消注解行 程序越短越好 程序結(jié)構(gòu)應(yīng)有助于讀者理解,202,程序設(shè)計(jì)方法與風(fēng)格,

35、例： 下列選項(xiàng)中不符合良好程序設(shè)計(jì)風(fēng)格的是 源程序要文檔化 數(shù)據(jù)說明的次序要規(guī)范化 避免濫用goto語句 模塊設(shè)計(jì)要保證高耦合、高內(nèi)聚,203,結(jié)構(gòu)化程序設(shè)計(jì),例： 結(jié)構(gòu)化程序設(shè)計(jì)的基本原則不包括 多態(tài)性 自頂向下 模塊化 逐步求精,204,結(jié)構(gòu)化程序設(shè)計(jì),例： 下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的是 自頂向下 逐步求精 模塊化 可復(fù)用,205,結(jié)構(gòu)化程序設(shè)計(jì),例： 結(jié)構(gòu)化程序設(shè)計(jì)方法的3種基本控制結(jié)構(gòu)中不包括 循環(huán)結(jié)構(gòu) 遞歸結(jié)構(gòu) 順序結(jié)構(gòu) 選擇結(jié)構(gòu),206,面向?qū)ο蟮某绦蛟O(shè)計(jì),對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，它的基本特點(diǎn)有：標(biāo)識惟一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性。,207,面向?qū)ο?/p>

36、的程序設(shè)計(jì),面向?qū)ο蟪绦蛟O(shè)計(jì)的3個(gè)主要特征是:封裝性、繼承性和多態(tài)性。,208,面向?qū)ο蟮某绦蛟O(shè)計(jì),封裝是一種信息屏蔽技術(shù),目的在于將對象的使用者和對象的設(shè)計(jì)者分開。用戶只能見到對象封裝界面上的信息,不必知道實(shí)現(xiàn)的細(xì)節(jié)。封裝一方面通過數(shù)據(jù)抽象,把相關(guān)的信息結(jié)合在一起,另一方面也簡化了接口。,209,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 面向?qū)ο蟮脑O(shè)計(jì)方法與傳統(tǒng)的面向過程的方法有本質(zhì)不同，它的基本原理是 模擬現(xiàn)實(shí)世界中不同事物之間的聯(lián)系 強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的算法而不強(qiáng)調(diào)概念 使用現(xiàn)實(shí)世界的概念抽象地思考問題從而自然地解決問題 鼓勵(lì)開發(fā)者在軟件開發(fā)的絕大部分中都用實(shí)際領(lǐng)域的概念去思考,210,面向?qū)ο蟮某绦蛟O(shè)

37、計(jì),例： 下面概念中，不屬于面向?qū)ο蠓椒ǖ氖?對象 繼承 類 過程調(diào)用,211,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 在面向?qū)ο蠓椒ㄖ?，不屬于對象基本特點(diǎn)的是 一致性 分類性 多態(tài)性 標(biāo)識唯一性,212,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 下面選項(xiàng)中不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)特征的是 繼承性 多態(tài)性 類比性 封裝性,213,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 以下不是面向?qū)ο笏枷胫械闹饕卣鞯氖?多態(tài) 繼承 封裝 垃圾回收,214,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 在面向?qū)ο蠓椒ㄖ?實(shí)現(xiàn)信息隱蔽是依靠 對象的繼承 對象的多態(tài) 對象的封裝 對象的分類,215,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 下面關(guān)于對象概念的描述中,錯(cuò)誤的是 對象就是C語言中的

38、結(jié)構(gòu)體變量 對象代表著正在創(chuàng)建的系統(tǒng)中的一個(gè)實(shí)體 對象是一個(gè)狀態(tài)和操作(或方法)的封裝體 對象之間的信息傳遞是通過消息進(jìn)行的,216,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 在面向?qū)ο蠓椒ㄖ?，一個(gè)對象請求另一對象為其服務(wù)的方式是通過發(fā)送 調(diào)用語句 命令 口令 消息,217,面向?qū)ο蟮某绦蛟O(shè)計(jì),例： 下列敘述中正確的是 在面向?qū)ο蟮某绦蛟O(shè)計(jì)中,各個(gè)對象之間具有密切的聯(lián)系 在面向?qū)ο蟮某绦蛟O(shè)計(jì)中,各個(gè)對象都是公用的 在面向?qū)ο蟮某绦蛟O(shè)計(jì)中,各個(gè)對象之間相對獨(dú)立,相互依賴性小 上述三種說法都不對,218,第3章 軟件工程基礎(chǔ),軟件工程基礎(chǔ)概念 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化設(shè)計(jì)方法 軟件測試 程序的調(diào)試,219,結(jié)構(gòu)化分

39、析方法,例： 在軟件開發(fā)中，需求分析階段可以使用的工具是 NS圖 DFD圖 PAD圖 程序流程圖,220,結(jié)構(gòu)化分析方法,例： 數(shù)據(jù)流圖中帶有箭頭的線段表示的是 控制流 事件驅(qū)動(dòng) 模塊調(diào)用 數(shù)據(jù)流,221,結(jié)構(gòu)化設(shè)計(jì)方法,例： 在結(jié)構(gòu)化分析使用的數(shù)據(jù)流圖(DFD)中,利用【5】對其中的圖形元素進(jìn)行確切解釋。,222,結(jié)構(gòu)化設(shè)計(jì)方法,例： 在結(jié)構(gòu)化設(shè)計(jì)方法中生成的結(jié)構(gòu)圖（SC）中，帶有箭頭的連線表示 模塊之間的調(diào)用關(guān)系 程序的組成成分 控制程序的執(zhí)行順序 數(shù)據(jù)的流向,223,結(jié)構(gòu)化設(shè)計(jì)方法,例： 下列軟件系統(tǒng)結(jié)構(gòu)圖的寬度為【1】。,224,結(jié)構(gòu)化設(shè)計(jì)方法,例： 程序流程圖中帶有箭頭的線段表示的是

40、 圖元關(guān)系 數(shù)據(jù)流 控制流 調(diào)用關(guān)系,225,結(jié)構(gòu)化設(shè)計(jì)方法,例： 為了避免流程圖在描述程序邏輯時(shí)的靈活性,提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖,通常也把這種圖稱為 PAD圖 N-S圖 結(jié)構(gòu)圖 數(shù)據(jù)流圖,226,結(jié)構(gòu)化程序設(shè)計(jì),例： 在結(jié)構(gòu)化程序設(shè)計(jì)中,模塊劃分的原則是 各模塊應(yīng)包括盡量多的功能 各模塊的規(guī)模應(yīng)盡量大 各模塊之間的聯(lián)系應(yīng)盡量緊密 模塊內(nèi)具有高內(nèi)聚度、模塊間具有低耦合度,227,結(jié)構(gòu)化程序設(shè)計(jì),例： 軟件設(shè)計(jì)中模塊劃分應(yīng)遵循的準(zhǔn)則是 低內(nèi)聚低耦合 高內(nèi)聚低耦合 低內(nèi)聚高耦合 高內(nèi)聚高耦合,228,軟件測試,229,程序的調(diào)試,230,第4章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ),數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)概念

41、數(shù)據(jù)模型 關(guān)系代數(shù) 數(shù)據(jù)庫設(shè)計(jì)與管理,231,數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)概念,數(shù)據(jù)庫系統(tǒng)在其內(nèi)部具有三級模式及二級映射，三級模式分別是概念級模式、內(nèi)部級模式與外部級模式，二級映射則分別是概念級到內(nèi)部級的映射及外部級到概念級的映射。,232,數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)概念,例： 在數(shù)據(jù)庫系統(tǒng)中，是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述的數(shù)據(jù)模式為 概念模式 外模式 內(nèi)模式 物理模式,233,數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)概念,例： 單個(gè)用戶使用的數(shù)據(jù)視圖的描述稱為 外模式 概念模式 內(nèi)模式 存儲模式,234,數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)概念,例： 下列模式中，能夠給出數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法的是 內(nèi)模式 外模式 概念模式 邏輯模式,

42、235,數(shù)據(jù)模型,E-R模型可用E-R圖來表示,它具有3個(gè)要素:實(shí)體(型)用矩形框表示,框內(nèi)為實(shí)體名稱。屬性用橢圓型來表示,并用線與實(shí)體連接。屬性較多時(shí)也可以將實(shí)體及其屬性單獨(dú)列表。實(shí)體間的聯(lián)系用菱形框表示。用線將菱形框與實(shí)體相連,并在線上標(biāo)注聯(lián)系的類型。,236,數(shù)據(jù)模型,例： 在E-R圖中，用來表示實(shí)體的圖形是 矩形 橢圓形 菱形 三角形,237,數(shù)據(jù)模型,例： 在E-R圖中,用來表示實(shí)體之間聯(lián)系的圖形是 矩形 橢圓形 菱形 平行四邊形,238,數(shù)據(jù)模型,例： 下列敘述中,正確的是 用E-R圖能夠表示實(shí)體集間一對一的聯(lián)系、一對多的聯(lián)系和多對多的聯(lián)系 用E-R圖只能表示實(shí)體集之間一對一的聯(lián)系

43、 用E-R圖只能表示實(shí)體集之間一對多的聯(lián)系 用E-R圖表示的概念數(shù)據(jù)模型只能轉(zhuǎn)換為關(guān)系數(shù)據(jù)模型,239,數(shù)據(jù)模型,例： 將E-R圖轉(zhuǎn)換到關(guān)系模式時(shí),實(shí)體與聯(lián)系都可以表示成 屬性 關(guān)系 鍵 域,240,關(guān)系代數(shù),查詢過程的查詢表達(dá)式用到的關(guān)系運(yùn)算有：選擇、投影、連接。,241,關(guān)系代數(shù),選擇運(yùn)算：從關(guān)系模式中找出滿足給定條件的元組的操作稱為選擇。 選擇運(yùn)算的運(yùn)算符：f(R),242,關(guān)系代數(shù),投影運(yùn)算：從關(guān)系模式中指定若干個(gè)屬性組成新的關(guān)系稱為投影。 投影運(yùn)算的運(yùn)算符：f(R),243,關(guān)系代數(shù),連接運(yùn)算：將兩個(gè)關(guān)系模式拼接成一個(gè)更寬的關(guān)系模式，生成的新關(guān)系中包含滿足條件的元組。 連接運(yùn)算的運(yùn)算符：R|S,244,關(guān)系代數(shù),在關(guān)系