时间复杂度：算法的时间复杂度是指执行算法所需要的时间 空间复杂度：算法的空间复杂度是指算法需要消耗的内存空间 线性表
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的 串
串是零个或多个字符组成的有限序列。可以是字母，数字或其它字符；串中所包含的字符个数为该串的长度。长度为零的串称为空串，它不包含任何字符。
称两个串是相等的，当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。
栈 (Stack)
是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据 栈也称为先进后出表。 队列
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列
在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。 递归
是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象 注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 数组
数组是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。 多维数组
二维数组以上的数组，既非线性也非平面的数组。 二叉树
二叉树是每个结点最多有两个子树的有序树，二叉树的子树有左右之分，次序不能颠倒
树和二叉树的2个主要差别：
1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分 树
树是由一个或多个结点组成的有限集合 森林
指若干棵互不相交的树的集合 遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。
图 (Graph)
图是由结点的有穷集合V和边的集合E组成 图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法 排序
将一组“无序”的记录序列调整为“有序”的记录序列
常见的排序算法 冒泡排序 选择排序 插入排序 快速排序 shell排序 箱排序
箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，?，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。 归并排序
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。 树型排序 查找算法
顺序查找、折半查找、二叉树查找、索引查找、开地址哈希查找方法、拉链法哈希查找方法。 数据库
数据库（Database）是按照数据结构来组织、存储和管理数据的仓库
结构化查询语言 SQL
SQL语言的功能包括查询、操纵、定义和控制，是一个综合的、通用的关系数据库语言，同时又是一种高度非过程化的语言，只要求用户指出做什么而不需要指出怎么做
数据库系统
数据库系统（database systems），是由数据库及其管理软件组成的系统
数据库管理系统
数据库管理系统(database management system)是一种操纵和管理数据库的大型软件，是用于建立、使用和维护数据库，简称dbms。它对数据库进行统一的管理和控制，以保证数据库的安全性和完整性
数据库系统的体系结构
数据库系统一般由4个部分组成：
①数据库，即存储在磁带、磁盘、光盘或其他外存介质上、按一定结构组织在一起的相关数据的集合。
②数据库管理系统（DBMS）。它是一组能完成描述、管理、维护数据库的程序系统。它按照一种公用的和可控制的方法完成插入新数据、修改和检索原有数据的操作。 ③数据库管理员（DBA）。 ④用户和应用程序 数据模型
数据模型是信息模型在数据世界中的表示形式。可将数据模型分为三类: 层次模型、网状模型和关系模型。
层次模型：使用树形结构来表示数据以及数据之间的联系. 网状模型：网状模型使用网状结构表示数据以及数据之间的联系.
关系模型：数据存放在一种称为二维表的逻辑单元中,整个数据库又是由若干个相互关联的二维表组成的.
关系
指的是集合中元素之间的某种相关性
关系模型
用二维表的形式表示实体和实体间联系的数据模型
数据库的完整性
数据库的完整性是指数据库中数据的正确性和相容性。 数据库的安全性
数据库的安全性是指保护数据库以防止非法使用所造成的数据泄露、更改或破坏。 数据库的完整性和安全性是数据库安全保护的两个不同的方面。数据库的安全性保护数据库以防止不合法用户故意造成的破坏，数据库的完整性保护数据库以防止合法用户无意中造成的破坏。 并发控制
并发控制指的是当多个用户同时更新行时，用于保护数据库完整性的各种技术 故障恢复
“数据故障恢复”和“完整性约束”、“并发控制”一样，都是数据库数据保护机制中的一种完整性控制。
所有的数据恢复的方法都基于数据备份。对于一些相对简单的数据库来说，每隔一段时间做个数据库备份就足够了，但是对于一个繁忙的大型数据库应用系统而言，只有备份是远远不够的，还需要其他方法的配合。恢复机制的核心是保持一个运行日志，记录每个事务的关键操作信息
数据库的设计
数据库设计(Database Design)是指对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能够有效地存储数据，满足各种用户的应用需求（信息要求和处理要求）。
事业单位招考计算机专业知识整理
