二级《公共基础知识》考试辅导(1)

1、辅导（辅导（1）1.1.1 算法的基本概念算法的基本概念 所谓算法是指解题方案的准确而完整的描述。所谓算法是指解题方案的准确而完整的描述。 1、算法的基本特征、算法的基本特征 可行性、确定性、有穷性、拥有足够的情报。可行性、确定性、有穷性、拥有足够的情报。 2、算法的基本要素、算法的基本要素 （1）算法中对数据的运算和操作）算法中对数据的运算和操作 （2）算法的控制结构）算法的控制结构 顺序、选择、循环三种基本控制结构顺序、选择、循环三种基本控制结构1. 算法的时间复杂度算法的时间复杂度 是指执行算法所需要的计算工作量。是指执行算法所需要的计算工作量。 算法的计算工作量用算法所执行的基本运算法

2、的计算工作量用算法所执行的基本运算次数来度量。算次数来度量。2. 算法的空间复杂度算法的空间复杂度 是指执行这个算法所需要的内存空间。是指执行这个算法所需要的内存空间。（包括程序、数据和额外空间）（包括程序、数据和额外空间）选择题选择题 (1) 下列叙述中正确的是下列叙述中正确的是 A) 算法的效率只与问题的规模有关，而与数据算法的效率只与问题的规模有关，而与数据的存储结构无关的存储结构无关 B) 算法的时间复杂度是指执行算法所需要的计算法的时间复杂度是指执行算法所需要的计算工作量算工作量 C) 数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的 D) 算法的时间复杂度与

3、空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关 B B（5）算法的有穷性是指）算法的有穷性是指 A）算法程序的运行时间是有限的）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的）算法程序的长度是有限的 D）算法只能被有限的用户使用）算法只能被有限的用户使用A A (7) 下列叙述中正确的是下列叙述中正确的是 _ 。 A) 一个算法的空间复杂度大，则其时间复杂度也必定大一个算法的空间复杂度大，则其时间复杂度也必定大 B) 一个算法的空间复杂度大，则其时间复杂度必定小一个算法的空间复杂度大，则其时间复杂度必定小 C)

4、 一个算法的时间复杂度大，则其空间复杂度必定小一个算法的时间复杂度大，则其空间复杂度必定小 D) 上述三种说法都不对上述三种说法都不对 D D（4）算法的空间复杂度是指）算法的空间复杂度是指 A A （2）算法的时间复杂度是指）算法的时间复杂度是指 D D （1）下列叙述中正确的是）下列叙述中正确的是 _ 。 D D1.2 数据结构的基本概念数据结构的基本概念1.2.1 什么是数据结构什么是数据结构1.2.1 什么是数据结构什么是数据结构1.2.1 什么是数据结构什么是数据结构1.2.1 什么是数据结构什么是数据结构1.2.1 什么是数据结构什么是数据结构数据的逻辑结构数据的逻辑结构数据的存储

5、结构数据的存储结构 采用不同的存储结构，其数据处理的效率采用不同的存储结构，其数据处理的效率是不同的。是不同的。数据的存储结构数据的存储结构数据的存储结构数据的存储结构1.2.3 线性结构与非线性结构线性结构与非线性结构 如果一个非空的数据结构满足下列两个条件：如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点；有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。则称该数据结构为线性结构。 线性结构又称线性表。线性结构又称线性表。 如果一个数据结构不是线性结构，则称之为如果一个数据结构不是线性结构，

6、则称之为非线性结构。非线性结构。1.3.1 线性表的基本概念线性表的基本概念 线性表是最简单、最常用的一种数据结构。线性表是最简单、最常用的一种数据结构。 线性表是由一组数据元素组成。数据元素在线线性表是由一组数据元素组成。数据元素在线性表中的位置只取决于它们的序号，即数据元素之性表中的位置只取决于它们的序号，即数据元素之间的相对位置是线性的。间的相对位置是线性的。 例如：例如： 一个一个 n 维向量（维向量（x1, x2, x3, , xn） 是一个长度是一个长度为为 n 的线性表，其中的每一个分量就是一个数据的线性表，其中的每一个分量就是一个数据元素。元素。 一年中的四个季节（春，夏，秋，

