全国计算机等级考试二级C语言考试复习资料及复习计划以及考试要点.pdf

《全国计算机等级考试二级C语言考试复习资料及复习计划以及考试要点.pdf》由会员分享，可在线阅读，更多相关《全国计算机等级考试二级C语言考试复习资料及复习计划以及考试要点.pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国计算机等级考试二级全国计算机等级考试二级 C C 语言考试复习语言考试复习资料及复习计划资料及复习计划一、一、C C 语言的特点语言的特点C 语言是近年来非常流行的语言，很多人宁愿放弃已经熟悉的其他语言而改用C 语言,其原因是C语言有优于其他语言的一系列特点.下面是 C 语言的主要特点:（1）语言简洁、紧凑,并且使用方便、灵活；C 语言程序的函数具体模块结构风格，使得程序整体结构清晰、层次清楚，为模块化程序设计提供了强有力的支持。C 语言的源程序的扩展名都是。C.C 语言中的注释格式为:/注释内容/与*之间不允许有空格，注释部分允许出现在程序中的任何位置。C 语言中的所有语句都必须以分号“

2、;结（2）运算符丰富;（3）数据结构丰富；(4)具有结构化的控制语句；（5）语法限制不太严格，使程序设计比较自由；（6)C 语言允许用户直接访问物理地址，能进行位（bit)操作,可以直接对硬件进行操作.二、源程序的书写规则二、源程序的书写规则C 语言的书写规则.C 语言书写格式自由，一行内可以写几个语句,一个语句也可以分写在多行上。C 程序没有行号，每个语句和数据定义的最后必须有一个分号。C 语言中分号是语句中不可少的，即使是程序中的最后一个语句也应该包含分号.C 语言中的注释可以用/*用*/结束，注释可以在任何允许插入空格符的地方插入。C 语言中注释不允许嵌套，注释可以用西文,也可以用中文。

