Code – 第270页

算法的有穷性是指：算法程序的运行时间是有限的

算法的空间复杂度是指：算法在执行过程中所需要的临时工作单元数

算法的时间复杂度是指：算法在执行过程中所需要的基本运算次数（计算工作量）

算法的时间复杂度和空间复杂度没有直接关系

数据的存储结构是指：数据的逻辑结构在计算机中的表示

有一个以上根结点的数据结构一定是非线性结构

只有一个根结点的数据结构不一定是线性结构，比如树只有一个根结点，但是树不是线性结构

循环链表和双向链表都是线性结构线性结构的定义是，有且只有一个根结点，且中间每个结点有且仅有一个前驱和后继

线性表即顺序表，数据之间是一对一的关系，除首尾，其他所有的元素都首尾相接

栈只能在栈顶插入数据

支持子程序调用的数据结构是栈因为递归调用子程序的时候就是先入后出的线性结构符合栈

栈有记忆作用；栈既能顺序存储，又能链式存储

在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针

循环队列是队列的一种，而队列和栈是一种顺序存储结构。

线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

二叉树的性质：

在非空二叉树中，第i层结点总数不超过2^(i-1)

深度为h的二叉树最多有2^h-1个结点最少有h个结点

对于任意一颗二叉树，其叶子结点数N0 = 度数为2的结点总数N2 + 1

具有n个结点的完全二叉树的深度为log2(n+1)

对于完全二叉树度为1的结点数只有两种可能：0或1

二分查找的最坏情况为log2n次（这是查找这是查找这是查找！）

（以下是排序以下是排序以下是排序！）

冒泡排序、快速排序、直接插入排序在最坏情况下的比较次数是n(n-1)/2

堆排序在最坏情况下比较次数最少，为nlogn

程序既要注重效率又要注重清晰的可读性

结构化程序设计的基本原则（方法）：自顶向下、逐步求精、模块化

继承是指类之间共享属性和操作的机制

对象的基本特点：分类性、多态性、标识唯一性

不是任何对象都必须有继承性，对象的多态性是指同一个操作可以是不同对象的行为

面向对象程序设计的特征有继承性、多态性、封装性不包括类比性

构成计算机软件的是程序、数据以及相关文档

软件危机的表现：软件开发的生产率低、软件质量难以控制、软件成本不断提高

软件工程的主要思想是强调在软件开发过程中需要应用工程化原则

软件工程的3个要素：工具、过程、方法

软件工程过程的4个基本活动：软件规格说明、软件开发、软件确认、软件演进

软件生命周期的定义阶段：可行性研究、计划制定、需求分析

软件生命周期的开发阶段：测试、概要设计、详细设计、实现

软件设计的基本原则是抽象、信息隐藏、模块化、局部化、确定

性、一致性、可验证性

需求分析阶段：需求分析、需求评审、需求获取

需求分析阶段可以使用的工具是：DFD、DD、判断树、判断表

在软件设计中不使用的工具是：程序流程图，使用的工具有：系统结构图、PAD图、数据流图（DFD图）

概要设计->系统结构图

详细设计->程序流程图、N-S、PAD等

数据字典（DD）所定义的对象都包含于数据流图（DFD图），数据字典在需求分析阶段建立。

软件设计中的模块划分应遵循高内聚、低耦合。

数据流程图中没有控制流、程序流程图中没有数据流。

软件测试的目的是尽可能多的发现错误，而并非改正错误。

检查软件产品是否符合需求定义的过程称为确认测试

黑盒测试方法是边界值分析、白盒测试方法是逻辑覆盖

软件测试实施步骤有：集成测试、确认测试、单元测试

软件调试的任务是诊断并改正程序中的错误

数据库管理系统是在操作系统支持下的系统软件

数据库应用系统的核心问题是数据库设计

数据库系统的核心是数据库管理系统

数据库管理系统DBMS包含数据库DB和数据库系统DBS

数据库管理系统中负责数据模式定义的语言是数据定义语言

数据库技术的根本目标是解决数据的共享问题

数据库设计是指在已有数据库管理系统的基础上建立数据库

E-R模型（实体-联系模型）

在E-R模型中，用来表示实体联系的图形是菱形，用来表示实体的图形是矩形，用来表现属性的是椭圆。

E-R图设计数据数据库设计的概念设计阶段

用树形结构表示实体之间联系的模型是层次模型

在关系模型中，每一个二维表称为一个关系

在满足实体完整性约束的条件下一个关系中应该有一个或多个候选关键字

在学生管理的关系数据库中，存取一个学生信息的数据单位是记录

负责数据库中查询操作的数据库语言是数据操纵语言（查询、添加、删除）

运算关系中不改变关系表的属性个数但能减少元组个数的是：交

投影：元组数量不变、属性减少