7、冬）是一个一年中的四个季节（春，夏，秋，冬）是一个长度为长度为 4 的线性表，其中的每一个季节名就是一个的线性表，其中的每一个季节名就是一个数据元素。数据元素。 矩阵也是一个线性表，把一行看成一个数据元素。矩阵也是一个线性表，把一行看成一个数据元素。1.3.2 线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特线性表的顺序存储结构具有以下两个基本特点：点： 线性表中所有元素所占的存储空间是连续线性表中所有元素所占的存储空间是连续的；的； 线性表中各数据元素在存储空间中是按逻线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。辑顺序依次存放的。 注意：在线性表的顺

8、序存储结构中，其前注意：在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，而且前后件两个元素在存储空间中是紧邻的，而且前件元素一定存储后件元素的前面。件元素一定存储后件元素的前面。线性表的顺序存储结构线性表的顺序存储结构（5）下列叙述中正确的是）下列叙述中正确的是 。 A）程序执行的效率与数据的存储结构密切相关）程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量）程序执行的效率只取决于所处理的数据量 D）以上三种说法都不对）以上三种说法都不对A A（6）下列叙述中正确的是

9、）下列叙述中正确的是 。 A）数据的逻辑结构与存储结构必定是一一）数据的逻辑结构与存储结构必定是一一对应的对应的 B）由于计算机存储空间是向量式的存储结）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构构，因此，数据的存储结构一定是线性结构 C）程序设计语言中的数组一般是顺序存储）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构结构，因此，利用数组只能处理线性结构 D）以上三种说法都不对）以上三种说法都不对D DB B（7）下列叙述中正确的是）下列叙述中正确的是 。1.4.1 栈及其基本运算栈及其基本运算栈的定义栈的定义栈的定义栈的定义栈的特点栈的

10、特点2. 栈的顺序存储及基本运算栈的顺序存储及基本运算栈的顺序存储示例栈的顺序存储示例 p20栈的基本运算栈的基本运算C C（2）下列叙述中正确的是）下列叙述中正确的是 。 (4) 按照按照“后进先出后进先出”原则组织数据的原则组织数据的数据结构是数据结构是 A) 队列队列 B) 栈栈 C) 双向链表双向链表 D) 二叉树二叉树B B填空题（每空填空题（每空2分）分） 4. 按按 “先进后出先进后出” 原则组织数据的数据原则组织数据的数据结构是结构是 【4】 。栈栈（7）下列关于栈的叙述正确的是）下列关于栈的叙述正确的是 A）栈按）栈按 “先进先出先进先出” 组织数据组织数据 B）栈按）栈按

11、“先进后出先进后出” 组织数据组织数据 C）只能在栈底插入数据）只能在栈底插入数据 D）不能删除数据）不能删除数据B B一、选择题一、选择题 （1）一个栈的初始状态为空。现将元素）一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，依次入栈，然后再依次出栈，则元素出栈的顺序是然后再依次出栈，则元素出栈的顺序是 A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBAB B一、选择题（每小题一、选择题（每小题2分）分） （1）下列叙述中正确的是）下列叙述中正确的是 A）栈是）栈是“先进先出先进先出”的线性表的线性表 B）

12、队列是）队列是“先进后出先进后出”的线性表的线性表 C）循环队列是非线性结构）循环队列是非线性结构 D）有序性表既可以采用顺序存储结构，）有序性表既可以采用顺序存储结构，也可以采用链式存储结构也可以采用链式存储结构D D二、填空题（每空二、填空题（每空2分）分） （1）假设一个长度为）假设一个长度为 50 的数组（数组元素的的数组（数组元素的下标从下标从 0到到 49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针 bottom 指向栈底元素，栈顶指针指向栈底元素，栈顶指针 top 指向栈顶元指向栈顶元素，如果素，如果 bottom=49，top=30（数组下标），则（数组下标），则栈

13、中具有栈中具有 【1】 个元素。个元素。 20 A1.4.2 对列及其运算对列及其运算对列是对列是“先进先出先进先出”或或“后进后出后进后出”的线性表。的线性表。对头指针对头指针对尾指针对尾指针排头指针排头指针队尾指针队尾指针队尾指针队尾指针排头指针排头指针排头指针排头指针队尾指针队尾指针2. 循环队列及其运算循环队列及其运算队尾指针队尾指针排头指针排头指针队尾指针队尾指针排头指针排头指针排头指针排头指针队尾指针队尾指针为了能区分队列空或队列满，故增加一个标志为了能区分队列空或队列满，故增加一个标志 S，S 值的定义如下：值的定义如下： 0 表示队列空表示队列空 S = 1 表示队列非空表示队

