C二級考試輔導.ppt

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

2、練習： 59, 08,13,數(shù)組,知識點主要集中在教材第6章前4節(jié) 三種題型都有，編程題居多，出現(xiàn)概率僅次于字符串,14,一維數(shù)組,例1：一維數(shù)組遍歷,15,一維數(shù)組,例2：一維數(shù)組遍歷,16,一維數(shù)組,例3：產(chǎn)生一維數(shù)組(元素個數(shù)不確定）,17,一維數(shù)組,例4：產(chǎn)生一維數(shù)組(元素個數(shù)不確定）,18,一維數(shù)組,例5：產(chǎn)生一維數(shù)組(元素個數(shù)不確定）,19,一維數(shù)組,例6：產(chǎn)生一維數(shù)組(元素個數(shù)不確定）,20,一維數(shù)組,例7：一維數(shù)組遍歷；產(chǎn)生一維數(shù)組(元素個數(shù)不確定）,21,一維數(shù)組,例8：一維數(shù)組遍歷；產(chǎn)生一維數(shù)組(元素個數(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ù)組,練習： 61,f65,p55,30,字符串,知識點主要集中在教材第6章第5節(jié) 三種題型都有，出現(xiàn)概率最高,31,字符串,例1：字符串遍歷,32,字符串,例2：字符串遍歷,33,字符串,例3：字符串遍歷；產(chǎn)生新字符串(個數(shù)不確定),34,字符串,例4：字符串遍歷；產(chǎn)生新字符串(個數(shù)不確定),35,字符串,例5：字符串遍歷；產(chǎn)生新字符串(個數(shù)不確定),36,字符串,例

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

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

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

7、23,80,指針,知識點主要集中在教材第8章前5節(jié) 很多考題都涉及指針，其知識點與字符串、數(shù)組相關,81,指針,例1：指針變量作為函數(shù)參數(shù),82,指針,例2：指針變量作為函數(shù)參數(shù),83,指針,例3：指針數(shù)組與數(shù)組指針,84,結構鏈表,知識點主要集中在教材第9章前4節(jié) 考題不是很多，變化不大，難度也不大,85,結構鏈表,例1：結構;產(chǎn)生一維數(shù)組(元素個數(shù)不確定),86,結構鏈表,例2：創(chuàng)建隊式鏈表；創(chuàng)建棧式鏈表,87,結構鏈表,例3：鏈表遍歷,88,結構鏈表,練習： m21,f53,p54,89,文件,知識點主要集中在教材第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ù)組(元素個數(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,兩個字符串同時遍歷,使用字符指針： while(*p|*q) *p*q if(*p)p+; if(*q)q+; ,使用字符指針： while(*p ,99,產(chǎn)生新字符串(個數(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,判別素數(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)建新結點：p=(*)mallco(); 給新結點數(shù)據(jù)域賦值 新結點進棧：p-next=head;head=p; 重復第2步到第4步若干次,110,創(chuàng)建隊式鏈表,創(chuàng)建隊列式鏈表的算法步驟： 創(chuàng)建首結點，并對數(shù)據(jù)域賦值：head=(*)malloc(); 對末結點指針last初始化：last=head; 開辟后

12、續(xù)新結點：p=(*)malloc(); 新結點插入表尾：last-next=p; last指針后移至末結點：last=p; 重復第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分 考試時間：90分鐘,114,第1章 數(shù)據(jù)結構與算法,算法 數(shù)據(jù)結構的基本概念 線性表 棧和隊列 線性鏈表 樹與二叉樹 查找技術 排序技術,115,數(shù)據(jù)結構,數(shù)據(jù)結構作為計算機的一門學科,主要研究和討論以下三個方面的問題:數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系,即數(shù)據(jù)的邏輯結構;在對數(shù)據(jù)進行處理時,各數(shù)據(jù)元素在計算機中的存儲關系,即數(shù)據(jù)的存儲結構;對各種數(shù)據(jù)結構進行的運算。,116,數(shù)據(jù)結構,例： 數(shù)據(jù)結構作為計算機的一門學科,主要研究數(shù)據(jù)的邏輯結構、對各種數(shù)據(jù)結構進行的運算,以及 數(shù)據(jù)的存儲結構

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、線性表的長度為n,則在最壞情況下,冒泡排序需要的比較次數(shù)為 log2n n2 O(n1.5) n(n-1)/2,194,排序技術,例： 在最壞情況下，堆排序需要比較的次數(shù)為【2】,195,排序技術,例： 對長度為n的線性表排序,在最壞情況下,比較次數(shù)不是n(n-1)/2的排序方法是 快速排序 冒泡排序 直接插入排序 堆排序,196,排序技術,例： 用快速排序法對下列關鍵字序列進行排序，速度最慢的是 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章 程序設計基礎,程

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

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

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

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

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

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

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

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

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

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