选择：元组数量减少、属性不变

自然连接：提取两个表中相同的内容然后连接起来

两个表之间的运算关系只能是投影和选择

当对关系R和S进行自然连接时、要求R和S含有一个或多个共有的属性

在数据库设计中，将E-R图转换成关系数据模型的过程属于逻辑设计阶段

将E-R图转换为关系模式时、实体和联系都可以表示为关系

数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和物理设计

一个C语言程序可以实现多种算法

C语言源程序可以放在不同的文件中，同一个源程序也可以放在不同的文件中

算法正确的程序可以有零个输入，但不能有零个输出

每一个C语言的文件或者函数都可以单独编译，但只有main函数才可以执行

sizeof(int) = 4 || sizeof(double) = 8

C语言函数可以嵌套调用，但是不是所有的函数之间都可以相互调用，比如说不可以调用main函数

规定 C程序中不能在函数的内部定义函数

块状注释不能嵌套使用

C语句与机器指令不是一一对应关系

我们所写的每条C语句，经过编译最终都将转换成二进制的机器指令

115L可以用作数据常量，L表示长整型

在C语言中没有定义逻辑类型，而是用0表示假，非零表示真

case是系统关键字，不能用作用户自定义标识符

常量中在前面加0表示八进制不能出现8和以上的数字在前面加0x表示十六进制前面不会出现o这个字母的

在转义字符中，\后面只能0~127 表示ASCII码（即八进制中的0~177）

符号常量是指在程序中通过宏定义用一个符号名来代表一个常量

标识符的长度不能任意长，最多只能包含32个字符

E/e前后都必须要有数字，且后面必须为整数

整型数据10，000 这样的表示形式是错误的

单引号里面的字符串有ASCII码和转义字符两种，ASCII必须为八进制或者十六进制即\ddd或者\xhh

x/y 若左右两边都为int型那么运算结果也是int型

double类型不能进行取余操作

&&表示逻辑与

C语言本身没有提供输入输出语句，但是可以通过调用标准库函数中提供的输入和输出函数来实现输入和输出

C语言中的注释可以出现在程序中的任何位置，但是不能夹在变量或者关键字之间

C语言的变量在函数开始位置进行定义，也可以在变量使用前位置定义

一个浮点数可以和一个整数相加，运算符两侧的运算类型也可以不一致

数值常量中不允许夹带空格

sizeof为测试内存的运算符，()为算数运算符，&&为逻辑运算符，<>不是运算符

强制转换类型表达式格式为(类型名)(表达式)，两个括号都不能省略

关系运算符两边的运算对象可以是C语言中任意合法的表达式

在C语言中，逻辑真值为任何非零数（！！），逻辑假值为0

赋值表达式左边必须为变量，不能是常量！！

逻辑表达式的运算比较复杂，有短路现象

“逻辑与”和“逻辑或”运算低于关系运算和算术运算，但是“逻辑非”却高于算术运算

采用printf输出数据，输出数据都默认为右对齐，若要左对齐，可以在格式控制的”%”和宽度之间加一个”-“来实现

printf的输出精度由变量的类型决定，与域宽无关

赋值语句是一种执行语句，必须放在函数的可执行部分

由printf输出的数据都隐含右对齐！！

%8.6f的意思是一共连着小数点占8位，小数点后面留6位数字

在printf语句中用%%输出一个%符号

负数取余后结果为负数：先按照正数时候情况算，然后加上负号

scanf语句中中间无间隔符，可以空格或者tab或者回车隔开不能用逗号隔开中间有逗号那必须用逗号隔开输入

double型数据scanf中要%lf格式

当scanf从键盘输入数据时，按下回车键后，scanf即接受了这一行数据，不能修改

分支结构是根据表达式的结果来判断流程走向的，不一定是算数表达式

关系运算符的结果只有两种，0和1

在scanf函数中的格式控制字符串是为了输入数据用的，不会输出到屏幕上

复合语句也可以是空语句，并没有规定语句条数

在scanf函数的格式字符前可以加入一个正整数指定输入数据所占的宽度，但不可以用实数制定小数位的宽度

scanf(“格式字符串”,输入项首地址列表) 对于double型，输入时要输入l修饰，否则会产生错误的输入信息，同时输入项必须为地址，也可以是保存变量地址的指针变量。

if(表达式) 表达式可以是任意合法的数值

看清if语句里面为赋值还是为== 赋值语句只要非零就为真赋值为0就是假

case后面只能跟常量表达式，不能跟变量表达式

在switch语句中并不是必须有break和default语句，可以根据需要安排是否有这两个语句

default后面看有没有break;如果没有break;那么后面的case还是要执行的

if(表达式);傻逼空语句= =

switch后面如果是表达式，那么要加括号。case后面必须要有一个空格。case后面也可以是表达式不一定非要数字