14、列非空 (5) 下列对队列的叙述正确的是下列对队列的叙述正确的是 A) 队列属于非线性表队列属于非线性表 B) 队列按队列按 “先进后出先进后出” 原则组织数据原则组织数据 C) 队列在队尾删除数据队列在队尾删除数据 D) 队列按队列按 “先进先出先进先出” 原则组织数据原则组织数据 D D二、填空题（每空二、填空题（每空2分）分） (3) 线性表的存储结构主要分为顺序存线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的的线性表，循环队列是队列的 【3】 存储存储结构。结构。顺序顺序二、填空题（每空二、填空题（每空2

15、分）分） (3) 设某循环队列的容量为设某循环队列的容量为50，头指针，头指针front=5（指向队头元素的前一位置），尾（指向队头元素的前一位置），尾指针指针 rear=29（指向队尾元素），则该循环（指向队尾元素），则该循环队列中共有队列中共有 【3】 个元素。个元素。2424即即 29-5=2429-5=24一、选择题一、选择题（2）下列叙述中正确的是）下列叙述中正确的是 A）循环队列有队头和队尾两个指针，因此，）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构循环队列是非线性结构 B）在循环队列中，只需要队头指针就能反映）在循环队列中，只需要队头指针就能反映队列中元素的动态变化

16、情况队列中元素的动态变化情况 C）在循环队列中，只需要队尾指针就能反映）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况队列中元素的动态变化情况 D）循环队列中元素的个数是由队头指针和队）循环队列中元素的个数是由队头指针和队尾指针共同决定尾指针共同决定 D D （2）下列数据结构中，能够按照）下列数据结构中，能够按照 “先进先进先出先出” 原则存取数据的是原则存取数据的是 A）循环队列）循环队列 B）栈）栈 C）队列）队列 D）二叉树）二叉树 C C（3）对于循环队列，下列叙述中正确的是）对于循环队列，下列叙述中正确的是 D D二、填空题（每空二、填空题（每空2分）分） A,B,C

17、,D,E,F,5,4,3,2,115（1）下列叙述中正确的是_。A循环队列是队列的一种链式存储结构 B循环队列是一种逻辑结构 C循环队列是非线性结构 D循环队列是队列的一种顺序存储结构 D D（2）下列叙述中正确的是）下列叙述中正确的是_。A栈是一种先进先出的线性表栈是一种先进先出的线性表 B队列是一种后进先出的线性表队列是一种后进先出的线性表 C栈与队列都是非线性结构栈与队列都是非线性结构 D以上三种说法都不对以上三种说法都不对D D1.5 线性链表线性链表 在链式存储方式中，要求每个结点有两部在链式存储方式中，要求每个结点有两部分组成：一部分用于存放数据元素值，称为数分组成：一部分用于存放

18、数据元素值，称为数据域；另一部分用于存放指针，称为指针域。据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个结点（前件）其中指针用于指向该结点的前一个结点（前件）或后一个结点（后件）。或后一个结点（后件）。 在链式存储结构中，存储结构的存储空间在链式存储结构中，存储结构的存储空间可以不连续。可以不连续。 链式存储结构既可以用于表示线性结构，链式存储结构既可以用于表示线性结构，也可以用于表示非线性结构。也可以用于表示非线性结构。数据域数据域指针域指针域 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。 线性链表在插入或删除过程中不发生数线性链表在插入或删除

19、过程中不发生数据元素移动的现象，只需改变有关结点的据元素移动的现象，只需改变有关结点的指针。指针。 线性单链表线性单链表 循环链表比线性单链表增加了一个表循环链表比线性单链表增加了一个表头结点。在对循环链表进行插入或删除过头结点。在对循环链表进行插入或删除过程中，实现了空表与非空表的运算统一。程中，实现了空表与非空表的运算统一。 5. 数据结构分为线性结构和非线性结构，数据结构分为线性结构和非线性结构，带链的队列属于带链的队列属于 【 5 】 。线性结构线性结构（2）下列叙述中正确的是）下列叙述中正确的是 _ 。 B （2）下列关于线性链表的叙述中，正确）下列关于线性链表的叙述中，正确的是的是

