公共基础在所有的二级考试科目中都占30分。
在试卷当中，前十道选择题和前五道填空题均是公共基础内容。
公共基础讲义
数据结构与算法（约占10分）
程序设计基础（约占4分）
软件工程基础（约占8分）
数据库设计基础（约占8分）
第一章数据结构基础
本章内容提要
●算法:算法的基本概念、算法复杂度
●数据结构的基本概念：什么是数据结构、数据结构的图形表示、线性结构与非线
性结构
●线性表及其顺序存储结构：线性表的基本概念、顺序存储结构、插入运算、删除
运算
●栈和队列：栈及其基本运算、队列及其基本运算
●线性链表：基本概念、基本运算、循环链表及其基本运算
●树与二叉树：树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树
的遍历
●查找技术：顺序查找、二分法查找
●排序技术：交换类排序法、插入类排序法、选择类排序法
算法
1.算法的基本概念：算法是解题方案的准确而完整的描述。
算法规定了解决某类问题所需的操作语句以及执行顺序，使其能够通过有限的指令语句，在一定时间内解决问题。
算法是一个操作序列，有限长度，目的是解决某类问题。
注意：（1）算法不等同于程序：因为程序的编制不可能由于算法的设计；
（2）算法也不等同于数学上的计算方法：因为很多数学计算公式也许无法在计算机上实现。
2.算法的基本特征（算法具有动态性）：可行性、确定性、有穷性、拥有足够的情报（指
的是有输入有输出）
在设计一个算法时，必须要考虑算法的执行过程保证结果的可靠性。
3.算法的基本要素：
第一要素：对数据对象的运算和操作
1)算术运算 + - * /
2)逻辑运算 NOT AND OR
3)关系运算 > < <>
4)数据传输赋值，输入与输出
第二要素：算法的控制结构（决定了算法中各操作的执行顺序）
顺序、选择、循环
4.算法设计的基本方法（计算机解题的过程实际上是在实施某种算法）
1)列举法（列举所有解决方案）
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
2)归纳法（特殊 -> 一般）适合于列举量为无限的情况
通过列举少量的特殊情况，经过分析，最后找出一般的关系。
3)递推法（已知 -> 未知）
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
4)递归法（逐层分解）
将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题……
5)减半递推法（对问题分而治之）
“减半”是指将问题的规模减半，而问题的性质不变。
所谓“递推”是指重复“减半”的过程。
6)回溯法
复杂应用，找出一个解决问题的线索，然后沿着这个线索逐步多次“探、试”。
5.算法的复杂度（一个算法所要付出的代价）
算法的复杂度可分为：时间复杂度和空间复杂度
算法的复杂度是衡量算法好坏的量度。
1)时间复杂度
概念：指执行算法所需要的计算工作量（即算法的运算次数）。
含义：算法执行过程中所需要的基本运算次数。
影响计算工作量的主要因素：
第一，基本运算次数第二，问题规模
下面的方法不能用来度量算法的时间复杂度：
a)算法程序的长度或算法程序汇总语句（指令）条数
b)算法程序所执行的语句条数
c)算法程序执行的具体时间
时间复杂度的具体度量方法：
在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：
a)平均性态分析
b)最坏情况复杂性分析
2)空间复杂度
概念：空间复杂度是指执行该算法所需要的存储空间（内存空间）
一个算法所用的内存空间包括：算法程序所占的存储空间；输入的初始数据所占的存储空间；算法执行过程中的额外空间。
注意：
a)如果额外空间量相对于问题规模来说是常数，即额外空间量不随问题规模的变化而变
化，则称该算法是原地工作的。
b)为了降低算法的空间复杂度，主要应减少需要处理的数据所占的存储空间以及额外空
间，通常采用压缩存储技术。
算法作业：（补完提纲）
考题练习：
1.下列叙述正确的是：
A.算法就是程序
B.算法强调的是利用技巧提高程序执行效率
C.设计算法时只需考虑结果的可靠性
D.以上三种说法都不对
2.下面叙述正确的是
A.算法的执行效率与数据的存储结构无关
B.算法的空间复杂度是指算法程序中指令（或语句）的条数
C.算法的有穷性是指算法必须能在执行有限个步骤之后终止
D.以上三种描述都不对
3.下列叙述中正确的是：
A.一个算法的空间复杂度大，则其时间复杂度也必定大
B.一个算法的空间复杂度大，则其时间复杂度必定小
C.一个算法的时间复杂度大，则其空间复杂度必定小
D.上述三种说法都不对
4.算法的空间复杂度是指
A.算法程序中变量的个数
B.算法程序中的指令条数
C.算法程序中各控制变量所占的额外空间
D.算法执行过程中所需要的存储空间
历年真题
选择题：0609（7）、0704(1)、0804 (5)、0909(4)、1003（2）
数据结构
目的：提高数据处理的效率（一是提高数据处理的速度；二是尽量节省在数据处理过程中所占用的计算机存储空间）
基本概念：
数据：在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的内容：
逻辑结构：数据元素之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
存储（物理）结构：是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。
注意：对于同一个逻辑结构来说，采用不同的存储结构，其数据处理的效率是不同的。
因此，在数据处理时，选择适合的存储结构很重要。
各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定相同。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据结构中，不仅要存放各数据元素的本身，而且还需要存放各数据元素之间的前后件关系的信息。
逻辑结构与物理结构的关系 (1) 一种逻辑结构可以用不同的物理结构来实现。
(2) 逻辑结构决定了算法的设计。
(3) 物理结构决定了算法的实现。
数据结构的图形表示
表示数据结构的常用方法：二元关系表和图形表示。
例：一年四季的数据结构可以用图形表示为：
数据元素：用中间标有元素值的方框来表示，称为数据结点，简称为结点。
元素之间的前后关系：用一条有向线段从前件结点指向后件结点（注意有时可以省略箭头）
例：家庭成员数据结构可以表示成为：
数据的逻辑结构
线性结构
线性表 栈 队列
非线性结构
树形结构 图形结构
数据的存储结构
顺序存储
链式存储
数据的运算：检索、排序、插入、删除、修改
在数据结构中，没有前件的结点称为根结点没有后件的结点称为终端结点（也称为叶子结点），其它的称为内部结点。
数据结构的分类：线性结构与非线性结构
根据数据结构中各数据元素之间的前后关系的复杂度，一般将数据结构分成两大类：线性结构和非线性结构。
注意：线性结构与非线性结构是在数据的逻辑结构概念下的一种划分方法，与数据的存储结构无关。
前面说过，一种数据的逻辑结构根据需要可以表示成多种存储结构，但只要数据的逻辑结构是属于线性结构，则该逻辑结构的任意一种存储结构也都属于线性结构。
线性结构的定义
如果一个非空的数据结构满足下列两个条件：
(1) 有且只有一个根结点（没有前件的结点称为根结点）
(2) 每个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，线性结构又称线性表。
线性结构的操作
在一个线性结构中插入或删除任何一个结点后还应是线性结构。
历年真题：选择：0709（5）、0709（6）、0809（4）、0909（1）
线性表
(1) 线性表就是线性结构。
(2) 线性表的顺序存储结构也称为顺序表。
(3) 在顺序表中，所有元素所占的存储空间是连续的，且各数据元素在存储空间中是按逻辑顺序依次存放的，其前后两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
(4) 线性表的长度：是指线性表中结点的个数，当n=0里，称为空表。
(5) 通常定义一个一维数组来表示线性表的顺序存储空间。
用一维数组来存放线性表时，该一维数组的长度不要定义为太短，也不要定义为太长。
顺序表（线性表的顺序结构）的插入运算：最坏情况下，N个元素的线性表要移动N次。
顺序表的删除运算：最坏情况下，N个元素的线性表要移动N-1次。
综上所述：线性表的顺序存储结构对于经常需要变动的大线性表就不合适了，因为插入和删
除的效率比较低。
栈
栈的定义：栈是一种特殊的线性表，即限定在一端进行插入与删除的线性表。
栈顶、栈底的定义：在栈中，允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。
入栈、退栈的定义：往栈中插入一个元素叫入栈运算（压栈），从栈中删除一个元素称为退栈运算。
栈的数据操作原则：先进后出FILO
栈具有记忆功能
注意：（1）在顺序存储结构下，栈的插入与删除运算都不需要移动表中其他数据元素。
（2）在栈中，栈顶指针动态反映了栈中元素的变化情况。
栈的存储结构与运算
栈的存储结构：在程序设计语言中，与普通线性表一样，用一维数组作为栈S（1:M）的顺序存储结构，其中M为栈的最大容量。
栈的基本运算：入栈、退栈和读栈顶元素。
在顺序结构下的读栈顶元素是指将栈顶元素赋值给一个指定的变量。
（读不是删除，删除一定要先读。
在只读的情况下，原来是多少，读后还是多少。
）
读栈顶元素过程中应注意的问题：
(1) 读栈顶元素不删除栈顶元素，只是将它的值赋给一个变量。
因此在这个运算中栈顶指针不会改变
(2) 当栈顶指针为0时，说明栈为空，读不到栈顶元素。
队列
队列的定义：队列也是一种特殊的线性表，即允许在一端进行插入，而另一端进行删除的线性表。
允许插入的一端叫队尾。
（尾指针，rear）
允许删除的一端叫队头。
（头指针，front）注意：在尾上插入，头上删除
队列的数据操作方法是：先进先出
在顺序存储结构下，队列的插入与删除运算都不需要移动表中其他数据元素。
在实际应用中，队列的顺序存储结构一般采用循环队列的形式，方法是将队列存储空间的最后一个位置绕到第一个位置，就形成逻辑上的环状空间，供队列循环使用。
确定循环队列中元素个数的方法如下：
设循环队列的容量为M
如果rear>front，则循环队列中的元素个数为rear-front
如果rear<front，则循环队列中的元素个数为m+(rear-front)
循环队列的运算有两个：
(1) 入队运算：是在循环队列的队尾加入一个新元素，也就是rear+1
(2) 退队运算：是在循环队列的排头位置退出一个元素并赋给指定的变量，也就是front+1
程序设计中用一维数组作为队列的顺序存储空间。
队列的实际应用实例
在操作系统中，用队列来组织管理用户程序的排队执行，其原则是：1）初始时该队列为空2）当有用户程序来到时，将该用户程序加入到队列的末尾进行等待3）当计算机系统执行完当前的用户程序后，就从队列头部取出一个用户程序执行。
线性表的顺序存储的缺点
第一、在插入和删除时需要移动元素（除栈和队列之外）
第二、上溢（或下溢）错误的出现，即存储空间不便于扩充。
第三、不便于对存储空间的动态分配
总结：对于大的线性表或者变动频繁的线性表不宜用顺序存储。
线性链表
一、链式存储方式
对于大的线性表或者变动频繁的线性表不宜用顺序存储，应该用链式存储。
链式存储方式的结点：由两部分组成，一部分用于存储数据元素值，称为数据域，另一部分用于存放指针，称为指针域。
指针域用来指向该结点的后一个（或前一个）结点。
链式存储方式的特点（注意与顺序存储方式区别）
(1) 在链式存储结构中，存储数据结构的存储空间可以是不连续的。
(2) 各结点的存储顺序与数据元素之间的逻辑关系可以不一致。
(3) 链式存储方式可以用于线性结构，也可以用于非线性结构。
注：线性链表是线性表的链式存储结构；带链的栈是栈的链式存储结构；带链的队列是队列的链式存储结构
线性链表的定义：线性链表是线性表的链式存储结构
线性链表的存储结点的定义：为了适应线性链表的链式存储结构，计算机存储空间被划分为一个一个小块，每个小块占若干个字节，通常称这些小块为存储结点。
存储结点=数据域（数据元素本身）+指针域（数据元素之间的前后逻辑关系）
头指针：在线性链表中，头指针（head）很关键，不得丢失。
最后一个结点的指针域：线性链表的最后一个结点的指针域为空（用NULL或0来表示）空表的定义：指向线性表的第一个结点的指针head称为头指针，当head等于NULL或0时称为空表。
线性链表种类：
1）单链表：一个结点只有一个指针域指向后件结点；从任何一个结点开始只能扫描到其后的所有结点。
单链表的缺点：只能找到后件，不能找到前件。
2）双向链表：一个结点有两个指针域，分别指向前件结点和后件结点；从任何一个结点开始可以扫描到其后或其前的所有结点，为了克服单链表的缺点，把每个结点修改为由三
部分组成：
双向链表克服了单向链表的只能找到后件不能找到前件的缺陷。
3）循环链表
在循环链表中，所有结点的指针构成了一个环状链。
表头结点的指针域指向线性表的第一个元素的结点，循环链表的头指针指向表头结点，循环链表中最后一个结点的指针也指向表头结点。
从任何一个结点开始可以扫描到链表中的所有结点。
由于在循环链表中设置了一个表头结点，因此在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
带链的栈（栈的链式存储结构）
在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。
这种带链的栈称为可利用栈。
当计算机系统需要存储结点时，退栈。
当计算机系统释放存储结点时，入栈。
线性链表的主要运算有以下三种：
1）在线性链表中查找指定元素。
主要目的是为线性链表的读写、插入和删除做准备。
2）在链式存储结构下的线性表中插入一个新元素。
3）在链式存储结构下的线性表中删除包含指定元素的结点。
注意：线性链表在插入与删除过程中均不发生数据元素移动的现象，只需改变有关结点的指针即可。
历年真题：选择：0704（5）、0804（7）、0809（1）、0809（2）、0903（1）、0903（2）、0909（2）、0909（3）、1009（1）、1009（2）、1103（1）、1103（2）
填空：0609（4）、0609（5）、0709（3）、0804（3）、0903（1）、1003（1）、1003（2）、1009（1）
考题练习：
1.以下数据结构中不属于线性数据结构的是（）
A. 队列
B. 线性表
C. 二叉树
D. 栈
2.数据的存储结构是指（）
A. 存储在外存中的数据
B. 数据所占的存储空间量
C．栈具有记忆作用 D. 数据的逻辑结构在计算机中的表示
3.下列关于栈的描述中错误的是（）
A. 栈是先进后出的线性表
B. 栈只顺序存储
C. 栈具有记忆作用
D. 对栈的插入与删除操作中，不需要改变栈底指针
4.下列对于线性链表的描述中正确的是（）
A.存储空间不一定是连续，且各元素的存储顺序是任意的
B.存储空间不一定是连续，且前件元素一定存储在后件元素的前面
C.存储空间必须连续，且前件元素一定存储在后件元素的前面
D.存储空间必须连续，且各元素的存储顺序是任意的
5.下列关于栈的描述正确的是（）
A.在栈中只能插入元素而不能删除元素
B.在栈中只能删除元素而不能插入元素
C.栈是特殊的线性表，只能在一端插入或删除元素
D.栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素
6.下列叙述中正确的是（）
A.一个逻辑数据结构只能有一种存储结构
B.数据的逻辑结构属于线性结构，存储结构属于非线性结构
C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
7.按照“后进先出”原则组织数据的数据结构是（）
A. 队列
B. 栈
C. 双向链表
D. 二叉树
8.下列叙述中正确的是（）
A. 线性链表是线性表的链式存储结构
B. 栈和队列是非线性结构
C. 双向链表是非线性结构
D. 只有根结点的二叉树是线性结构
1.数据结构分为逻辑结构和存储结构，循环队列属于（）结构。
2.数据的逻辑结构在计算机存储空间中的存放形式称为数据的（）。
3.按“先进后出”原则组织数据的数据结构是（）。
4.数据结构分为线性结构和非线性结构，带链的队列属于（）。
树与二叉树
（树是一种非线性结构，所有数据元素之间的关系具有明显的层次特性）
结点的定义：数据元素+若干指向子树的分支
结点的度的定义：子树的个数。
即拥有的后件的个数称为该结点的度。
树的度的定义：树中所有结点的度的最大值。
叶子结点的定义：度为零的结点，即没有后件的结点。
分支结点的定义：度不为零的结点。
路径的定义：由从根到该结点所经分支和结点构成。
结点的层次（深度）的定义：假设根结点的层次为1，第K层的结点的子树根结点的层次为K+1。
总结：线性结构与树形结构的区别。
二叉树的定义：是一种特殊的树，非空二叉树只有一个根结点。
每个根结点最多有两棵子树，其分别称为该结点的左子树和右子树（注意：左右两个子树的次序不能任意颠倒）
二叉树的基本性质
性质1：在二叉树的第K层上，最多有2k-1（k>=1）个结点。
性质2：深度为M的二叉树最多有2m -1个结点。
性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。
n0=n2+1 性质4：具有n个结点的二叉树，其深度至少为[log2n]+1 。
其中[log2n]表示取log2n的整数部分。
性质5：具有n个结点的完全二叉树的深度为[log2n]+1。
性质6：具有n个结点的完全二叉树，它的叶子结点的个数按照如下公式计算：n为偶数时，叶子结点数为n/2个；
n为奇数时，叶子结点数为(n+1)/2个。
满二叉树与完全二叉树是特殊的二叉树
满二叉树的定义：是指除最后一层外，每一层上的所有结点都有两个子结点。
（注意不要混淆二叉树与满二叉树的概念）
满二叉树的特征：满二叉树上的第k层上有2k-1个结点。
完全二叉树的定义：除最后一层之外，每一层上的结点数均达到了最大值，在最后一层上只缺少右边的若干个结点。
二叉树的存储结构：在计算机中存储二叉树时，除了可以将满二叉树与完全二叉树按层次进行顺序存储之外，其余二叉树通常采用链式存储结构。
二叉树的遍历根据根结点的遍历顺序可分为：
前序遍历：根、左、右
中序遍历：左、根、右
后序遍历：左、右、根
历年真题：选择：0609（10）、0704（6）、0704（7）、0709（8）、0903（3）、1103（3）
填空：0704（1）、0709（4）、0804（2）、0809（1）、0909（1）、1003（3）、1009（3）、1103（2）
考题练习：
1. 在一棵二叉树上第5层的结点数最多是
A)8 B)16 C)32 D)15
2. 某二叉树中度为2的结点有18个，则该二叉树中有_____个叶子结点。
3. 一棵二叉树第六层（根结点为第一层）的结点数最多为______个。
4. 在深度为7的满二叉树中，叶子结点的个数为_______。
5. 有如下边的二叉树，进行后序遍历的结果为_________________。
6. 对如上二叉树进行中序遍历的结果是__________________。
查找技术
顺序查找：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示查找成功，若找不到相等的则查找失败。
对于庞大的线性表来说，顺序查找的效率很低。
但是在下列两种情况下只能采用顺序查找：第一、线性表是无序表（即表中的元素的排列是无序的），则不管顺序结构还是链式结构，都只能用顺序查找。
第二、即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
二分法查找（折半查找）只适用于顺序存储的有序表。
优点是：1)二分查找的效率比顺序查找高得多
2)对于长度为n的有序线性表，在最坏的情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。
最坏情况下查找的次数：
排序技术
排序技术有三大类方法：交换类排序、插入类排序、选择类排序。
交换类排序法的定义：是指借助数据元素之间的相互交换进行排序的一种方法。
典型的交换类排序法：冒泡排序和快速排序
典型的插入类排序法：简单插入排序（也称为直接插入排序）和希尔排序
典型的选择类排序法：简单选择排序和堆排序
以上排序方法最坏情况下需要排序的次数（时间复杂度）
历年真题：选择：0609（8）、0709（7）、0804（6）、0809（3）、0903（4）、1003（1）
填空：1009（2）、1103（1）
考题练习：
1. 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是
A)冒泡排序为n/2 B)冒泡排序为n
C)快速排序为n D) 快速排序为n(n-1)/2
2. 对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为
A)log2n B) n/2 C)n D)n+1
3. 数据结构中，能用二分法进行查找的是
A)顺序存储的有序线性表B)线性链表C)二叉链表D)有序线性表
4. 在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为______。
A)63 B)64 C)6 D)7
5. 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（）。
习题一
一、选择题
1.算法的时间复杂度是指（）
A) 执行算法程序所需要的时间B)算法程序的长度
C) 算法执行过程中所需要的基本运算次数D)算法程序中的指令条数
2. 算法的空间复杂度是指（）
A)算法程序的长度B)算法程序中的指令条数
C)算法程序所占的存储空间D)算法执行过程中所需要的存储空间
3. 下列叙述中正确的是（）
A)线性表是线性结构B)栈与队列是非线性结构
C)线性链表是非线性结构D)二叉树是线性结构
4. 数据的存储结构是指（）
A)数据所占的存储空间量B)数据的逻辑结构在计算机中的表示
C)数据在计算机中的顺序存储方式D)存储在外存中的数据
5. 下列关于队列的叙述中正确的是（）
A)在队列中只能插入数据B)在队列中只能删除数据
C)队列是先进先出的线性表D)队列是先进后出的线性表
6. 下列关于栈的叙述中正确的是（）
A)在栈中只能插入数据B)在栈中只能删除数据
C)栈是先进先出的线性表D)栈是先进后出的线性表
7. 设有右列二叉树：对此二叉树中序遍历的结构为( )
A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA
8. 在深度为5的满二叉树中，叶子结点的个数为（）
A)32 B)31 C)16 D)15
9. 对长度为n的线性表进行顺序查找，在最坏情况下所需要比较次数为（）
A)n+1 B)n C)(n+1)/2 D)n/2
10. 设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。
则T中的叶子结点数为( )
A)8 B)7 C)6 D)5。