while语句条件表达式的执行次数总是比循环体的执行次数多一次

do……while语句条件表达式的执行次数和循环体的执行次数一样

while(y—);每次变量y的值减1，直到等于0退出循环

continue是终止本次循环（但还继续下一轮循环），break是跳出当前循环体，后面的不执行了，只执行到这一步

if(i == 3)

continue：0，1，2，4，5

break：0，1，2

!0 为 1 非任何非零数的结果为0 如！2 为 0

for(i = 0;i < 8;i++){ } 执行完for循环体后最后一步i++还是要执行的

只要适当地修改代码，就可以将do-while和while相互转换

break语句！！只能用在循环体内和switch语句内

当break出现在循环体中的switch语句体内时，只是跳出switch，而不终止循环体执行

函数可以在主函数体内进行声明然后进行调用

若调用子函数的主函数在子函数之前，那么前面必须有子函数的定义，子函数必须先定义后使用

各函数间没有主从关系，不能嵌套定义函数

strlen(s)计算字符串长度不包括末尾的结束标志符’\0’

strcmp(str1,str2) 若str1 == str2 那么函数值为0 若str1 > str2函数值是一个正数若str1 < str2 函数值是一个负数

\n \t \\这些都是转义字符，只要一个字节长度

函数名代表该函数的入口地址

一个自定义函数中可以根据不同情况设置多条return语句

int fun(int *p) {return *p;} fun函数返回值是一个整数，因为返回的是整型指针变量p所指向的数据

无论有多少个return语句，return只能执行一次，返回一个函数值

若函数有返回值，必须通过return语句返回

C程序必须由一个或一个以上的函数组成

( )的优先级高于*

static 在函数定义的静态变量，只需赋值1次，即可保存初始值，不需要每次调用时都赋初始值

函数的形参和实参分别占用不同的存储单元

函数的形式参数属于局部变量

子函数中可以给全局变量赋值，如在头文件下所有函数之外定义int a = 1; 然后 void fun(){a = 3;}这样a的值在调用fun()的时候变成了3

在一个C源程序文件中所定义的全局变量，其作用域由具体定义位置和extern说明来决定范围

子函数中的静态局部变量a和主函数中定义的一个a是没有任何关系的

C语言中形式参数组是指针变量，其数组中元素的个数由传递的实参数组决定，因此可以在定义的时候，不给出元素个数的具体说明

在函数内定义的变量是局部变量，而在函数之外定义的变量称为外部变量，也就是全局变量。全局变量可以为源文件中其他函数所公用，其作用域为从定义变量的位置开始到源文件结束。因此只要用户定义的标识符，全部都有作用域。局部变量可以说明为auto、register以及static。

动态变量auto存储在内存中的动态存储区，在程序运行中，只有当调用变量所在的函数时，系统才临时给变量分配存储单元，全局变量extern一经定义，系统为其分配固定的内存单元；静态变量static编译系统为其分配固定的存储空间；寄存器变量register不保存在内存上，而是直接存储在CPU的寄存器中。

所以说在C语言中，只有在使用时才占用内存单元的变量，其存储类型是auto和register。

在C语言中，有两种对文件的存储方式：顺序存取和直接存取。

如果以“a”的方式对一个已打开的文件进行写操作后，则原有文件中内容将保存，新的数据写在原有内容之后。

如果以“a+”的方式为读和写而打开一个文件，则既可以对文件进行读，也可以对文件进行写，而且在读和写操作之间不必关闭文件，可以从头开始读。

当对文件的读（写）操作完成之后，必须将它关闭。

文件指针实际上是指向一个结构体类型的指针，这个结构体中包含如缓冲区的地址、在缓冲区中当前存取的字符的位置、对文件是“读”或“写”、是否出错、是否已经遇到文件结束标志等信息。

一般称文件指针结构体类型名为FILE,可以用此类型名来定义文件指针。所以说文件指针是程序中用FILE定义的指针变量

文件由数据序列构成，可以工程二进制文件或文本文件

调用函数rewind把文件内部的位置指针重新指向一个文件的开头

fread(buffer,size,count,fp); buffer是数据块指针，对fread来说，它是内存块的首地址，输入的数据存入此内存块中

gets和getchar函数用于从标准输入设备终端读入字符串和字符，并非从磁盘文件读入，fputs用于把字符串输出到文件，fwrite用于以二进制形式输出数据到文件。

fp = (filename,”rb+”);

fwrite的调用形式为：int fwrite(char *pt,unsigned size,unsigned n,FILE *fp); 其功能是把pt所指向的n*size个字节输出到fp所指文件中。

ANSIC提供的feof函数的功能是判断fp所指的文件的位置是否已达到文件尾，如果达到文件尾，则feof函数的值为1，否则为0，表示文件尚未结束。