3、三、三、C C 语言的风格语言的风格由于 C 语言对语法限制不太严格,为了保证程序的准确性和可读性，建议在书写程序采用阶梯缩进格式。也就是按如下格式书写C语言程序：*;*（）*;*；*;.。.。.。*;概括起来，C 语言程序具有如下的风格:束一、程序的构成一、程序的构成尽管 C 程序的内容千变万化，但是它们的构成都是一致的，一个完整的 C 源程序的格式可以如下表示:编译预处理主函数（）函数(）.。函数（）从上面中可以看出，一个 C 源程序实际上就是若干函数的集合,这些函数中有一个是程序的主函数，任何 C 的源程序执行时,都是从主函数开始执行的,其它的函数最终必将被这个主函数所调用。C 语言除了

4、主函数规定必须取名 main 外，其它的函数名可以任取，但是要符合 C 的标识符取名规则，另外注意不要与保留字重名，最好也不可与 C 语言中的库函数或其它一些命令如编译预处另命令重名.各个函数在程序中所处的位置并不是固定的，但要求一个函数是完整的、独立的.不允许出现在一个函数内部又去定义另一个函数，或是函数格式不齐全的现象。一个完整的一般意义上的函数有一个固定的框架,编写具体的函数时，只需在这个框架中填入相应的内容即可.框架如下：函数类型 函数名（形参）形参说明内部变量说明;执行语句部分;二、二、C C 语言的基本词法语言的基本词法 C 语言的基本词法由三部分组成：符号集、关键字、保留字.符号

5、集就是一门语言中允许出现的字符的集合，C 语言的符号集就是 ASC码表中的一些字符,在键盘上不能直接得到(比如说响铃字符），C 语言引入了转义字符的概念,利用反斜杠符号后加上字母的一个字符组合来表示这些字符，当在源程序中遇到这类字符组合时，虽然这个字符组合是一个字符串的形式，但 C 语言仍会自动将之理解成某一特定的字符。比如，C 语言在处理这个字符组合时，会自动理解成回车换行符号.转义字符经过进一步引申应用，形成了另外两种形式:ddd和xnn,这里后的 ddd 和 xnn 分别代表三位八进制和两位十六进制数(打头的x只是标明后面跟着的是十六进制数）,这两种形式不再局限于表示不可打印的字符，它们

6、可以表示 ASC码表中的任意字符，只要把所需表示的字符的ASCII码转换成八进制数或十六进制数即可。比如说字母A，ASCII码为 65，65 的八进制和十六进制分别为101和 x41，所以，字母 A 可表示为101或x41,对转义字符应认真理解。标识符就是用以标识的符号.正如现实生活中给每一个人都取一个名字一样,C 语言中的每一个对象(如函数、变量等)都必须取一个标识符以和其它对象区别开。在C语言中,这个标识符是一个字符串，这个字符串的选定有一定的规则：必须是以字母或下划线开头的字母与数字的序列.除了这个基本的规则外，C 语言对标识符的命名还有几个限制需加以注意：长度最好不要超过八个字符。因

7、C 中对标识符只处理前 8 个字符，超过 8 个长度的部分将被 C 自动忽略掉.ABCDEFGH1和ABCDEFH2是同一个标识符；标识符不要与保留字同名，最好也不要与 C 提供的标准标识符，如库函数重名；应注意 C 语言对大小写字母是敏感的，ABcd 和 abcd 是两个不同的标识符。关键字实际上就是一些特殊的标识符，又称保留字，这些保留字不允许用户对它重新定义。三、头文件、数据说明、函数的开始和结束三、头文件、数据说明、函数的开始和结束标志标志1.头文件:也称为包含文件或标题文件，一般放在一个C 语言程序的开头，用include文件名的格式，其中文件名是头文件名，一般用.h作为扩展名。2。

8、数据说明:C 语言中的数据分常量和变量两种.3。常量：有数值常量和符号常量两种。4.数值常量：可以分为整型常量、实型常量、浮点型常量和字符常量。5。符号常量：用一个标识符代表的一个常量,又称标识符形式的常量.6.变量:其值可以改变的量,变量名习惯上用小写字母表示.7。标识符:用来标识变量名、符号常量名、函数名、数组名、类型名、文件名的有效字符序列。8.标识符的命名规则:C 语言中标识符只能由字母、数字和下划线三种字符组成，且第一个字符必须为字母或下划线.C 语言是大小写敏感语言,即对大小写字母认为是不同的字符。C 语言中标识符的长度随系统不同而字，如TURBO C 中取前8 个字符，8 个字符

9、后面的字符会自动取消。四、数据类型四、数据类型C 语言的数据类型可以分为三类：基本类型构造类型派生类型整型 int字符型结构体charstruct实型（浮公用（联合)数组点型）体 union类型float 双 用户定义类 指针精度型型（使用关 类型double键字空类型typedef）void1.整型常量:C 语言中的整型常量有三种形式：十进制整型常量、八进制整型常量和十六进制整型常量。十进制整型常量可以用一串连续的十进制数字来表示；八进制整型常量用数字 0 开头（注意：不是字母 O），后面可以跟一串合法的八进制数字；十六进制整型常量用 0 x或 0X 开头，后面可以跟一串合法的十六进制数字。

10、整型常量又有短整型（short int)、基本整型（int）、长整型（long int）和无符号型（unsinged）之分。2.整型变量：整型变量也可以分为基本型、短整型、长整型和无符号型四种。分别用int，short int（或 short）,long int（或 long），unsignedint（unsigned short,unsigned long）对它们进行定义。不同的计算机对上述几种整型数据所占用的内存字节数和数值范围有不同的规定，以IBM-PC 微机为例，以上各种数据所分配的存储空间和数值范围见下表所占类型名字数值范围节数intshort-32768int+32767long2

11、32768int2+32767unsigned4-2147483648int2unsigned2+2147483647short4065535065535unsigned04294697295long3。实型常量：C 语言中的实型常量有两种表示形式：十进制数形式和指数形式。在用指数形式表示实型数据时,字母E可以用小写e代替,指数部分必须是整数(若为正整数时，可以省略+号)。4。实型变量：C 语言中的实型变量分为两种：单精度类型和双精度类型，分别用保留关键字 float 和double进行定义。在一般系统中,一个float型数据在内存中占 4 个字节；一个 double型数据占 8 个字节（一个

12、 long double 型数据占 16 个字节）。5。字符常量:C 语言的字符常量代表 ASC码字符集里的一个字符，在程序中要单引号括起来。C 语言规定字符常量可以作为整数常量来处理（注:这里的整数常量指的是相应字符的ASC代码，因此字符常量可以参与算术运算)。在 C 语言中还有一类特殊形式的字符常量，称为转义字符。这类字符常量是以一个反斜杠开头的字符序列,但它们只代表某个特定的 ASC码字符，在程序中使用这种常量时要括在一对单引号中.6.字符变量：C 语言中的字符变量用关键字char 来定义，每个字符变量中只能存放一个字符。在一般系统中，一个字符变量在计算机内存中占一个字节。与字符常量一样

