计算机二级C语言重点笔试复习资料

《计算机二级C语言重点笔试复习资料》由会员分享，可在线阅读，更多相关《计算机二级C语言重点笔试复习资料（32页珍藏版）》请在装配图网上搜索。

1、C语言最重要的知识点复习资料笔试注意事项【考点5】书写格式1、笔试满分100分，共两大题，选择 70分40小题，填空30分15小题。C语 言占70分，公共基础占30分。选择题的前10题和填空题的前5题考公共基础知识， 其他考知识。C语言笔试时间为 2010年3月27日上午9:00-10:30。2、选择用铅笔涂答题卡，填空用黑色签字笔在答题上写。3、 考前准备好身份证、准考证、2B铅笔、橡皮、黑色签字笔、手表等。第一章吾言基本知识【考点1】C程序C语言程序结构有三种：顺序结构,循环结构(三个循环结构),选择结构(if和 switch)【考点2】main函数每个C语言程序中main函数是有且只有一

2、个。读程序都要从main()入口，然后 从最上面顺序往下读(碰到循环做循环，碰到选择做选择)。【考点3】存储形式计算机的数据在电脑中是以二进制的形式保存。最低的存储单元是bit (位)，位是由为0或者1构成。byte是指字节，一个字节=八个位。数据存放的位置就是 它的地址。【考点4】注释是对程序的说明，可岀现在程序中任意合适的地方，注释从“/* ”开始到最近一个“*/”结束，其间任何内容都不会被计算机执行，注释不可以嵌套。每条语句的后面必须有一个分号，分号是语句的一部分。一行内可写多条语句， 一个语句可写在多行上。【考点6】标识符合法的用户标识符考查：合法的要求是由字母，数字，下划线组成。有其

3、它元素就错了。 并且第一个必须为字母或则是下划线。第一个为数字就错了。C语言标识符分如下 3类(1) 关键字。它们在程序中有固定的含义，不能另作他用。女口int、for、switch 等。(2) 预定义标识符。预先定义并具有特定含义的标识符。如define、include等。(3) 用户标识符。用户根据需要定义的标识符，符合命名规则且不与关键字相 同。关键字不可以作为用户标识符号。main define scanf printf都不是关键字。迷惑你的地方If是可以做为用户标识符。因为If中的第一个字母大写了，所以不是关键 字。【考点7】实型数据实型数据的合法形式：小数形式和指数形式。掌握判定指

