一、二级公共基础知识的高频考点

（一）数据结构与算法

【考点1】算法的基本概念

1.算法的基本概念

（1）概念：算法是指一系列解决问题的清晰指令。

（2）4个基本特征：可行性、确定性、有穷性、拥有足够的情报。

（3）两种基本要素：对数据对象的运算和操作、算法的控制结构（运算和操作时间的顺序）。

（4）设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。

2.算法的复杂度

（1）算法的时间复杂度：执行算法所需要的计算工作量。

（2）算法的空间复杂度：执行算法所需的内存空间。

【考点2】数据结构的基本概念

数据结构指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间的逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储、链式存储、索引存储和散列存储4种方式。

数据结构按各元素之间前后件关系的复杂度可划分为以下两种。

（1）线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。

（2）非线性结构：不满足线性结构的数据结构。

【考点3】线性表及其顺序存储结构

1.线性表的基本概念

线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。

2.线性表的顺序存储结构

●元素所占的存储空间必须连续。

●元素在存储空间的位置是按逻辑顺序存放的。

3.线性表的插入运算

在第i个元素之前插入一个新元素的步骤如下。

步骤一：把原来第n个节点至第i个节点依次往后移一个元素位置。

步骤二：把新节点放在第i个位置上。

步骤三：修正线性表的节点个数。

在最坏情况下，即插入元素在第一个位置，线性表中所有元素均需要移动。

4.线性表的删除运算

删除第i个位置的元素的步骤如下。

步骤一：把第i个元素之后不包括第i个元素的n-i个元素依次前移一个位置。

步骤二：修正线性表的节点个数。

【考点4】栈和队列

1.栈及其基本运算

（1）基本概念：栈是一种特殊的线性表，其插入运算与删除运算都只在线性表的一端进行，也被称为“先进后出”表或“后进先出”表。

●栈顶：允许插入与删除的一端。

●栈底：栈顶的另一端。

●空栈：栈中没有元素的栈。

（2）特点。

●栈顶元素是最后被插入和最早被删除的元素。

●栈底元素是最早被插入和最后被删除的元素。

●栈有记忆作用。

●在顺序存储结构下，栈的插入和删除运算不需移动表中其他数据元素。

●栈顶指针top动态反映了栈中元素的变化情况。

（3）顺序存储和运算：入栈运算、退栈运算和读栈顶运算。

2.队列及其基本运算

（1）基本概念：队列是指允许在一端进行插入，在另一端进行删除的线性表，又称“先进先出”的线性表。

●队尾：允许插入的一端，用尾指针指向队尾元素。

●排头：允许删除的一端，用头指针指向头元素的前一位置。

（2）循环队列及其运算。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

入队运算是指在循环队列的队尾加入一个新元素。当循环队列非空（s=1）且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。

退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行退队运算，这种情况称为“下溢”。

【考点5】线性链表

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。

在链式存储方式中，要求每个节点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该节点的前一个或后一个节点（即前件或后件）。

【考点6】树和二叉树

1.树的基本概念

树是简单的非线性结构，树中有且仅有一个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，称T1,T2,…,Tmm为根节点的子树。

●父节点：每一个节点只有一个前件，无前件的节点只有一个，称为树的根节点（简称树的根）。

●子节点：每一个节点可以有多个后件，无后件的节点称为叶子节点。

●树的度：所有节点最大的度。

●树的深度：树的最大层次。

2.二叉树的定义及其基本性质

（1）二叉树的定义：二叉树是一种非线性结构，是有限的节点集合，该集合为空（空二叉树）或由一个根节点及两棵互不相交的左右二叉子树组成。可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。二叉树具有如下两个特点。

●二叉树可为空，空的二叉树无节点，非空二叉树有且只有一个根节点。

●每个节点最多可有两棵子树，称为左子树和右子树。

（2）二叉树的基本性质。

性质1：在二叉树的第k层上至多有2k-1个节点（k≥1）。

性质2：深度为m的二叉树至多有2m-1个节点。

性质3：对任何一棵二叉树，度为0的节点（即叶子节点）总是比度为2的节点多一个。

性质4：具有 n个节点的完全二叉树的深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。

3.满二叉树与完全二叉树