20、 _ 。 C 桥1. 数据结构分为线性结构和非线性数据结构分为线性结构和非线性结构，带链的栈属于结构，带链的栈属于 【 1 】 。线性结构线性结构1.6 树与二叉树树与二叉树1.6 树与二叉树树与二叉树1.6.1 树的概念树的概念 树是一种简单的非线性结构。树中的所有元树是一种简单的非线性结构。树中的所有元素之间的关系具有明显的层次特性。素之间的关系具有明显的层次特性。 在树的图形中，用直线连起来的两端结点中，在树的图形中，用直线连起来的两端结点中，上端结点是前件，下端结点是后件。上端结点是前件，下端结点是后件。树结构的基本特征和术语树结构的基本特征和术语 在树结构中，每一个结点只有一个前件，

21、称为父结点，没有在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。前件的结点只有一个，称为树的根结点，简称为树的根。 在在树结构中，每一个结点可以有多个后件，它们都称为该结点的子树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件个数称为该结点的度。在树结构中，一个结点所拥有的后件个数称为该结点的度。在树中，所有结点中的最大的度称为树的度。在树中，所有结点中的最大的度称为树的度。 树是一种层次结构，根结点在树中的第一层。树的最大层次树是一

22、种层次结构，根结点在树中的第一层。树的最大层次称为树的深度。在树中，叶子结点没有子树。称为树的深度。在树中，叶子结点没有子树。根结点根结点叶子结点叶子结点第第 1 层层第第 2 层层第第 3 层层第第 4 层层该树的度为该树的度为2树的深度为树的深度为4一、选择题（每小题一、选择题（每小题2分）分） （1）下列数据结构中，属于非线性结构）下列数据结构中，属于非线性结构的是的是 A）循环队列）循环队列 B）带链队列）带链队列 C）二叉树）二叉树 D）带链栈）带链栈 C C1.6.2 二叉树及其性质二叉树及其性质二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树的基本性质二叉树的基

23、本性质二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树 (7) (7)在深度为在深度为7 7的满二叉树中，叶子结点的个数为。的满二叉树中，叶子结点的个数为。 A)32 B) 31 C) 64 D) 63A)32 B) 31 C) 64 D) 63 性质性质3(P34)3(P34) 在任意一棵二叉树中，度为在任意一棵二叉树中，度为0 0的结点（即叶子结的结点（即叶子结点）总是比度为点）总是比度为2 2的结点多一个。的结点多一个。 (P35)(P35)满二叉树每层上的结点数都达到最大值，即第满二叉树每层上的结点数都达到最大值，即第k k层上有层上有2 2k-1k-1个结点，且深度为个结点，且深度为

24、m m的满二叉树有的满二叉树有2 2m m-1-1个结点个结点解法解法1 1：= 2= 27-1 7-1 = = 2 26 6 = 64 = 64 解法解法2 2：设叶子结点（度为设叶子结点（度为0 0）为）为n n 2 27 7 -1-1 = n + n -1= n + n -1 n=64 n=64解法解法3 3：直接推算出来直接推算出来C C 1 1 = 2 = 20 0 2 2 = 2 = 21 1 4 4 = 2 = 22 2 8 8 = 2 = 23 3 16 16 = 2 = 24 4 32 32 = 2= 25 56464 = 2 = 26 6n-1是度为是度为2的结点数的结点数

25、 (7) 某二叉树中有某二叉树中有 n 个度为个度为 2 的结点的结点,则该二叉则该二叉树中的叶子结点数为树中的叶子结点数为 A) n+1 B) n-1 C) 2n D) n/2 A A填空题（每空填空题（每空2分，共分，共30分）分） （1）在深度为）在深度为 7 的满二叉树中，度为的满二叉树中，度为 2 的的结点个数为结点个数为_。 第第7 7层的结点均为叶子结点，层的结点均为叶子结点，叶子结点共叶子结点共有有 2 27-17-1=2=26 6=64 =64 个，个，故度为故度为 2 的结点个数为的结点个数为 64-1个。即个。即 6363（8）一棵二叉树中共有）一棵二叉树中共有 70 个

