3月計算機二級C語言公共基礎知識復習資料

1、C語言知識復習全國計養(yǎng)機等級考試二級C內部資料僅限學員第一部分C語言知識復習資料第一章C語言基本知識【考點1】C程序用C語言編寫的程序稱為C語言源程序，源程序文件的后綴名為“c”。源程序經(jīng)編譯 后生成后綴名為“obj”的目標文件，再把忖標文件與各種庫函數(shù)連接起來，生成“.exe” 可執(zhí)行文件。C語言有三種基本結構：順序結構、選擇結構、循環(huán)結構?！究键c2】main皈數(shù)乂稱主函數(shù)，足C程序的入口。main后而跟-對小拈號和対花播號，花插號描起米 的部分稱為main函數(shù)的函數(shù)體° 個C程序從main函數(shù)開始執(zhí)彳J：,到main函數(shù)體執(zhí)彳j： 完結束，而不論main函數(shù)在整個程序中的位置如何

2、。每一個程序有且僅有一個main函數(shù), 具他函數(shù)都足為main函數(shù)服務的?！究键c3】存儲形式計算機在電腦中保存數(shù)據(jù)是采用二進制形式，由0或1構成的二進制稱為位（bit）,八 個位構成一個字節(jié)（Byte）, 1個Byte=8個bit。二進制、八進制、卜六進制轉化為卜進制采用乘法，I進制轉化為二進制、八進制、1叭進制采用除法。數(shù)據(jù)的存放位置就是它的 地址。【考點4】注釋是對程序的說明，町出現(xiàn)住程序中任意合適的地方，注釋從“戶”開始到最近一個"/” 結束，其間任何內容都不會被計算機執(zhí)行，注釋不可以嵌套?！究键c5】書嗎格式每條語句的后而必須有一個分號，分號是語旬的一部分。一行內對嗎多條語句，

3、一個 語句可寫在多行上?！究键c6】標識符足標識名字的有效字符序列，可以理解為C程序中的單詞。標識符的命名規(guī)則足：（1）標識符只能由字母、數(shù)字和下劃線組成，字母區(qū)分人小寫。（2）標識符的第一個字符必須足字母或卜劃線，不能為數(shù)字。C語言標識符分如下3類（1）關鍵字。它們在程序中有固定的含義，不能另作他用。如int、for、switch等。（2）預定義標識符。預先定義并具有特定含義的標識符。如define、include等。（3）用戶標識符。用戶根據(jù)需要定義的標識符，符介命名規(guī)則IL不與關鍵字相同。 【考點7】常星與變量常応是指在程序運彳J：過程中，其值不能改變的址。常雖分為整型常暈、實型常応、字

4、符常童、字符串常量、符號常量5種。在程序運行過程中其侑可以改變的盤稱為變雖。C 語言中沒有字符申變童。存放字符串使用字符數(shù)組?！究键c8】整型數(shù)據(jù)整型常暈有I進制、八進制、I六進制三種表示形貳，沒有二進制形式。八進制整型 常口加詢導數(shù)字0,1/弋進制常W加前導0X,八進制?！爸胁粫霈F(xiàn)8。整型變雖可分為基本整型（int）、短整熨（short）、長整型（10陰）、和無符號整熨 （unsigned）。-個基本整型山4個字節(jié)。其它類型的整舉占用字節(jié)數(shù)和取侑范國詳見教材 C語言知識復習第9頁?！究键c9】實型數(shù)據(jù)實型數(shù)據(jù)有阿種表示形式：小數(shù)形式和指數(shù)形式°掌握判定指數(shù)形式合法性?？谠E：E前E后必

5、有數(shù)，E后必須為整數(shù)。實型變雖分為單糟度型（float）和雙粘度型（double）,單精度型山四個字節(jié)。【考點10】算術運算算術運算符一共有+、一、*、/、這五個。求余運算要求運算對象只能為整型，除法 運算符兩邊運算對彖都為整型時，運算結果也為整型即舍掉小數(shù)部分?！究键c11】強制類型轉換將一個運算對象轉換成指定類型，格式為（類型名）表達式，注意小扌舌號位置?！究键c12】賦侑賦值運算符為“ = ”，不同r關系等“二二“。賦值表達式格式為：變量名=農達式，賦 侑運算符莊邊必須為變雖，賦值運算足把賦值運算符右邊表達式的侑賦給左邊變址。復合賦值運算符足將算術運算符或位運算符打賦值運算符組合在-起組成的

6、運算符， 掌握復合賦值表達式轉化為賦值表達式的方法。如n+=100可轉化為n=n+100。【考點13】口加口減運算口加運算符“+”與口減運算符“”是單II運算符，運算對象必須是變暈?？谠隹跍p 運算分詢綴運算和后綴運算，它們所對應的表達式的值是有區(qū)別的，如ki+：等價于 i=i；i=i+l：而 等價于 i=i+ld=i;。口訣：加加在祈先加后用，加加在后先用后加.【考點14】逗號運算逗號運算符運算優(yōu)先級最低，可將多個表達式構成一個新的表達式。第二章順序結構【考點1】運算符、表達式、語句運算對象加運算符構成表達式，表達式加分號構成表達式語句，運算對象可以是表達 式、常就、變型。如賦侑運算符加運算對

7、彖構成賦侑表達忒，賦值農達式加分號乂可構成 賦值語句?！究键c2】運算符的優(yōu)先級和結合順序運算符按參加運算的對象數(shù)目可分為單目運算符、雙目運算符和二目運算符。初籌運 算符的優(yōu)先級別最高，然后依次足單目運算符、算術運算符、關系運算符、邏輯運算符（除 邏輯非！）、條件運算符、賦值運算符、逗號運算符。位運算符優(yōu)先級介于算術運算符號邏 輯運算符之間。結合順序人多為口圧向右，而口右向出的有三個：單E運算符、條件運算 符和賦值運算符?！究键c3】printf函數(shù)格式為:DFintf（輸出控制,出列表）。輸出控制是用一對雙引號括起來的包含格式說明和原樣信息。輸出列表包含若干弓【考點4】Mintf換數(shù)中格式說明%