4、数形式合法性。2.333e-1就是合法的，且数据是 2.333X 10-1。考试口诀：e前e后必有数，e后必为整数。【考点8字符字符数据的合法形式:1是字符占一个字节，1是字符串占两个字节(含有一个结束符号)oO的ASCII数值表示为48, a的ASCII数值是97, 7V的ASCII数值是65字符型和整数是近亲：char a = 65 ;printf( a%c，觴到的输出结果：aprintf( “d，鵝到的输出结果：65一般考试表示单个字符错误的形式：65 1字符是可以进行算术运算的，记住：0-0=48大写字母和小写字母转换的方法：,A+32=a,相互之间一般是相差32 o【考点9整型数据整

5、型一般是两个字节，字符型是一个字节，双精度一般是 4个字节：考试时候一般会说，在16位编译系统，或者是32位系统。碰到这种情况，不 要去管，一样做题。掌握整型一般是两个字节，字符型是一个字节，双精度一般是 4个字节就可以了。【考点10转义字符转义字符的考查：在程序中inta = 0x6d,是把一个十六进制的数给变量 a注意这里的Ox必须存 在。在程序中int a = 06d,是一个八进制的形式。在转义字符中，x6d才是合法的，0不能写，并且x是小写。H4T是合法的，0是不能写的。H08是非法的，因为不可以出现 8o【考点111算术运算算术运算符一共有+、一、*、/、这五个。符号两边要求是整数。

6、不是整数就错了三种取整丢小数的情况：不是四舍五入是舍掉小数部分。1、int a =1.6；2、（int）a ；3、1/2;3/2;【考点12强制类型转换将一个运算对象转换成指定类型，格式为（类型名）表达式一定是 （int） a不是int （a）,注意类型上一定有括号的。注意（int） （ a+b）和（int） a+b的区别。前是把a+b转型，后是把a转型再 加bo【考点13赋值是表达式就一定有数值。赋值表达式：表达式数值是最左边的数值，a=b=5;该表达式为5,常量不可以赋值。复合赋值运算符：注意：a*=m+2 是 a=a*（m+2）自加、自减表达式：假设a=5, +a （表达式的值为6） ,

7、 a+ （表达式的值为5）;j=a+;等价于 j=a;a=a+1; Mj=+a;等价于 a=a+1 ;j=a;。考试口诀：+在前先加后用，+在后先用后加。【考点14逗号运算逗号表达式：优先级别最低；表达式的数值逗号最右边的那个表达式的数值。（2, 3, 4）的表达式的数值就是4o【考点15数制转换一定要记住二进制如何转换成十进制。八进制是没有8的，逢8进1, 018的数值是非法的。【考点16位运算会有一到二题考试题目。C语言提供6种位运算符：按位求反，按位左移vv,按位右移 ,按位与&,按 位异或|,按位或Ao总的处理方法：几乎所有的位运算的题目都要按这个流程来处理（先把十进制 变成二进制再变

8、成十进制）。异或运算的规则：0异或1得到1, 0异或0得到0, 1异或1得到0。可记为“相 同为0,不同为见教材31页例1 o在没有舍去数据的时候，vv左移一位表不乘以2; 右移一位表不除以2o第二章数据的输入输出（顺序结构）【考点1 printf函数格式为：printf（输出控制，输出列表）o输出控制是用一对双引号括起来的，包 含格式说明和原样信息。输出列表包含若干输出项。%d对应整型，f对应单精度实型， c对应字符型，o对应八进制无符号整型，x对应无符号十六进制整型，u对应无符号整型，eM应指数型，sM应字符串型。可在和格式字符之间加一个数来控制数据所占的宽度和小数位数。【考点2】scan

9、f函数格式为：scanf(输入控制，输入列表)注意该函数的第二个部分是 &a这样的地址，不是a；scanf( “d%d%*d%d,&a,&b,&c);跳过输入的第三个数据。【考点3 putchar与getchar函数可用于输出或输入 单个字符，这两个函数是stdio.h文件中的库函数，它们是printf 与scanf函数的简化。char a = getchar()是没有参数的，从键盘得到你输入的一个字符给变量a。putchar( y把字符y输出到屏幕中。【考点4】如何交换两个变量如何实现两个变量x , y中数值的互换(要求背下来)不可以把 x=y ,y=x;要用中间变量 t=x; x=y ;

10、y=t。【考点5】实现保留三位小数如何实现保留三位小数，第四位四舍五入的程序，(要求背下来)float x=12.34567;float y=(int)(x*1000+0.5)/1000.0;这个有推广的意义，注意x= (int) x这样是把小数部分去掉。第三章选择结构特别要注意：c语言中是用非0表示逻辑真的，用0表示逻辑假的。【考点1 关系运算关系运算符有6个，分别是,=,8这个是真的，所以表达式的数值就是1o【考点2逻辑运算只能为1 （表不为真），或0 （表不假）a）共有三种逻辑运算符号。逻辑非（！），辑与（& ）,逻辑或（|） ob）! &|优先的级别。c）注意短路现象。考试比较喜欢考到

11、。例a+|b+,如果表达式a+的值非零，则表达式 b+不再执行。d）要表示x是比0大，比10小的方法。OvxBO是不可以的（一定记住）。是先计 算Ovx得到的结果为1或则0;再用0,或1与10比较得到的总是真（为1） o所以一 定要用（0=6.cib呈实期指针变量是用来存储地址的，而一般变量是存储数值的。指针变量可指向任意，.I；i rvi a1叫行首地址，是地址常量。*(a0+1)是第一行第一个元素往后跳一列， 即元素a01值为2, *(a0+3)是第一行第一个元素往后跳三个，即元素a10值为4。【考点5行指针是一个指针变量，占四个字节，行指针指向一行连续数据，形式为：int (*p)2;,

12、 p只能存放含有 两个整型元素的一维数组的首地址o注意(*p)两边的小括号不能省略，否则就成了指针数组，是若干指针元素的集合。【考点6数组名数组名是数组的首地址。数组名不能单独引用，不能通过一个数组名代表全部元素。数组名是地址常量，不能对数组名赋值，所以a+是错误的。但数组名可以作为地址与一个整数相加得到一个新地址。【考点7元素形式的转换助记：“脱衣服法则” a2变成*(a+2) , a23变成*(a+2)3再可变成*(*(a+2)+3)。 这个思想很重要！二维数组做题目的技巧：如果有 a33=1,2,3,4,5,6,7,8,9这样的题目。步骤一：把他们写成： 第一列 第二列 第三列a0123

13、- 第一行a1456 第二行a2789 -第三行步骤二：这样作题目间很简单：*(a0+1)我们就知道是第一行的第一个元素往后面跳一列，那么这里就是a01元素，所以是1。*(a1+2)我们就知道是第二行的第一个元素往后面跳二列。那么这里就是a12元素，所以是6o一定记住：只要是二维数组的题目，一定是写成如上的格式，再去做题目，这 样会比较简单。两种重要的数组长度：chara=a敝组长度为乃，字符串长度不定。sizeof(a)为3。char a5= a,数组长度的5,字符串长度3。sizeof(a)为5。第八章字符串【考点1字符串常量及表示字符串常量是由双引号括起来的一串字符，女口” ABC”。在

14、存储字符串时，系统 会自动在其尾部加上一个空值0,空值也要占用一个字节，也就是字符串”ABC需要占四个字节。【考点2字符数组C语言没有字符串变量，只能采用字符数组来存储字符串。数组的大小应该比它 将要实际存放的最长字符串多一个元素，从而存放0。【考点3字符串赋值字符串赋值的两种形式：charstr= Hello!;或 char*p;p= Hello!但不能用下面的形式：char str1O;str= w Hellow ;因为str是一个地址常量，不能 进行赋值操作。【考点4字符串的输入与输出可以用scanOprintf函数，女口 scanf( %s ,str);,也可用专门处理字符串的两个函数

15、 gets 和puts函数，还可以对字符数组逐个元素进行赋值，但一定要在最后赋一个0。使用gets数可以接收空格，使用 puts函数在最后输出一个换行。scanf和gets的数据：如果输入的是 good good study!那么scanf( a%s ,a)R会接收good.考点：不可以接收空格。gets(a);会接收 good good study!考点：可以接收空格。【考点5字符串函数要掌握的四个字符串函数：字符串拷贝函数strcpy (),求字符串长度函数strlen(),字符串链接函数strcat (),字符串比较函数strcmp ()。使用这些函数需在预处理部分包含头文件string

16、.h。字符串长度要小于字符数组的长度，例： char str10=w Hellow jsizeof(str)的值为10 (数组长度)，strlen(str)的值为5 (字符串长度)。这些函数是考试常用到的函数， 大家一定要熟练应用这几个函数。第九章文件【考点11文件类型指针文件指针是一个指向结构体类型的指针，定义格式为：FILE*指针变量名。在使用文件时，都需要先定义文件指针。【考点2文本文件与二进制文件文本形式存放的是字符的ASCII码，二进制形式存放的是数据的二进制。例如“100”如果是文本形式就是存储T、0、 0三个字符的ASCII码(0011000100110000 00110000)

17、,如果是二进制形式就把 100转化成二进制(01100100) o【考点3打开文件文件的打开形式：FILE *fp;fp=fopen( c:lab.c，” rb);。fopen函数的前面一部分为文件名，后面一部分为文件的使用方式。打开方式见 教材第116页，其中r代表读，w代表写，a代表添加，b代表二进制位的。【考点4文件函数判断文件结束feof函数，移动文件指针位置fseek函数，获得文件位置ftell函数， 文件位置移到开头rewind函数，文件字符输入输出fgetc函数和fputc函数，文件输入输出fscanf函数和fprintf函数，文件字符串输入输出fgets函数和fputs函数，读

18、写 二进制文件fread函数和fwrite函数。以上函数要求知道格式会用，清楚是用于二进制文件还是文本文件。上课时候 讲的文件这一章的题目要做一遍，一定要做，基本上考试的都会在练习当中。第十章对C语言的深入探讨【考点11编译预处理凡以#开头的这一行，都是编译预处理命令行，编译预处理不加分号，不占运行时间。宏替换仅是简单的文本替换，如#define f(x) (x)*(x)和#define f(x) x*x替换f(2+2)时就有区别，前者展开为(2+2)*(2+2),后者为2+2*2+2。如果源文件f2.c中有#includew f1.cw可以理解为把源文件f1.c原样包含到f2.c中，使f1.

19、c和f2.c融合到一起成为一个 C程序编译。所以一个 C程序必有主函数， 但一个C源文件未必有主函数。【考点2标识符作用域局部变量是在函数内或复合语句内定义的变量，作用域为定义它的函数内。局部变量有三种类型：自动 auto,寄存器register和静态statico自动变量随着函数的使用与否创建消失；寄存器变量分配在cpu中，没有内存地址；静态变量占用固定存储单元，在程序执行过程不释放，直到程序运行结束。全局变量是在函数外定义的变量，作用域从定义它的位置到整个源文件结束为 止，生存期为整个程序运行期间。全局变量都是静态变量。【考点3动态存储分配malloc(size)用来创建size个字节的连

20、续存储空间， 返回值类型为 void *型。malloc 函数常用于动态创建链表结点，女口 int *p; p=(int *)malloc(sizeof(int);。calloc (n,size)创建n个同一类型的连续存储空间，可以理解为n个malloc。int *p; p=(int *) calloc (10 , sizeof(int); o p 指向首地址。free(p)释放动态分配的存储单元。【考点4 main函数的参数还有main (intargc , char*argv )这种含有参数的题目，是很呆板的题目。第一个参数是表示输入的字符串的数目，第二个参数是指向存放的字符串。【考点5函

21、数指针函数指针的用法(*f)()记住一个例子：int add(int x, int y)main()int (节)()；f=add;赋值之后：合法的调用形式为1、add(2, 3);2、f(2, 3);3、(节)(2, 3)第一章结构体和共用体【考点11结构体类型的说明结构体是若干个类型数据的集合，结构体类型说明格式：struct类型名类型1成员名1;类型2成员名2;,以上整个部分是一个数 据类型，与整型的int是同样地位。可用typedef把结构体类型替换成一个只有几个字 母的简短标识符。【考点2结构体变量的定义结构体变量是用说明的结构体类型所定义的一个变量，与结构体类型不是一回事。一个结构

22、体变量所占字节数为其所有成员所占字节数之和。如struct stucharname10;int age; a,b;则表明定义了两个结构体变量 a,b,每个变量占14个字节。a,b与 int i,j;中的变量i,j是同样地位。typedef考的很多（教材150页例6）。【考点3结构体成员的引用引用成员可用以下 3种方式：（1）结构体变量名成员名；（2）指针变量名-成 员名：（3） （*指针变量名）成员名。点（.）称为成员运算符，箭头（-）称为结构 指向运算符。【考点5共用体共用体的使用格式与结构体相似，共用体定义的关键字为union ,共用体所占字节数是所有成员中字节数最大的那个。union T

23、Tint a;char ch2; t1 ;main（）t1.a=0x1234;线性链表1 2分20%栈及其基本运算2 4分100%队列及其基本运算树与二叉树26100%查找于排序技术2480%第二章程序设计基础知识点所占分值考核几率程序设计方法与风格0 2分40%结构化程序设计0 2分20%面向对象程序设计0 2分70%知识点所占分值考核几率软件工程基本概念2480%软件分析及其方法0240%软件设计及其方法2460%软件测试2480%程序的调试0280%第三章软件工程基础知识点所占分值考核几率算法24分50%知识点乂匚丄匚I宀K /亠占厶七片丄数据结构的基本概念24分50%数据库系统的基本概

24、线性表及其顺序存储结构1 2分50%数据模型第一章数据结构与算法第三章软件工程基础 所占分值2426考核几率100%90%printf(%xn,t1.ch0);printf(%xn,t1.ch1 );考点一：sizeof (struct TT) = 2;考点二：TT t1 ; t1.a=0x1234;那么 ch0=0x 34; ch1=0x127)结构体和共用体以及链表要掌握最简单的。typedef考的很多，而且一定要知道如何引用结构体中的各个变量，链表中如何填加和删除节点，以及何如构成一个简单的链表，一定记住链表中的节点是有两个域，一个放数值，一个放指针。【考点4】链表链表是由一个个结点构成

25、的，一个结点就是一个结构体变量。每个结点可以分为数据 域与指针域两个部分，数据域用来存放要存储的数据，指针域用来指向下一个结点。 链表是考试中的难点，在 C语言和公共基础部分都会考到，要掌握，链表中如何增加 和删除节点(每年都考)，以及何如构成一个简单的链表，一定记住链表中的节点是 有两个域，一个放数值，一个放指针。(教材162页例2 一定要看懂)二、公共基础关系代数0250%数据元素：数据元素数据库库设计与管理2440%数据对象：数据对象第一章数据结构与算法【考点1】算法的基本概念算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。算法不等于程序， 也不等于计算方法。算法的基本特征：确

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

27、这个算法所需要的内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。空间复杂度和时间复杂度并不相关。【考点3】数据结构的基本概念数据：数据是客观事物的符号表示，是能输入到计算机中并被计算程序识别和处理的 符号的总称，如文档，声音，视频等。是数据的基本单位。是性质相同的数据元素的集合。数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。【考点4】逻辑结构和存储结构数据结构可分为数据的逻辑结构和存储结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述，与数据的存储无关，是面向问题的，是独立于计算机的。它包括数据对象和数据对象之间的关系。数据的存储结

28、构也称为数据的物理结构，是数据在计算机中的存放的方式，是面向计算机的，它包括数据元素的存储方式和关系的存储方式。数据结构和逻辑结构的关系： 一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对应。常见的存储结构有：顺序，链接，索引等。采用不同的存储结构其数据处理的效率是不同的。【考点5】线性结构和非线性结构线性结构的条件（一个非空数据结构）：（1 ）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。栈、队列、双向链表是线性结构，树、二叉树为非线性结构。【考点6】线性表及其顺序存储结构线性表是由一组数据元素构

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

30、)+(i-1)*k ，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运算：查找、插入、删除。【考点7】线性链表线性链表是线性表的链式存储结构，数据结构中的每一个结点对应于一个存储单元， 这种存储单元称为存储结点，简称结点。结点由两部分组成：(1)用于存储数据元素值，称为数据域；(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。图2双链表的结构循环链表：循环链表与单链表的不同的是它的最后一个结点的指针域存放的事指向

31、第 一个结点的指针而单链表存放的是空指针。图3循环链表的结构线性链表的基本运算：查找、插入、删除。【考点8】栈1、栈的基本概念栈是一种特殊的线性表，只允许在表的一端进行插入和删除的线性表；插入，删除的一端为栈顶，另一端为栈底；当表中没有元素时为空栈。栈是一种后进先出(或先进后出Last In First Out )的线性表。栈具有记忆功能。栈的链式存储方式既可用于表示线性结构，也可用于表示非线性结构。实例：火车调度，子弹夹线性单链表中，HEAD称为头指针，HEAD=NULL (或0)称为空表。数据域指针域-数据域指针域 -数据域指针域图1单链表的结构双向链表有两个指针：左指针(Llink )指

32、向前件结点，右指针(Rlink)指向后件结点。2、栈的存储结构顺序存储结构：用一组地址连续的存储单元即一维数组来存储；链式存储：用线性链表来存储；3、栈的基本运算(1) 入栈运算，在栈顶位置插入元素；(2) 退栈运算，删除元素(取岀栈顶元素并赋给一个指定的变量)(3) 读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。【考点9】队列1队列的基本概念队列是一种特殊的线性表，只允许在表的一端插入，在另一端删除，允许插入的一端 是队尾（rear），允许删除的一端为队头（front）；当表中没有元素是空队列；队列是 一种先进先岀的线性表。（FIFO）2、队列的存储结构顺序存储：一维数组。链式存

33、储：线性链表。3、队列的运算：（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。队列的顺序存储结构一般采用循环队列的形式。循环队列s=0表示队列为空；s=1且front=rear表示队满。计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。【考点10】树的基本概念树是一种非线性结构， 是n个结点的有限集。当n=0时为空树，n0时为非空树。结 点的度：结点所拥有的子树的个数。叶子结点：度为0的结点。分支结点：除叶子结点以外的结点。结点的层次：根结点在第一层，同一层上左右结点的子结点在下一层。树的深度：所处层次最大的那个结点的层次。树的度：树中所有结点的度的

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

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

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

37、 查找。(2) 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。【考点16】二分查找二分查找的条件：(1)用顺序存储结构(2)线性表是有序表。查找的步骤：详见教材第 16页。对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较Iog2n次，而顺序查找需要比较 n次。【考点17】排序1、交换排序(1) 冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为n(n 1)/2。(2) 快速排序法 ，在最坏的情况下，快速排序需要比较次数为n(n 1)/2。2、插入类排序法：(1) 简单插入排序法，最坏情况需要 n(n-1)/2次比较;(2)希尔排序法，最坏情况需要0(n1.5)次比较。(大

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

39、是最基本、最普通的结构形式，按照程序中的语句行的先后顺序逐条执行。 选择结构：又称为分支结构，它包括简单选择和多分支选择结构。循环结构：根据给定的条件，判断是否要重复执行某一相同的或类似的程序段。循环结构对应两类循环语句：先判断后执行的循环体称为当型循环结构；先执行循环体后判断的称为直到型循环结构。【考点4】面向对象的程序设计及面向对象方法的优点面向对象的程序设计以对象为核心，强调对象的抽象性，封装性，继承性和多态性。面向对象方法的优点(1) 人类习惯的思维方法一致；(2)稳定性好；(3)可重用性好；(4) 易于开发大型软件产品；(5)可维护性好。【考点5】对象及其特点名称描述程序软件开发人员

40、根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列数据使程序能正常操纵信息的数据结构文档与程序的开发、维护和使用有关的图文资料软件指的是计算机系统中与硬件相互依存的另一部分，包括程序、数据和相关文档的完整集合。软件的特点：软件是一种逻辑实体，具有抽象性；名称描述应用软件:为解决特定领域的应用而开发的软件，如办公自动化软件系统软件计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件，如操作系统支撑软件（或工具软件）支撑软件是介于两者之间，协助用户开发软件的工具性软件。【考点2】软件的生命周期对象（object）:面向对象方法中最基本的概念， 可以用来表示客观世界

41、中的任何实体， 对象是实体的抽象。对象的基本特点：（1）标识惟一性； （2 ）分类性； （3 ）多态性； （4 ）封装性； （5）模块独立 性好。【考点6】属性，类和实例属性：即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来 改变。类：是具有相似属性与操作的一组对象。类是关于对象性质的描述。类是对象的抽象， 对象是其对应类的一个实例。【考点7】消息及其组成消息：是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。它请求 对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。消息的组成包括：（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个

42、或多个参数。【考点8】继承和多态继承：是使用已有的类定义作为基础建立新类的定义技术，广义指能够直接获得已有的性质和特征，而不必重复定义他们。继承具有传递性，一个类实际上继承了它上层的全部基类的特性。继承分单继承和多重继承。 单继承指一个类只允许有一个父类， 即类等级为树形结构； 多重继承指一个类允许有多个父类。多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象第三章软件工程基础【考点1】软件定义与软件特点软件的生产与硬件不同，它没有明显的制作过程；软件在运行、使用期间不存在磨损、老化问题；软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制， 这导致了软件移植的问题；软件

43、复杂性高，成本昂贵；软件开发涉及诸多的社会因素。根据应用目标的不同，软件可分应用软件、系统软件和支撑软件（或工具软件）。软件生命周期是指软件产品从提岀、实现、使用维护到停止使用退役的整个过程。可分为软件定义，软件开发及软件维护 3个阶段。软件生命周期中，能够准确确定软件 系统必须做什么和必须具备哪些功能的阶段是：需求分析。名称描述方法方法是完成软件工程项目的技术手段(工具工具支持软件的开发、管理、文档生成从过程过程支持软件开发的各个环节的控制、管理【考点4】软件工程过程定义阶段开发阶段维护阶段【考点3】软件危机和软件工程的概念软件危机泛指在计算机软件的开发和维护过程中遇到的一系列严重的问题，集

44、中表现在成本，质量。生产效率等几个方面。所谓软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护。是 _立并使用完善的工程化原则，以较经济的手段获得，能在实际机器上有效运行的可靠 软件的一系列方法；软件工程的主要思想强调在软件开发过程中需要应用工程化原 则。软件工程的核心思想是把软件当作一个工程产品来处理。软件工程包括3个要素：方法，工具和过程软件工程过程是把软件转化为输岀的一组彼此相关的资源活动，包含4种基本活动：（1）P（plan）软件规格说明；（2） D（do）软件开发；（3）C（check）软件确认；（4） A（action）软件演进。【考点5】软件开发技术和软件工程管理软

45、件工程的理论和技术性研究的内容主要包括软件开发技术和软件工程管理。软件开发技术包括软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学。软件开发方法包括分析方法，设计方法和程序设计方法。软件工程管理包括软件管理学，软件工程经济学，软件心理学等。软件管理学包括人员组织，进度安排，质量保证，配置管理，项目计划等。 软件工程经济学是研究软件开发中成本的估算，成本效益的方法和技术。【考点6】软件工程的原则软件工程的原则：抽象，信息隐蔽，模块化，局部化，确定性，一致性，完备性，可 验证性（详细见教材第 28-29页）。【考点7】需求分析概述需求分析阶段的工作：需求获取，需求分析，

46、编写需求规格说明书，需求评审。需求分析方法有：（1 ）结构化需求分析方法； 面向数据结构的 Jackson方法（ISD）； 面向数据流的结构化分析方法（SA）；面向数据结构的结构化数据系统开发方法（DSSD ）；2）面向对象的分析的方法（00A ）需求分析建立的模型的特性来分：静态分析和动态分析。考点8】结构化方法和结构化分析方法结构化方法包括结构化分析方法，结构化设计方法，结构化编程方法。结构化方法中，软件功能分解属于总体设计阶段。2、结构化分析方法的概念结构化分析方法是面向数据流自顶而下逐步求精进行需求分析的方法。结构化分析方法在软件需求分析阶段的应用。3、结构化分析的常用工具数据流图（D

47、FD-Data Flow Diagram ）：是结构化分析方法中用于系统逻辑模型的一种 工具。它以图形的方式描绘在系统中流动和处理的过程。数据流图中四种基本的符号。箭头：表示数据流，数据流是数据在系统中传播的路径。圆或椭圆：表示加工，加工又称为数据处理，是对数据流进行某些操作或变换。双横：表示数据存储（数据源）。数据存储又称为文件，指暂时保存的数据，它可以 是数据库文件或任何形式的数据组织。方框：源、潭。表示数据的源点或终点。它是软件系统外部环境中的实体，统称外部 实体数据字典（DD ）:它是结构分析方法的核心，是用来描述系统中所用到的全部数据和 文件的文档，作用是对 DFD中出现的被命名的图

48、形元素进行确切解释。数据字典由以下4类元素组成（1）数据流（2）数据流分量 （3）数据存储（4）处理判定树（决策树）：是一种描述加工的图形工具，适合描述时候处理中具有多个判断， 而且每个决策与若干条件有关。判定表：与判定树类似，也是一种描述加工的图形工具。如果一个加工逻辑有多个条 件、多个操作，并且在不同的条件组合下执行不同的操作，那么可以使用判定表来描 述。【考点9】软件需求规格说明书软件需求规格说明书（ SRS，Software Requirement Specification ） 是需求分析阶段得 岀的最主要的文档。软件需求规格说明书的特点：有正确性、无歧义性、完整性、可 验证性、一致

49、性、可理解性、可修改性和可追踪性。其中最重要的是无歧义性。【考点10】软件设计的基本概念软件设计是确定系统的物理模型。软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的 唯一途径。从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。（1）结构设计定义软件系统各主要部件之间的关系；（2）数据设计将分析时创建的模型转化为数据结构的定义；（3）接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信；（4）过程设计则是把系统结构部件转换为软件的过程性描述。从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。（1）概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或 数据库模式；（2）详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数 据结构的细节。【考点11】软件设计的基本原理1、软件设计中应该遵循的基本原理和与软件设计有关的概念：模块化：把程序划分成独立命名且可独立访问的模块，每个模块完成一个子功能。抽象化：抽岀事物的本质特性而暂时不考虑它们的细节。信息隐藏和局部化：信息隐蔽是指在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的，实现信息隐蔽依靠对象的封装。模块