26、叶子结点与个叶子结点与 80 个个度为度为 1 的结点，则该二叉树中的总结点数为的结点，则该二叉树中的总结点数为 A）219 B）221 C）229 D）231提示：叶子结点总是比度为提示：叶子结点总是比度为2的结点多的结点多1个。个。(p34) 70 + 69 + 80 = 219C C填空题（每空填空题（每空2分，共分，共30分）分） (2) 深度为深度为5的满二叉树有的满二叉树有 【2】 个叶子节点。个叶子节点。 16 （3）某二叉树有）某二叉树有 5 个度为个度为 2 的结点，则该二的结点，则该二叉树中的叶子结点数是叉树中的叶子结点数是 A）10 B）8 C）6 D）4 C C二、填空

27、题（每空二、填空题（每空2分）分） 14D D （3）下列关于二叉树的叙述中，正确的）下列关于二叉树的叙述中，正确的是是 _ 。 BD D （3）一棵二叉树共有25个结点，其中5个 是叶子结点，则度为 1 的结点数为_。 A4 B10 C 6 D16 D D1.6.4 二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树二叉树(6) 对如下二叉树对如下二叉树进行后序遍历的结果为进行后序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCAD DACBDEF (10) 对下列二叉树：对下列二叉树：进行中序遍历

28、的结果是进行中序遍历的结果是 _ 。 A) ACBDFEG B) ACBDFGE C) ABDCGEF D) FCADBEG FECADGBA A （6) 对下列二叉树对下列二叉树 进行前序遍历的结果为进行前序遍历的结果为 A) DYBEAFCZX B) YDEBFZXCA C) ABDYECFXZ D) ABCDEFXYZ C C(4) 对下列二叉树进行中序遍历的结果为对下列二叉树进行中序遍历的结果为【4】 。ACBDFEHGPACBDFEHGP二、填空题（每空二、填空题（每空2分）分） (1) 对下列二叉树进行中序遍历的结果是对下列二叉树进行中序遍历的结果是 【1】 。 DBXEAYFZC

29、EDBGHFCA（3）设二叉树如下：）设二叉树如下：对该二叉树进行后序遍历的结果是对该二叉树进行后序遍历的结果是 【 3 】 DEBFCA1.7 查找技术查找技术 查找是指查找是指 在一个给定的数据结构中查找某在一个给定的数据结构中查找某个指定的元素。个指定的元素。1.7.1 顺序查找顺序查找 顺序查找又称顺序搜索。顺序查找又称顺序搜索。 （1）对于无序的线性表，则不管是顺序存）对于无序的线性表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。储结构还是链式存储结构，都只能用顺序查找。 （2）对于有序的线性表，如果采用链式存）对于有序的线性表，如果采用链式存储结构，也只能用顺序查找。储

30、结构，也只能用顺序查找。1.7.2 二分法查找二分法查找 二分法查找只适用于顺序存储的有序表。二分法查找只适用于顺序存储的有序表。有序表是指线性表中的元素按值非递减排列有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素相等）（即从小到大，但允许相邻元素相等） 对于长度为对于长度为 n 的线性表，在最坏情况下，的线性表，在最坏情况下，二分法查找只需要比较二分法查找只需要比较 log2n 次，而顺序查找次，而顺序查找需要比较需要比较 n 次。次。 (8) 在长度为在长度为 64 的有序线性表中进行顺的有序线性表中进行顺序查找，最坏情况下需要比较的次数为序查找，最坏情况下需要比较的次数为 _ 。 A) 63 B) 64 C) 6 D) 7 B B一、选择题（每小题一、选择题（每小题2分）分） （1）下列叙述中，正确的是）下列叙述中，正确的是 A A （3）在长度为）在长度为 n 的有序线性表中进行二的有序线性表中进行二分查找，最坏情况下需要比较的次数是分查找，最坏情况下需要比较的次数是 A）O(n) B）O(n2) C）O(log2n) D）O(nlog2n)C C1.8 排序技术排序技术 排序是指将一个无序序列整理成按值非递减顺序排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排列