还剩25页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
注意公共基础的重点在后面(从12页开始)前面是C语言的复习要点,大家也可以参考一下公共基础的内容可以打印出来反复看几遍,考试就没问题了C语言最重要的知识点复习资料笔试注意事项
1、笔试满分100分,共两大题,选择70分40小题,填空30分15小题C语言占70分,公共基础占30分选择题的前10题和填空题的前5题考公共基础知识,其他考知识C语言笔试时间为2010年3月27日上午9:00-10:
302、选择用铅笔涂答题卡,填空用黑色签字笔在答题上写
3、考前准备好身份证、准考证、2B铅笔、橡皮、黑色签字笔、手表等第一章C语言基本知识【考点1】C程序C语言程序结构有三种:顺序结构循环结构三个循环结构选择结构if和switch【考点2】main函数每个C语言程序中main函数是有且只有一个读程序都要从main入口然后从最上面顺序往下读碰到循环做循环碰到选择做选择【考点3】存储形式计算机的数据在电脑中是以二进制的形式保存最低的存储单元是bit(位),位是由为0或者1构成byte是指字节一个字节=八个位数据存放的位置就是它的地址【考点4】注释是对程序的说明,可出现在程序中任意合适的地方,注释从“/*”开始到最近一个“*/”结束,其间任何内容都不会被计算机执行,注释不可以嵌套【考点5】书写格式每条语句的后面必须有一个分号,分号是语句的一部分一行内可写多条语句,一个语句可写在多行上【考点6】标识符合法的用户标识符考查合法的要求是由字母,数字,下划线组成有其它元素就错了并且第一个必须为字母或则是下划线第一个为数字就错了C语言标识符分如下3类
(1)关键字它们在程序中有固定的含义,不能另作他用如int、for、switch等
(2)预定义标识符预先定义并具有特定含义的标识符如define、include等
(3)用户标识符用户根据需要定义的标识符,符合命名规则且不与关键字相同关键字不可以作为用户标识符号maindefinescanfprintf都不是关键字迷惑你的地方If是可以做为用户标识符因为If中的第一个字母大写了,所以不是关键字【考点7】实型数据实型数据的合法形式小数形式和指数形式掌握判定指数形式合法性
2.333e-1就是合法的,且数据是
2.333×10-1考试口诀e前e后必有数,e后必为整数【考点8】字符字符数据的合法形式:1是字符占一个字节,1是字符串占两个字节含有一个结束符号0的ASCII数值表示为48,a的ASCII数值是97,A的ASCII数值是65字符型和整数是近亲chara=65;printf“%c”a;得到的输出结果aprintf“%d”a;得到的输出结果65一般考试表示单个字符错误的形式651字符是可以进行算术运算的,记住0-0=48大写字母和小写字母转换的方法A+32=a相互之间一般是相差32【考点9】整型数据整型一般是两个字节字符型是一个字节,双精度一般是4个字节考试时候一般会说,在16位编译系统,或者是32位系统碰到这种情况,不要去管,一样做题掌握整型一般是两个字节字符型是一个字节,双精度一般是4个字节就可以了【考点10】转义字符转义字符的考查在程序中inta=0x6d,是把一个十六进制的数给变量a注意这里的0x必须存在在程序中inta=06d是一个八进制的形式在转义字符中,’\x6d’才是合法的,0不能写,并且x是小写‘\141’是合法的,0是不能写的‘\108’是非法的,因为不可以出现8【考点11】算术运算算术运算符一共有+、—、*、/、%这五个%符号两边要求是整数不是整数就错了三种取整丢小数的情况不是四舍五入是舍掉小数部分1、inta=
1.6;2、inta;3、1/2;3/2;【考点12】强制类型转换将一个运算对象转换成指定类型,格式为(类型名)表达式一定是(int)a不是int(a),注意类型上一定有括号的注意(int)(a+b)和(int)a+b的区别前是把a+b转型,后是把a转型再加b【考点13】赋值是表达式就一定有数值赋值表达式表达式数值是最左边的数值,a=b=5;该表达式为5,常量不可以赋值复合赋值运算符注意a*=m+2是a=a*m+2自加、自减表达式假设a=5,++a(表达式的值为6),a++(表达式的值为5);j=a++;等价于j=a;a=a+1;而j=++a;等价于a=a+1;j=a;考试口诀++在前先加后用,++在后先用后加【考点14】逗号运算逗号表达式优先级别最低;表达式的数值逗号最右边的那个表达式的数值(2,3,4)的表达式的数值就是4【考点15】数制转换一定要记住二进制如何转换成十进制八进制是没有8的,逢8进1,018的数值是非法的【考点16】位运算会有一到二题考试题目C语言提供6种位运算符按位求反~,按位左移,按位右移,按位与,按位异或|,按位或^总的处理方法几乎所有的位运算的题目都要按这个流程来处理(先把十进制变成二进制再变成十进制)异或运算的规则0异或1得到1,0异或0得到0,1异或1得到0可记为“相同为0,不同为1”见教材31页例1在没有舍去数据的时候,左移一位表示乘以2;右移一位表示除以2第二章数据的输入输出(顺序结构)【考点1】printf函数格式为printf输出控制,输出列表输出控制是用一对双引号括起来的,包含格式说明和原样信息输出列表包含若干输出项%d对应整型,%f对应单精度实型,%c对应字符型,%o对应八进制无符号整型,%x对应无符号十六进制整型,%u对应无符号整型,%e对应指数型,%s对应字符串型可在%和格式字符之间加一个数来控制数据所占的宽度和小数位数【考点2】scanf函数格式为scanf输入控制,输入列表注意该函数的第二个部分是a这样的地址,不是a;scanf“%d%d%*d%d”abc;跳过输入的第三个数据【考点3】putchar与getchar函数可用于输出或输入单个字符,这两个函数是stdio.h文件中的库函数,它们是printf与scanf函数的简化chara=getchar是没有参数的,从键盘得到你输入的一个字符给变量aputchar‘y’把字符y输出到屏幕中【考点4】如何交换两个变量如何实现两个变量x,y中数值的互换(要求背下来)不可以把x=yy=x;要用中间变量t=x;x=y;y=t【考点5】实现保留三位小数如何实现保留三位小数,第四位四舍五入的程序,(要求背下来)floatx=
12.34567;floaty=intx*1000+
0.5/
1000.0;这个有推广的意义,注意x=(int)x这样是把小数部分去掉第三章选择结构特别要注意c语言中是用非0表示逻辑真的,用0表示逻辑假的【考点1】关系运算关系运算符有6个,分别是,=,,=,==,!=,前四种优先级高于后两种关系表达式关系表达式真时为1,假时为0当关系的表达是为真的时候得到1如98这个是真的,所以表达式的数值就是1【考点2】逻辑运算只能为1(表示为真),或0(表示假)a共有三种逻辑运算符号逻辑非(!),辑与(),逻辑或(||)b!||优先的级别c注意短路现象考试比较喜欢考到例a++||b++,如果表达式a++的值非零,则表达式b++不再执行d要表示x是比0大,比10小的方法0x10是不可以的(一定记住)是先计算0x得到的结果为1或则0;再用0,或1与10比较得到的总是真(为1)所以一定要用0xx10表示比0大比10小【考点3】if语句可以单独出现,也可以与else匹配出现if语句可以嵌套,这时else总是与离它最近的且没有与else匹配的if匹配注意if语句的子句是紧接if或else的一句,如有多句需要用{}括起来【考点4】条件运算是唯一的三目运算符,格式表达式1?表达式2表达式3表达式1值为非0时,整个表达式值为表达式2的值,表达式1值为0时,整个表达式值为表达式3的值考试口诀真前假后【考点5】switch语句a一定要注意有break和没有break的差别,书上(53,54页)的两个例子,没有break时候,只要有一个case匹配了,剩下的都要执行,有break则是直接跳出了switch语句bswitch只可以和break一起用,不可以和continue一起用cswitchxx是整型常量,字符型常量,枚举型数据{case1:….不可以是变量case2:….}switch后小括号里面的表达式不能为实型,case后表达式不能有变量口诀switch表不为实,case表不为变第四章循环结构【考点1】三种循环结构while;do-while;for()三种三种结构的格式及执行顺序详见教材第
58、
62、64页b)for循环当中必须是两个分号,千万不要忘记c)写程序的时候一定要注意,循环一定要有结束的条件,否则成了死循环ddo-while循环的最后一个while;的分号一定不能够丢(当心上机改错),do-while循环是至少执行一次循环【考点2】break与continuebreak和continue的差别记忆方法break是打破的意思,(破了整个循环)所以看见break就退出这一层循环continue是继续的意思,是要结束本次循环,就是循环体内剩下的语句不再执行,跳到循环开始,然后判断循环条件,进行新一轮的循环【考点3】循环的嵌套就是有循环里面还有循环,这种比较复杂,要一层一层一步一步耐心的计算,一般只考查两层嵌套,循环嵌套通常是处理二维数组循环结构是重点,笔试所占分值一般在13分左右,在上机考试中也是必考点,应用性很强要求学员重点理解并多加练习,领会掌握第五章函数【考点1】函数的定义函数是具有一定功能的一个程序块;是C语言的基本组成单位函数的首部为函数类型函数名(类型1形参1,类型2形参2,……)在函数定义中不可以再定义函数,即不能嵌套定义函数函数类型默认为int型【考点2】库函数调用C语言标准库函数时要包含include命令,include命令行以#开头,后面是“”或括起来的后缀为”.h”的头文件以#开头的一行称为编译预处理命令行,编译预处理不是C语言语句,不加分号,不占运行时间【考点3】函数的返回值函数通过return语句返回一个值,返回的值类型与函数类型一样return语句只执行一次,执行完或函数体结束后退出函数【考点4】函数的声明函数要“先定义后调用”,或“先声明再调用后定义”函数的声明一定要有函数名、函数返回值类型、函数参数类型,但不一定要有形参的名称【考点5】函数的调用程序从上往下执行,当碰到函数名后,把值传给调用函数,当程序得到了返回值或调用函数结束,再顺序往下执行【考点6】函数的参数及值传递形式参数简称形参,是定义函数时函数名后面括号中的参数实在参数简称实参,是调用函数时函数名后面括号中的参数实参和形参分别占据不同的存储单元实参向形参单向传递数值“传值”与“传址”的区别传数值的话,形参的变化不会改变实参的变化传地址的话,形参的变化就有可能改变实参所对应的量(考试的重点)函数的参数,返回数值(示意图)【考点7】函数的递归调用函数直接或间接地调用自己称为函数的递归调用递归调用必须有一个明确的结束递归的条件在做递归题时可把递归的步骤一步步写下来,不要弄颠倒了【考点8】要求掌握的库函数sqrt算术平方根函数,fabs绝对值函数,sin正弦函数,sin
3.14159/180*30;,pow幂函数,23是由pow2,3表示的第六章指针【考点1】指针变量指针变量是用来存储地址的,而一般变量是存储数值的指针变量可指向任意一种数据类型,但不管它指向的数据占用多少字节,一个指针变量占用四个字节【考点2】指针变量的定义格式为类型名*指针变量名二维指针int**p;可以理解为基类型为int*类型【考点3】指针变量的初始化指针变量在使用前必须要初始化,把一个具体的地址赋给它,否则引用时会有副作用,如果不指向任何数据就赋“空值”NULL指针变量两种初始化方法一inta=2,*p=a;定义的同时初始化方法二inta=2,*p;定义之后初始化p=a;【考点4】指针变量的引用是取地址符,*是间接访问运算符,它们是互逆的两个运算符在指针变量名前加间接访问运算符就等价它所指向的量【考点5】指针的运算int*p中*p和p的差别*p可以当做变量来用;*的作用是取后面地址p里面的数值p是当作地址来使用*p++和(*p)++的之间的差别改错题目中很重要*p++是地址会变化(*p)++是数值会要变化三名主义(考试的重点)数组名表示第一个元素的地址数组名不可以自加,他是地址常量名(考了很多次)函数名表示该函数的入口地址字符串常量名表示第一个字符的地址考试重要的话语指针变量是存放地址的并且指向哪个就等价哪个,所有出现*p的地方都可以用它等价的代替指向的变量例如inta=2,*p=a;*p=*p+2;由于*p指向变量a所以指向哪个就等价哪个,这里*p等价于a,可以相当于是a=a+2第七章数组【考点1】数组的定义数组是一组具有相同类型的数据的集合,这些数据称为数组元素格式为类型名数组名[常量表达式]数组的所占字节数为元素个数与基类型所占字节数的乘积【考点2】数组的初始化第一维长度可以不写,其它维必须写inta[]={12};合法,inta[]
[3]={234};合法,inta
[2][]={234};非法数组初始化元素值默认为0,没有初始化元素值为随机如在inta
[5]={012};中,元素a
[4]值为0;而在inta
[5];中,元素a
[4]值为一个不确定的随机数【考点3】元素的引用数组元素的下标从0开始,到数组长度减1结束所以inta
[5];中数组最后一个元素是a
[4]要把数组元素看作一个整体,可以把a
[4]当作一个整型变量【考点4】二维数组数组a
[2]
[3]={123456};中含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这个思想很重要!二维数组做题目的技巧如果有a
[3]
[3]={123456789}这样的题目步骤一把他们写成第一列第二列第三列a
[0]123-第一行a
[1]456—第二行a
[2]789-第三行步骤二这样作题目间很简单*a
[0]+1我们就知道是第一行的第一个元素往后面跳一列,那么这里就是a
[0]
[1]元素,所以是1*a
[1]+2我们就知道是第二行的第一个元素往后面跳二列那么这里就是a
[1]
[2]元素,所以是6一定记住只要是二维数组的题目,一定是写成如上的格式,再去做题目,这样会比较简单两种重要的数组长度chara[]={‘a’’b’’c’};数组长度为3,字符串长度不定sizeofa为3chara
[5]={‘a’’b’’c’}数组长度为5,字符串长度3sizeofa为5第八章字符串【考点1】字符串常量及表示字符串常量是由双引号括起来的一串字符,如”ABC”在存储字符串时,系统会自动在其尾部加上一个空值’\0’,空值也要占用一个字节,也就是字符串”ABC”需要占四个字节【考点2】字符数组C语言没有字符串变量,只能采用字符数组来存储字符串数组的大小应该比它将要实际存放的最长字符串多一个元素,从而存放’\0’【考点3】字符串赋值字符串赋值的两种形式charstr[]=“Hello!”;或char*p;p=“Hello!”;,但不能用下面的形式charstr
[10];str=”Hello”;因为str是一个地址常量,不能进行赋值操作【考点4】字符串的输入与输出可以用scanf和printf函数,如scanf”%s”str;,也可用专门处理字符串的两个函数gets和puts函数,还可以对字符数组逐个元素进行赋值,但一定要在最后赋一个’\0’使用gets函数可以接收空格,使用puts函数在最后输出一个换行scanf和gets的数据如果输入的是goodgoodstudy!那么scanf“%s”a;只会接收good.考点不可以接收空格getsa;会接收goodgoodstudy!考点可以接收空格【考点5】字符串函数要掌握的四个字符串函数字符串拷贝函数strcpy(),求字符串长度函数strlen(),字符串链接函数strcat(),字符串比较函数strcmp()使用这些函数需在预处理部分包含头文件”string.h”字符串长度要小于字符数组的长度,例charstr
[10]=”Hello”;sizeofstr的值为10(数组长度),strlenstr的值为5(字符串长度)这些函数是考试常用到的函数,大家一定要熟练应用这几个函数第九章文件【考点1】文件类型指针文件指针是一个指向结构体类型的指针,定义格式为FILE*指针变量名在使用文件时,都需要先定义文件指针【考点2】文本文件与二进制文件文本形式存放的是字符的ASCII码,二进制形式存放的是数据的二进制例如“100”如果是文本形式就是存储’1’、’0’、’0’三个字符的ASCII码
(001100010011000000110000),如果是二进制形式就把100转化成二进制
(01100100)【考点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函数,读写二进制文件fread函数和fwrite函数以上函数要求知道格式会用,清楚是用于二进制文件还是文本文件上课时候讲的文件这一章的题目要做一遍,一定要做,基本上考试的都会在练习当中第十章对C语言的深入探讨【考点1】编译预处理凡以#开头的这一行,都是编译预处理命令行,编译预处理不加分号,不占运行时间宏替换仅是简单的文本替换,如#definefxx*x和#definefxx*x替换f2+2时就有区别,前者展开为2+2*2+2,后者为2+2*2+2如果源文件f
2.c中有#include”f
1.c”可以理解为把源文件f
1.c原样包含到f
2.c中,使f
1.c和f
2.c融合到一起成为一个C程序编译所以一个C程序必有主函数,但一个C源文件未必有主函数【考点2】标识符作用域局部变量是在函数内或复合语句内定义的变量,作用域为定义它的函数内局部变量有三种类型自动auto,寄存器register和静态static自动变量随着函数的使用与否创建消失;寄存器变量分配在cpu中,没有内存地址;静态变量占用固定存储单元,在程序执行过程不释放,直到程序运行结束全局变量是在函数外定义的变量,作用域从定义它的位置到整个源文件结束为止,生存期为整个程序运行期间全局变量都是静态变量【考点3】动态存储分配mallocsize用来创建size个字节的连续存储空间,返回值类型为void*型malloc函数常用于动态创建链表结点,如int*p;p=int*mallocsizeofint;calloc(nsize)创建n个同一类型的连续存储空间,可以理解为n个mallocint*p;p=int*calloc10,sizeofint;p指向首地址freep释放动态分配的存储单元【考点4】main函数的参数还有main(intargc,char**argv){}这种含有参数的题目,是很呆板的题目第一个参数是表示输入的字符串的数目,第二个参数是指向存放的字符串【考点5】函数指针函数指针的用法(*f)()记住一个例子intaddintxinty{....}main{int(*f)();f=add;}赋值之后合法的调用形式为1、add2,3;2、f2,3;3、(*f)(2,3)第十一章结构体和共用体【考点1】结构体类型的说明结构体是若干个类型数据的集合,结构体类型说明格式struct类型名{类型1成员名1;类型2成员名2;……};,以上整个部分是一个数据类型,与整型的int是同样地位可用typedef把结构体类型替换成一个只有几个字母的简短标识符【考点2】结构体变量的定义结构体变量是用说明的结构体类型所定义的一个变量,与结构体类型不是一回事一个结构体变量所占字节数为其所有成员所占字节数之和如structstu{charname
[10];intage;}ab;则表明定义了两个结构体变量ab每个变量占14个字节ab与intij;中的变量ij是同样地位typedef考的很多(教材150页例6)【考点3】结构体成员的引用引用成员可用以下3种方式
(1)结构体变量名.成员名;
(2)指针变量名-成员名
(3)(*指针变量名).成员名点(.)称为成员运算符,箭头(-)称为结构指向运算符【考点5】共用体共用体的使用格式与结构体相似,共用体定义的关键字为union,共用体所占字节数是所有成员中字节数最大的那个unionTT{inta;charch
[2];}t1;main{t
1.a=0x1234;printf%x\nt
1.ch
[0];printf%x\nt
1.ch
[1];}考点一sizeofstructTT=2;考点二TTt1;t
1.a=0x1234;那么ch
[0]=0x34;ch
[1]=0x127)结构体和共用体以及链表要掌握最简单的typedef考的很多,而且一定要知道如何引用结构体中的各个变量,链表中如何填加和删除节点,以及何如构成一个简单的链表,一定记住链表中的节点是有两个域,一个放数值,一个放指针【考点4】链表链表是由一个个结点构成的,一个结点就是一个结构体变量每个结点可以分为数据域与指针域两个部分,数据域用来存放要存储的数据,指针域用来指向下一个结点链表是考试中的难点,在C语言和公共基础部分都会考到,要掌握,链表中如何增加和删除节点(每年都考),以及何如构成一个简单的链表,一定记住链表中的节点是有两个域,一个放数值,一个放指针(教材162页例2一定要看懂)
二、公共基础第一章数据结构与算法知识点所占分值考核几率算法2~4分50%数据结构的基本概念2~4分50%线性表及其顺序存储结构1~2分50%线性链表1~2分20%栈及其基本运算2~4分100%队列及其基本运算树与二叉树2~6100%查找于排序技术2~480%第二章程序设计基础知识点所占分值考核几率程序设计方法与风格0~2分40%结构化程序设计0~2分20%面向对象程序设计0~2分70%第三章软件工程基础知识点所占分值考核几率软件工程基本概念2~480%软件分析及其方法0~240%软件设计及其方法2~460%软件测试2~480%程序的调试0~280%第三章软件工程基础知识点所占分值考核几率数据库系统的基本概念2~4100%数据模型2~690%关系代数0~250%数据库库设计与管理2~440%第一章数据结构与算法【考点1】算法的基本概念算法是指一组有穷的指令集,是解题方案的准确而完整的描述算法不等于程序,也不等于计算方法算法的基本特征确定性,算法中每一步骤都必须有明确定义,不允许有多义性;有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止;可行性,算法原则上能够精确地执行;拥有足够的情报算法的组成要素一个算法由数据对象的运算和操作以及其控制结构这两部分组成算法的基本运算和操作算术运算,逻辑运算,关系运算,数据传输算法的基本控制结构顺序,选择,循环算法基本设计方法列举法、归纳法、递推、递归、减半递推技术【考点2】算法的复杂度算法效率的度量——算法的复杂度时间复杂度和空间复杂度算法时间复杂度指执行算法所需要的计算工作量通常,一个算法所用的时间包括编译时间和运行时间算法空间复杂度指执行这个算法所需要的内存空间包括算法程序所占的空间,输入的初始数据所占的空间,算法执行过程中所需的额外空间空间复杂度和时间复杂度并不相关【考点3】数据结构的基本概念数据数据是客观事物的符号表示,是能输入到计算机中并被计算程序识别和处理的符号的总称,如文档,声音,视频等数据元素数据元素是数据的基本单位数据对象数据对象是性质相同的数据元素的集合数据结构是指由某一数据对象中所有数据成员之间的关系组成的集合【考点4】逻辑结构和存储结构数据结构可分为数据的逻辑结构和存储结构数据的逻辑结构是对数据元素之间的逻辑关系的描述,与数据的存储无关,是面向问题的,是独立于计算机的它包括数据对象和数据对象之间的关系数据的存储结构也称为数据的物理结构,是数据在计算机中的存放的方式,是面向计算机的,它包括数据元素的存储方式和关系的存储方式数据结构和逻辑结构的关系一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对应常见的存储结构有顺序,链接,索引等采用不同的存储结构其数据处理的效率是不同的【考点5】线性结构和非线性结构线性结构的条件(一个非空数据结构
(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件非线性结构不满足线性结构条件的数据结构栈、队列、双向链表是线性结构,树、二叉树为非线性结构【考点6】线性表及其顺序存储结构线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的在复杂线性表中,由若干项数据元素组成的数据元素称为记录;由多个记录构成的线性表称为文件非空线性表的结构特征
(1)有且只有一个根结点a1,它无前件;
(2)有且只有一个终端结点an,它无后件;
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件结点个数n称为线性表的长度,当n=0时,称为空表线性表的顺序存储结构具有以下两个基本特点
(1)线性表中所有元素所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的元素ai的存储地址为ADRai=ADRa1+i-1*k,ADRa1为第一个元素的地址,k代表每个元素占的字节数顺序表的运算查找、插入、删除【考点7】线性链表线性链表是线性表的链式存储结构,数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点结点由两部分组成1用于存储数据元素值,称为数据域;2用于存放指针,称为指针域,用于指向前一个或后一个结点在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的链式存储方式既可用于表示线性结构,也可用于表示非线性结构线性单链表中,HEAD称为头指针,HEAD=NULL(或0)称为空表双向链表有两个指针左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点循环链表循环链表与单链表的不同的是它的最后一个结点的指针域存放的事指向第一个结点的指针而单链表存放的是空指针线性链表的基本运算查找、插入、删除【考点8】栈
1、栈的基本概念栈是一种特殊的线性表,只允许在表的一端进行插入和删除的线性表;插入,删除的一端为栈顶,另一端为栈底;当表中没有元素时为空栈栈是一种后进先出(或先进后出LastInFirstOut)的线性表栈具有记忆功能栈的实例火车调度,子弹夹
2、栈的存储结构顺序存储结构用一组地址连续的存储单元即一维数组来存储;链式存储用线性链表来存储;
3、栈的基本运算1入栈运算,在栈顶位置插入元素;2退栈运算,删除元素取出栈顶元素并赋给一个指定的变量;3读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化【考点9】队列
1.队列的基本概念队列是一种特殊的线性表,只允许在表的一端插入,在另一端删除,允许插入的一端是队尾(rear),允许删除的一端为队头(front);当表中没有元素是空队列;队列是一种先进先出的线性表FIFO
2、队列的存储结构顺序存储一维数组链式存储线性链表
3、队列的运算:1入队运算从队尾插入一个元素;2退队运算从队头删除一个元素队列的顺序存储结构一般采用循环队列的形式循环队列s=0表示队列为空;s=1且front=rear表示队满计算循环队列的元素个数“尾指针减头指针”,若为负数,再加其容量即可【考点10】树的基本概念树是一种非线性结构,是n个结点的有限集当n=0时为空树,n0时为非空树结点的度结点所拥有的子树的个数叶子结点度为0的结点分支结点除叶子结点以外的结点结点的层次根结点在第一层,同一层上左右结点的子结点在下一层树的深度所处层次最大的那个结点的层次树的度树中所有结点的度的最大值【考点11】二叉树及其基本性质
1、二叉树的概念二叉树是一种特殊的树形结构,每个结点最多只有两棵子树,且有左右之分不能互换,因此,二叉树有五种不同的形态,见教材12页
2、二叉树的性质性质1在二叉树的第k层上,最多有2k-1k≥1)个结点性质2深度为m的二叉树最多有2m-1个结点性质3在任意一棵二叉树中,度为0的结点(叶子结点)总是比度为2的结点多一个性质4具有n个结点的二叉树,其深度不小于[log2n]+1其中[log2n]表示为log2n的整数部分
3、二叉树的存储结构详见教材第13-14页【考点12】满二叉树与完全二叉树满二叉树除最后一层外,每一层上的所有结点都有两个子结点在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点完全二叉树是指这样的二叉树除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点满二叉树是完全二叉树,而完全二叉树一般不是满二叉树【考点13】完全二叉树的性质性质1具有n个结点的完全二叉树的深度为[log2n]+1性质2完全二叉树中度为1的结点数为0或1【考点14】二叉树的遍历前序遍历先访问根结点、然后遍历左子树,最后遍历右子树;并且,在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树前序遍历图5可得ABCDFHEG中序遍历先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树中序遍历图5可得BAFHDCGE后序遍历先遍历左子树、然后遍历右子树,最后访问根结点;并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点后序遍历图5可得BHFDGECA【考点15】顺序查找顺序查找是从表的一端开始,依次扫描表中的各个元素,并与所要查找的数进行比较在下列两种情况下也只能采用顺序查找
(1)如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找
(2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找【考点16】二分查找二分查找的条件
(1)用顺序存储结构2线性表是有序表查找的步骤详见教材第16页对于长度为n的有序线性表,在最坏情况下,二分法查找只需比较log2n次,而顺序查找需要比较n次【考点17】排序
1、交换排序
(1)冒泡排序法,在最坏的情况下,冒泡排序需要比较次数为nn-1/2
(2)快速排序法,在最坏的情况下,快速排序需要比较次数为nn-1/
22、插入类排序法
(1)简单插入排序法,最坏情况需要nn-1/2次比较;
(2)希尔排序法,最坏情况需要On
1.5次比较(大写O是算法复杂度的表示方法)
3、选择类排序法
(1)简单选择排序法,最坏情况需要nn-1/2次比较;
(2)堆排序法,最坏情况需要Onlog2n次比较相比以上几种除希尔排序法外,堆排序法的时间复杂度最小第二章程序设计基础【考点1】程序设计方法与风格形成良好的程序设计风格需注意详见教材第19页
1、源程序文档化;
2、数据说明的方法;
3、语句的结构;
4、输入和输出注释分序言性注释和功能性注释语句结构清晰第
一、效率第二【考点2】结构化程序设计方法的四条原则
1、自顶向下;
2、逐步求精;
3、模块化;
4、限制使用goto语句【考点3】结构化程序的基本结构顺序结构是最基本、最普通的结构形式,按照程序中的语句行的先后顺序逐条执行选择结构又称为分支结构,它包括简单选择和多分支选择结构循环结构根据给定的条件,判断是否要重复执行某一相同的或类似的程序段循环结构对应两类循环语句先判断后执行的循环体称为当型循环结构;先执行循环体后判断的称为直到型循环结构【考点4】面向对象的程序设计及面向对象方法的优点面向对象的程序设计以对象为核心,强调对象的抽象性,封装性,继承性和多态性面向对象方法的优点
(1)人类习惯的思维方法一致;
(2)稳定性好;
(3)可重用性好;
(4)易于开发大型软件产品;
(5)可维护性好【考点5】对象及其特点对象(object)面向对象方法中最基本的概念,可以用来表示客观世界中的任何实体,对象是实体的抽象对象的基本特点
(1)标识惟一性;
(2)分类性;
(3)多态性;
(4)封装性;
(5)模块独立性好【考点6】属性,类和实例属性即对象所包含的信息,它在设计对象时确定,一般只能通过执行对象的操作来改变类是具有相似属性与操作的一组对象类是关于对象性质的描述类是对象的抽象,对象是其对应类的一个实例【考点7】消息及其组成消息是一个实例与另一个实例之间传递的信息对象间的通信靠消息传递它请求对象执行某一处理或回答某一要求的信息,它统一了数据流和控制流消息的组成包括1接收消息的对象的名称;
(2)消息标识符,也称消息名;
(3)零个或多个参数【考点8】继承和多态继承是使用已有的类定义作为基础建立新类的定义技术,广义指能够直接获得已有的性质和特征,而不必重复定义他们继承具有传递性,一个类实际上继承了它上层的全部基类的特性继承分单继承和多重继承单继承指一个类只允许有一个父类,即类等级为树形结构;多重继承指一个类允许有多个父类多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象第三章软件工程基础【考点1】软件定义与软件特点软件指的是计算机系统中与硬件相互依存的另一部分,包括程序、数据和相关文档的完整集合名称描述程序软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列数据使程序能正常操纵信息的数据结构文档与程序的开发、维护和使用有关的图文资料软件的特点软件是一种逻辑实体,具有抽象性;软件的生产与硬件不同,它没有明显的制作过程;软件在运行、使用期间不存在磨损、老化问题;软件的开发、运行对计算机系统具有依赖性,受计算机系统的限制,这导致了软件移植的问题;软件复杂性高,成本昂贵;软件开发涉及诸多的社会因素根据应用目标的不同,软件可分应用软件、系统软件和支撑软件(或工具软件)名称描述应用软件为解决特定领域的应用而开发的软件,如办公自动化软件系统软件计算机管理自身资源,提高计算机使用效率并为计算机用户提供各种服务的软件,如操作系统支撑软件(或工具软件)支撑软件是介于两者之间,协助用户开发软件的工具性软件【考点2】软件的生命周期软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的整个过程可分为软件定义,软件开发及软件维护3个阶段软件生命周期中,能够准确确定软件系统必须做什么和必须具备哪些功能的阶段是需求分析定义阶段开发阶段维护阶段【考点3】软件危机和软件工程的概念软件危机泛指在计算机软件的开发和维护过程中遇到的一系列严重的问题,集中表现在成本,质量生产效率等几个方面所谓软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护是建立并使用完善的工程化原则,以较经济的手段获得,能在实际机器上有效运行的可靠软件的一系列方法;软件工程的主要思想强调在软件开发过程中需要应用工程化原则软件工程的核心思想是把软件当作一个工程产品来处理软件工程包括3个要素方法,工具和过程名称描述方法方法是完成软件工程项目的技术手段工具工具支持软件的开发、管理、文档生成过程过程支持软件开发的各个环节的控制、管理【考点4】软件工程过程软件工程过程是把软件转化为输出的一组彼此相关的资源活动,包含4种基本活动
(1)Pplan——软件规格说明;
(2)Ddo——软件开发;
(3)Ccheck——软件确认;
(4)Aaction——软件演进【考点5】软件开发技术和软件工程管理软件工程的理论和技术性研究的内容主要包括软件开发技术和软件工程管理软件开发技术包括软件开发方法学、开发过程、开发工具和软件工程环境,其主体内容是软件开发方法学软件开发方法包括分析方法,设计方法和程序设计方法软件工程管理包括软件管理学,软件工程经济学,软件心理学等软件管理学包括人员组织,进度安排,质量保证,配置管理,项目计划等软件工程经济学是研究软件开发中成本的估算,成本效益的方法和技术【考点6】软件工程的原则软件工程的原则抽象,信息隐蔽,模块化,局部化,确定性,一致性,完备性,可验证性(详细见教材第28-29页)【考点7】需求分析概述需求分析阶段的工作需求获取,需求分析,编写需求规格说明书,需求评审需求分析方法有
(1)结构化需求分析方法;
①面向数据结构的Jackson方法(ISD);
②面向数据流的结构化分析方法(SA);
③面向数据结构的结构化数据系统开发方法(DSSD);
(2)面向对象的分析的方法(OOA)从需求分析建立的模型的特性来分静态分析和动态分析【考点8】结构化方法和结构化分析方法
1、结构化方法包括结构化分析方法,结构化设计方法,结构化编程方法结构化方法中,软件功能分解属于总体设计阶段
2、结构化分析方法的概念结构化分析方法是面向数据流自顶而下逐步求精进行需求分析的方法结构化分析方法在软件需求分析阶段的应用
3、结构化分析的常用工具数据流图(DFD-DataFlowDiagram)是结构化分析方法中用于系统逻辑模型的一种工具它以图形的方式描绘在系统中流动和处理的过程数据流图中四种基本的符号箭头表示数据流,数据流是数据在系统中传播的路径圆或椭圆表示加工,加工又称为数据处理,是对数据流进行某些操作或变换双横表示数据存储(数据源)数据存储又称为文件,指暂时保存的数据,它可以是数据库文件或任何形式的数据组织方框源、潭表示数据的源点或终点它是软件系统外部环境中的实体,统称外部实体数据字典(DD)它是结构分析方法的核心,是用来描述系统中所用到的全部数据和文件的文档作用是对DFD中出现的被命名的图形元素进行确切解释数据字典由以下4类元素组成
(1)数据流
(2)数据流分量
(3)数据存储
(4)处理判定树(决策树)是一种描述加工的图形工具,适合描述时候处理中具有多个判断,而且每个决策与若干条件有关判定表与判定树类似,也是一种描述加工的图形工具如果一个加工逻辑有多个条件、多个操作,并且在不同的条件组合下执行不同的操作,那么可以使用判定表来描述【考点9】软件需求规格说明书软件需求规格说明书(SRS,SoftwareRequirementSpecification)是需求分析阶段得出的最主要的文档软件需求规格说明书的特点有正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性其中最重要的是无歧义性【考点10】软件设计的基本概念软件设计是确定系统的物理模型软件设计是开发阶段最重要的步骤,是将需求准确地转化为完整的软件产品或系统的唯一途径从技术观点上看,软件设计包括软件结构设计、数据设计、接口设计、过程设计
(1)结构设计定义软件系统各主要部件之间的关系;
(2)数据设计将分析时创建的模型转化为数据结构的定义;
(3)接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信;
(4)过程设计则是把系统结构部件转换为软件的过程性描述从工程管理角度来看,软件设计分两步完成概要设计和详细设计
(1)概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式;
(2)详细设计确立每个模块的实现算法和局部数据结构,用适当方法表示算法和数据结构的细节【考点11】软件设计的基本原理
1、软件设计中应该遵循的基本原理和与软件设计有关的概念模块化把程序划分成独立命名且可独立访问的模块,每个模块完成一个子功能抽象化抽出事物的本质特性而暂时不考虑它们的细节信息隐藏和局部化信息隐蔽是指在一个模块内包含的信息(过程或数据),对于不需要这些信息的其他模块来说是不能访问的,实现信息隐蔽依靠对象的封装模块独立性模块独立性是指每个模块只完成系统要求的独立的子功能,并且与其他模块的联系最少且接口简单模块的独立程度是评价设计好坏的重要度量标准【考点12】耦合性和内聚性衡量软件的模块独立性是用耦合性和内聚性两个定性的度量标准耦合性是对一个软件结构内不同模块之间互联程度的度量耦合性的强弱取决于模块间接口的复杂程度内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量一个模块的内聚性越强则该模块的模块独立性越强一个模块与其他模块的耦合性越强则该模块的模块独立性越弱在结构程序设计中,模块划分的原则是模块内具有高内聚度,模块间具有低耦合度耦合和内聚的种类(详见教材第35页)耦合度由低到高非直接耦合,数据耦合,标记耦合,控制耦合,外部耦合,公共耦合,内容耦合内聚性由强到弱功能内聚,顺序内聚,通信内聚,过程内聚,时间内聚,逻辑内聚,偶然内聚【考点13】结构化设计方法结构化分析方法是面向数据流自顶而下,逐步求精进行需求分析的方法,基本思想将软件设计成由相对独立,单一功能的模块组成的结构,与结构分析方法衔接使用,以数据流图为基础得到软件的模块结构,适用于变换型结构和事物型结构的目标系统
1、概要设计的任务
(1)划分出组成系统的物理元素
(2)设计软件的结构
2、概要设计的工具结构图(SC-StructureChart)也称程序结构图,在结构图中,模块用一个矩形表示,箭头表示模块间的调用关系可以用带注释的箭头表示模块调用过程中来回传递的信息还可用带实心圆的箭头表示传递的是控制信息,空心圆箭心表示传递的是数据结构图的基本形式基本形式、顺序形式、重复形式、选择形式结构图有四种模块类型传入模块、传出模块、变换模块和协调模块程序结构图中的专业术语名称描述深度表示控制的层数上级模块,从属模块上,下两层模块a和b,且有a调用b,则a是上级模块,b是从属模块宽度整体控制跨度(最大模块的层)的表示扇入调用该模块的模块个数扇出一个模块直接调用的其他模块数原子模块树中位于叶子节点的模块
3、面向数据流的设计方法任何软件系统都可以用数据流图表示,典型的数据流类型有两种变换型和事务型变换型系统结构图由输入、中心变换、输出三部分组成
4、设计的准则
(1)提高模块独立性
(2)模块规模适中
(3)深度,宽度,扇出和扇入适当如果深度过大,则说明有的控制模块可能简单了,如果宽度过大,则说明系统的控制过于集中,扇出过大说明模块过分复杂,需要控制和协调过多的下级模块,应适当加中间层次,扇出过小可以把模块进一步分解成若干小模块,或合并到上级模块中,扇入越大则共享该模块的上级数目越多好的软件设计结构通常顶层高扇出,中间扇出较少,底层高扇入
(4)使模块的作用域在该模块的控制域内
(5)减少模块的接口和界面的复杂性
(6)设计成单入口,单出口的模块
(7)设计功能可预测的模块详细设计常用的设计工具(工程设计工具)图形工具,表格工具和语言工具图形工具程序流程图箭头表示控制流,方框表示加工步骤,菱形表示逻辑条件N-S图有五种基本图形PAD图问题分析图,有五种基本图型表格工具判定表语言工具PDL——过程设计语言(结构化的英语和伪码)【考点14】软件测试的目标和准则软件测试的目标发现程序中的错误软件测试的准则
(1)所有测试都是应追溯到需求
(2)严格执行测试计划,排除测试的随意性
(3)充分注意测试中的群集表现程序中存在错误的概率与该程序中已发现的错误数成正比
(4)程序员应避免检查自己的程序
(5)穷举测试不可能穷举测试是把程序所有可能的执行路径都进行检查,即使小规模的程序的执行路径数也相当大,不可能穷尽,说明测试只能证明程序有错,不能证明程序中无错
(6)妥善保存测试计划,测试用例出错统计和最终分析报告【考点15】软件测试方法从是否需要执行被测软件的角度分为静态测试和动态测试;按功能分为白盒测试和黑盒测试
1、静态测试和动态测试静态测试包括代码检查、静态结构分析、代码质量度量不实际运行软件,主要通过人工进行动态测试是通过运行软件来检验软件中的动态行为和运行结果的正确性动态测试的关键是使用设计高效、合理的测试用例测试用例就是为测试设计的数据,由测试输入数据(输入值集)和预期的输出结果(输出值集)两部份组成测试用例的设计方法一般分为两类黑盒测试方法和白盒测试方法
2、白盒测试和黑盒测试
(1)白盒测试白盒测试也称为结构测试或逻辑测试,是把程序看成装在一只透明的白盒子里,测试者完全了解程序的结构和处理过程它根据程序的内部逻辑来设计测试用例,检查程序中的逻辑通路是否都按预定的要求正确地工作白盒测试的基本原则
(1)保证所测模块中每一独立路径至少执行一次
(2)保证所测模块所有判断的每一分支至少执行一次
(3)保证所测模块每一循环都在边界条件和一般条件下至少各执行一次
(4)验证所有内部数据结构的有效性
(5)按照白盒测试的基本原则,“白盒”法是穷举路径测试白盒测试的方法逻辑覆盖,基本路经测试
(2)黑盒测试黑盒测试也称功能测试或数据驱动测试,是把程序看成一只黑盒子,测试者完全不了解,或不考虑程序的结构和处理过程它根据规格说明书的功能来设计测试用例,检查程序的功能是否符合规格说明的要求黑盒测试的方法等价划分法,边界值分析法,错误推测法【考点16】软件测试的实施软件测试过程分4个步骤,即单元测试、集成测试、验收测试和系统测试单元测试是对软件设计的最小单位——模块进行正确性检验的测试,单元测试的根据是源程序和详细设计说明书,单元测试的技术可以采用静态分析和动态测试单元测试期间对模块进行的测试模块接口,局部数据结构,重要的执行通路,出错处理通路,边界条件驱动模块相当于被测模块的主程序,它接收测试数据,并传给所测模块,输出实际测试结果桩模块通常用于代替被测模块调用的其他模块,其作用仅做少量的数据操作,是一个模拟子程序集成测试是测试和组装软件的系统化技术,主要目的是发现与接口有关的错误,集成测试的依据是概要设计说明书集成测试的方法非增量方式组装和增量方法组装增量方式包括自顶而下的增量方式,自底而上的增量方式和混合增量方式确认测试的任务是验证软件的功能和性能,确认测试的实施首先运用黑盒测试方法,对软件进行有效性测试,即验证被测软件是否满足需求规格说明确认的标准检查软件产品是否符合需求定义的过程是确认测试系统测试是通过测试确认的软件,作为整个基于计算机系统的一个元素,与计算机硬件、外设、支撑软件、数据和人员等其他系统元素组合在一起,在实际运行(使用)环境下对计算机系统进行一系列的集成测试和确认测试系统测试的具体实施一般包括功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测试等【考点17】程序调试在对程序进行了成功的测试之后将进入程序调试(通常称Debug,即排错)程序的调试任务是诊断和改正程序中的错误程序调试和软件测试的区别
(1)软件测试是尽可能多地发现软件中的错误,而程序调试先要发现软件的错误,然后借助于一定的调试工具去执行找出软件错误的具体位置
(2)软件测试贯穿整个软件生命期,调试主要在开发阶段程序调试的基本步骤
(1)错误定位从错误的外部表现形式入手,研究有关部分的程序,确定程序中出错位置,找出错误的内在原因;
(2)修改设计和代码,以排除错误;
(3)进行回归测试,防止引进新的错误软件调试可分为静态调试和动态调试静态调试主要是指通过人的思维来分析源程序代码和排错,是主要的设计手段,而动态调试是辅助静态调试的主要的调试方法有
(1)强行排错法;
(2)回溯法;
(3)原因排除法,包括演绎法,归纳法和二分法第四章数据库设计基础【考点1】数据库的基本概念数据(Data)是数据库存储的基本对象,是描述事物的符号记录数据库(DB)是长期储存在计算机内、有组织的、可共享的大量数据的集合,它具有统一的结构形式并存放于统一的存储介质内,是多种应用数据的集成,并可被各个应用程序所共享,所以数据库技术的根本目标是解决数据共享问题数据库管理系统(DBMS)是数据库的管理机构,负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等数据库管理系统是数据库系统的核心数据库系统包含数据库和数据库管理系统数据库管理系统的功能
(1)数据模式定义即为数据库构建其数据框架;
(2)数据存取的物理构建为数据模式的物理存取与构建提供有效的存取方法与手段;
(3)数据操纵为用户使用数据库的数据提供方便,如查询、插入、修改、删除等以及简单的算术运算及统计;
(4)数据的完整性、安全性定义与检查;
(5)数据库的并发控制与故障恢复;
(6)数据的服务如拷贝、转存、重组、性能监测、分析等为完成数据库管理系统的功能,数据库管理系统提供相应的数据语言数据定义语言(DDL)负责数据模式定义和数据物理存取构建数据操纵语言(DML)负责数据的操纵数据控制语言(DCL)负责数据完整性,安全性的定义与检查以及并发控制,故障恢复等功能数据语言按使用方式具有两个结构形式交互式命令语言(自含型和自主型语言)和宿主型语言数据库管理员(DBA)的工作数据库设计,数据库维护,改善系统性能,提高系统效率数据库系统(DBS)是指在计算机系统中引入数据库后的系统,一般由数据库、数据库管理系统、应用系统、数据库管理员和用户构成数据库应用系统(DBAS)是数据库系统再加上应用软件及应用界面这三者所组成,具体包括数据库、数据库管理系统、数据库管理员、硬件平台、软件平台、应用软件、应用界面【考点2】数据管理的发展和基本特点数据管理技术的发展经历了三个阶段人工管理阶段、文件系统阶段和数据库系统阶段,数据独立性最高的阶段是数据库系统阶段人工管理阶段特点
(1)计算机系统不提供对用户数据的管理功能
(2)数据不能共享
(3)不单独保存数据文件系统阶段的缺陷
(1)数据冗余
(2)不一致性
(3)数据联系弱数据库系统的发展阶段第一代的网状、层次数据库系统;第二代的关系数据库系统;第三代的以面向对象模型为主要特征的数据库系统数据库系统的基本特点
(1)数据的高集成性
(2)数据的高共享性和低冗余性
(3)数据高独立性
(4)数据统一管理与控制数据独立性是数据与程序间的互不依赖性,即数据库中的数据独立于应用程序而不依赖于应用程序数据的独立性一般分为物理独立性与逻辑独立性两种
(1)物理独立性当数据的物理结构(包括存储结构、存取方式等)改变时,其逻辑结构,应用程序都不用改变
(2)逻辑独立性数据的逻辑结构改变了,如修改数据模式、增加新的数据类型、改变数据间联系等,用户的应用程序可以不变【考点3】数据系统的内部结构体系
1、数据统系统的三级模式
(1)概念模式,也称逻辑模式,是对数据库系统中全局数据逻辑结构的描述,是全体用户公共数据视图一个数据库只有一个概念模式
(2)外模式,外模式也称子模式,它是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述,一个概念模式可以有若干个外模式
(3)内模式,内模式又称物理模式,它给出了数据库物理存储结构与物理存取方法一个数据库只有一个内模式内模式处于最底层,它反映了数据在计算机物理结构中的实际存储形式,概念模式处于中间层,它反映了设计者的数据全局逻辑要求,而外模式处于最外层,它反映了用户对数据的要求
2、数据库系统的两级映射(详见教材第55页)两级映射保证了数据库系统中数据的独立性
(1)概念模式到内模式的映射该映射给出了概念模式中数据的全局逻辑结构到数据的物理存储结构间的对应关系;
(2)外模式到概念模式的映射概念模式是一个全局模式而外模式是用户的局部模式一个概念模式中可以定义多个外模式,而每个外模式是概念模式的一个基本视图【考点4】数据模型的基本概念数据模型按不同的应用层次分为概念数据模型简称概念模型,是一种面向客观世界,面向用户的模型,不涉及具体的硬件环境和平台也与具体的软件环境无关的模式,它是整个数据模型的基础逻辑数据模型又称数据模型,它是一种面向数据库的模型分为层次模型,网状模型,关系模型和面向对象模型,其中层次模型和网状模型统称为非关系模型层次模型用树型结构表示实体之间联系的模型物理数据模型又称物理模型,它是一种面向计算机物理表示的模型【考点5】E—R模型
1、E-R模型的基本概念
(1)实体现实世界中的事物可以抽象成为实体,实体是概念世界中的基本单位,它们是客观存在的且又能相互区别的事物
(2)属性现实世界中事物均有一些特性,这些特性可以用属性来表示
(3)码唯一标识实体的属性集称为码
(4)域属性的取值范围称为该属性的域
(5)联系在现实世界中事物间的关联称为联系两个实体集间的联系实际上是实体集间的函数关系,这种函数关系可以有下面几种一对一的联系、一对多或多对一联系、多对多
2、E-R模型的的图示法E-R模型用E-R图来表示,E-R图包含了表示实体集、属性和联系的方法
(1)实体的表示用矩形表示实体集,在矩形内写上该实体集的名字
(2)属性的表示用椭圆形表示属性,在椭圆形内写上该属性的名称
(3)联系的表示用菱形表示联系,菱形内写上联系名【考点6】层次模型和网状模型层次模型是有根的定向有序树,是数据库系统中最早出现的数据模型网状模型对应的是有向图层次模型和网状模型各自应满足的条件模型名称满足的条件层次模型
(1)有且只有一个结点没有双亲结点,这个结点称为根结点
(2)根以外的其他结点有且只有一个双亲结点网状模型
(1)允许一个以上的结点无双亲
(2)一个结点可以有多于一个的双亲【考点7】关系模型及相关概念关系模式采用二维表来表示,由关系数据结构,关系操纵和关系完整性约束3部分组成,在关系数据库中,用来表示实体间联系的是关系关系一个关系对应一张二维表一个关系就是一个二维表,但是一个二维表不一定是一个关系元组表中的一行即为一个元组属性表中的一列即为一个属性,给每一个属性起一个名称即属性名分量元组中的一个属性值,是不可分割的基本数据项域属性的取值范围在二维表中惟一标识元组的最小属性值称为该表的键或码二维表中可能有若干个健,它们称为表的候选码或候选健从二维表的所有候选键选取一个作为用户使用的键称为主键或主码表A中的某属性集是某表B的键,则称该属性值为A的外键或外码关系操纵数据查询、数据的删除、数据插入、数据修改关系模型允许定义三类数据约束,它们是实体完整性约束、参照完整性约束以及用户定义的完整性约束其中实体完整性约束、参照完整性约束必须满足的完整性约束条件参照完整性约束不允许关系应用不存在的元组实体完整性约束要求关系的主键中属性值不能为空,这是数据库完整性的最基本要求【考点8】关系代数关系代数是一种抽象的查询语言,关系代数的运算对象是关系,运算结果也是关系运算对象,运算符和运算结果是运算的三大要素集合运算符,专门的运算符,算术比较符和逻辑运算符关系模型的基本运算
(1)插入
(2)删除3修改
(4)查询(包括投影、选择、笛卡尔积运算)还有扩充运算交、除、连接及自然连接运算关系代数的5个基本操作中并,差,交,笛卡尔积是二目运算设关系R和S具有相同的关系模式
1、并R和S的并是由属于R或属于S的所有元组构成的集合
2、差R和S的差是由属于R但是不属于S的元组构成的集合
3、笛卡尔积设R和S的元数分别为r和s,R和S的笛卡尔积是一个(r+s)元的元组集合,每个元组的前r个分量来自R的一个元组,后s个分量来自S的一个元组运算后得到的新表的元组数是R*S,属性是r+s
4、交属于R又属于S的元组构成的集合
5、投影一元运算,对一个关系进行垂直切割,消去某些列,并重新按排列的顺序
6、选择一元运算,根据某些条件对关系进行水平分割即选择符合条件的元组
7、除给定关系R(X,Y)和S(Y,Z),其中X,Y,Z是属性组,R中的Y和S中Y可以有不同的属性名,但必须出自相同的域集
8、连接也称θ连接运算,是一种二元运算,它的操作是从两个关系的笛卡尔积中选取属性间满足一定条件的元组,以合并成一个大关系连接运算包括等值连接和不等值连接连接运算后得到的新表的属性是运算前表中属性相加即多于原来关系中属性的个数
9、自然连接自然连接满足的条件是
(1)两关系间有公共域
(2)通过公共域的相等值进行连接【考点9】数据库设计和管理数据库设计中有两种方法,面向数据的方法和面向过程的方法面向数据的方法是以信息需求为主,兼顾处理需求;面向过程的方法是以处理需求为主,兼顾信息需求由于数据在系统中稳定性高,数据已成为系统的核心,因此面向数据的设计方法已成为主流数据库设计目前一般采用生命周期法,即将整个数据库应用系统的开发分解成目标独立的若干阶段它们是需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段一个低一级范式的关系模式,通过模式分解可以转化为若干个高一级范式的关系模式的集合,这种过程就叫规范化概念结构设计是将需求分析阶段得到的用户需求抽象为信息结构即概念模型的过程,它是整个数据库设计的关键逻辑结构设计的任务是将E—R图转换成关系数据模型的过程数据库的物理结构是指数据库在物理设备上的存储结构和存取方法它依赖于给定的计算机系统常用的存取方法索引方法,聚簇方法和HASH方法数据库管理的内容
(1)数据库的建立,它是数据库管理的核心,包括数据模式的建立和数据加载
(2)数据库的重组
(3)数据库安全性控制
(4)数据库的完整性控制,数据库的完整性是指数据的正确性和相容性
(5)数据库的故障恢复
(6)数据库监控大家记住一定要把08,09年的真题做一遍!图1单链表的结构单链表的结构(图1)……数据域指针域数据域指针域数据域指针域……LDR……图2双链表的结构LDRLDR……图3循环链表的结构ABCEDGFH图4二叉树的遍历可行性研究初步项目计划需求分析概要设计详细分析实现测试维护退役交付使用。