（1）满二叉树。满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有节点都有两个子节点。满二叉树在其第i层上有2i-1个节点。

从上面满二叉树定义可知，二叉树的每一层上的节点数必须都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个节点。

（2）完全二叉树。完全二叉树是指这样的二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。

一棵具有n个节点的深度为k的二叉树，它的每一个节点都与深度为k的满二叉树中编号为1～n的节点一一对应。

4.二叉树的存储结构

二叉树通常采用链式存储结构，存储节点由数据域和指针域（左指针域和右指针域）组成。二叉树的链式存储结构也称二叉链表，对满二叉树和完全二叉树可按层次进行顺序存储。

5.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中所有节点，主要指非空二叉树，对于空二叉树则结束返回。二叉树的遍历包括前序遍历、中序遍历和后序遍历。

（1）前序遍历。

前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树。并且，在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作；否则①访问根节点，②前序遍历左子树，③前序遍历右子树。

（2）中序遍历。

中序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根节点，最后遍历右子树。并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。中序遍历描述为：若二叉树为空，则执行空操作；否则①中序遍历左子树，②访问根节点，③中序遍历右子树。

（3）后序遍历。

后序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根节点。并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。后序遍历描述为：若二叉树为空，则执行空操作；否则①后序遍历左子树，②后序遍历右子树，③访问根节点。

【考点7】查找技术

（1）顺序查找：在线性表中查找指定的元素。

最坏情况下，最后一个元素才是要找的元素，则需要与线性表中所有元素比较，比较次数为n。

（2）二分查找：二分查找也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制，它要求表必须用顺序存储结构，且表中元素必须按关键字有序（升序或降序均可）排列。对长度为n的有序线性表，在最坏情况下，二分查找法只需比较log2n次。

【考点8】排序技术

（1）交换类排序法。

●冒泡排序：通过对待排序序列从后向前或从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部，直到所有元素有序为止。

在最坏情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n（n-1）/2。

●快速排序：它是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。最坏情况下，即每次划分，只得到一个序列，时间效率为O（n2）。

（2）插入类排序法。

●简单插入排序法：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素。排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。在最坏情况下，即初始排序序列是逆序的情况下，比较次数为n（n-1）/2，移动次数为n（n-1）/2。

●希尔排序法：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

（3）选择类排序法。

●简单选择排序法：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。最坏情况下需要比较n（n-1）/2次。

●堆排序的方法：首先将一个无序序列建成堆；然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。反复做第二个步骤，直到剩下的子序列空为止。在最坏情况下，堆排序法需要比较的次数为nlog2n。

真题演练

（1）下列叙述中正确的是（　）。

A）算法就是程序

B）设计算法时只需要考虑数据结构的设计

C）设计算法时只需要考虑结果的可靠性

D）以上3种说法都不对

（2）算法的有穷性是指（　）。

A）算法程序的运行时间是有限的

B）算法程序所处理的数据量是有限的

C）算法程序的长度是有限的

D）算法只能被有限的用户使用

（3）算法的空间复杂度是指（　）。

A）算法在执行过程中所需要的计算机存储空间

B）算法所处理的数据量

C）算法程序中的语句或指令条数

D）算法在执行过程中所需要的临时工作单元数

（4）定义无符号整数类为UInt，下面可以作为类UInt实例化值的是（　）。

A）-369

B）369

C）0.369

D）整数集合｛1,2,3,4,5}

（5）下列叙述中正确的是（　）。

A）程序执行的效率与数据的存储结构密切相关

B）程序执行的效率只取决于程序的控制结构

C）程序执行的效率只取决于所处理的数据量

D）以上说法均错误

（6）下列叙述中正确的是（　）。

A）有一个以上根节点的数据结构不一定是非线性结构

B）只有一个根节点的数据结构不一定是线性结构

C）循环链表是非线性结构

D）双向链表是非线性结构

（7）下列叙述中正确的是（　）。

A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C）顺序存储结构能存储有序表，链式存储结构不能存储有序表

D）链式存储结构比顺序存储结构节省存储空间

（8）下列选项中，（）不是一般算法应该有的特征。

A）无穷性

B）可行性

C）确定性