fputc()是以字符（字节）为单位的读写函数。每次可从文件读出或向文件写入一个字符。使用格式为fputc(ch,fp);

EOF是stdio.h库函数文件中定义的符号常量，其值等于-1.EOF用作文件结束标志（！！！）。在二进制或者文本文件内部有一个位置指针，用以指示文件内部的当前读写位置。使用fgetc函数，每读写一次，该指针均向后移动。

每个数组包含一组具有同一类型的变量，这些变量在内存中占有连续的存储单元

语句float a[10],x; a = &x;是非法的，a表示首地址，在程序中为常量不可更改

二维数组的初始化时，允许省略行下标，不允许省略列下标

在逻辑上，可以把二维数组看成是一个具有行和列的表格或矩阵

int x[2][3]; 数组x可以看作是由x[0]和x[1]两个元素组成的一维数组；元素x[0]可看作是由3个整型元素组成的一维数组；x[0]和x[1]是数组名，分别代表一个地址常量

在定义一维数组时，数组的下标应该是一个确定的整数值。要注意的是在定义二维数组时，其第一维下标可以省略，但第二维下标不能省略。

不可以int n = 5; a[n];在C语言中，定义以为数组中n不可以是变量，必须是整型常量表达式。

char ss[][20] = {“right?”} 这样的赋值是错误的，定义二维数组后，字符串的存储不能通过赋值，只能通过初始化或输入得到

不可以对字符串进行关系运算

两个连续的双引号(“”)是合法的字符串常量

char s[5] = {‘a’,’b’,’c’,’d’,’e’}; 是错误的字符串结束标志无法存储

char *s;gets(s); 是错误的要先对指针变量初始化

C语言中没有字符串数据存储类型

字符串数组，是指数组中的每个元素都是一个存放字符串的一维数组

C语言本身没有提供对字符串进行整体操作的运算符

sizeof是实际占用内存，strlen是实际字符个数

字符数组不能直接赋值

字符数组仅仅可以采用定义时初始化以及输入得到数据，在程序其他部分不允许对其进行赋值。字符串常量中除了实际字符之外还有结束标志，没有字符串结束标志的运行是不安全的

gets(s)函数的作用是将输入的字符读入字符串s，直到遇到回车。而scanf()函数接收字符串时的结束标志为回车或者空格。

char *s; s = “hello”;是正确的而 char *s;s = {“hello”};是错误的定义指针变量s，通过赋值语句保存字符串常量的地址是可以的，而字符数组决不能赋值，而只能初始化或者输入。

s[] = “abcde”; s += 2; 因为s表示的是一个地址常量，常量是不可以被赋值的，所以这句话是错的，程序会出错

预处理命令可以放在程序的任何位置，其有效范围是从定义开始到文件结束。预处理命令有宏定义、文件包含和条件编译三类。

预处理语句后面不能加分号！！

宏定义仅仅只是符号替换，不是赋值语句，因此不做语法检查；双引号中出现的宏名不替换；使用宏定义可以嵌套，即后定义的宏中可以使用先定义的宏。

预处理命令行是在系统对源程序进行编译之前处理的，不是在程序执行的过程中

在C语言中，凡是以“#”开头的行，都称为“编译预处理”。

包含头文件的#include 命令行是通常书写在所用源程序文件的开头，故有时也把包含文件称为头文件。头文件名可以由用户指定，其后缀不一定用“.h”

当包含文件修改后，对包含该文件的源程序必须重新进行编译连接

a = b = (int *)malloc(sizeof(int));含义为申请了一个整型的存储空间，让指针a,b,c分别指向它，*a = 1; *b = 2; *c = 3;语句的含义为所申请的整型存储空间的内容，*c = 3; 最后执行导致存储空间的内容为3.

ANSIC标准规定calloc函数返回值的类型为void*。具体使用格式为：calloc(n,size)。该函数用来给n个同一类型的数据项分配连续的存储空间，每个数据项的长度为size个字节。若分配成功，函数返回存储空间的首地址；否则返回空。通过调用calloc函数所分配的存储单元，系统自动置初值0。

指针变量赋地址值的方式有3种方式：通过求地址运算符(&);通过指针变量获得地址值；通过标准函数获得地址值。

NULL是stdio.h头文件中定义的预定义符。NULL的代码值为0.可以给指针变量赋NULL值。例如p = NULL;赋值语句，称p为空指针。这条语句等价于p = ‘\0’;或者p = 0;这时，指针p并不是指向地址为0的存储单元，而是具有一个确定的值——“空”。

在C语言中，二维数组名也是一个存放地址常量的指针，其值为二维数组中第一行的地址。

int x = 0,*p; p = NULL;

float x; float *p = &x;

*(s + 3)表示的是引用数组a[3].