13、，字符变量也可以出现在任何允许整型变量参与的运算中。7.字符串常量:C 语言中的字符串常量是由一对双引号括起来的字符序列。注意不要将字符常量和字符串常量混淆.C 语言对字符串常量的长度不加限制，C 编译程序总是自动地在字符串的结尾加一个转义字符0，作为字符串常量的结束标志。C 语言中没有专门的字符串变量，如果要把字符串存放在变量中，则要用一个字符型数组来实现.五、运算符的种类、运算优先级、结合性C 语言中的运算符可以归纳为下列5 类：算术运算符、关系运算符、赋值运算符、逻辑运算符和条件运算符。1。算术运算符有+、-、*、/、.分别表示算术加、减、乘、除和取余运算。这些运算符需要两个运算对象，称

14、双目运算符。除取余（%)运算符外,这些运算符的运算对象可以是整型,也可以是实型数据。取余运算的运算对象只能是整型。取余运算的结果是两数相除后所得的余数。+和-也可以用做单目运算符，但作为单目运算符时必须出现在运算量的左边，运算量可为整型，也可以为实型.C 语言中还提供两个特殊的单目运算符:+和-，这两个运算符既可以放在运算对象之前，又可以放在运算对象之后。在C语言中，凡是按C语言语法规则用常量、赋值运算的功能是先计算右边表达式的值，然后再把此值赋给赋值号左边的变量，确切地说，是把数据放入以该变量为标识的存储单元中去。5.条件运算符C 语言中把？：称作条件运算符。条件运算符要求有三个运算对象，它