8、d對應整型，對應單粘度實型，（:對應字符型，o對應八進制無符號整型，x 對應力符號I八進制整型，u對應無符號整型，e對應指數(shù)型，s對應字符串型。叮 在和格式字符之間加一個數(shù)來控制數(shù)據(jù)所占的寬度和小數(shù)位數(shù)。【號點5】scanf函數(shù)輸入項要求帶取地址符&。當用鍵盤輸入多個數(shù)據(jù)時，數(shù)據(jù)之間用分隔符。分隔符包括 空格符、制表符和回車符，但不包括逗號?！究键c】6如何交換兩個變W要使用中間變審:，語句為：x=y;第三章選擇結構【考點1】關系運算c語言用非0表示邏輯真，用0表示邏轎假。關系運算符有6個.分別是” xI種優(yōu)先級島于后兩種.關系表達式真時為1假時為0。注總avbvc是不9町以的，町用(a

9、vb)&&(bvc)來表示。【考點2】邏輯運算邏碌運算符共有3個：邏輯與(&&),邏僻:或(II),邏骨非(！)。注詭短路現(xiàn)象，例 a+llb”，如果表達式a+的侑非零，則表達式bF+不再執(zhí)彳?！究键c3】if語旬可以單獨出現(xiàn)，也可以與else匹配出現(xiàn)。if語句可以嵌奩，這時else總足與離它最近 的且沒有與else匹配的if匹配?！究键c4】條件運算是唯一的二目運算符，格式為：表達式1?表達式2:表達式3。表達式1值為非0時， 整個表達式值為表達式2的值，表達式1值為0時，轅個表達式值為表達式3的值?？谠E：真前假后【考點5】switch語句格氏及執(zhí)行過程詳見教材P

