下载文档原格式
第1章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。
详细重点学习知识点：1．算法的概念、算法时间复杂度及空间复杂度的概念2．数据结构的定义、数据逻辑结构及物理结构的定义3．栈的定义及其运算、线性链表的存储方式4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历5．二分查找法6．冒泡排序法1。
1算法考点1 算法的基本概念考试链接:考点1在笔试考试中考核的几率为30％,主要是以填空题的形式出现，分值为2分,此考点为识记内容，读者还应该了解算法中对数据的基本运算。
计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。
1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。
2．算法的基本要素：（1)算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构.在一般的计算机系统中，基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。
（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等.一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成.考点2 算法复杂度考试链接：考点2在笔试考试中,是一个经常考查的内容，在笔试考试中出现的几率为70％，主要是以选择的形式出现,分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念.1。
算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。
同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。
这表明使用绝对的时间单位衡量算法的效率是不合适的.撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量”的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。
计算机二级C语言的二级共公基础知识教程第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
计算机二级C语言公共基础计算机二级C语言公共基础是计算机类专业学生必须掌握的基础知识。
C语言是一种通用的、过程式的编程语言，广泛应用于操作系统、嵌入式系统、游戏开发等领域。
本文将从C语言的基本语法、数据类型、运算符、控制流、函数等方面，介绍C语言的公共基础知识。
一、基本语法C语言的基本语法主要包括变量声明、注释、标识符等。
变量声明即告诉计算机需要分配内存空间来存储变量的值，语法为：```c数据类型变量名;```其中，数据类型可以是int、float、char等，变量名是自定义的名字。
注释用于解释代码的作用，提高代码的可读性，C语言中有两种注释方式：```c//单行注释/*多行注释*/```标识符是变量、函数、数组等自定义名称，标识符必须以字母或下划线开头，由字母、数字和下划线组成。
二、数据类型C语言支持的数据类型包括基本数据类型和派生数据类型。
基本数据类型有int、float、char、double等，派生数据类型有数组、结构体、指针等。
不同的数据类型在内存中占用的空间大小不同，因此在使用时需要根据需要选择合适的数据类型。
三、运算符C语言提供了一系列的运算符用于进行数值计算和逻辑操作。
常见的运算符有算术运算符（+、-、*、/等）、逻辑运算符（&&！等）、关系运算符（>、<、==、!=等）、赋值运算符（=、+=、-=等）等。
通过组合运算符可以进行复杂的运算操作。
四、控制流控制流用于根据条件来控制程序的执行顺序，主要包括条件语句和循环语句。
条件语句用于判断给定条件是否成立，从而决定执行的代码块，常见的条件语句有if语句和switch语句。
循环语句用于重复执行一段代码，常见的循环语句有while循环、do-while循环和for循环。
掌握条件语句和循环语句可以灵活地控制程序的逻辑流程。
五、函数函数是C语言中的一种封装的机制，通过函数可以对代码进行模块化设计，提高代码的重用性和可读性。
`第1章数据结构与算法§1.1 算法的复杂度1. 算法的基本概念①.算法：即解题方案的准确而完整的描述【注意：算法不等于程序，也不等于计算方法，通常，程序的编制不可能优于算法的设计】②.利用计算机算法为计算机解题的过程实际上是在实施某种算法。
（1）算法的基本特征算法一般具有4个基本特征：可行性、确定性、有穷性（包括精度要求确定的计算过程和合理的执行时间的含义）、拥有足够的情报。
（2）算法的基本要素①.对数据对象的运算和操作计算机算法就是计算机能处理的操作所组成的指令序列。
通常，计算机可以执行的基本操作是以指令的形式描述的，一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。
其中基本的运算和操作包括：算术运算、逻辑运算、关系运算、数据传输（赋值、输入、输出等）。
②.控制结构：算法中各操作之间的执行顺序称为算法的控制结构。
ⅰ.描述算法的工具通常有：传统流程图、N—S结构化流程图、算法描述语言。
ⅱ.一个算法的3种基本控制结构：顺序结构、选择结构、循环结构。
（3）算法基本设计方法算法基本设计方法：列举法、归纳法、递推（逐成分解）、递归、减半递推技术、回溯法。
2. 算法复杂度算法复杂度包括时间复杂度和空间复杂度。
注意两者的区别，不要混淆，见表1-1§1.2 数据结构逻辑结构和存储结构1. 数据结构的基本概念（1）数据结构：指相互有关联的数据元素的集合。
（2）数据处理：指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算、也包括对数据元素进行分析。
（3）数据结构研究的3个方面①.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构;②.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构;③.对各种数据结构进行的运算。
2. 数据的逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。
全国计算机等级考试二级c语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计.算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性；(3)有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止,包括合理的执行时间的含义；（4）拥有足够的情报.算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统:一个计算机系统能执行的所有指令的集合。
基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1。
2 数据结构的基本基本概念数据结构研究的三个方面：（1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；(3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1)表示数据元素的信息；(2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等.线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件,也最多有一个后件.非线性结构:不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的.在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
计算机二级c语言公共基础知识计算机二级 C 语言公共基础知识是准备参加 C 语言二级考试的考生必备的知识点。
C 语言是一种高级程序设计语言，广泛用于计算机科学与工程领域。
本文将从以下几个方面介绍 C 语言的公共基础知识。
一、C 语言基本语法1. 注释：在 C 语言中，使用 // 进行单行注释，使用 /* */ 进行多行注释。
注释是用来解释代码的作用，提高代码的可读性。
2. 数据类型：C 语言支持的数据类型包括整型、浮点型、字符型、布尔型等。
声明变量时需要指定变量的数据类型。
3. 运算符：C 语言中有各种算术运算符、关系运算符和逻辑运算符，用于进行相应的计算和比较操作。
4. 控制语句：C 语言提供了条件语句（if-else、switch）、循环语句（for、while、do-while）和跳转语句（break、continue、goto）等控制流程语句。
二、C 语言数组与函数1. 数组：数组是一种存储相同类型数据的集合，通过下标来访问数组中的元素。
C 语言中，数组的声明和初始化需要指定数组的大小。
2. 函数：函数是一段封装了一组语句的代码块，可以在程序中多次调用。
C 语言中的函数包括库函数和用户自定义函数。
函数需要声明和定义，通过函数名和参数可以调用函数。
三、C 语言指针与字符串处理1. 指针：指针是存储变量内存地址的变量。
通过指针，可以对变量进行间接访问，实现对内存的灵活操作。
C 语言中使用 * 运算符来定义和操作指针。
2. 字符串处理：C 语言中的字符串是以字符数组的形式存储的，通过使用相应的库函数可以进行字符串的读取、拷贝、连接等操作。
四、C 语言文件操作与结构体1. 文件操作：C 语言提供了一系列函数来进行文件的读写操作，如fopen、fclose、fread、fwrite 等。
通过文件操作，可以实现对外部文件的读取和写入。
2. 结构体：结构体是一种自定义的数据类型，可以将不同类型的数据组合在一起形成一个新的数据类型。
第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位臵只取决于自己的序号，元素之间的相对位臵是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
第章数据结构与算法算法．算法地概念：是指解题方案地准确而完整地描述．算法地基本特征：可行性、确定性、有穷性(有限地时间)、拥有足够地情报．算法地复杂度：时间复杂度和空间复杂度()时间复杂度：算法所需要地计算工作量（算法所执行地基本运算次数）()空间复杂度：执行这个算法所需要地内存空间数据结构地基本概念．数据结构研究地三个问题()逻辑结构：指反应数据元素之间逻辑关系地数据结构()存储结构（物理结构）：数据地逻辑结构在计算机存储空间中地存放形式.()对各种数据结构进行地运算．数据结构定义：是指带有结构地数据元素地集合.所谓结构就是指数据元素之间地前后件关系.在数据结构中，没有前件地结点称为根结点，没有后件地结点为终端结点（也叫叶子结点）.．空地数据结构：一个元素都没有地数据结构.．数据结构地种类：线性结构与非线性结构.线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件.非线性结构：如果一个数据结构不是线性结构，则称之为非线性结构.线性表及其顺序存储．线性表是最简单、最常用地一种线性结构.．非空线性表地结构特征：()有且只有一个根结点，无前件()有且只有一个终端（叶子）结点，无后件()除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件.在线性表中结点地个数称为线性表地长度，当时，称为空表.．线性表顺序存储结构地基本特点：()所有元素所占地存储空间是连续地()各元素在存储空间中是按逻辑顺序依次存放地．在长度为地顺序存储地线性表中，当在任何位置上插入或删除一个元素概率都相等时，插入或删除一个元素所需移动元素地平均个数是为.栈和队列．栈：限定在一端进行插入与删除地线性表.．栈地结构特点：先进后出或后进先出．栈地基本运算：入栈运算、退栈运算、读栈顶元素()上溢：当栈空间已满，不能再入栈时，称为“上溢”.()下溢：当栈空间已空，不能再出栈时，称为“下溢”.．队列：允许在一端进行插入、而在另一端进行删除地线性表．队列地结构特点：先进先出或后进后出．循环队列：将队列存储空间地最后一个位置绕到第一个位置，形成逻辑上地环状空间.．循环队列中元素个数：(分两种情况)()队尾指针>队头指针：元素个数队尾指针队头指针()队尾指针<队头指针：元素个数队尾指针队列容量–队头指针线性链表．线性表地链式存储结构称为线性链表.．在链式存储结构中，每个数据结点由两部分组成：一部分存放数据元素地值，称为数据域；另一部分存放下一结点地存储地址，称为指针域.．在链式存储结构中，存储数据结构地存储空间可以不连续，各数据结点地存储顺序与数据元素地逻辑关系可以不一致，而数据元素之间地逻辑关系是由指针域来确定地.．线性链表地优点：在线性链表中插入或删除一个元素时，不需要移动元素地位置，只需改变指针地指向就行了.．循环链表地优点：只要指出表中任何一个结点地位置，就可以从它出发访问到表中其他所有地结点，而线性单链表做不到这一点.树与二叉树．树是一种简单地非线性结构.．树地基本术语：父结点；根结点；子结点；叶子结点；结点地度；树地度；树地深度根结点在第层.叶子结点没有子树.．二叉树：只有一个根结点，每一个结点最多有颗子树，且分别叫做左子树和右子树.．二叉树地基本性质：()在二叉树地第层上，最多有（>）个结点()深度为地二叉树最多有个结点()度为地结点（叶子结点）是比度为地结点多一个()具有个结点地二叉树，其深度至少为[]当完全二叉树总结点为偶数时，叶子节点地个数为：当完全二叉树总结点为奇数时，叶子节点地个数为：()．二叉树地遍历：前序遍历（根左右）；中序遍历（左根右）；后序遍历（左右根）查找技术．顺序查找：最坏情况下，需比较次.．二分法查找：最坏情况下，需比较次.排序技术．交换类排序：（）冒泡排序法：()（最坏情况下）（）快速排序法：()（最坏情况下） ()（平均情况下）．插入类排序：（）简单插入排序法：()（最坏情况下）（）希尔排序法：(. )（最坏情况下）．选择类排序：（）简单选择法：()（最坏情况下）（）堆排序法： () （最坏情况下）第章程序设计基础．程序设计风格：清晰第一，效率第二．注释一般分为：序言性注释和功能性注释．结构化程序设计地原则：自顶向下，逐步求精，模块化，限制使用语句．结构化程序地基本结构：顺序结构、选择结构、重复结构（循环结构）．对象：客观世界中地任何实体.类是具有共同属性、共同方法地对象地集合.对象是类地一个实例.类是对象地抽象.．对象特点：标识唯一性、分类性、多态性、封装性、模块独立性好．消息：是对象与对象之间传递地信息.．在面向对象方法中，类之间共享属性和操作地机制称为：继承．继承性地优点：相似地对象可以共享程序地代码和数据结构,从而大大减少了程序中地冗余信息,提高软件地可重用性,便于软件修改维护第章软件工程基础软件工程地基本概念．软件：包括程序、数据及相关文档地完整集合.．软件按功能分为：应用软件、系统软件、支撑软件（或工具软件）.．软件危机：是泛指在计算机软件地开发和维护过程中所遇到地一系列严重问题. ．软件工程概念地出现源自软件危机．软件工程要素：方法，工具，过程（支持软件开发地各个环节地控制、管理）.．软件生命周期：将软件产品从提出、实现、使用维护到停止使用退役地过程. ．软件工程地理论和技术性研究：软件开发技术和软件工程管理.．软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性结构化分析方法．需求分析地任务：发现需求、求精、建模和定义需求地过程.需求分析地目地是确定系统地功能.．结构化需求分析地常用工具()数据流图（）：()数据字典（）：结构化需求分析方法地核心.、软件地需求分析阶段地工作，可以概括为四个方面：需求获取、需求分析、编写需求规格说明书和需求评审.．软件需求规格说明书：是需求分析阶段地最后成果，是软件开发中地重要文档之一.．软件需求规格说明书地作用：()便于用户、开发人员进行理解和交流()反映出用户问题地结构，可以作为软件开发工作地基础和依据.()作为确认测试和验收地依据.．软件需求规格说明书地特点：正确性、无歧义性（最重要）、完整性、可验证性、一致性、可理解性、可修改性、可追踪性结构化设计方法．软件设计从技术观点看，软件设计包括软件结构设计、数据设计、接口设计、过程设计.()结构设计：定义软件系统各主要部件之间地关系.()数据设计：将分析时创建地模型转化为数据结构地定义.()接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信.()过程设计：把系统结构部件转换成软件地过程性描述.．软件设计从工程管理角度看，软件设计分两步完成：概要设计和详细设计．软件设计地基本原理抽象、模块化、信息隐蔽、模块独立性．衡量软件独立性依据：耦合性（是模块间互相连接地紧密程度地度量）内聚性（是一个模块内部各个元素间彼此结合地紧密程度地度量）．耦合性包括：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合.．优秀地软件设计应做到“高内聚，低耦合”.．与结构化需求分析方法对应地是结构化设计方法.．常用地软件结构设计工具是结构图（程序结构图）.其中箭头表示模块间地调用关系.．典型地数据流类型有两种：变换型和事务型.．结构化详细设计工具：()程序流程图：表示控制流；矩形□表示加工步骤；菱形◇表示逻辑条件.()图：为了避免流程图在描述程序逻辑时地随意性和灵活性，提出了用方框图来代替传统地程序流程图，通常也称为图.软件测试．软件测试地目地：检验它是否满足规定地需求可是弄清预期结果与实际结果之间地差别，是为了发现错误而执行程序地过程.．测试要以查找错误为中心，而不是为了演示软件地正确功能.．软件测试地准则：()所有测试都应追溯到需求()严格执行测试计划，排除测试地随意性()充分注意测试中地群集现象:为了提高测试效率，测试人员应该集中对付那些错误群集地程序.()程序员应避免检查自己地程序()穷举测试不可能：测试只能证明程序中有错误，不能证明程序中没有错误()妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便．软件测试地方法：()按是否需要执行被测软件划分：①静态测试：包括代码检查、静态结构分析、代码质量度量等.②动态测试：是为了发现错误而执行程序地过程.测试用例由测试输入数据和之与对应地预期输出结果两部分组成.()按功能划分：①白盒测试：保证所侧模块中每一独立路径至少执行一次（穷举路径测试）②黑盒测试：完全不考虑程序内部地逻辑结构和内部特性，只依据程序地需求和功能规格说明，检查程序地功能是否符合它地功能说明.黑盒测试方法包括：等价类划分法、边界值分析法、错误推测法、因果图等.．软件测试地实施：软件测试是保证软件质量地重要手段，目地是使软件测试工作系统化.软件测试地过程：() 单元测试：目地是发现各模块内部可能存在地各种错误.() 集成测试：是测试和组装软件地过程.() 确认测试：验证软件地功能和性能及其他特性是否满足了需求规格说明中确定地各种需求.() 系统测试：．程序地调试地任务：诊断和改正程序中地错误（主要在开发阶段）.软件测试是尽可能多地发现软件中地错误.第章数据库设计基础数据库系统地基本概念．数据库技术地基本目标是解决数据共享问题.．数据：是描述事物地符号记录.．数据库()：是结构化地相关数据集合，是多种应用数据地集成，并可被多个应用程序共享.．数据库管理系统()：是一种系统软件，是数据库系统地核心，位于用户和操作系统（）之间.．数据语言： ()数据定义语言（）：负责数据地模式定义与数据地物理存取构建.()数据操纵语言（）：负责数据地操作，包括查询及增、删、改等操作.()数据控制语言（）：负责数据完整性、安全性地定义与检查以及并发控制、故障恢复等功能.．数据库管理员（）：主要工作包括数据库设计、数据库维护、改善系统性能，提高系统效率.．数据库系统（）由五部分组成：数据库、数据库管理系统、数据库管理员、硬件平台、软件平台.数据库系统包括数据库和数据库管理系统. （即包括和）．数据管理发展三个阶段：人工管理阶段、文件系统阶段、数据库系统阶段.在数据管理技术地发展过程中，可实现数据共享地是：数据库系统系统阶段.数据库系统阶段并没有完全消除数据冗余，只是减少了数据冗余.．数据库系统基本特点：()数据地集成性()数据地高共享性与低冗余性()数据独立性分为物理独立性和逻辑独立性两级.()数据统一管理与控制物理独立性：当数据地物理结构（存储结构）改变时，不影响数据地逻辑结构，从而不引起应用程序地变化.逻辑独立性：当数据地逻辑结构改变，不需要相应地修改应用程序. ．数据库系统地三级模式：()概念模式：全体用户（应用）公共数据视图()外模式：子模式（用户模式）单个用户地数据视图()内模式：物理模式．数据库系统地二级映射： ()概念模式到内模式地映射 ()外模式到概念模式地映射数据模型．数据模型描述地内容：数据结构、数据操作、数据约束．数据模型按不同地层次分为：概念数据模型、逻辑数据模型、物理数据模型．模型(也叫实体联系模型)：()实体：现实世界中地事物可以抽象成为实体()属性：事物地特性()联系：现实世界中事物之间地关联（一对一联系、一对多联系、多对多联系）()模型图示法：实体集表示法：矩形属性表示法：椭圆形联系表示法：菱形．数据模型分为三种：层次模型、网状模型和关系模型.．关系模型：用二维表结构来表示实体及实体间联系地方法就是关系模型.．在关系模型中，一个二维表就是一个关系；表中每行数据称为元组；每列是一个属性，二维表中属性地个数，称为属性元数.．关系中地数据约束分为三种：实体完整性约束、参照完整性约束和用户定义地完整性约束.关系代数(见公共基础课本—)关系地基本运算：并，交，选择，投影，连接，笛卡尔积.数据库设计与管理．数据库设计是数据库应用地核心. 重点有三个阶段：需求分析、概念设计、逻辑设计．数据库设计一般采用生命周期法，包括：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段.．需求分析阶段：是整个设计活动地基础，也是最困难、最花时间地一步.．数据字典是在需求分析阶段建立，在数据库设计过程中不断修改、充实、完善地. 数据项是数据地最小单位.．概念设计阶段视图设计地三种次序：自顶向下、由底向上、由内向外.．数据库地逻辑设计：主要工作是将—图转换成指定地中地关系模式.()实体与联系都可以表示成关系.()图中属性也可以转换成关系地属性.()实体集也可以转换成关系.。
`第1章数据结构与算法§1.1 算法的复杂度1. 算法的基本概念①.算法：即解题方案的准确而完整的描述【注意：算法不等于程序，也不等于计算方法，通常，程序的编制不可能优于算法的设计】②.利用计算机算法为计算机解题的过程实际上是在实施某种算法。
（1）算法的基本特征算法一般具有4个基本特征：可行性、确定性、有穷性（包括精度要求确定的计算过程和合理的执行时间的含义）、拥有足够的情报。
（2）算法的基本要素①.对数据对象的运算和操作计算机算法就是计算机能处理的操作所组成的指令序列。
通常，计算机可以执行的基本操作是以指令的形式描述的，一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。
其中基本的运算和操作包括：算术运算、逻辑运算、关系运算、数据传输（赋值、输入、输出等）。
②.控制结构：算法中各操作之间的执行顺序称为算法的控制结构。
ⅰ.描述算法的工具通常有：传统流程图、N—S结构化流程图、算法描述语言。
ⅱ.一个算法的3种基本控制结构：顺序结构、选择结构、循环结构。
（3）算法基本设计方法算法基本设计方法：列举法、归纳法、递推（逐成分解）、递归、减半递推技术、回溯法。
2. 算法复杂度算法复杂度包括时间复杂度和空间复杂度。
注意两者的区别，不要混淆，见表1-1§1.2 数据结构1.2.1 逻辑结构和存储结构1. 数据结构的基本概念（1）数据结构：指相互有关联的数据元素的集合。
（2）数据处理：指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算、也包括对数据元素进行分析。
（3）数据结构研究的3个方面①.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构;②.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构;③.对各种数据结构进行的运算。
2. 数据的逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。
数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。
一个数据结构可以表示成：B=(D,R)其中，B表示数据结构。
为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。
在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系（或直接前驱或直接后继关系）来描述。
例如，假设a 与b是D中的；两个数据，则二元组（a，b）表示a是b的前件，b是a的后件例如，如果把一年四季看作一个数据结构，则可表示成：B =(D,R)D ={春季,夏季,秋季,冬季}R ={(春季,夏季),(夏季,秋季),(秋季,冬季)}3. 数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。
顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。
链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。
1.2.2 数据结构的图形表示一个数据结构除了用二元关系表示外，还可以直观地用图形表示。
在数据结构的图形表示中，对于数据集合D 中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R 中的每一个二元组，用一条有向线段从前件结点指向后向结点。
例如，一年四季的数据结构可以用如图的图形表示又如，反映家庭成员间辈分关系的数据结构可以用如图的图形表示在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称叶子结点）。
例如，在数据结构一年四季中，―春‖所在的结点（简称为结点―春‖，下同）为根结点，结点―冬‖为终端结点。
通常，一个数据结构中的元素结点可能是在动态变化的。
根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中某个结点（称为删除运算）插入与删除是对数据结构的两种基本运算。
除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等等。
1.2.3 线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
（1）如果一个非空的数据结构满足下列两个条件： ①.有且只有一个根结点；②.每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构。
线性结构又称线性表。
在一个线性结构中插入或删除任何一个结点后还应是线性结构。
栈、队列、串等都为线性结构。
如果一个数据结构不是线性结构，则称之为非线性结构。
数组、广义表、树和图等数据结构都是非线性结构。
（2）线性表的顺序存储（也称顺序分配）结构具有以下两个基本特点： ①.线性表中所有元素所占的存储空间是连续的；②.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
元素ai 的存储地址为：ADR(ai)=ADR(a1)+(i-1)k ，ADR(a1)为第一个元素的地址，k 代表每个元素占的字节数。
（3）顺序表的运算有查找、插入、删除3种。
§1.3 栈（zhàn）1. 栈的基本概念栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。
在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。
通常称插入、删除的这一端为栈顶，另一端为栈底。
当表中没有元素时称为空栈。
栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。
栈是按照―先进后出‖或―后进先出‖的原则组织数据的。
因此，栈也被称为―先进后出‖表或―后进先出‖表。
由此可以看出，栈具有记忆作用通常用指针top来表示栈顶的位置，用指针botton指向栈底。
往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。
栈顶指针top动态反应了栈中的元素变化情况。
（如右图所示）栈这种数据结构在日常生活中也是常见的。
例如，枪械的子弹匣就可以用来形象的表示栈结构。
子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。
2. 栈的顺序存储及其运算栈的基本运算有3种：入栈、退栈与读栈顶元素。
①.入栈运算：在栈顶位置插入一个新元素；即先将栈顶指针进一（即top加1），然后将新元素插入到栈顶指针指向的位置当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作，这种情况称为―上溢‖错误。
②.退栈运算：取出栈顶元素并赋给一个指定的变量；即先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退一（即top减1）。
当栈顶指针为0时，说明栈空，不可能再进行退栈操作，这种情况称为―下溢‖错误。
③.读栈顶元素：将栈顶元素赋给一个指定的变量。
必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。
当栈顶指针为0时，说明栈空，读不到栈顶元素。
§1.4 队列1. 队列的基本概念队列是只允许在一端进行删除，在另一端进行插入的顺序表，通常将允许删除的这一端称为队头或排头（通常用排头指针【front】指向排头元素的前一个位置），允许插入的这一端称为队尾（通常用一个称为尾指针【rear】的指针指向队尾元素，即尾指针总是指向最后被插入的元素）。
当表中没有元素时称为空队列。
队列的修改是依照先进先出的原则进行的，因此队列也称为先进先出的线性表，或者后进后出的线性表。
例如：火车进遂道，最先进遂道的是火车头，最后是火车尾，而火车出遂道的时候也是火车头先出，最后出的是火车尾。
若有队列：Q =(q1,q2,…,qn)那么，q1为队头元素（排头元素），qn为队尾元素。
队列中的元素是按照q1，q2，…，qn的顺序进入的，退出队列也只能按照这个次序依次退出，即只有在q1，q2，…，qn-1都退队之后，qn才能退出队列。
因最先进入队列的元素将最先出队，所以队列具有先进先出的特性，体现―先来先服务‖的原则。
队头元素q1是最先被插入的元素，也是最先被删除的元素。
队尾元素qn是最后被插入的元素，也是最后被删除的元素。
因此，与栈相反，队列又称为―先进先出‖（First In First Out，简称FIFO）或―后进后出‖（Last In Last Out，简称LILO）的线性表。
2.循环队列ⅰ.循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
ⅱ.循环队列的两种基本运算：入队运算与退队运算。
ⅲ.队列的顺序存储结构一般采用队列循环的形式，即循环队列。
循环队列s=0表示队列空。
s=0且front=rear表示队列满。
计算循环队列的元素个数：―尾指针减头指针‖，若为负数，再加其容量即可。
假设循环队列初始状态为空,即：s=0,且front=rear=m。
①.入队运算：指往队列（循环队列）队尾插入一个数据元素；即将队尾指针进一（即rear=rear+1），并当rear=m+1时置rear=1，然后将新元素插入到队尾指针指向的位置。
当循环队列非空（s=1）且队尾指针等于排头指针时，说明循环列已满，不能进行入队运算，这种情况称为―上溢‖。
②.退队运算：指从队列（循环队列）的队头删除一个数据元素，并赋给指定的变量；即将将排头指针进一（front=front+1），并当front=m+1时置front=1。
然后将排头指针指向的元素赋给指定的变量。
当循环队列为空（s=0）是不能进行退队运算，这种情况称为―下溢‖。
§1.5 链表在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。
其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。
（1）线性链表线性表的链式存储结构称为线性链表。
在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其前件结点；另一个称为右指针，用以指向其后件结点。
这样的表称为双向链表。
在线性链表中，各数据元素结点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致。