15、是 C 语言中唯一的一个三目运算符。由条件运算符构成的条件表达式的一般形式为：表达式1？表变量、函数调用以及运算符把运算数连接起来的式子都是合法的表达式。凡表达式都有一个值，即运算结果。2。在算术表达式中,C 语言提供 6 种关系运算符:,，=，=,！=。前四种运算符（，,=,=，=，！=，前四种优先级高于后两种.关系表达式真时为1,假时为0。注意ab c是不可以的，可用（ab)&(bc)来表示.【考点【考点2 2】逻辑运算】逻辑运算逻辑运算符共有3个:逻辑与(&），逻辑或（|），逻辑非（!）.注意短路现象，例a+|b+，如果表达式a+的值非零，则表达式b+不再执行。【考点【考点3 3】if

16、if语句语句可以单独出现，也可以与else匹配出现。if语句可以嵌套,这时else总是与离它最近的且没有与else匹配的if匹配。【考点【考点4 4】条件运算】条件运算是唯一的三目运算符，格式为：表达式1?表达式2:表达式3。表达式1值为非0时，整个表达式值为表达式2的值，表达式1值为0时，整个表达式值为表达式3的值.口诀：真前假后口诀：真前假后【考点【考点5 5】switchswitch语句语句格式及执行过程详见教材P33,要注意每条case后有没有break语句的区别。还要注意switch后小括号里面的表达式不能为实型，case后表达式不能有变量。口诀：口诀：switchswitch表不为

17、实表不为实,case,case表不为变。表不为变。第四章第四章循环结构循环结构【考点【考点1 1】三种循环结构】三种循环结构三种循环结构分别为：while，do-while，for,三种结构的格式及执行顺序详见教材第36、39、40页。注意for循环中的小括号中必须是两个分号；循环一定要有结束条件，否则成了死循环；dowhile()循环最后的while(）;后一定要有分号.【考点【考点2 2】breakbreak与与continuecontinuebreak是终止所在整个循环，而continue是提前结束本轮循环。break语句可出现在循环结构与switch语句中，continue只出现在循环

18、结构中。【考点【考点3 3】循环的嵌套】循环的嵌套就是循环里面还有循环，计算要一层一层分析，一般只考查两层嵌套,循环嵌套通常是处理二维数组.【考点【考点4 4】循环结构的复习】循环结构的复习循环结构是重点，笔试所占分值一般在13分左右，在上机考试中也是必考点,应用性很强。要求学员重点理解并多加练习,领会掌握。第五章第五章 字符型数据字符型数据 位运算位运算【考点【考点1 1】字符常量】字符常量一个字符常量用一对单引号括起来，字符常量只能包括一个字符，ab是非法的.空格常用 来表示.字符常量可用对应的ASCII码表示，需记住：0的ASCII码为48，A的ASCII码为65,a的ASCII码为97

19、。的值类型与函数类型一样。return语句只执行一次，执行完或函数体结束后退出函数。【考点【考点4 4】函数的声明】函数的声明函数要“先定义后调用，或“先声明再调用后定义”。函数的声明一定要有函数名、函数返回值类型、函数参数类型,但不一定要有形参的名称。【考点【考点5 5】函数的调用】函数的调用程序从上往下执行，当碰到函数名后,【考点【考点2 2】转义字符】转义字符一对单引号中以一个反斜线后跟一个特定字符或八进制、十六进制数来构成转义字 符。比 如 n 表 示 换 行,101 或x41表示ASCII码为65的字符A。【考点【考点3 3】字符型数据可以和整型数据相互】字符型数据可以和整型数据相互

20、转换转换如：00=48A+32=achar a=65;printf(“d%c”,a,a）；结果为65A【考点【考点4 4】位运算符】位运算符C语言提供6种位运算符:按位求反，按位左移，按位与，按位异或，按位或。一般情况下需要先转化进制。异或运算的规则：0异或1得到1,0异或0得到0，1异或1得到0.可记为“相同为0，不同为1”。【考点【考点5 5】putcharputchar与与getchargetchar函数函数可用于输出或输入单个字符，这两个函数是stdio.h文件中的库函数，它们是printf与scanf函数的简化。第六章第六章 函数函数【考点【考点1 1】函数的定义】函数的定义函数是具

21、有一定功能的一个程序块.函数的首部为：函数类型 函数名(类型1 形参1,类型2 形参2，）。在函数定义中不可以再定义函数，即不能嵌套定义函数。函数类型默认为int型。【考点【考点2 2】库函数】库函数调用C语言标准库函数时要包含 include命令，include命令行以#开头,后面是或括起来的后缀为.h”的头文件.以#开头的一行称为编译预处理命令行，编译预处理不是C语言语句，不加分号，不占运行时间。【考点【考点3 3】函数的返回值】函数的返回值函数通过return语句返回一个值，返回把值传给调用函数，当程序得到了返回值或调用函数结束，再顺序往下执行。【考点【考点6 6】函数的参数及值传递】函

22、数的参数及值传递形式参数简称形参，是定义函数时函数名后面括号中的参数。实在参数简称实参，是调用函数时函数名后面括号中的参数。实参和形参分别占据不同的存储单元.实参向形参单向传递数值。“传值”与“传址”的区别：传数值的话，形参的变化不会改变实参的变化。传地址的话，形参的变化就有可能改变实参所对应的量。【考点【考点7 7】函数的递归调用】函数的递归调用函数直接或间接地调用自己称为函数的递归调用.递归调用必须有一个明确的结束递归的条件。在做递归题时可把递归的步骤一步步写下来,不要弄颠倒了。【考点【考点8 8】要求掌握的库函数】要求掌握的库函数sqrt(）算术平方根函数,fabs（）绝对值函数,pow

23、（)幂函数，sin()正弦函数第七章第七章 指针指针【考点【考点1 1】指针变量】指针变量指针变量是用来存储地址的，而一般变量是存储数值的。指针变量可指向任意一种数据类型,但不管它指向的数据占用多少字节，一个指针变量占用四个字节。【考点【考点2 2】指针变量的定义】指针变量的定义格式为:类型名 指针变量名。二维指针int*p;可以理解为基类型为(int）类型.【考点【考点3 3】指针变量的初始化】指针变量的初始化指针变量在使用前必须要初始化，把一个具体的地址赋给它，否则引用时会有副作用，如 果 不 指 向 任 何 数 据 就 赋“空值”NULL。【考点【考点4 4】指针变量的引用】指针变量的引

24、用是取地址符,*是间接访问运算符，它们是互逆的两个运算符.在指针变量名前加间接访问运算符就等价它所指向的量。【考点【考点5 5】指针的运算】指针的运算p+和(*p）+之间的差别：p+是地址变化，（p）+是指针变量所指的数据变化。一个指针变量加一个整数不是简单的数学相加，而是连续移动若干地址.当两个指针指向同一数组时,它们可以比较大小进行减法运算。第八章第八章 数组数组【考点【考点1 1】数组的定义】数组的定义数组是一组具有相同类型的数据的集合，这些数据称为数组元素。格式为:类型名数组名常量表达式。数组的所占字节数为元素个数与基类型所占字节数的乘积。【考点【考点2 2】数组的初始化】数组的初始化

25、第一维长度可以不写，其它维必须写。int a=1，2；合法，int a3=2,3，4；合法，int a2=2，3,4；非法。数组初始化元素值默认为0，没有初始化元素值为随机。如在int a5=0，1,2；中，元素a4值为0;而在int a5;中，元素a 4值为一个不确定的随机数。【考点【考点3 3】元素的引用】元素的引用数组元素的下标从0开始，到数组长度减1结束。所以int a5；中数组最后一个元素是a4.要把数组元素看作一个整体，可以把a4当作一个整型变量。【考点【考点4 4】二维数组】二维数组数组a23=1，2,3，4，5,6；中含6个元素，有2行3列。第一行为a0行,第2行为a1行，a0

26、、a1叫行首地址，是地址常量。*(a0+1)是第一行第一个元素往后跳一列,即元素a01值为2,(a0+3)是第一行第一个元素往后跳三个,即元素a 10值为4。【考点【考点5 5】行指针】行指针是一个指针变量，占四个字节，行指针指向一行连续数据，形式为：int(p）2;,p只能存放含有两个整型元素的一维数组的首地址。注意(p)两边的小括号不能省略，否则就成了指针数组,是若干指针元素的集合。【考点【考点6 6】数组名】数组名数组名是数组的首地址。数组名不能单独引用，不能通过一个数组名代表全部元素。数组名是地址常量，不能对数组名赋值，所以a+是错误的。但数组名可以作为地址与一个整数相加得到一个新地址

27、。【考点【考点7 7】元素形式的转换】元素形式的转换助记：“脱衣服法则”a2变成*（a+2），a23变成(a+2)3 再可变成*(*（a+2)+3)。第九章第九章 字符串字符串【考点【考点1 1】字符串常量及表示】字符串常量及表示字符串常量是由双引号括起来的一串字符,如”ABC”.在存储字符串时,系统会自动在其尾部加上一个空值0，空值也要占用一个字节,也就是字符串”ABC需要占四个字节.【考点【考点2 2】字符数组】字符数组C语言没有字符串变量，只能采用字符数组来存储字符串。数组的大小应该比它将要实际存放的最长字符串多一个元素，从而存放0.【考点【考点3 3】字符串赋值】字符串赋值可以用下面的

28、形式进行赋值：charstr=”Hello!”;或char p；p=”Hello!”;，但 不 能 用 下 面 的 形 式：charstr10;str=”Hello”；因为str是一个地址常量,不能进行赋值操作。【考点【考点4 4】字符串的输入与输出】字符串的输入与输出可 以 用 scanf 和 printf 函 数，如 scanf（”%s”,str）；，也可用专门处理字符串的两个函数gets和puts函数，还可以对字符数组逐个元素进行赋值，但一定要在最后赋一个0。使用gets函数可以接收空格,使用puts函数在最后输出一个换行。【考点【考点5 5】字符串函数】字符串函数要掌握的四个字符串函数

29、：字符串拷贝函数strcpy(），求字符串长度函数strlen（)，字符串链接函数 strcat(）,字符串比较函数strcmp（)。使用这些函数需在预处理部分包含头文件string.h”。字符串长度要小于字符数组的长度,例：char str 10=”Hello；sizeof(str)的值为10(数组长度）,strlen(str)的值为5（字符串长度）.这些函数是考试常用到的函数，大家一定要熟练应用这几个函数。第十章第十章 结构体与共用体结构体与共用体【考点【考点1 1】结构体类型的说明】结构体类型的说明结构体是若干个类型数据的集合，结构体类型说明格式如下：struct 类型名 类型1 成员名

30、1；类型2 成员名2;；,以上整个部分是一个数据类型，与整型的int是同样地位。可用typedef把结构体类型替换成一个只有几个字母的简短标识符。【考点【考点2 2】结构体变量的定义】结构体变量的定义结构体变量是用说明的结构体类型所定义的一个变量，与结构体类型不是一回事。一个结构体变量所占字节数为其所有成员所占字节数之和。如struct stuchar name10；int age;a,b；则表明定义了两个结构体变量a,b，每个变量占14个字节。a,b与int i,j；中的变量i,j是同样地位。【考点【考点3 3】结构体成员的引用】结构体成员的引用引用成员可用以下3种方式：（1）结构体变量名.

31、成员名（;2）指针变量名-成员名：（3）(*指针变量名)。成员名.点(。)称为成员运算符，箭头（-）称为结构指向运算符.【考点【考点4 4】链表】链表链表是由一个个结点构成的，一个结点就是一个结构体变量.每个结点可以分为数据域与指针域两个部分，数据域用来存放要存储的数据，指针域用来指向下一个结点。链表是考试中的难点，在C语言和公共基础部分都会考到，要领悟掌握。【考点【考点5 5】共用体】共用体共用体的使用格式与结构体相似，共用体定义的关键字为union，共用体所占字节数是所有成员中字节数最大的那个。第十一章第十一章 文件文件【考点【考点1 1】文件类型指针】文件类型指针文件指针是一个指向结构体

32、类型的指针，定义格式为：FILE*指针变量名。在使用文件时，都需要先定义文件指针。【考点【考点2 2】文本文件与二进制文件】文本文件与二进制文件文本形式存放的是字符的ASCII码，二进制形式存放的是数据的二进制。例如“100”如 果 是 文 本 形 式 就 是 存 储1、0、0三个字符的 ASCII码（00110001 00110000 00110000）,如果是二进制形式就把100转化成二进制(01100100）。【考点【考点3 3】打开文件】打开文件文件的打开形式如下：FILE fp;fp=fopen(“c：lab。c”，rb)；。fopen函数的前面一部分为文件名，后面一部分为文件的使用

33、方式。打开方式详见教材第127页，其中r代表读，w代表写，a代表添加，b代表二进制位的.【考点【考点4 4】文件函数】文件函数判断文件结束feof函数，移动文件指针位置fseek函数，获得文件位置ftell函数，文件位置移到开头rewind函数，文件字符输入输出 fgetc函数和 fputc函数,文件输入输出fscanf函数和fprintf函数，文件字符串输入输出fgets函数和 fputs函数,读写二进制文件fread函数和fwrite函数.以上函数要求知道格式会用，清楚是用于二进制文件还是文本文件，要把教材文件这章仔细复习下，不要在考试的时候把这些文件函数搞混了.第十二章第十二章 深入讨论

34、深入讨论【考点【考点1 1】编译预处理】编译预处理凡以开头的这一行，都是编译预处理命令行,编译预处理不加分号，不占运行时间.宏替换仅是简单的文本替换，如definef(x）(x）(x）和#definef(x)xx替换（f 2+2)时就有区别,前者展开为（2+2)*(2+2），后者为2+22+2.如果源文件f2.c中有include”f1。c”可以理解为把源文件f1.c原样包含到f2。c中,使f1。c和f2.c融合到一起成为一个 C程序编译。所以一个C程序必有主函数，但一个 C源文件未必有主函数。【考点【考点2 2】标识符作用域】标识符作用域局部变量是在函数内或复合语句内定义的变量，作用域为定义

35、它的函数内。局部变量有三种类型:自动auto,寄存器register和静态static。自动变量随着函数的使用与否创建消失；寄存器变量分配在cpu中，没有内存地址;静态变量占用固定存储单元，在程序执行过程不释放，直到程序运行结束.全局变量是在函数外定义的变量,作用域从定义它的位置到整个源文件结束为止，生存期为整个程序运行期间。全局变量都是静态变量。【考点【考点3 3】动态存储分配】动态存储分配malloc（size）用来创建连续size个字节存储区，返回值类型为void 型.malloc函数常用于动态创建链表结点，如int p；入到计算机中并被计算程序识别和处理的符号的总称，如文档，声音，视频

36、等。数据元素:数据元素是数据的基本单位。数据对象：数据对象是性质相同的数据元素的集合。数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。p=(int）malloc（sizeof(int）)；。calloc（n，size）创建n个同一类型的存储空间，可以理解为n个malloc。free（p)释放动态分配的存储单元。第二部分第二部分 公共基础知识资料公共基础知识资料第一章第一章数据结构与算法数据结构与算法【考点【考点1 1】算法的基本概念】算法的基本概念算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法.算法的基本特征：确定性，算法中每一步骤都

37、必须有明确定义,不允许有多义性;有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；可行性，算法原则上能够精确地执行；拥有足够的情报。算法的组成要素:一个算法由数据对象的运算和操作以及其控制结构这两部分组成。算法的基本运算和操作：算术运算，逻辑运算，关系运算，数据传输。算法的基本控制结构:顺序，选择，循环。算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术。【考点【考点2 2】算法的复杂度】算法的复杂度算法效率的度量-算法的复杂度：时间复杂度和空间复杂度。算法时间复杂度：指执行算法所需要的计算工作量。通常，一个算法所用的时间包括编译时间和运行时间。算法空间复杂度：指执行这

38、个算法所需要的内存空间。包括算法程序所占的空间,输入的初始数据所占的空间，算法执行过程中所需的额外空间.空间复杂度和时间复杂度并不相关。【考点【考点3 3】数据结构的基本概念】数据结构的基本概念数据：数据是客观事物的符号表示，是能输【考点【考点4 4】逻辑结构和存储结构】逻辑结构和存储结构数据结构可分为数据的逻辑结构和存储结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述,与数据的存储无关,是面向问题的,是独立于计算机的.它包括数据对象和数据对象之间的关系。数据的存储结构也称为数据的物理结构，是数据在计算机中的存放的方式，是面向计算机的，它包括数据元素的存储方式和关系的存储方式。数据结构和逻

39、辑结构的关系：一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对应。常见的存储结构有:顺序,链接，索引等。采用不同的存储结构其数据处理的效率是不同的。【考点【考点5 5】线性结构和非线性结构】线性结构和非线性结构线性结构的条件(一个非空数据结构）：(1)有且只有一个根结点;（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。栈、队列、双向链表是线性结构，树、二叉树为非线性结构。【考点【考点6 6】线性表及其顺序存储结构】线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号,元素之间的相对位置是线性

40、的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录；由多个记录构成的线性表称为文件.非空线性表的结构特征：（1）有且只有一个根结点a1，它无前件;（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件.结点个数n称为线性表的长度，当n=0时,称为空表。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的;（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的.元素ai的存储地址为：ADR(ai)=ADR（a1)+（i1）k,ADR(a1）为第一个元素的地址,k代表每个元素占的字节数。顺

41、序表的运算：查找、插入、删除。【考点【考点7 7】线性链表】线性链表线性链表是线性表的链式存储结构，数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。结点由两部分组成：(1)用于存储数据元素值，称为数据域；(2)用于存放指针,称为指针域，用于指向前一个或后一个结点.在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的.链式存储方式既可用于表示线性结构，也可用于表示非线性结构.线性单链表中,HEAD称为头指针，HEAD=NULL（或0）称为空表。双向链表有两个指针：左指针

42、（Llink）指向前件结点，右指针（Rlink)指向后件结点.循环链表：循环链表与单链表的不同的是它的最后一个结点的指针域存放的事指向第一个结点的指针而单链表存放的是空指针。线性链表的基本运算：查找、插入、删除。【考点【考点8 8】栈】栈1、栈的基本概念栈是一种特殊的线性表，只允许在表的一端进行插入和删除的线性表；插入,删除的一端为栈顶,另一端为栈底;当表中没有元素时为空栈。栈是一种后进先出（或先进后出Last In FirstOut)的线性表。栈具有记忆功能.栈的实例:火车调度,子弹夹。2、栈的存储结构顺序存储结构：用一组地址连续的存储单元即一维数组来存储；链式存储：用线性链表来存储；3、栈

43、的基本运算（1)入栈运算，在栈顶位置插入元素；(2）退栈运算，删除元素(取出栈顶元素并赋给一个指定的变量)；(3)读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。【考点【考点9 9】队列】队列1.队列的基本概念队列是一种特殊的线性表,只允许在表的一端插入，在另一端删除，允许插入的一端是队尾（rear），允许删除的一端为队头（front）；当表中没有元素是空队列；队列是一种先进先出的线性表。(FIFO）2、队列的存储结构顺序存储：一维数组.链式存储:线性链表。3、队列的运算:（1)入队运算：从队尾插入一个元素；（2)退队运算：从队头删除一个元素.队列的顺序存储结构一般采用循环队列的形式

44、。循环队列 s=0表示队列为空;s=1且front=rear表示队满。计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。【考点【考点1010】树的基本概念】树的基本概念树是一种非线性结构，是n个结点的有限集。当n=0 时为空树，n0时为非空树。结点的度：结点所拥有的子树的个数.叶子结点：度为0的结点.分支结点：除叶子结点以外的结点。结点的层次:根结点在第一层，同一层上左右结点的子结点在下一层。树的深度：所处层次最大的那个结点的层次。树的度：树中所有结点的度的最大值.【考点【考点1111】二叉树及其基本性质】二叉树及其基本性质1、二叉树的概念二叉树是一种特殊的树形结构,每个结

45、点最多只有两棵子树,且有左右之分不能互换，因此，二叉树有五种不同的形态，见教材12页.2、二叉树的性质性质1 在二叉树的第k层上，最多有2k1(k1）个结点。性质2 深度为m的二叉树最多有 2m1个结点。性质3 在任意一棵二叉树中，度为0的结点（叶子结点)总是比度为2的结点多一个.性质4 具有n个结点的二叉树，其深度不小于log2n+1,其中log2n表示为log2n的整数部分。3、二叉树的存储结构：详见教材第13-14页。【考点【考点1212】满二叉树与完全二叉树】满二叉树与完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点.在满二叉树中，每一层上的结点数都达到最大值，即在满

46、二叉树的第k层上有2k1个结点,且深度为m的满二叉树有2m1个结点。完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点.满二叉树是完全二叉树，而完全二叉树一般不是满二叉树.【考点【考点1313】完全二叉树的性质】完全二叉树的性质性质1 具有n个结点的完全二叉树的深度为log2n+1。性质2 完全二叉树中度为 1的结点数为 0或1。【考点【考点1414】二叉树的遍历】二叉树的遍历前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树;并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树.前序遍历图5可得：ABCDFHEG

47、。中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树;并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历图5可得:BAFHDCGE。后序遍历:先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历图5可得：BHFDGECA。【考点【考点1515】顺序查找】顺序查找顺序查找是从表的一端开始，依次扫描表中的各个元素，并与所要查找的数进行比较。在下列两种情况下也只能采用顺序查找:（1)如果线性表为无序表,则不管是顺序存储结构还是链式存储结构，只能用顺序查找。(2）即使是有序线性表，如果采

48、用链式存储结构，也只能用顺序查找.【考点【考点1616】二分查找】二分查找二分查找的条件：（1）用顺序存储结构（2）线性表是有序表.查找的步骤:详见教材第16页。对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次.【考点【考点1717】排序】排序1、交换排序(1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为n（n1）/2.（2)快速排序法，在最坏的情况下，快速排序需要比较次数为n（n1)/2。2、插入类排序法:（1)简单插入排序法，最坏情况需要n（n1)/2次比较;(2)希尔排序法，最坏情况需要O(n1。5）次比较。（大写O是算法复杂度的表示方

49、法）3、选择类排序法:(1）简单选择排序法,最坏情况需要n(n1)/2次比较；（2）堆排序法，最坏情况需要 O(nlog2n)次比较.相比以上几种（除希尔排序法外），堆排序法的时间复杂度最小。第二章第二章程序设计基础程序设计基础【考点【考点1 1】程序设计方法与风格】程序设计方法与风格形成良好的程序设计风格需注意：（详见教材第19页)。1、源程序文档化；2、数据说明的方法；3、语句的结构；4、输入和输出。注释分序言性注释和功能性注释。语句结构清晰第一、效率第二。【考点【考点2 2】结构化程序设计方法的四条原则】结构化程序设计方法的四条原则1、自顶向下;2、逐步求精；3、模块化；4、限制使用go

50、to语句。【考点【考点3 3】结构化程序的基本结构】结构化程序的基本结构顺序结构:是最基本、最普通的结构形式，按照程序中的语句行的先后顺序逐条执行。选择结构：又称为分支结构,它包括简单选择和多分支选择结构。循环结构：根据给定的条件，判断是否要重复执行某一相同的或类似的程序段。循环结构对应两类循环语句:先判断后执行的循环体称为当型循环结构;先执行循环体后判断的称为直到型循环结构。【考点【考点4 4】面向对象的程序设计及面向对象】面向对象的程序设计及面向对象方法的优点方法的优点面向对象的程序设计以对象为核心,强调对象的抽象性,封装性，继承性和多态性。面向对象方法的优点（1）人类习惯的思维方法一致；