10、33,要注意每條case后有沒有break語句的區(qū)別。還要注 惡switch后小括號里而的表達式不能為實型，case后表達式不能有變童?？谠E：switch 表不為實，case 表不為變。第四章循環(huán)結構【考點1】三種循環(huán)結構二種循環(huán)結構分別為：while, dowhile, for,上種結構的格式及執(zhí)行順序詳見教材第 36、39、40頁。注意ftir循環(huán)中的小括號中必須足兩個分號；循環(huán) 定要有結束條件，否 則成了死循環(huán)：dowhile()循環(huán)最后的while()：后一定要有分號。【考點 2】break 與 coi)(inu£break是終止所在整個循環(huán)，而contimie兄提前結束木輪

11、環(huán)。break語句可出現(xiàn)在循環(huán)結構 打switch 語句中，continiie 只出現(xiàn)在循環(huán)結構中。【考點3】循環(huán)的嵌套就是循環(huán)里而還有循環(huán)，計算要一層一層分析，一般只考査兩層嵌套，循環(huán)嵌套通常 是處理二維數(shù)組?！究键c4】循環(huán)結構的復習循環(huán)結構是取點，筆試所山分值一般在13分山右.在上機考試中也是必考點，應用性 很強。要求學員乖點理解并多加練習，領會掌握。第五章字符型數(shù)據(jù)位運算【考點1】字符常重一個字符常址用一對單引號括起來，字符常量只能包括一個字符， ab'是非法的。空 格常用'來表示。字符常顯可用對應的ASCII碼表示，需記?。?'的ASCII碼為48,'

12、A'怡 ASCII 碼為 65,' a'的 ASCII 碼為 97?！究键c2】轉義字符一對單引號中以一個反斜線后跟一個特定字符或八進制、I六進制數(shù)來構成轉義字符。 比如n'表示換行，101'或x41'表示ASCII碼為65的字符A'。【考點3】字符型數(shù)據(jù)可以和整型數(shù)據(jù)相互轉換Ml：' (T 0=48 A' +32二a°char a=65；Drintf( “ d%c”，a,a);結果為 65A【考點4】位運算符C語言提供6種位運算符：按位求反按位左移,按位右移:>>,按位與&,按位異 或I，按位

13、或r 一般情況卜需要先轉化進制。異或運算的觀則：0界或1得到1, 0斥或0 得到0, 1異或1得到0。町記為“相同為0,不同為1”?！究键c5】putchar與getchar函數(shù)可用J：輸出或輸入單個字符，這兩個函數(shù)是stdioJi文件中的庫函數(shù)，它們是Drintf與 scanf函數(shù)的簡化。第六章函數(shù)【考點1】函數(shù)的定義函數(shù)足具有一定功能的一個程序塊。函數(shù)的首部為：函數(shù)類型函數(shù)名(類型1形參1, 類型2形參2,)。在函數(shù)定義中不可以再定義函數(shù)，即不能嵌套定義函數(shù)。函數(shù)類型 默認為int型?！究键c2】庫函數(shù)調用C語言標準庫函數(shù)時要包含include命令，inchide命令彳f以#開頭，后而是”或

14、o括起來的后綴為”h”的頭文件。以#開頭的一彳j稱為編譯預處理命令彳J：,編譯預處理不 是C語言語句，不加分號，不占運行時間。【考點3】函數(shù)的返回值雷數(shù)通過rehini語句返回一個值，返回的值類型與疽數(shù)類型一樣。rehirn語句只執(zhí)行 一次，執(zhí)行完或函數(shù)體結束后退出函數(shù)?！究键c4】函數(shù)的聲明曲數(shù)要“先定義后調用”，或“先川明再調用后定義”。函數(shù)的押明-怎要有函數(shù)名、 函數(shù)返回值類型、函數(shù)參數(shù)類型，但不 泄要有形參的名稱?！究键c5】函數(shù)的調用程序從上往下執(zhí)行，當碰到函數(shù)名后，把值傳給調用函數(shù)，當程序得到了返回值或調 用函數(shù)結束，再順序往下執(zhí)行?！究键c6】函數(shù)的參數(shù)及值傳遞形式參數(shù)簡稱形參，是定義

15、函數(shù)時函數(shù)名后而括號中的參數(shù)。實在參數(shù)簡稱實參，是 調用函數(shù)時函數(shù)名后而括號中的參數(shù)。實參和形參分別打據(jù)不同的存儲單元。實參向形參 單向傳遞數(shù)值?！皞鱾帯迸c“傳址”的區(qū)別：傳數(shù)值的話，形參的變化不會改變實參的變化。傳地址 的話，形參的變化就有可能改變實參所對應的呈?！究键c7】函數(shù)的遞歸調用函數(shù)肖接或間接地調用口己稱為兩數(shù)的遞歸調用。遞歸調用必須有一個明確的結束遞 歸的條件。在做遞歸題時可把遞歸的步驟一步步寫卜來，不要弄顛倒了?！究键c8】要求學握的庫曲數(shù)sqrt()算術平方根函數(shù)，fabs()絕對ffi函數(shù)，pow()幕肉數(shù)，sin()iE弦曲數(shù)第七章指針【考點1】指針變雖指針變域足用來存儲地址

16、的，而一般變僦足存儲數(shù)值的。指針變試可指向任意一種數(shù) 據(jù)類型，但不管它指向的數(shù)據(jù)山用多少字節(jié)，一個指針變址打用四個字節(jié)C【考點2】指針變雖的定義格式為：類型名*指針變肚名。二維指針int杯D：可以理解為基類型為(int*)類型。 【考點3】指針變暈的初始化指針變皐在使用就必須要初始化，把一個具體的地址賦給它，否則引用時會有副作用, 如果不指向任何數(shù)據(jù)就賦“空值” NULL。【考點4】指針變童的引用&是取地址符，套是間接訪問運算符，它們足互逆的兩個運算符。在指針變試名前加間 接訪問運算符就等價它所指向的直?！究键c5】指針的運算F+和(5)+之.汕的刀:別：F+足地址變化，(5)卄足后針變

17、過所指的數(shù)拯變化。- 個指針變g加 個整數(shù)不足簡單的數(shù)學相加，而足連續(xù)移動若T地址。當兩個指針指向I 一數(shù)組時，它們可以比較人小進行減法運算。第八章數(shù)組【考點1】數(shù)組的定義數(shù)組是一組具有相同類型的數(shù)據(jù)的集合，這些數(shù)據(jù)稱為數(shù)組尤索.格式為：類型名 數(shù) 組名常3表達式1。數(shù)組的所占字節(jié)數(shù)為元索個數(shù)為基類型所山字節(jié)數(shù)的乘積。【考點2】數(shù)組的初始化第一維長度可以不耳，其它維必須耳。iBLgiMUk合法，int時1勻234上介法，int a21Z234k非法。數(shù)組初始化尤素値默認為0,沒有初始化兀素值為隨機。如在int a勻01:中，兀素a41侑為0：血在in":中，兀索aI4侑為一個不確宦的

18、隨機數(shù)?！究键c3】尤素的引用數(shù)組兀素的卜標從0開始，到數(shù)紐氏度減1結束。所以inta5|;中數(shù)組最后一個兀素是 咄4。要把數(shù)組兀素看作一個整體.可以把襯4當作一個整型變缸。【考點4】二維數(shù)組數(shù)組a2l=(12345血:中含6個元索，有2行3列c第彳為訥01彳.第2彳為aQJ 疔，袖01、訥11叫行首地址，足地址常雖。*(訥01+1)足第一彳亍第一個尤素往后跳一列，即元 素alSimifl為2, *(a0i+3)是第彳:第-個兀素往后跳丄人，即兀素aUJIfflig為 生【考點5】行指針是一個指針變該，山四個字節(jié)，行指針指向一行連續(xù)數(shù)據(jù)，形式為：int (");.D 只能存放含有兩個整

19、型元索的一維數(shù)組的首地址。注意廣D)兩邊的小括號不能省略.否則就 成了指針數(shù)組，是若干指針元素的集合。【考點6】數(shù)組名數(shù)組名是數(shù)組的首地址。數(shù)組名不能單獨引用，不能通過一個數(shù)組名代表全部元素。 數(shù)組名是地址常雖，不能對數(shù)組名賦值，所以a+是錯誤的。但數(shù)組名可以作為地址與一個 整數(shù)村加得到一個新地址。【考點7】元素形式的轉換 助記'脫衣服法則” a21變成*(a+2)a變成*(a+2)引再町變成水廣(a+2)+3)°第九章字符串【考點1】字符串常屋及表示字符串常駄足由雙引號括起來的一串字符，如” ABC"。在存儲字符串時，系統(tǒng)會自動在其尾部加上一個空值0，空值也要山用

20、一個字節(jié)，也就是字符串” ABC”需要打四個 字節(jié)?！究键c2】字符數(shù)組C語言沒有字符串變只能采用字符數(shù)組來存儲字符串。數(shù)組的人小應該比它將要 實際存放的最長字符串多一個元素，從而存放'0'。【考點3】字符串賦值可以用 卜而的形式進行賦值：charstrflu" Hello!” ；或char *d;p=" Hello!"但不能 用卜而的形式：chaFstr101;str=” Hello” ；因為sti是一個地址常址，不能進行賦值操作?！究键c4】字符串的輸入與輸出可以用scanf和Mintf函數(shù)，如scanf（” s” /）;，也對用專門處理字符巾的兩

21、個函 數(shù)Eels和puts函數(shù)，還可以對字符數(shù)組逐個元素進行賦值，但一定要在最后賦-個'3'。 使用2ets函數(shù)可以接收空格，使用puts函數(shù)在最后輸出個換行?！究键c5】字符串函數(shù)要學握的四個字符串函數(shù)：字符串拷貝函數(shù)stMDV（）,求字符串長度函數(shù)strlenO, 頭文件” mingjr。字符串鏈接函數(shù)shrat （）,字符串比較函strcmp （）。使用這些函數(shù)需在預處理部分包含字符串長度要小于字符數(shù)組的長度，例：char SWOA'Hello” ;sizeof（str）的值為10（數(shù)組長度）.strlen（str）的值為5 （字符串長度）。這些函數(shù)是考試常用到的函

22、數(shù)，人家一定要 熟練應用這兒個函數(shù)。第十章結構體與共用體【考點1】結構體類型的說明結構體是若I：個類型數(shù)摒的集合，結構體類型說明格式如卜：struct類型名類型1成 員名1;類型2成員名2;,以上整個部分是一個數(shù)據(jù)類型，與整型的int足同樣地位。 叮用typedef把結構體類型替換成一個只有兒個字母的簡短標識符?！究键c2】結構體變址的宦義結構體變最足用說明的結構體類型所定義的個變雖，與結構體類熨不是回爭。 個結構體變雖所占字節(jié)數(shù)為具所有成員所山字節(jié)數(shù)之和。如struct stufchar name10;iiif age;a,b;則表明定義了兩個結構體變雖a,b,每個變皐Yf 14個字節(jié)。a,b

23、 9 inti;中的變就訂 足同樣地位?！究键c3】結構體成員的引用引用成員可用以下3種方式：（1）結構體變皐名成員名；（2）指針變址名成員名：（3） “指針變城名）成員名。點（）稱為成員運算符，箭頭（）稱為結構指向運算符。 【考點4】鏈表鏈表是由一個個結點構成的，一個結點就是一個結構體變屋。每個結點可以分為數(shù)據(jù) 域與抬針域兩個部分，數(shù)據(jù)域用來"放要”儲的數(shù)據(jù)，指針域用來指向卜一個結點。鏈表 是考試中的難點，在C語言和公共基礎部分都會考到，要領悟掌握。【考點5】共用體共用體的使用格式與結構體相似，共用體疋義的關鍵字為union,共用體所占字節(jié)數(shù)是 所有成員中字節(jié)數(shù)最大的那個。第十一章文

24、件【考點1】文件類型指針文件指針足一個指向結構體類型的指針，定義格式為：FILE 指針變雖名。在使用文件時，都需要先定義文件指針?！究键c2】文本文件與二進制文件文本形式存放的是字符的ASCII碼，二進制形式放的是數(shù)據(jù)的二進制例如“UMT如果是文木形式就是儲 1= 0= 0'二個字符的ASCII碼(00110001 0011000000110000),如果是二進制形式就把100轉化成二進制(01100100)?！究键c3】打開文件文件的打開形式如卜：FILE 如 fp=f0Den( “c:Mahc”，” rb”);fopen曲數(shù)的而而 一部分為文件名，后而一部分為文件的使用方式。打開方式詳

25、見教材第127頁，其中I代 表讀，w代表寫，a代表添加，b代表二進制位的。【考點4】文件函數(shù)判斷文件結束feof函數(shù)，移動文件指針位置fseek函數(shù)，獲得文件位置fteii函數(shù)，文件 位國移到丿I：頭rewind因數(shù)，文件手符輸入輸;li仗etc因數(shù)和fuutc函數(shù)文件輸入輸出fscanf 函數(shù)和fprintf函數(shù)，文件字符串輸入輸山fzets函數(shù)和fDiits函數(shù)，讀寫二進制文件仏ad 函數(shù)和fwrite函數(shù)。以上函數(shù)要求知道格式會用，清楚是用于二進制文件還是文木文件，要把教材文件這 章仔細復習下，不要在考試的時候把這些文件函數(shù)搞混了。第十二章深入討論【考點1】編譯預處理凡以#開頭的這一行，

26、都是編譯預處理命令行，編譯預處理不加分號,不打運行時宏替換僅是簡單-的文木替換，如#define f(x) (x)*(x)和#define f(x)桂換f(2+2)時就 有區(qū)別，前者展開為(2+2嚴(2+2),后者為2+2吆+2。如果源文件f2c中有#include” flc”可以理解為把源文件fl.c原樣包含到f2c中，使 fl.c和f2c融合到一起成為一個C程序編譯。所以一個C程序必有主函數(shù)，但一個C源文 件未必有主函數(shù)?！究键c2】標識符作用域局部變雖是在函數(shù)內或復合語句內總義的變3，作用域為疋義它的函數(shù)內。丿訪部變屋 有二種類型：口動auto,寄存器register和靜態(tài)static?？?/p>

27、動變適隨著函數(shù)的使用與否創(chuàng)建消失：寄存器變屋分配在CDU中，沒有內存地址： 靜態(tài)變雖占用固泄存儲單尤，在程序執(zhí)彳f過程不釋放，宜到程序運行結束。全局變域是在函數(shù)外定義的變磧，作用域從定義它的位置到整個源文件結束為止，生 存期為第個程序運行期間。全同變呈都足靜態(tài)變最?！究键c3】動態(tài)存儲分配malloc(size)用來創(chuàng)建連續(xù)size個字節(jié)存儲區(qū)，返回值類型為void *型。malloc函數(shù)常 用于動態(tài)創(chuàng)建鏈表結點，如 int *d; p=(int *)malloc(sizeof(iiit);。calloc( n&ze)創(chuàng)建n個同一類 型 的儲 空間，可以 理解為n個 malloc。 fr

28、ee(D)釋放動態(tài)分配的心儲單九。公共斟出知識第二部分公共基礎知識資料第一章數(shù)據(jù)結構與算法【考點1】算法的基木概念算法:是指一組有窮的指令集，是解題方案的準確而完整的描述。算法不等于程序，也不 辱于計算方法。算法的基本特征：確宦性，算法中每一步驟都必須有明確定義，不允許有多義性；有窮性，算法必須能在有限的時間內做完，即能在執(zhí)行有限個步驟后終止；町行性，算法原則上能夠梢確地執(zhí)行；擁有足夠的情報。算法的組成要素：一個算法由數(shù)據(jù)對象的運算和操作以及其控制結構這兩部分組成。算法的基木運算和操作：算術運算，邏輯運算，關系運算，數(shù)據(jù)傳輸。算法的基本控制結構：順序，選擇，循環(huán)。算法基本設計方法：列舉法、歸納

29、法、遞推、遞歸、減半遞推技術?！究键c2】算法的復雜度算法效率的度暈算法的復雜度：時間復朵度和空間復雜度。算法時間復朵度：指執(zhí)行算法所需要的計算匸作量。通常，一個算法所用的時間包括編譯 時間和運行時間。算法空間復雜度：指執(zhí)行這個算法所需要的內空間。包括算法程序所片的空間，輸入的 初始數(shù)據(jù)所冉的空間，算法執(zhí)行過程中所需的額外空間?？臻g復朵度和時間復朵度并不相關?！究键c3】數(shù)據(jù)結構的基木概念數(shù)據(jù)：數(shù)抓定客觀爭物的符號表爪，是能輸入到計算機中并被計算程序識別和處理的符號 的總稱，如文檔，聲音，視頻等。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的搖木單位。數(shù)據(jù)對彖：數(shù)據(jù)對彖是性質相同的數(shù)據(jù)元素的集合。數(shù)據(jù)結構：是指由某一

30、數(shù)據(jù)對彖中所有數(shù)據(jù)成員之間的關系組成的集合?！究键c4】邏輯結構和存儲結構數(shù)據(jù)結構可分為數(shù)據(jù)的邏輯結構和存儲結構。數(shù)據(jù)的邏輯結構是對數(shù)據(jù).尤素Z間的邏輯關系的描述，與數(shù)據(jù)的心儲無關，足而向問題的, 足獨立于計算機的。它包插數(shù)據(jù)對象和數(shù)據(jù)對象之間的關系。數(shù)據(jù)的存儲結構也稱為數(shù)據(jù)的物理結構，是數(shù)據(jù)在計算機中的存放的方式，是而向計算機 的，它包括數(shù)據(jù)兀素的存儲方式和關系的心儲方式。數(shù)據(jù)結構和邏輯結構的關系：一種數(shù)據(jù)的邏輯結構可以表示成多種心儲結構即數(shù)據(jù)的邏輯 結構和存儲結構不一定一一對應。常見的存儲結構有：順序，鏈接，索引等。采用不同的儲結構其數(shù)擁處理的效率是不同 的?！究键c5】線性結構和非線性結構

31、線性結構的條件（一個非空數(shù)據(jù)結構）；（1）有且只有一個根結點；（2每一個結點最多有 一個前件，也最務有一個后件。非線性結構：不滿足線性結構條件的數(shù)據(jù)結構。11公共基礎知識棧、隊列、雙向鏈表足線性結構.樹、二義樹為非線性結構?！究键c6】線性表及其順序存儲結構線性表是由一組數(shù)據(jù)元索構成，數(shù)據(jù)兀索的位脣只取決于口己的序號，元索之間的相對位 置是線性的。在復雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄；由多個記錄構成的線性表 稱為文件。非空線性表的結構特征：(1) 有且只有一個根結點al,它無前件：(2) 有且只有一個終端結點an,它無后件：(3) 除根結點與終端結點外，其他所有結點有且只有一個

32、前件，也有且只有一個后件。結點個數(shù)n稱為線性表的長度，當d=0時，稱為空表。線性表的順序仔儲給構只有以卜兩個基本特點：(1) 線性表中所有元素所片的存儲空間是連續(xù)的；(2) 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。元素ai的存儲地址為：ADR(ai)=ADR(al)+(il)*k, ADR(al)為第一個元素的地址，k代表 每個元素占的字節(jié)數(shù)。順序表的運算：査找、插入.刪除?！究键c7】線性鏈 線性鏈表是線性我的鏈式存儲結構，數(shù)據(jù)結構中的每一個結點對應于一個存儲單元，這種 儲單尤稱為存儲結點，簡稱結點。結點由兩部分組成：(1)用于存儲數(shù)據(jù)兀素值，稱為數(shù) 據(jù)域； 用于放指針，稱為指針

33、域，川于指向諭一個或后一個結點。在鏈式儲結構中，"儲數(shù)據(jù)結構的儲空間M以不連續(xù)，各數(shù)據(jù)結點的儲順序與數(shù)據(jù) 元素之間的邏輯關系可以不一致，而數(shù)據(jù)元素之間的邏碌關系是由指針域來確定的。鏈式存儲方式既可用表示線性結構，也町用r表示非線性結構。線性單鏈表中:AD稱為頭指針.HEAD=NULL (或0)稱為空表。圖1單鏈表的結構雙向鏈表有兩個指針：左指針(Llink)指向詢件結點.右指針(Rlink)指向后件結點°圖2雙鏈表的結構循環(huán)鏈表：循環(huán)鏈表與單鏈表的不同的是它的最后一個結點的指針域心放的事指向第一個 結點的指針而單鏈表存放的是空指針。圖3循環(huán)鏈表的結構線性鏈表的基木運算；金找

34、、插入、刪除°【考點8】棧1、棧的韓木概念 公共斟岀知識棧足一種特殊的線性表，只允許在表的一端進行插入和刪除的線性表；插入，刪除的一端 為棧頂，另一端為棧底；當表中沒有元索時為空棧。棧是一種后進先出（或先進后出Las（ In First Out）的線性表。棧具有記憶功能。棧的實例: 火車調度，子彈夾。2、棧的存儲結構順序存儲結構：用一組地址連續(xù)的存儲單元即一維數(shù)組來存儲；鏈式存儲：用線性鏈表來存儲；3、棧的基木運算（1）入棧運算，在棧頂位置插入元素：退棧運算，刪除尤素（取出棧頂尤素并賦給一個指定的變錄）： 讀棧頂元素，將棧頂元素賦給個指定的變址，此時指針無變化。【考點9】隊列1 隊列

35、的基木概念隊列足一種特殊的線性表，只允許在表的一端插入，在另一端刪除，允許插入的一端是隊 尾（rear）,允許刪除的一端為隊頭（front）；當表中沒有元素足空隊列；隊列足一種先進 先出的線性表。（FIFO）2、隊列的存儲結構順序存儲：一維數(shù)組.鏈式存儲：線性鏈表。3、隊列的運算:（1）入隊運算：從隊尾插入一個尤索;（2）退隊運算：從隊頭隊列的順序存儲結構一般采用循環(huán)隊列的丿孩式c循環(huán)隊列=0表示隊列為空：=1 front=rear表示 隊滿。計算循環(huán)隊列的元索個數(shù)：“尾指針減頭指針”，若為負數(shù).再加其容債即町?！究键c10】樹的基木概念樹是 種非線性結構，是n個結點的有限集。當n=0時為空樹，

36、n>0時為非空樹。結點的 度：結點所擁有的了樹的個數(shù)。葉子結點：度為0的結點。分支結點：除葉子結點以外的結點。結點的層次：根結點在第一層，同一層上左右結點的子結點在下一層。樹的深度：所處層次最人的那個結點的層次。樹的度：樹中所有結點的度的最人值?！究键c11】二義樹及其里本性質1、二義樹的概念二叉樹是一種特殊的樹形結構，每個結點最多只有兩棵子樹，11有左右之分不能互換，囚 此，二叉樹有五種不同的形態(tài)，見教材12頁。2、二義樹的性質性質1在二義樹的第k層匕，最多有2他$1）個結點。性質2深度為m的二義樹最多有2°*1個結點。性質3在任意一棵二義樹中，度為0的結點（葉子結點）總是比度

37、為2的結點多一個。性質4只有n個結點的二義樹，其深度不小Hloggiil+l,具中l(wèi)ogjnl表示為108典的整數(shù)部分。3、二叉樹的療儲結構：詳見教材第13-14頁-【考點12】滿二叉樹與完全二叉樹滿:叉樹：除最后一層外，每一層上的所有結點都有兩個子結點。住滿二叉樹中，每一層 11公共基礎知識上的結點數(shù)都達到最人值，即在滿二義樹的第k層上有2“個結點，且深度為m的滿二叉 樹有2-1個結點。完全二義樹是指這樣的二義樹：除最后一層外.每一層上的結點數(shù)均達到戢人值；在戢后 一層上只缺少右邊的若干結點。滿二義樹足完全二義樹.而完全二義樹一般不是滿二義樹, 【考點13】完全二叉樹的性質性質1具有n個結點

38、的完全二義樹的深度為logl+l.性質2完全二義樹中度為1的結點數(shù)為0或X前序遍歷：先訪問根結點、然后遍歷左子樹，最后遍歷 右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結 點，然后遍歷左于樹，最后遍歷右于樹。詢序遍歷圖5可得:ABCDFHEGe中序遍歷：先遍歷Ai了樹、然后訪問根結點最后遍歷 右子樹：并且，在遍歷左、右子樹時，仍然先遍歷子 樹，然后訪問根結點，最后遍歷右子樹。中序遍歷圖5可得：BAFHDCGE。后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問 根結點；并且，在遍歷左、右子樹時，仍然先遍歷左子 樹，然后遍歷右子樹，最后訪問根結點。后序遍歷圖5可得：BHFDGECA。【考點15】

39、順用杳找順序杳找是從表的一端丿始，依次掃描表中的各個元素，并與所要倉找的數(shù)進行比較。 在卜列兩種情況卜也只能采用順序查找：（1如風線性衣為無序表，則不管是順序存儲結構還是璉式存儲結構，只能用順序任找。（2）即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。【考點16】二分査找二分査找的條件：（1）用順序存儲結構 （2）線性表足有序表。査找的步驟：詳見教材第16頁。對于長度為n的有序線性表，在最壞悄況下，1分法査找只需比較10巧1次，而順序査找需 要比較n次?！究键c17】排序1、交換排序（1）冒泡排序法，在最壞的惰況F,旨泡排序需要比較次數(shù)為n（n-l）/2。（2）快速排序法，在最壞的情

40、況卜，快速排序需要比較次數(shù)為ii（nl）/2。2、插入類排序法：（1）簡單插入排序法，最壞情況需要n（iil）/2次比較：（2）希爾排序法，最壞怙況需要On"）次比較。（人寫O是算法復朵度的表示方法）3、選擇類排序法：（1）簡單選擇排序法，最壞情況需要n（n）/2次比較；（2）堆排序法，最壞情況需要O（nlogzii）次比較。相比以上兒種（除希爾排序法外），堆排序法的時間復雜度最小。II公共Si岀知識第二章程序設計基礎【考點1】程序設計方法與風格形成良好的程序設計風格需注意：（詳見教材第19頁）。1、源程序文檔化；2、數(shù)據(jù)說明的方法：3、語句的結構；4、輸入和輸出。注釋分序言性注釋和

41、功能性注釋。語句結構清晰第一、效率第二?！究键c2】結構化程序設計方法的四條原則1、口頂向卜一：2、逐步求精：3、模塊化；4、限制使用goto語句。【考點3】結構化程序的基本結構順序結構：足最基木、最普通的結構形式，按照程序中的浴句行的先后順序逐條執(zhí)行。選擇結構：又稱為分支結構，它包括簡單選殲和多分支選禪結構。循環(huán)結構：根據(jù)給定的條件，判斷足否要重復執(zhí)彳某一相同的或類似的程序段。循環(huán)結構 對應兩類循環(huán)語句：先判斷后執(zhí)行的循環(huán)體稱為當型循環(huán)結構：先執(zhí)行循環(huán)體后判斷的稱 為直到型循環(huán)結構。【考點4】而向對彖的程序設計及而向對象方法的優(yōu)點而向對象的程序設計以對象為核心，強調對象的抽彖性，封裝性，繼承性

42、和多態(tài)性。 面向對象方法的優(yōu)點（1）人類習慣的思維方法一致：（2）穩(wěn)定性好：（3）可帝用性好：（4）易于開發(fā)大型軟件產品；（5）可維護性好?！究键c5】對象及其特點對象（object）：而向對象方法中星基本的概念，町以用來表示客觀世界中的任何實體，對 象足實體的抽象。對象的基木特點：（1）標識惟一性；（2）分類性；（3）多態(tài)性：（4）封裝性：（5）模塊獨立性好?！究键c6】屬性，類和實例屬性：即對彖所包含的佶息，它在設il對彖時確定,般只能通過執(zhí)行對彖的操作來改變。15類：是具有相似屬性與操作的一組對象。類是關于對象性質的描述。類足對象的抽象，對 彖足其對應類的一個實例。【考點7】消息及其組成消息

43、：足一個實例9另一個實例ZI傳遞的信息。對象間的通信靠消息傳遞。它請求對象執(zhí)彳f某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。消息的組成包括:接收消息的對象的名稱：（2）消息標識符，也稱消息名；（3）零個或多個參數(shù)。 【考點8】繼承和多態(tài)繼承：是使用己有的類定義作為基礎建立新類的定義技術.廣義指能夠戌接獲得已有的性質和特征，而不必取復定義他們。繼承具有傳遞性，一個類實際上繼承了它上層的全部基類的特性。繼承分單繼承和多重繼承。單繼承指個類只允許有一個父類，即類等級為樹形結構：多朿繼承指一個類允許有多個父類。多態(tài)性：是指冋樣的消息被不同的對彖接受時町導致完全不同的行動的現(xiàn)象第三章軟件丄程基

44、礎【考點1】軟件定義號軟件特點軟件指的足計算機系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)和相關文檔的完整集合。名稱描述軟件開發(fā)人員根掘用八需求開發(fā)的、用程序設計語言描述的、適合汁算機執(zhí)行的指令序列數(shù)據(jù)jt程序能正常操縱信息的數(shù)據(jù)結構文檔與程序的開發(fā)、維護和使用有關的圖文資料軟件的特點：軟件是一種邏輯實體，具有捕象性：軟件的生產與硬件不同，它沒有明顯的制作過程：軟件在運行、使用期間不存在磨損、老化問題：軟件的開發(fā)、運行對計算機系統(tǒng)只有依賴性.受計算機系統(tǒng)的限制，這導致了軟件移植的 問題；軟件復雜性窩，成木昂貴；軟件開發(fā)涉及諸多的社會因素。根據(jù)應用II標的不同，軟件可分應用軟件、系統(tǒng)軟件和支掙

45、軟件（或匚具軟件）。名稱應用軟件為解決特定領域的應用而開發(fā)的軟件，如辦公口動化軟件系統(tǒng)軟件計算機管理口身資源，提尚計算機使用效率并為計算機用戶提供各 種服務的軟件，如操作系統(tǒng)一支撐軟件（或工具軟倫支搏軟件是介于兩者之間，協(xié)助用戶開發(fā)軟件的11只性軟件。【考點2】軟件的生命周期軟件生命周期足指軟件產品從提出、實現(xiàn)、使用維護到停止使用退役的整個過程?？煞譃?軟件定義，軟件開發(fā)及軟件維護3個階段。軟件生命周期中，能夠準確確應軟件系統(tǒng)必須 做什么和必須具備哪些功能的階段是：需求分析。可行性研究初 步項忖計劃>>設計>分析>實現(xiàn)*交付退役癥義階段開發(fā)階段維護階段【考點3】軟件危機

46、和軟件匸程的概念軟件危機泛指在計算機軟件的開發(fā)和維護過程中遇到的一系列嚴重的問題，集中表現(xiàn)在成 本，質量。生產效挙等兒個方而。所謂軟件程是指采用程的概念、原理、技術和方法指導軟件的開發(fā)與維護。是建立并 使用完善的1程化原則，以較經(jīng)濟的于段獲得，能住實際機器匕有效運行的可靠軟件的一 系列方法；軟件匚程的上要思想強調在軟件開發(fā)過程中需要應用匚程化原則。軟件工程的 核心思想是把軟件當作一個匸程產品來處理。軟件工程包括3個要素：方法，匸具和過程名稱描述方法是完成軟件工程項目的技術手段工具支持軟件的開發(fā)、管理、文檔生成過程過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、悖理【考點4】軟件匸程過程軟件匸程過程是把軟件轉

47、化為輸岀的一俎彼此相關的資源活動，包含4種堪本活動：（1）peian軟件規(guī)格說明：（2） D（do軟件開發(fā)：（3） C（check軟件確認：（4） A（action）軟件演進。【考點5】軟件開發(fā)技術和軟件工程管理軟件程的理論和技術性研究的內容上要包括軟件開發(fā)技術和軟件I程管理。軟件開發(fā)技術包括軟件開發(fā)方法學、開發(fā)過程、開發(fā)具和軟件程環(huán)境，其上體內容是 軟件開發(fā)方法學。軟件開發(fā)方法包括分析方法，設計方法和程序設計方法。軟件工程管理包括軟件管理學，軟件T程經(jīng)濟學，軟件心理學等。軟件管理學包括人員組織，進度女排，質星保證，配置管理，項H計劃等。軟件1程經(jīng)濟學足研究軟件開發(fā)中成木的估算，成木效益的方法

48、和技術?！究键c6】軟件丄程的原則軟件匸程的原則：捕象，信息隱蔽，模塊化，局部化，確疋性，致性，完備性，可驗證 性（詳細見教材第2829頁）?！究键c7】需求分析概述需求分析階段的I作：需求獲取，需求分析.編寫需求規(guī)格說明廿.需求評審。需求分析方法有：（1）結構化需求分析方法: 而向數(shù)據(jù)結構的Jackson方法（ISD）； 而向數(shù)據(jù)流的結構化分析方法（SA）； 而向數(shù)據(jù)結構的結構化數(shù)據(jù)系統(tǒng)開發(fā)方法（DSSD）；（2）而向對象的分析的方法（OOA）。從需求分析建立的模型的特性來分：靜態(tài)分析和動態(tài)分析?！究键c8】結構化方法和結構化分析方法I、結構化方法包括結構化分析方法，結構化設計方法.結構化編程方法

49、結構億方法中.軟件功能分解屬于總體設計階段。2、結構化分析方法的概念結構化分析方法是而向數(shù)據(jù)流口頂而卜逐步求精進行需求分析的方法 結構化分析方法在軟件需求分析階段的應用°3、結構化分析的常用工具數(shù)據(jù)沆圖（DFD.DataFlowDi昶ram）：是結構化分析方法中用J：系統(tǒng)邏斬模型的種1爪 它以圖形的方式描繪在系統(tǒng)中流動和處理的過程。汲圖中四種基本的符號。箭頭：表不數(shù)據(jù)流.數(shù)據(jù)流是數(shù)據(jù)在系統(tǒng)中傳播的路徑°或橢圓：表示加1加匸乂稱為數(shù)據(jù)處理.足對數(shù)據(jù)流進行某些操作或變換。雙橫：表示數(shù)據(jù)存儲（數(shù)據(jù)源數(shù)據(jù)存儲乂稱為文件，指暫時保存的數(shù)據(jù)，它可以是數(shù)據(jù) 庫文件或任何形式的數(shù)據(jù)組織。方

50、框：源、潭。表樂數(shù)據(jù)的源點或終點。它是軟件系統(tǒng)外部環(huán)境中的實體，統(tǒng)稱外部實體 數(shù)據(jù)7典（DD）：它是結構分析方法的核心，是用來描述系統(tǒng)中所用到的全部數(shù)據(jù)和文件 的文檔作用是對DFD中出現(xiàn)的被命名的圖形元索進行確切解釋。數(shù)據(jù)字典由以卜 4類兀素組成（1）數(shù)據(jù)流 （2）數(shù)據(jù)流分童（3）數(shù)據(jù)"儲（4）處理判定樹（決策樹）：是一種描述加丄的圖形1只，適合描述時候處理中貝有多個判斷，而且 每個決策與若干條件有關?？ū恚慌c刊定樹類似也是種描述加工的I形匚具。如果-個加匸邏輯有多個條件.多個操作，并且在不同的條件組合下執(zhí)行不同的操作，那么可以使用判定表來描述。【考點9】軟件需求規(guī)格說明竹公共基礎

51、知識軟件需求觀格說明 W （SRS. Software Requirement Specification） 是需求分析階段得出“勺 最上孌的文檔。軟件需求規(guī)格說明書的特點：有正確性、無歧義性、完整性、可驗證性、 一致性、可理解性、可修改性和可追蹤性。其中最匝要的是無歧義性?！究键c10】軟件設計的基本概念軟件設計是確定系統(tǒng)的物理模型。軟件垃計是開發(fā)階段最匝要的步驟，足將需求準確地轉化為完整的軟件產品或系統(tǒng)的唯一 途徑。從技術觀點上看，軟件設計包括軟件結構設計、數(shù)據(jù)設計.接口設計、過程設計。（1）結構設計定義軟件系統(tǒng)各主要部件之間的關系：（2）數(shù)拯設計將分析時創(chuàng)建的模型轉化為數(shù)據(jù)結構的定文：（3

52、）接口設計是描述軟件內部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；（4）過程設計則足把系統(tǒng)結構部件轉換為軟件的過程性描述。從匸程管理角度來看，軟件設計分兩步完成：概要設計和洋細設計。（1）概要設計將軟件需求轉化為軟件體系結構、確定系統(tǒng)級接口、全局數(shù)據(jù)結構或數(shù)據(jù)應 模式：（2）詳細設計確立侮個模塊的實現(xiàn)算法和廂部數(shù)據(jù)結構，用適當方法表示算法和數(shù)據(jù)結構 的細節(jié)。【考點11】軟件設計的基本原理1、軟件設計中應該遵循的基本原理和與軟件設計有關的概念：模塊億：把程序劃分成獨立命名Q可獨立訪問的模塊，每個模塊完成一個子功能。捕彖化：捕出事物的木質特性而暫時不考虔它們的細節(jié)。信息隱藏和局部化：信息隱蔽是

53、指在一個模塊內包含的信息（過程或數(shù)據(jù)），對于不需要這 些信息的其他模塊來說是不能訪問的，實現(xiàn)信息隱蔽依靠對象的封裝。模塊獨立性：模塊獨立性是指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊 的聯(lián)系最少接口簡單。模塊的獨立程度是評價設計好壞的求要度暈標準?！究键c12】耦合性和內聚性衡雖軟件的模塊獨立性足用耦合性和內聚性兩個定性的度聯(lián)標準。耦介性：足對-個軟件結構內不同模塊z間互聯(lián)程度的度值。耦介性的強弱取決r模塊間 接口的復雜程度。內聚性：是一個模塊內部各個元素間彼此結合的緊密程度的度雖。-個棋塊的內聚性越強則該模塊的模塊獨苦性越強。一個模塊吋具他模塊的耦合性越強則 該模塊的模塊獨立性越弱

54、。在結構程序設計中，模塊劃分的原則是模塊內具有高內聚度，模塊間具有低耦合度。 耦介和內聚的種類（詳見教材第35頁）。耦介度由低到高：非宜接耦合，數(shù)據(jù)耦合，標記耦合，控制耦合，外部耦合，公共耦合， 內容耦合。內聚性由強到弱：功能內聚，順序內聚，通信內聚，過程內聚，時間內聚，邏輯內聚，偶 然內聚。【考點13】結構化設計方法結構化分析方法是而向數(shù)據(jù)流口頂而卜，逐步求精進行需求分析的方法，基木思想將軟件 設計成由相對獨立，單-功能的模塊組成的結構，與結構分析方法銜接使用，以數(shù)據(jù)流圖 為早礎得到軟件的模塊結構，適用變換熨結構和中物熨結構的日標系統(tǒng)。1、概要設計的任務：（1）劃分出組成系統(tǒng)的物理元素 （2

55、）設計軟件的結構2、概要設計的工具：21結構圖（SOStnictureChart）也稱程庁結構圖，在結構圖中，模塊用一個矩形表示，箭頭表示模塊間的調用關系?？梢杂脦ё⑨尩募^表示模塊調用過程中來回傳遞的信息。還可用帶實心圓的箭頭表不傳遞的是控制信息,空心圓箭心表示傳遞的是數(shù)據(jù)結構圖的基本形式：基木形式、順序彫式、車復形式、選杼形式。結構圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調模塊。 程序結構圖中的專業(yè)術語：深度表示控制的層數(shù)上級模塊，從屬模塊上，卜兩層模塊a和b, IL有a調用b,則a是上級模塊，b是從屬模塊寬度整體控制跨度（最人模塊的層）的表示扇入調用該模塊的模塊個數(shù)扇出一個模塊直接調用的其他模塊數(shù)塩子模塊獨中位于葉子節(jié)點的模址3、而向數(shù)據(jù)流的設計方法任何軟件系統(tǒng)都可以用數(shù)據(jù)流圖表示，典型的數(shù)據(jù)流類世有兩種：變換型和弔務理 變換型系統(tǒng)結構圖由輸入、中心變換、輸出三部分組成。4、設計的準則（1）提高模塊獨立性。（2）模塊規(guī)模適中。（3）深度，寬度，扇出和翩入適當。如果深度過人，則講明有的控制模塊可能簡單了，如 果寬度過人，則說明系統(tǒng)的控制過于集中，扇出過人說明模塊過分復雜，需要控制和協(xié)調 過多的卜級模塊，應適半加中間層次.朗出過小可以把模塊進一步分解成若小模塊，或 合并到上級模塊中，扇入越大則共享該模塊的匕級數(shù)冃越多。好的軟件設計結構通常頂層 高扇出，中間扇出較少