第一章数据结构及算法
笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查，读者应对此部分进行重点学习。
公务员缺考禁考三年
详细重点学习知识点：
1．算法的概念、算法时间复杂度及空间复杂度的概念
2．数据结构的定义、数据逻辑结构及物理结构的定义
3．栈的定义及其运算、线性链表的存储方式
4．树及二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历
5．二分查法
6．冒泡排序法
考点1  算法的基本概念
考试链接：
考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。
考点2  算法复杂度
考试链接：
考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。疑难解答：算法的工作量用什么来计算？
算法的工作量用算法所执行的基本运算次数来计算，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量（n），其中n是问题的规模。头发秃了一小块
考点3  数据结构的定义
考试链接：
考点3在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为识记内容，读者还应该识记数据的逻辑结构和存储结构的概念。
考点4  线性结构及非线性结构
考试链接：
考点4在笔试考试中，虽然说不是考试经常考查的内容，但读者还是对此考点有所了解，在笔试考试中出现的几率为30%，主要是以填
2分，此考点为识记内容。
疑难解答：空的数据结构是线性结构还是非线性结构？
考点5  栈及其基本运算
考试链接：
考点5在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100%，主要是以选择的形式出现，分值为2分，此考点为重点掌握内容，读者应该掌握栈的运算。
"先进后出"或"后进先出"的原则组织数据，
但是出栈方式有多种选择，在考题中经常考查各种不同的出栈方式。
考点6  线性链表的基本概念
考试链接：
考点6在笔试考试中出现的几率为30%，主要是以选择的形式出现，2分，此考点为识记内容。重点识记结点的组成。
疑难解答：在链式结构中，存储空间位置关系及逻辑关系是什
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序及数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
考点7  树及二叉树及其基本性质
考试链接：
考点7在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100%，主要是以选择的形式出现，有时也有出现在填空题中，分值为2分，此考点为重点掌握内容。重点识记树及二叉树的性质。
误区警示：
满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。应该注意二者的区别。
在二叉树的遍历中，无论是前序遍历，中序遍历还是
后序遍历，二叉树的叶子结点的先后顺序都是不变的。
考点8  二叉树的遍历
考试链接：
考点8在笔试考试中考核几率为30%，分值为2分，读者应该熟练掌握各种遍历的具体算法，能由两种遍历的结果推导另一种遍历的结果。
疑难解答：树及二叉树的不同之处是什么？
公共基础知识考点大全考点9  顺序查
考试链接：
考点9在笔试考试中考核几率在30%，一般出现选择题中，分值为2分，读者应该具体掌握顺序查的算法。
考点10  二分法查
考试链接：
考点10在笔试考试中考核几率为30%，一般出现填空题中，分值为2分，考核比较多查的比较次数，读者应该具体掌握二分查法的
疑难解答：二分查法适用于哪种情况？
这个过程一直进行到查成功或子表长度为0为止。
对于长度为n的有序线性表，在最坏情况下，二分查只需要比较2n次。
考点11  交换类排序法
考试链接:
考点11属于比较难的内容，一般以选择题的形式考查，考核几率为30%，分值约为2分，读者应该熟练掌握几种排序算法的基本过程。
冒泡排序法和快速排序法都属于交换类排序法。
疑难解答：冒泡排序和快速排序的平均执行时间分别是多少？
1.7 例题详解
一、选择题
【例1】算法的时间复杂度取决于。（考点2）
A）问题的规模B）待处理的数据的初态
C）问题的难度D）A）和B）
解析：算法的时间复杂度不仅及问题的规模有关，在同一个问题规模下，而且及输入数据有关。即及输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。
答案：D）
【例2】在数据结构中，从逻辑上可以把数据结构分成。（考点3）A）内部结构和外部结构B）线性结构和非线性结构
C）紧凑结构和非紧凑结构D）动态结构和静态结构全国会计资格评价网报名入口
解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。
答案：B）
【例3】以下不是栈的基本运算。（考点5）
二建报名费多少钱A）判断栈是否为素空B）将栈置为空栈
C）删除栈顶元素D）删除栈底元素解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。
答案：D）
【例4】链表不具备的特点是。（考点6）
A）可随机访问任意一个结点B）插入和删除不需要移动任何元素
C）不必事先估计存储空间D）所需空间及其长度成正比
解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查每个结点。所以答案为A）。
答案：A）
【例5】已知某二叉树的后序遍历序列是，中序遍历序列是，则它的前序遍历序列是。（考点8）
行测常识2022背诵A）B）
C）D）
解析：后序遍历的顺序是"左子树－右子树－根结点"；中序遍历顺序是"左子树－根结点－右子树"；前序遍历顺序是"根结点－左子树－右子树"。根据各种遍历算法，不难得出前序遍历序列是。所以答案为D）。
答案：D）
【例6】设有一个已按各元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查法和二分查法查一个及k相等的元素，比较的次数分别是s和b，在查不成功的情况下，s和b的关系是。（考点9）
A）B）s>b C）s<b D）s≥b 解析：对于顺序查，查不成功时和给定关键字比较的次数为1。二分查查不成功的关键字比较次数为［2n］+1。当n≥2时，显然1>［2n］+1。
答案：B）
【例7】在快速排序过程中，每次划分，将被划分的表（或子表）分成左、右两个子表，考虑这两个子表，下列结论一定正确的是。（考点11）
A）左、右两个子表都已各自排好序
B）左边子表中的元素都不大于右边子表中的元素
C）左边子表的长度小于右边子表的长度