资源描述
/.
二级公共基础知识作为必考内容出现，出题形式为选择题前10道，占考试总分的10%。
考试其它比重：
1、C语言程序的结构 占总分1%
2、数据类型及其运算 占总分4%
3、选择结构程序设计 占比分的3%
4、循环结构 占比分的5%
5、数组的定义和引用 占比分的5%
6、函数 占比分的5%
7、编译预处理 占比分1%
8、指针 占比分的5%
9、结构体 占比分的3%
10、位运算 占比分的2%
11、文件操作 占比分的2%
考试方式
上机考试，时长120分钟
单选题40分（含公共基础10分），操作题60分（包括程序填空题、程序修改题、程序设计题）
第一部分 C语言知识复习资料
第一章 C语言基本知识（90分）
【考点1】C程序
用C语言编写的程序称为C语言源程序，源程序文件的后缀名为“.c”。源程序经编译后生成后缀名为“.obj”的目标文件，再把目标文件与各种库函数连接起来，生成“.exe”可执行文件。C语言有三种基本结构：顺序结构、选择结构、循环结构。
【考点2】main函数
又称主函数，是C程序的入口。main后面跟一对小括号和一对花括号，花括号括起来的部分称为main函数的函数体。一个C程序从main函数开始执行，到main函数体执行完结束，而不论main函数在整个程序中的位置如何。每一个程序有且仅有一个main函数，其他函数都是为main函数服务的。
【考点3】存储形式
计算机在电脑中保存数据是采用二进制形式，由0或1构成的二进制称为位（bit），八个位构成一个字节（Byte），1个Byte=8个bit。二进制、八进制、十六进制转化为十进制采用乘法，十进制转化为二进制、八进制、十六进制采用除法。数据的存放位置就是它的地址。
【考点4】注释
是对程序的说明，可出现在程序中任意合适的地方，注释从“/*”开始到最近一个“*/”结束，其间任何内容都不会被计算机执行，注释不可以嵌套。
【考点5】书写格式
每条语句的后面必须有一个分号，分号是语句的一部分。一行内可写多条语句，一个语句可写在多行上。
【考点6】标识符
是标识名字的有效字符序列，可以理解为C程序中的单词。
标识符的命名规则是：
（1）标识符只能由字母、数字和下划线组成，字母区分大小写。
（2）标识符的第一个字符必须是字母或下划线，不能为数字。
C语言标识符分如下3类
（1）关键字。它们在程序中有固定的含义，不能另作他用。如int、for、switch等。
（2）预定义标识符。预先定义并具有特定含义的标识符。如define、include等。
（3）用户标识符。用户根据需要定义的标识符，符合命名规则且不与关键字相同。
【考点7】常量与变量
常量是指在程序运行过程中，其值不能改变的量。常量分为整型常量、实型常量、字符常量、字符串常量、符号常量5种。在程序运行过程中其值可以改变的量称为变量。C语言中没有字符串变量。存放字符串使用字符数组。
【考点8】整型数据
整型常量有十进制、八进制、十六进制三种表示形式，没有二进制形式。八进制整型常量加前导数字0，十六进制常量加前导0X，八进制常量中不会出现8。
整型变量可分为基本整型（int）、短整型（short）、长整型（long）、和无符号整型（unsigned）。一个基本整型占4个字节。其它类型的整型占用字节数和取值范围详见教材第9页。
【考点9】实型数据
实型数据有两种表示形式：小数形式和指数形式。掌握判定指数形式合法性。
口诀：E前E后必有数，E后必须为整数。
实型变量分为单精度型（float）和双精度型（double），单精度型占四个字节。
【考点10】算术运算
算术运算符一共有+、—、*、/、%这五个。求余运算要求运算对象只能为整型，除法运算符两边运算对象都为整型时，运算结果也为整型即舍掉小数部分。
【考点11】强制类型转换
将一个运算对象转换成指定类型，格式为（类型名）表达式，注意小括号位置。
【考点12】赋值
赋值运算符为“=”，不同于关系等于“= =”。赋值表达式格式为：变量名=表达式，赋值运算符左边必须为变量，赋值运算是把赋值运算符右边表达式的值赋给左边变量。
复合赋值运算符是将算术运算符或位运算符与赋值运算符组合在一起组成的运算符，掌握复合赋值表达式转化为赋值表达式的方法。如n+=100可转化为n=n+100。
【考点13】自加自减运算
自加运算符“++”与自减运算符“--”是单目运算符，运算对象必须是变量。自增自减运算分前缀运算和后缀运算，它们所对应的表达式的值是有区别的，如j=i++;等价于j=i;i=i+1;而j=++i;等价于i=i+1;j=i;。
口诀：加加在前先加后用，加加在后先用后加。
【考点14】逗号运算
逗号运算符运算优先级最低，可将多个表达式构成一个新的表达式。
考试真题：
1、下列叙述中错误的是（D）——2006年4月选择第44题
A）C语言源程序经编译后生成后缀为.obj的目标程序
B）C语言经过编译、连接步骤之后才能形成一个真正可执行的二进制机器指令文件C）用C语言编写的程序称为源程序，它以ASCII代码形式存放在一个文本文件中D）C语言中的每条可执行语句和非执行语句最终都将被转换成二进制的机器指令2、下列叙述中错误的是（B）——2006年4月选择第45题
A）算法正确的程序最终一定会结束B）算法正确的程序可以有零个输出C）算法正确的程序可以有零个输入
D）算法正确的程序对于相同的输入一定有相同的结果3、下列叙述中错误的是（A）——2006年9月选择第11题
A）一个C语言程序只能实现一种算法B）C程序可以由多个程序文件组成C）C程序可以由一个或多个函数组成
D）一个C函数可以单独作为一个C程序文件存在4、下列叙述中正确的是（D）——2006年9月选择第12题
A）每个C程序文件中都必须要有一个main（）函数算法正确的程序对于相同的输入一定有相同的结果B）在C程序中main（）函数的位置是固定的
C）C程序中所有函数之间都可以相互调用，与函数所处位置无关D）在C程序的函数中不能定义另一个函数
5、在算法中，对需要执行的每一步操作，必须给出清楚、严格的规定，这属于算法的（C）——2007年4月选择第11题
A）正当性
B）可行性
C）确定性
D）有穷性
6、下列叙述中错误的是（D）——2007年4月选择第12题
A）计算机不能直接执行用C语言编写的源程序
B）C程序经C编译程序编译后，生成后缀为.obj的文件是一个二进制文件
C）后缀为.obj的文件，经连接程序生成后缀为.exe的文件是一个二进制文件
D）后缀为.obj和.exe的二进制文件都可以直接运行
7、下列叙述中错误的是（C）——2007年4月选择第14题
A）C语言是一种结构化程序设计语言
B）结构化程序由顺序、分支、循环3种基本结构组成
C）使用3种基本结构构成的程序只能解决简单问题
D）结构化程序设计提倡模块化的设计方法
8、对于一个正常运行的C程序，下列叙述中正确的是（A）—2007年4月选择第15题
A）程序的执行总是从main函数开始，在main函数结束
B）程序的执行总是从程序的第一个函数开始，在main函数结束
C）程序的执行总是从main函数开始，在程序的最后一个函数中结束
D）程序的执行总是从程序中的第一个函数开始，在程序的最后一个函数结束
9、C语言源程序名的后缀是（B）——2007年9月选择第11题
A）.exeB）.cC）.objD）.cp
10、下列叙述中正确的是（C）——2007年9月选择第14题
A）C语言程序将从源程序中第一个函数开始执行
B）可以在程序中由用户指定任意一个函数作为主函数，程序将从此开始执行C）C语言规定必须用main作为主函数名，程序将从此开始执行，在此结束D）Main可作为用户标识符，用以命名任意一个函数作为主函数
1.以下选项中合法的标识符是（2009年3月）c
A）1_1B）1-1C）_11D）1_2.以下选项中不合法的标识符是c（2008年4月）
A）printB）FORC）&aD）_00
3.可在C程序中用做用户标识符的一组标识符是（2007年9月）
A）andB）DateC）HiD）case_2007y-m-dDr.TomBigl
4.按照C语言规定的用户标识符命名规则，不能出现在标识符中的是（2007年4月）
A）大写字母B）连接符C）数字字符D）下划线5.以下不合法的用户标识符是（2006年4月）
A）j2_KEYB）DoubleC)4dD)_8_
1.以下选项中不属于字符常量的是（2008年4月）
A）CB）"C"C）\xCC0D）\0722.以下合法的字符常量的是
A）\x13B）‟\081‟C）65D）”\n”
3.已知大写字母A的ASCII码是65，小写字母a的ASCII码是97。下列不能将变量c中
的大写字母转换为对应小写字母的语句是（2007年4月）A）c=(c-„A‟)%26+‟a‟B）c=c+32C）c=c-„A‟+‟a‟D）c=(„A‟+c)%26-„a‟4.以下选项中，值为1的表达式________。（2006年9月）A）1-„0‟B）1-„\0‟C）‟1‟-0D）‟\0‟-„0‟1.以下选项中，能用作数据常量的是（2009年3月）
A）o115B）0118C）1.5e1.5D）115L2.以下选项中不能作为C语言合法常量的是（）。
A）cdB）0.1e+6C）"\a"D）\0113.以下不合法的数值常量是
A）011B）lelC）8.0E0.5D）0xabcd4.C源程序中不能表示的数制是（）。（2008年9月）
A）二进制
B）八进制
C）十进制
D）十六进制
5.以下关于long、int和short类型数据占用内存大小的叙述中正确的是（2007年9月）
A）均占4个字节
B）根据数据的大小来决定所占内存的字节数
C）由用户自己定义D）由C语言编译系统决定6.以下选项中，合法的一组C语言数值常量是（2007年9月）
A）028B）12.
C）.177
D）0x8A
.5e-3
0xa23
4e1.5
10,000
-0xf4.5e00abc3.e5
第二章 顺序结构
【考点1】运算符、表达式、语句
运算对象加运算符构成表达式，表达式加分号构成表达式语句，运算对象可以是表达式、常量、变量。如赋值运算符加运算对象构成赋值表达式，赋值表达式加分号又可构成赋值语句。
【考点2】运算符的优先级和结合顺序
运算符按参加运算的对象数目可分为单目运算符、双目运算符和三目运算符。初等运算符的优先级别最高，然后依次是单目运算符、算术运算符、关系运算符、逻辑运算符（除逻辑非！）、条件运算符、赋值运算符、逗号运算符。位运算符优先级介于算术运算符与逻辑运算符之间。结合顺序大多为自左向右，而自右向左的有三个：单目运算符、条件运算符和赋值运算符。
【考点3】printf函数
格式为：printf(输出控制，输出列表)。输出控制是用一对双引号括起来的，包含格式说明和原样信息。输出列表包含若干输出项。
【考点4】printf函数中格式说明
%d对应整型，%f对应单精度实型，%c对应字符型，%o对应八进制无符号整型，%x对应无符号十六进制整型，%u对应无符号整型，%e对应指数型，%s对应字符串型。可在%和格式字符之间加一个数来控制数据所占的宽度和小数位数。
【考点5】scanf函数
输入项要求带取地址符&。当用键盘输入多个数据时，数据之间用分隔符。分隔符包括空格符、制表符和回车符，但不包括逗号。
【考点】6如何交换两个变量
要使用中间变量，语句为：t=x; x=y; x=t;。
第三章 选择结构
【考点1】关系运算
C语言用非0表示逻辑真，用0表示逻辑假。关系运算符有6个，分别是>，>=，<，<=，==，!=，前四种优先级高于后两种。关系表达式真时为1，假时为0。注意a>，按位与&，按位异或|，按位或^。一般情况下需要先转化进制。异或运算的规则：0异或1得到1，0异或0得到0，1异或1得到0。可记为“相同为0，不同为1”。
【考点5】putchar与getchar函数
可用于输出或输入单个字符，这两个函数是stdio.h文件中的库函数，它们是printf与scanf函数的简化。
第六章 函数
【考点1】函数的定义
函数是具有一定功能的一个程序块。函数的首部为：函数类型 函数名（类型1 形参1，类型2 形参2，……）。在函数定义中不可以再定义函数，即不能嵌套定义函数。函数类型默认为int型。
【考点2】库函数
调用C语言标准库函数时要包含include命令，include命令行以#开头，后面是””或<>括起来的后缀为”.h”的头文件。以#开头的一行称为编译预处理命令行，编译预处理不是C语言语句，不加分号，不占运行时间。
【考点3】函数的返回值
函数通过return语句返回一个值，返回的值类型与函数类型一样。return语句只执行一次，执行完或函数体结束后退出函数。
【考点4】函数的声明
函数要“先定义后调用”，或“先声明再调用后定义”。函数的声明一定要有函数名、函数返回值类型、函数参数类型，但不一定要有形参的名称。
【考点5】函数的调用
程序从上往下执行，当碰到函数名后，把值传给调用函数，当程序得到了返回值或调用函数结束，再顺序往下执行。
【考点6】函数的参数及值传递
形式参数简称形参，是定义函数时函数名后面括号中的参数。实在参数简称实参，是调用函数时函数名后面括号中的参数。实参和形参分别占据不同的存储单元。实参向形参单向传递数值。
“传值”与“传址”的区别：传数值的话，形参的变化不会改变实参的变化。传地址的话，形参的变化就有可能改变实参所对应的量。
【考点7】函数的递归调用
函数直接或间接地调用自己称为函数的递归调用。递归调用必须有一个明确的结束递归的条件。在做递归题时可把递归的步骤一步步写下来，不要弄颠倒了。
【考点8】要求掌握的库函数
sqrt()算术平方根函数，fabs()绝对值函数，pow()幂函数，sin()正弦函数
第七章 指针
【考点1】指针变量
【考点2】指针变量的定义指针变量是用来存储地址的，而一般变量是存储数值的。指针变量可指向任意一种数据类型，但不管它指向的数据占用多少字节，一个指针变量占用四个字节。
格式为：类型名 *指针变量名。二维指针int **p;可以理解为基类型为(int *)类型。
【考点3】指针变量的初始化
指针变量在使用前必须要初始化，把一个具体的地址赋给它，否则引用时会有副作用，如果不指向任何数据就赋“空值”NULL。
【考点4】指针变量的引用
&是取地址符，*是间接访问运算符，它们是互逆的两个运算符。在指针变量名前加间接访问运算符就等价它所指向的量。
【考点5】指针的运算
*p++和(*p)++之间的差别：*p++是地址变化，(*p)++是指针变量所指的数据变化。一个指针变量加一个整数不是简单的数学相加，而是连续移动若干地址。当两个指针指向同一数组时，它们可以比较大小进行减法运算。
第八章 数组
【考点1】数组的定义
数组是一组具有相同类型的数据的集合，这些数据称为数组元素。格式为：类型名 数组名[常量表达式]。数组的所占字节数为元素个数与基类型所占字节数的乘积。
【考点2】数组的初始化
第一维长度可以不写，其它维必须写。int a[]={1,2};合法，int a[][3]={2,3,4};合法，int a[2][]={2,3,4};非法。数组初始化元素值默认为0，没有初始化元素值为随机。如在int a[5]={0,1,2};中，元素a[4]值为0；而在int a[5];中，元素a[4]值为一个不确定的随机数。
【考点3】元素的引用
数组元素的下标从0开始，到数组长度减1结束。所以int a[5];中数组最后一个元素是a[4]。要把数组元素看作一个整体，可以把a[4]当作一个整型变量。
【考点4】二维数组
数组a[2][3]={1,2,3,4,5,6};中含6个元素，有2行3列。第一行为a[0]行，第2行为a[1]行，a[0]、a[1]叫行首地址，是地址常量。*(a[0]+1)是第一行第一个元素往后跳一列，即元素a[0][1]值为2，*(a[0]+3)是第一行第一个元素往后跳三个，即元素a[1][0]值为4。
【考点5】行指针
是一个指针变量，占四个字节，行指针指向一行连续数据，形式为：int (*p)[2];，p只能存放含有两个整型元素的一维数组的首地址。注意(*p)两边的小括号不能省略，否则就成了指针数组，是若干指针元素的集合。
【考点6】数组名
数组名是数组的首地址。数组名不能单独引用，不能通过一个数组名代表全部元素。数组名是地址常量，不能对数组名赋值，所以a++是错误的。但数组名可以作为地址与一个整数相加得到一个新地址。
【考点7】元素形式的转换
助记：“脱衣服法则”a[2]变成*(a+2)，a[2][3]变成*(a+2)[3]再可变成*(*(a+2)+3)。
第九章 字符串
【考点1】字符串常量及表示
字符串常量是由双引号括起来的一串字符，如”ABC”。在存储字符串时，系统会自动在其尾部加上一个空值’\0’，空值也要占用一个字节，也就是字符串”ABC”需要占四个字节。
【考点2】字符数组
C语言没有字符串变量，只能采用字符数组来存储字符串。数组的大小应该比它将要实际存放的最长字符串多一个元素，从而存放’\0’。
【考点3】字符串赋值
可以用下面的形式进行赋值：char str[]=”Hello!”;或char *p;p=”Hello!”;，但不能用下面的形式：char str[10];str=”Hello”;因为str是一个地址常量，不能进行赋值操作。
【考点4】字符串的输入与输出
可以用scanf和printf函数，如scanf(”%s”,str);，也可用专门处理字符串的两个函数gets和puts函数，还可以对字符数组逐个元素进行赋值，但一定要在最后赋一个’\0’。使用gets函数可以接收空格，使用puts函数在最后输出一个换行。
【考点5】字符串函数
要掌握的四个字符串函数：字符串拷贝函数strcpy（），求字符串长度函数strlen（），字符串链接函数strcat（），字符串比较函数strcmp（）。使用这些函数需在预处理部分包含头文件”string.h”。
字符串长度要小于字符数组的长度，例：char str[10]=”Hello”;sizeof(str)的值为10（数组长度），strlen(str)的值为5（字符串长度）。这些函数是考试常用到的函数，大家一定要熟练应用这几个函数。
第十章 结构体与共用体
【考点1】结构体类型的说明
结构体是若干个类型数据的集合，结构体类型说明格式如下：struct 类型名 {类型1 成员名1;类型2 成员名2;……};，以上整个部分是一个数据类型，与整型的int是同样地位。可用typedef把结构体类型替换成一个只有几个字母的简短标识符。
【考点2】结构体变量的定义
结构体变量是用说明的结构体类型所定义的一个变量，与结构体类型不是一回事。一个结构体变量所占字节数为其所有成员所占字节数之和。如struct stu{char name[10];int age;} a,b;则表明定义了两个结构体变量a,b,每个变量占4个字节。a,b与int i,j;中的变量i,j是同样地位。
【考点3】结构体成员的引用
引用成员可用以下3种方式：（1结构体变量名.成员名；（2）指针变量名->成员名：（3）（*指针变量名）.成员名。点（.）称为成员运算符，箭头（->）称为结构指向运）
【考点4】链表
链表是由一个个结点构成的，一个结点就是一个结构体变量。每个结点可以分为数据域与指针域两个部分，数据域用来存放要存储的数据，指针域用来指向下一个结点。链表是考试中的难点，在C语言和公共基础部分都会考到，要领悟掌握。
【考点5】共用体
共用体的使用格式与结构体相似，共用体定义的关键字为union，共用体所占字节数是所有成员中字节数最大的那个。
第十一章 文件
【考点1】文件类型指针
文件指针是一个指向结构体类型的指针，定义格式为：FILE *指针变量名。在使用文件时，都需要先定义文件指针。
【考点2】文本文件与二进制文件
文本形式存放的是字符的ASCII码，二进制形式存放的是数据的二进制。例如“100”如果是文本形式就是存储’1’、 ’0’、 ’0’三个字符的ASCII码（00110001 00110000 00110000），如果是二进制形式就把100转化成二进制（01100100）。
【考点3】打开文件
文件的打开形式如下：FILE *fp; fp=fopen(“c:\\lab.c”,”rb”);。fopen函数的前面一部分为文件名，后面一部分为文件的使用方式。打开方式详见教材第127页，其中r代表读，w代表写，a代表添加，b代表二进制位的。
【考点4】文件函数
l 判断文件结束feof函数，调用形式为：feof(FILE *fp); //文件指针，如果文件结束，则函数返回1，否则返回0
l fseek用来设置文件的位置，接着的读或写操作将从此位置开始。函数的调用形式如下：
fseek（文件指针，位移量，移动起始点）；
eg。FILE*fp=fopen(“C:\\xiaoyu.c”,”rb”);
fseek(fp,12,SEEK_SET); //表示将文件fp的位置移动到文件起始位置后面的第12个字节的位置上
或者 fseek(fp,12,0);
fseek(fp,-12,SEEK_END; //表示将文件fp的位置移动到文件末尾位置前面的第12个字节的位置上
或者 fseek(fp,12,2);
如果是
fseek(fp,12,SEEK_CUR); //表示将文件fp的位置从当前位置移动后面的第12个字节的位置上
或者 fseek(fp,12,1);
l ftell用来获得文件当前的位置，函数给出当前位置相对于文件开头的字节数。函数调用形式如下：
ftell(FILE *fp) //给出当前闻之相对于开头的字节数 ，出错时，返回-1L
l 文件位置移到开头rewind函数功能等价于 fseek(fp,0,SEEK_SET)
l 文件字符输入输出ch=fgetc(FILE *fp)函数用于从fp指定的文件中读入一个字符并把它作为函数值返回
l fputc(char ch,FILE *fp),将字符ch写到文件指针fp所指的文件中去，输出成功，则返回输出的字符，失败，则返回一个EOF值
l 文件输入输出fscanf函数和fprintf函数，一般形式fscanf(文件指针，格式控制字符串，输入项表或输入项表)
l 文件字符串输入输出fgets函数（fgets(str,n,fp),功能是从fp所指文件中读入n-1个字符放入str为起始地址的空间内）和fputs函数( fputs(str,fp) )
l 读写二进制文件fread函数和fwrite函数。
以上函数要求知道格式会用，清楚是用于二进制文件还是文本文件，要把教材文件这章仔细复习下，不要在考试的时候把这些文件函数搞混了。
典型例题：
给定程序中,函数fun的功能是将形参给定的字符串、整数、浮点数写到文本 文件中，再用字符方式从此文本文件中逐个读入并显示在终端屏幕上。 请在程序的下划线处填入正确的内容并把下划线删除, 使程序得出正确的结果。
注意：源程序存放在考生文件夹下的BLANK1.C中。
不得增行或删行，也不得更改程序的结构！
给定源程序：
#include
void fun(char *s, int a, double f)
{
__1__ fp;
char ch;
fp = fopen("file1.txt", "w");
fprintf(fp, "%s %d %f\n", s, a, f);
fclose(fp);
fp = fopen("file1.txt", "r");
printf("\nThe result :\n\n");
ch = fgetc(fp);
while (!feof(__2__)) {
putchar(__3__); ch = fgetc(fp); }
putchar(\n);
fclose(fp);
}
main()
{ char a[10]="Hello!"; int b=12345;
double c= 98.76;
fun(a,b,c);
}
第十二章 深入讨论
【考点1】编译预处理
凡以#开头的这一行，都是编译预处理命令行，编译预处理不加分号，不占运行时间。宏替换仅是简单的文本替换，如#define f(x) (x)*(x)和#define f(x) x*x替换f(2+2)时就有区别，前者展开为(2+2)*(2+2)，后者为2+2*2+2。
如果源文件f2.c中有#include”f1.c”可以理解为把源文件f1.c原样包含到f2.c中，使f1.c和f2.c融合到一起成为一个C程序编译。所以一个C程序必有主函数，但一个C源文件未必有主函数。
【考点2】标识符作用域
局部变量是在函数内或复合语句内定义的变量，作用域为定义它的函数内。局部变量有三种类型：自动auto，寄存器register和静态static。
自动变量随着函数的使用与否创建消失；寄存器变量分配在cpu中，没有内存地址；静态变量占用固定存储单元，在程序执行过程不释放，直到程序运行结束。
全局变量是在函数外定义的变量，作用域从定义它的位置到整个源文件结束为止，生存期为整个程序运行期间。全局变量都是静态变量。
eg
.#include
int fun()
{
static int x = 1;
x*=2;
return x;
}
main()
{
int i,s=1;
for(i=1;i<=3;i++)
s*=fun();//i=1 S=2 i=2 S=8
printf(“%d\n”,s);
} 64
【考点3】动态存储分配
malloc(size)用来创建连续size个字节存储区，返回值类型为void *型。malloc函数常用于动态创建链表结点，如int *p; p=(int *)malloc(sizeof(int));。
calloc（n,size）创建n个同一类型的存储空间，可以理解为n个malloc。
free(p)释放动态分配的存储单元。
/.
第二部分 公共基础知识资料
第一章 数据结构与算法
【考点1】算法的基本概念
算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法。
算法的基本特征：
确定性，算法中每一步骤都必须有明确定义，不允许有多义性；
有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；
可行性，算法原则上能够精确地执行；
拥有足够的情报。
算法的组成要素：一个算法由数据对象的运算和操作以及其控制结构这两部分组成。
算法的基本运算和操作：算术运算，逻辑运算，关系运算，数据传输。
算法的基本控制结构：顺序，选择，循环。
算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术。
【考点2】算法的复杂度
算法效率的度量——算法的复杂度：时间复杂度和空间复杂度。
算法时间复杂度：指执行算法所需要的计算工作量。通常，一个算法所用的时间包括编译时间和运行时间。
算法空间复杂度：指执行这个算法所需要的内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。
空间复杂度和时间复杂度并不相关。
【考点3】数据结构的基本概念
数据：数据是客观事物的符号表示，是能输入到计算机中并被计算程序识别和处理的符号的总称，如文档，声音，视频等。
数据元素：数据元素是数据的基本单位。
数据对象：数据对象是性质相同的数据元素的集合。
数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。
【考点4】逻辑结构和存储结构
数据结构可分为数据的逻辑结构和存储结构。
数据的逻辑结构是对数据元素之间的逻辑关系的描述，与数据的存储无关，是面向问题的，是独立于计算机的。它包括数据对象和数据对象之间的关系。
数据的存储结构也称为数据的物理结构，是数据在计算机中的存放的方式，是面向计算机的，它包括数据元素的存储方式和关系的存储方式。
数据结构和逻辑结构的关系：一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对应。
常见的存储结构有：顺序，链接，索引等。采用不同的存储结构其数据处理的效率是不同的。
【考点5】线性结构和非线性结构
线性结构的条件（一个非空数据结构)：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
栈、队列、双向链表是线性结构，树、二叉树为非线性结构。
【考点6】线性表及其顺序存储结构
线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录；由多个记录构成的线性表称为文件。
非空线性表的结构特征：
（1）有且只有一个根结点a1，它无前件；
（2）有且只有一个终端结点an，它无后件；
（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
结点个数n称为线性表的长度，当n=0时，称为空表。
线性表的顺序存储结构具有以下两个基本特点：
（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
元素ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)*k，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。
顺序表的运算：查找、插入、删除。
【考点7】线性链表
线性链表是线性表的链式存储结构，数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：(1) 用于存储数据元素值，称为数据域；(2) 用于存放指针，称为指针域，用于指向前一个或后一个结点。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。
线性单链表中，HEAD称为头指针，HEAD=NULL（或0）称为空表。
图1 单链表的结构
单链表的结构（图1）
……
数据域 指针域
数据域 指针域
数据域 指针域
……
双向链表有两个指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。
L D R
……
图2 双链表的结构
L
展开阅读全文
相关搜索