D）有穷性

（9）下列叙述中正确的是（　）。

A）栈是“先进先出”的线性表

B）队列是“先进后出”的线性表

C）循环队列是非线性结构

D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构

（10）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（　）。

A）12345ABCDE

B）EDCBA54321

C）ABCDE12345

D）54321EDCBA

（11）下列关于栈的叙述中正确的是（　）。

A）栈按“先进先出”组织数据

B）栈按“先进后出”组织数据

C）只能在栈底插入数据

D）不能删除数据

（12）下列关于栈的叙述中正确的是（　）。

A）在栈中只能插入数据，不能删除数据

B）在栈中只能删除数据，不能插入数据

C）栈是先进后出（FILO）的线性表

D）栈是先进先出（FIFO）的线性表

（13）下列叙述中正确的是（　）。

A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化

B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化

C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化

D）以上说法都不正确

（14）下列关于栈的叙述中正确的是（　）。

A）栈顶元素最先被删除

B）栈顶元素最后才能被删除

C）栈底元素永远不能被删除

D）栈底元素最先被删除

（15）下列关于栈的叙述中正确的是（　）。

A）栈底元素一定是最后入栈的元素

B）栈顶元素一定是最先入栈的元素

C）栈操作遵循先进后出的原则

D）以上说法均错误

（16）下列与队列结构有关联的是（　）。

A）函数的递归调用

B）数组元素的引用

C）多重循环的执行

D）先到先服务的作业调度

（17）下列数据结构中，能够按照“先进后出”原则存取数据的是（　）。

A）循环队列

B）栈

C）队列

D）二叉树

（18）下列数据结构中，属于非线性结构的是（　）。

A）循环队列

B）带链队列

C）二叉树

D）带链栈

（19）下列关于循环队列的叙述中正确的是（　）。

A）队头指针是固定不变的

B）队头指针一定大于队尾指针

C）队头指针一定小于队尾指针

D）队头指针既可以大于队尾指针，也可以小于队尾指针

（20）下列叙述中正确的是（　）。

A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

D）循环队列中元素的个数是由队头指针和队尾指针共同决定的

（21）下列叙述中正确的是（　）。

A）循环队列是队列的一种链式存储结构

B）循环队列是队列的一种顺序存储结构

C）循环队列是非线性结构

D）循环队列是一种逻辑结构

（22）设循环队列的存储空间为Q（1∶35），初始状态为front=rear=35。现经过一系列入队与出队运算后，front=15,rear=15，则循环队列中的元素个数为（　）。

A）15

B）16

C）20

D）0或35

（23）下列关于线性链表的叙述中正确的是（　）。

A）各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致

B）各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续

C）进行插入与删除时，不需要移动表中的元素

D）以上说法均不正确

（24）下列链表中，其逻辑结构属于非线性结构的是（　）。

A）二叉链表

C）双向链表

B）循环链表

D）带链的栈

（25）支持子程序调用的数据结构是（　）。

A）栈

B）树

C）队列

D）二叉树

（26）某二叉树有5个度为2的节点，则该二叉树中的叶子节点数是（　）。

A）10

B）8

C）6

D）4

（27）一棵二叉树共有25个节点，其中5个是叶子节点，则度为1的节点数为（　）。

A）16

B）10

C）6

D）4

（28）下列关于二叉树的叙述中正确的是（　）。

A）叶子节点总是比度为2的节点少1个

B）叶子节点总是比度为2的节点多1个

C）叶子节点数是度为2的节点数的两倍

D）度为2的节点数是度为1的节点数的两倍

（29）对下列二叉树：

进行前序遍历的结果为（　）。

A）DYBEAFCZX

B）YDEBFZXCA

C）ABDYECFXZ

D）ABCDEFXYZ

（30）在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（　）。

A）n

B）n2

C）log2n

D）nlog2n

（31）对长度为n的线性表排序，在最坏情况下，比较次数不是n（n-1）/2的排序方法是（　）。

A）快速排序

B）冒泡排序

C）直接插入排序

D）堆排序

（32）下列排序方法中，最坏情况下比较次数最少的是（　）。

A）冒泡排序

B）简单选择排序

C）直接插入排序

D）堆排序