作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
全国计算机等级考试《二级公共基础知识》【教材精讲＋真题解析】讲义与视频课程【12小时高清视频】试读：
视频讲解教师简介
赵亮，毕业于中科院研究生院的计算机科学与技术专业。常年从事计算机学科的研究和教学，有较强的专业知识和教学能力，能够根据学科特点，深入浅出的讲解课程内容，使学生快速理解掌握，达到教学目标。
授课特点：亲和力强，课堂氛围轻松，授课思路明朗，能够让枯燥的知识形象生动，帮助学员轻松掌握核心知识点，深受广大学员喜爱。
教材精讲部分[视频讲解]
考试形式1公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。
2考试方式为上机考试，10道选择题，占10分。知识点分布
1数据结构与算法
2程序设计基础
3软件工程基础
4数据库设计基础大纲基本要求
1掌握算法的基本概念。
2掌握基本数据结构及其操作。
3掌握基本排序和查找算法。
4掌握逐步求精的结构化程序设计方法。
5掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。
6掌握数据库的基本知识，了解关系数据库的设计。
第1章 数据结构与算法[视频讲解]
1算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。
2数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3线性表的定义；线性表的顺序存储结构及其插入与删除运算。
4栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
5线性单链表、双向链表与循环链表的结构及其基本运算。
6树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。
1.1 算 法
一、算法的基本概念
1算法的定义
算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。【注意】算法不等于程序，也不等于计算方法。
2算法的基本特征（1）可行性（Effectiveness）：算法中的每一个步骤必须能够实现，执行的结果要能够达到预期的目的。（2）确定性（Definiteness）：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释或多义性。（3）有穷性（Finiteness）：算法必须能在有限的时间（合理的时间）内做完，即算法必须能在执行有限个步骤之后终止。（4）拥有足够的情报：输入是否足够并正确，输出是否合理。初始状态是否正确。
二、算法设计基本方法
1列举法（1）基本思想
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。（2）特点
简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。（3）使用
将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。【例1】今有鸡母一，值钱三；鸡翁一，值钱二；鸡雏一，值钱半。凡百钱买百鸡，问鸡母、鸡翁、鸡雏各几何？
假设买母鸡I只、公鸡J只、小鸡K只。根据题意，粗略的列举算法描述如下：
共有三层循环，每层循环各需要循环101次，大约为100万次。
优化后的算法
共有两层循环，循环次数为
2归纳法（1）基本思想
通过列举少量的特殊情况，经过分析最后找出一般的关系。（2）特点
归纳是一种抽象，即从特殊现象中找出一般关系。（3）使用
由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。
3递推（1）基本思想
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（2）特点
本质上属于归纳法，递推关系式往往是归纳的结果。（3）使用
递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。
4递归（1）基本思想
为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。（2）特点
结构清晰，可读性强。（3）使用
递归在可计算性理论和算法设计中占有很重要的地位。（4）分类
直接递归（自己调用自己）和间接递归（P调用Q，Q又调用P）。【例2】编写一个过程，对于输入的参数n，依次打印输出自然数1到n。
非递归算法：
递归算法：
5减半递推技术
所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。【例3】设方程f（x）＝0在区间[a，b]上有实根，且f（a）与f（b）异号。利用二分法求该方程在区间[a，b]上的一个实根。
用二分法求方程实根的减半递推过程如下：（1）首先取给定区间的中点c＝（a＋b）/2。（2）然后判断f（c）是否为0：
如果f（c）＝0，则说明c即为所求的根，求解过程结束；
如果f（c）≠0，则根据以下原则将原区间减半：
①若f（a）f（c）＜0，则取原区间的前半部分；
②若f（b）f（c）＜0，则取原区间的后半部分。（3）最后判断减半后的区间长度是否已经很小：
①若|a－b|＜ε，则过程结束，取（a＋b）/2为根的近似值；
②若|a－b|≥ε，则重复上述的减半过程。
6回溯法（1）基本思想
通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。（2）特点
在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。
三、算法复杂度
主要包括时间复杂度和空间复杂度。
1算法的时间复杂度（1）定义
执行算法所需要的计算工作量。（2）衡量标准
通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关。
综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量＝f（n）。（3）存在问题
算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。（4）解决方法
①平均性态（Average Behavior）
用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量：
②最坏情况复杂性（Worst-Case Complexity）
规模为n时，算法所执行的基本运算的最大次数：
2算法的空间复杂度【定义】执行这个算法所需要的内存空间。（1）算法程序所占的空间；（2）输入的初始数据所占的存储空间；（3）算法执行过程中所需要的额外空间。【注意】
①如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。
②在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。【考题1】算法的时间复杂度是指（ ）。
A．执行算法程序所需要的时间
B．算法程序的长度
C．算法执行过程中所需要的基本运算次数
D．算法执行过程中所需要的所有运算次数
E．算法程序中的指令条数【答案】C【解析】算法的时间复杂度是指算法执行过程中所需要的基本运算次数。执行算法程序所需要的时间、算法长度、指令条数等与时间复杂度没有直接关系。【考题2】算法的空间复杂度是指（ ）。
A．算法程序的长度
B．算法程序中的指令条数
C．算法程序所占的存储空间
D．算法执行过程中所需要的存储空间
E．算法所处理的数据量【答案】D【解析】算法的空间复杂度是指算法执行过程中所需要的存储空间。算法程序的长度、指令条数、所处理的数据量等与空间复杂度没有直接关系。
1.2 数据结构的基本概念
数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
讨论以上问题的目的：（1）提高数据处理的速度；（2）尽量节省在数据处理过程中所占用的计算机存储空间。
一、什么是数据结构【定义】数据结构是指相互有关联的数据元素的集合。
数据元素具有广泛的含义：
描述一年四季的季节名：春、夏、秋、冬
表示数值的各个数：18、11、35、23、16…
表示家庭成员的各成员名：父亲、儿子、女儿
数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。【注意】作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。
1数据的逻辑结构（1）定义
反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：
①表示数据元素的信息；
②表示各数据元素之间的前后件关系。（2）数据的逻辑结构有两个要素：
一是数据元素的集合，通常记为D；
二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R；
即一个数据结构可以表示成B＝（D，R）。【例4】一年四季的数据结构可以表示成
B＝（D，R）
D＝{春，夏，秋，冬}
R＝{（春，夏），（夏，秋），（秋，冬）}
2数据的存储结构
定义：数据的逻辑结构在计算机存储空间中的存放形式。【注意】
①各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
②在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
③常用的存储结构有顺序、链接、索引等存储结构。
④采用不同的存储结构，其数据处理的效率是不同的。
二、数据结构的图形表示
一个数据结构除了用二元关系表示外，还可以直观地用图形表示。（1）对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；（2）对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点，有时箭头可省去。
图1-1 一年四季数据结构的图形表示图（线性）
图1-2 家庭成员间关系数据结构的图形表示（树型结构）【考题】下列叙述中正确的是（ ）。
A．线性表是线性结构
B．栈与队列是非线性结构
C．循环链表是非线性结构
D．二叉树是线性结构【答案】A【解析】选项A正确；选项B，栈和队列都是线性结构，二者区别是，栈只允许在一端插入和删除，队列只允许在一端插入，在另一端删除；选项C，循环链表是线性表的链式存储结构；选项D，二叉树是一种典型的非线性结构。
三、线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，线性结构又称线性表。【注意】在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。【考题】设数据集合为D＝{1，3，5，7，9}，D上的关系为R。下列数据结构B＝（D，R）中为非线性结构的是（ ）。
A．R＝{（5，1），（7，9），（1，7），（9，3）}
B．R＝{（9，7），（1，3），（7，1），（3，5）}
C．R＝{（1，9），（9，7），（7，5），（5，3）}
D．R＝{（1，3），（3，5），（5，9）}【答案】D【解析】如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。则该数据结构为线性结构。
选项A：5是根结点，5的后件是1，1的后件是7，7的后件是9，9的后件是3，故选项A是线性结构；
选项B：9是根结点，9的后件是7，7的后件是1，1的后件是3，3的后件是5，故选项B是线性结构；
选项C：1是根结点，1的后件是9，9的后件是7，7的后件是5，5的后件是3，故选项C是线性结构；
选项D：1是根结点，1的后件是3，3的后件是5，5的后件是9，7也是根结点，没有前件也没有后件，线性数据结构第一个条件不满足，故选项D是非线性结构，即选项D正确。
1.3 线性表及其顺序存储结构
一、线性表的基本概念
线性表（Linear List）是最简单、最常用的一种数据结构。如：一个n维向量、矩阵，学生情况登记表。
线性表是由n（n≥0）个数据元素a，a，…，a组成的一个有限12n序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为（a，a，…，a，…，a），其中a（i＝1，2，…，n）是属12ini于数据对象的元素，通常也称其为线性表中的一个结点。
非空线性表有如下一些结构特征：（1）有且只有一个根结点a它无前件；1（2）有且只有一个终端结点a，它无后件；n（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。【说明】
①线性表中结点的个数n称为线性表的长度。
②当n＝0时，称为空表。
二、线性表的顺序存储结构
1特点（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
图1-3 线性表的顺序存储结构【注意】
①在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。
②在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。
2线性表的相关操作（1）插入：在线性表的指定位置处加入一个新的元素。（2）删除：在线性表中删除指定的元素。（3）查找：在线性表中查找某个（或某些）特定的元素。（4）排序：对线性表中的元素进行整序（即线性表的）。（5）分解：按要求将一个线性表分解成多个线性表。（6）合并：按要求将多个线性表合并成一个线性表。（7）复制：复制一个线性表。（8）逆转：逆转一个线性表。
三、顺序表的插入运算【例5】长度为8的线性表顺序存储在长度为10的存储空间中。在第2个元素之前插入一个新元素87。然后在线性表的第9个元素之前插入一个新元素14。
图1-4 线性表在顺序存储结构下的插入
线性表的存储空间从1到m，线性表的长度为n（n≤m），插入的位置为i（i表示在第i个元素之前插入）。线性表的插入操作如下：
第一步首先处理以下三种异常情况：
①当存储空间已满（即n＝m）时为“上溢”错误，不能进行插入，算法结束；
②当i＞n时，认为在最后一个元素之后插入；
③当i＜1时，认为在第1个元素之前插入。
第二步从最后一个元素开始，直到第i个元素，每一个元素往后移动一个位置。
第三步将新元素插入到第i个位置，线性表的长度加1。
四、顺序表的删除运算【例6】长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素。再删除线性表中的第6个元素。
图1-5 线性表在顺序存储结构下的删除
线性表的存储空间从1到m，线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素）。线性表的删除操作如下：
第一步首先处理以下两种异常情况：
①当线性表为空（即n＝0）时错误，不能进行删除，算法结束；
②当i＜1或i＞n时，错误，不能进行删除，算法结束。
第二步删除线性表中的第i个元素。
第三步从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。线性表的长度减小1。
1.4 栈和队列
一、栈及其基本运算
1什么是栈【定义】限定在一端进行插入与删除的线性表【说明】
①允许插入与删除的一端称为栈顶（指针top），而不允许插入与删除的另一端称为栈底（指针bottom）。
②栈是按照“先进后出”（FILO）的原则组织数据。
③栈具有记忆作用。
④往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为出栈运算。
图1-6 栈示意图
2栈的顺序存储及其运算
图1-7（a）是容量为10的栈顺序存储空间，栈中已有6个元素；图1-7（b）与图1-7（c）分别为入栈与退栈后的状态。
图1-7 栈在顺序存储结构下的运算（1）入栈运算
入栈运算是指在栈顶位置插入一个新元素。操作过程如下：
①首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
②然后将栈顶指针进一（即top加1）。
③最后将新元素x插入栈顶指针指向的位置。（2）退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。
②然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
③最后将栈顶指针退一（即top减1）。（3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。
②然后将栈顶元素赋给指定的变量y。【注意】这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。【考题】下列关于栈的叙述中正确的是（ ）。
A．在栈中只能插入数据
B．在栈中只能删除数据
C．栈是先进先出的线性表
D．栈是先进后出的线性表
E．栈是一种非线性结构【答案】D【解析】在栈中，只允许在栈顶一端进行插入和删除，所以A、B错误；队列是“先进先出”的线性表，栈是“先进后出”的线性表，所以C、E错误，D正确。
二、队列及其基本运算
1什么是队列
加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。【说明】
①允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
②在队列中按照“先进先出”的原则进行操作。
图1-8 具有6个元素的队列示意图
图1-9 队列运算示意图【考题】下列关于队列的叙述中正确的是（ ）。
A．在队列中只能插入数据
B．在队列中只能删除数据
C．队列是先进先出的线性表
D．队列是先进后出的线性表【答案】C【解析】在队列中，只允许在一端进行插入，在另一端进行删除，所以A、B错误；队列是“先进先出”的线性表，栈是“先进后出”的线性表，所以D错误，选择C。
2循环队列及其运算【定义】循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
图1-10 循环队列存储空间示意图
用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。
在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：
由此可以得出队列空与队列满的条件如下：
队列空的条件为s＝0；
队列满的条件为s＝1且front＝rear。
图1-11 循环队列运算示意图（1）入队运算
入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：
①首先判断循环队列是否满。当循环队列非空（S＝1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。
②然后将队尾指针进一（即rear＝rear＋1），并当rear＝m＋1时置rear＝1。
③最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。（2）退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
①首先判断循环队列是否为空。当循环队列为空（s＝0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。
②然后将排头指针进一（即front＝front＋1），并当front＝m＋1时置front＝1。
③再将排头指针指向的元素赋给指定的变量。
④最后判断退队后循环队列是否为空。当front＝rear时置循环队列空标志（即s＝0）。【考题】设循环队列为Q（1：m），其初始状态为front＝rear＝m。经过一系列入队与退队运算后，front＝30，rear＝10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（ ）。
A．19
B．20
C．m－19
D．m－20【答案】D【解析】在该循环队列中作顺序查找，最坏情况下需要比较的次数，实际上就是求循环队列中元素的个数。元素的个数＝（rear－front＋m）mod m＝（10－30＋m） mod m＝m－20，选项D正确。
1.5 线性链表
一、线性链表的基本概念【定义】线性表的链式存储结构称为线性链表。线性链表的数据结构包括两部分，一是数据元素的值，二是数据元素之间的前后件关系。
图1-12 线性链表的一个存储结点
为什么用线性链表？（1）线性表顺序存储结构存在的缺点：
①插入或删除过程中需要移动大量的数据元素。
②出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。
③线性表的顺序存储结构不便于存储空间的动态分配。（2）线性表链式存储结构存在的优点：
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。【说明】
①在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。
图1-13 线性链表的逻辑结构
②在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。
③当HEAD＝NULL（或0）时称为空表。
图1-14 线性链表例
1双向链表
对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。
图1-15 双向链表示意图
2带链的栈
栈也是线性表，也可以采用链式存储结构。
图1-16 带链的栈
在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。
图1-17 可利用栈及其运算
3带链的队列
队列也是线性表，也可以采用链式存储结构。
图1-18 带链的队列及其运算
二、线性链表的基本运算
线性链表的运算主要有以下几个：
①插入：在线性链表中包含指定元素的结点之前插入一个新元素。
②删除：在线性链表中删除包含指定元素的结点。
③合并：将两个线性链表按要求合并成一个线性链表。
④分解：将一个线性链表按要求进行分解。
⑤逆转
⑥复制
⑦排序
⑧查找
1在线性链表中查找指定元素
从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。
因此，由这种方法找到的结点p有两种可能：
①当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；
②当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。
2线性链表的插入
图1-19 线性链表的插入
3线性链表的删除
试读结束[说明：试读内容隐藏了图片]