全国计算机二级公共基础知识
一、数据结构与算法
数据结构指的是数据之间的相互关系，即数据的组织形式。
数据结构用来反映一个数据的内部构成，即一个数据由哪些成分构成、以什
么方式构成、呈现什么样的结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映数据之间的逻辑关系，而物理上的数据结构反映数据在计算机内部的存储安排。数据结构是数据存在的形式。
算法是解题的步骤，是指令的有限序列。它们规定了解决某一特定类型
问题的一系列运算，是对解题方案的准确与完整的描述。一个问题的解决方案要以算法为基础。
1.1 概念介绍
◆算法的时间复杂度：
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
算法的工作量=f(n)
其中n是问题的规模。
例如，两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为n3，即计算工作量为n3，也就是时间复杂度为n3。
◆算法的空间复杂度：
算法的空间复杂度一般是指执行这个算法所需要的内存空间。
◆数据的逻辑结构
数据元素相互之间的关系，称为结构。
数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。
◆数据的存储结构
数据的存储结构：是数据的逻辑结构在计算机存储空间中的存放形式。也称数据的物理结构。
各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结构。
数据的顺序存储方式：是将逻辑上相邻的结点存储在物理位置上亦相邻的存储单元里。也就是将所有存储结点相继存入在一个连续相邻的存储区里。
数据的链式存储方式：是在存储每个结点信息的同时，增加一个指针来表示结点间的逻辑关系。该方式不要求逻辑上相邻结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。因此，链式存储结构中的每个结点都由两部分组成：一部分用于存储结点本身的信息，称为数据域；另一部分用于存储该结点的后继结点(或前驱结点)的存储单元地址，称为指针域。指针域可以包含一个或多个指针，这由结点之间的关系所决定。
◆线性结构和非线性结构
如果在一个线性结构中，一个数据元素都没有，则称该数据结构为空数据结构。
线性结构的逻辑特征：在一个非空的数据结构中，除第一个数据元素只有一个后继没有前驱、最后一个数据元素只有一个前驱没有后继外，其他的
每一个数据元素仅有一个前驱和一个后继。线性结构也称为线性表。
注：某个元素直接相邻的前一个元素称为此元素的前驱、直接相邻的后一个元素称为此元素的后继。
非线性结构的逻辑特征：在一个非空的数据结构中，某数据元素可能有多于一个前驱或后继。如树型结构等。
习题：
（一）选择题(单选)
1. 算法的时间复杂度是指（D）
A) 算法的执行时间
B) 算法所处理的数据量
C) 算法程序中的语句或指令条数
D) 算法在执行过程中所需要的基本运算次数
1.2线性表
线性表是由同一类型的数据元素构成的一种线性的数据结构。是一种最基本、最常用的数据结构。线性表常用的存储方式有两种：顺序存储方式和链接存储方式。
线性表的数学定义：
L=(a1,a2,a3,…,a n)
说明：
线性表是具有相同类型的n(n≥0)个数据元素组成的有限序列。
L：为表的名称。
a i(i=1,2, …,n)：为表的元素，也称为线性表中的一个结点。它可以是一个数、一个字符、一个字符串，也可以是一条记录，还可以是复杂的数据对象。a1是a2的前驱、a2是a1的后继，a2是a3的前驱、a3是a2的后继，…，依次类推。
n：为线性表的长度(元素个数)，当n=0时称线性表为空表。
线性表的特点：
在非空的线性表中：存在唯一的一个“第一个元素”(根结点)。存在唯一的一个“最后一个元素”(终端结点)。除第一个元素外，其他的元素均有唯一的前驱。除最后一个元素外，其他的元素均有唯一的后继。
1.3栈和队列
栈和队列本质上也是线性表，只是它们的操作受到了限制。1.3.1栈
栈是限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶(top)，表头称为栈底(bottom)。
栈这种数据结构，类似于子弹夹，底端是封闭的，最后压入的子弹总是最先被弹出，最先压入的子弹只能最后被弹出。
栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后能被删除的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。
1.3.2队列
队列是指只允许在表的一端插入元素、在另一端删除元素的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。
在队列这种数据结构中，最先插入的元素将最先能够被删除，反之最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表。
1.4树和二叉树
1.4.1树
树形结构是数据结构中一种很重要的非线性结构。在树形结构中，所有数据元素之间的关系具有明显的层次特性。树形结构很像自然界中的树，像一棵倒长的树。在现实生活中，能用树形结构表示的例子很多。参见下面的图形：
树形结构的基本特征及基本术语：
以下图为例：
树的根：
在树形结构中，没有前驱的结点只有一个，称为树的根结点，简称为树的根。如：上图中的“R”。
父结点：
在树形结构中，每一个结点(除了树的根结点)只有一个前驱，称为父结点。
如：上图中的“R”是K、P、Q、D的父结点；“N”是X、Y的父结点。
子结点：
在树形结构中，每个结点可以有多个后继，称为该结点的子结点。
如：上图中的K、P、Q、D是“R”的子结点；X、Y是“N”的子结点。
叶子结点：
在树形结构中，没有后继的结点称为叶子结点，也称终端结点。
如：上图中的C、M、F、E、X、G、S、L、Z、A均为叶子结点。
结点的度：
在树形结构中，一个结点所拥有的后继个数称为该结点的度。
如：上图中根结点R的度是4；结点T的度是3；结点P、Q、D、O、Y、W的度都为1。叶子结点的度为0。
树的度：
在树形结构中，所有结点中的最大的度称为树的度。如：上图中树的度为4，因为结点R的度最大，是4。
树的深度：
在树形结构中，树的最大层数称为树的深度(或高度)。如：上图中树的深度是5。说明：树形结构具有明显的层次关系，即树是一种层次结构。在树形结构中一般按如下原则分层：
1) 根结点在第1层。
2) 其余结点的层数等于其父结点的层数加1。
子树：
在树形结中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。如：上图中，结点R有4棵子树，它们分别以K、P、Q、D为根结点；结点P 有1棵子树，其根结点为N；结点T有3棵子树，它们分别以W、Z、A为根结点。
在树形结构中，子树间互不相交，叶子结点没有子树。
森林：
森林是M(M≥0)棵互不相交的树的集合。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
1.4.2二叉树
(1) 二叉树的特点
①非空二叉树只有一个根结点。
②二叉树中的每个结点，最多有两棵子树，分另称为该结点的左子树与右子树。当一个结点即没有左子树也没有右子树时，该结点就是叶子结点。在下面的图中，左面是只有根结点的二叉树，右面是深度为4的二叉树：
(2) 满二叉树与完全二叉树
1) 满二叉树：
满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。
就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2i-1(k≥1)个结点，且深度为k的满二叉树有2k-1(k≥1)个结点。
在下图中分别是深度为2、3、4的满二叉树：
满二叉树中不存在度数为1的结点，每个分支结点均有两棵深度相同的子树，且叶子结点都在最下一层。
2) 完全二叉树：
若一棵二叉树最多只有最下面的两层上结点的度数可以小于2，并且最下一层上的所有结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
在下图的4棵二叉树中，分别是深度为3和4的完全二叉树：
满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
在完全二叉树中，若某个结点没有左子结点，则它一定没有右子结点，即该结点必是叶子结点。
(3) 二叉树的性质
假设定义根结点的层数为1(注意：有些资料中规定根结点的层数为0)。
性质1：在二叉树的第i层上，最多有2i-1(i≥1)个结点。
性质2：深度为k的二叉树最多有2k-1(k≥1)个结点。
性质3：在任意二叉树中，若度为0的结点(即叶子结点)的个数为n0，度为2的结点的个数为n2，则：n0= n2+1
(对于完全二叉树还有如下属性)
性质4：具有n个结点的完全二叉树，其深度为[log2n]+1。注：[log2n]表示取log2n的整数部分。性质5：如果将一棵有n个结点的完全二叉树自顶向下、同一层自左向右连续给结点编号1、2、3、…、n，则对于任意结点i(1≤i≤n)有如下结论：
1) 如果i=1，此结点为根结点，无前驱(即无父结点)；
如果i>1，则该结点的父结点编号为Int(i/2)。也可表示成[i/2]，都
表示取整数。
2) 如果2i>n，则结点i无左子结点，显然也没有右子结点，是叶子结点。
如果2i≤n，则结点i的左子结点是编号为2i的结点。
3) 如果2i+1>n，则结点i无右子结点。
如果2i+1≤n，则结点i的右子结点的编号为2i+1。
(4) 二叉树的遍历
二叉树的遍历就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。
一棵非空二叉树是由根结点、左子树和右子树三部分组成。因此遍历一棵非空二叉树的问题就可以分解为三项“子任条”：
①访问根结点(假设用D表示)。
②遍历左子树(假设用L表示)。
③遍历右子树(假设用R表示)。
在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可分为三种：前序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)。
以下图中的二叉树为例：
前序遍历(DLR)：
首先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时，
仍然先访问子树的根结点，然后遍历其左子树，最后遍历其右子树。即，前序遍历是指访问所有的根结点(包括子树的根结点)都在遍历其左、右子树之前。
前序遍历的操作：
若二叉树为空，则结束反返回。否则：
①访问根结点
②前序遍历左子树
③前序遍历右子树
如，对上图中的二叉树进行前序遍历的结果是：F C A D B E G H P 中序遍历(LDR)：
首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历其左子树，然后访问子树的根结点，最后遍历其右子树。即，中序遍历是指访问所有的根结点(包括子树的根结点)都在遍历其左子树之后、在遍历其右子树之前。
中序遍历的操作：
若二叉树为空，则结束反返回。否则：
①中序遍历左子树
②访问根结点
③中序遍历右子树
如，对上图中的二叉树进行中序遍历的结果是：A C B D F E H G P 后序遍历(LRD)：
首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历其左子树，然后遍历其右子树，最后访问子树的根结点。即，后序遍历是指访问所有的根结点(包括子树的根结点)都在遍历其左、右子树之后。
后序遍历的操作：
若二叉树为空，则结束反返回。否则：
①后序遍历左子树
②后序遍历右子树
③访问根结点
如，对上图中的二叉树进行后序遍历的结果是：A B D C H P G E F
1.5查找
查找又称检索。查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。
1.5.1 顺序查找
顺序查找又称顺序搜索或线性查找。顺序查找一般是指在线性表中查找指定的元素。
顺序查找的基本思想：
在n个结点组成的线性表中，从线性表的一端开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到，即查找成功；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素，即查找失败。
在顺序查找中，查找成功时最多需要比较n次、最少比较1次、平均比较次数约为表长的一半。查找失败时比较n+1次。
顺序查找的时间复杂度为O(n)。
对于无序表(即表中的元素的排列是无序的)和链式存储结构的线性表(有序的和无序的)，只能用顺序查找。
顺序查找的优点：
算法简单而适用范围广。对表中元素的排列次序无要求，既可以是按关键字排列的有序表，也可以是无序表；对表的存储结构也无任何要求，既适用于顺序存储的顺序表，也适用于链接存储的链表。
顺序查找的缺点：
查找效率低，平均查找长度较大。当n很大时不宜采用顺序查找。
1.5.2 二分查找
二分查找又称折半查找。它是一种查找效率较高的查找方法。该方法只适用于顺序存储结构的有序表。通常是指有序表中的元素按值升序排列(非递减有序排列)。二分查找不能用于链式存储结构的线性表。
二分查找的基本思想：参见“C语言程序设计”或“VB程序设计”课件的相应内容动画。
对于长度为n的有序线性表，查找成功时最多需要比较log2(n+1)次、最少比较1次、平均查找长度近似log2n。当查找失败时，比较log2n或log2(n+1)次。
不管二分查找成功与否，其时间复杂度均为O(log2n)。
二分查找的最坏性能和平均性能相当接近。
1.6 排序
排序就是将文件中的记录进行整理，使之按照关键字进行递增或递减的顺序排列起来，成为一个有序序列的过程。在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。
这里的排序算法，都是针对升序排序。
1.6.1 交换排序
交换排序是两两比较待排序记录的关键字，若发现两个记录关键字的次序相反时即进行交换，直到没有反序的记录为止。下面介绍两种常用的交换排序。
(1) 冒泡排序
冒泡排序的基本思想：参见“C语言程序设计”或“VB程序设计”课件的
相应内容动画。
对于长度为n的线性表，在最坏情况下，冒泡排序需要经过n/2遍的扫描，比较次数为n(n-1)/2。
冒泡排序算法的平均时间复杂度为O(n2)，空间复杂度为O(1)。
(2) 快速排序
快速排序的基本思想：
参见下图：
从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，将线性表前面大于T的元素移到后面，结果就把线性表分成了两部分(称为两个子表)，T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，后面子表中的所有元素均不小于T。
如果对分割后的各子表再按上述原则进行分割，并且这种分割过程可以一直做下去，随着对各子表不断地进行分割，划分出的子表会越来越多(一次只能对一个子表进行再分割处理)，直到所有子表中的元素都排好序为止，则此时的线性表就变成了有序表。
对于长度为n的线性表：
在最坏情况下，快速排序比较次数为n(n-1)/2。算法的时间复杂度为O(n2)，空间复杂度为O(n)。
在最好情况下，快速排序算法的时间复杂度为O(nlog2n)，空间复杂度为O(log2n)。
快速排序算法的平均时间复杂度是O(nlog2n)，平均比较次数不大于(n+1)log2n
1.6.2 插入排序
插入排序是每次将一个待排序的记录按其关键字大小，插入到前面已排好的序列中的适当位置，直到全部记录插入为止。
(1) 直接插入排序
快速排序的基本思想：请查看相关资料。
对于长度为n的线性表：
在最坏情况下，直接插入排序比较次数为n(n-1)/2。算法的时间复杂度为O(n2)。
(2) 希尔排序
希尔排序的基本思想：请查看相关资料。
对于长度为n的线性表：
在最坏情况下希尔排序比较次数为O(n1.5)。
1.6.3 选择排序
选择排序的基本思想是：每一遍在n-i+1(i=1,2,…,n-1)个待排序记录中选取关键字最小的记录作为有序序列中第i个记录，直到全部记录排完为止。
(1) 直接选择排序
选择排序的基本思想：参见“C语言程序设计”或“VB程序设计”课件的
相应内容动画。
在最坏情况下，直接选择排序比较次数为n(n-1)/2。
(2) 堆排序
希尔排序的基本思想：请查看相关资料。
在最坏情况下，堆排序比较次数为O(nlog2n)。
习题：
（一）选择题(单选)
1. 下列叙述中正确的是( D )
A）栈是“先进先出”的线性表
B）队列是“先进后出”的线性表
C）循环队列是非线性结构
D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
2.下列关于栈的叙述中正确的是( A )
A) 栈顶元素最先被删除 B) 栈顶元素最后才能被删除
C) 栈底元素永远不能被删除 D) 以上三种说法都不对
3. 下列叙述中正确的是( B )
A) 有一个以上根结点的数据结构不一定是非线性结构
B) 只有一个根结点的数据结构不一定是线性结构
C) 循环链表是非线性结构
D) 双向链表是非线性结构
4.支持子程序调用的数据结构是( A )
A) 栈B) 树C) 队列D) 二叉树
5. 某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是( C )
A）10 B）8 C）6 D）4
提示：在任意二叉树中，若度为0的结点(即叶子结点)的个数为n0，度为2的结点的个数为n2，则：n0= n2+1 即n0(叶子结点数)=5+1=6
6.某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第一层)( D )
A) 3 B) 4 C) 6 D)7
7. 下列排序方法中，最坏情况下比较次数最少的是( D )
A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序
8. 下列叙述中正确的是( A )
A) 对长度为n的有序链表进行查找，最坏的情况下需要的比较次数为n
B) 对长度为n的有序链表进行对分查找，最坏的情况下需要的比较次数为（n/2）
C) 对长度为n的有序链表进行对分查找，最坏的情况下需要的比较次数为(log2n)
D) 对长度为n的有序链表进行对分查找，最坏的情况下需要的比较次数为(nlog2n)
(二) 填空题
1. 假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49,top=30(数组下标)，则栈中具有________个元素。
答案：20
2. 一个队列的初始状态为空。现将元素A、B、C、D、E、F、5、4、3、2、1一次入队，然后再一次退队，则元素退队的顺序为________________________。
答案：A、B、C、D、E、F、5、4、3、2、1
3. 设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一个位置)，尾指针rear=10（指向队尾元素），则该循环队列中共有_____个元素。
答案：15
4. 设二叉树如下：
对该二叉树进行后序遍历的结果为________________________。
答案：E、D、B、G、H、F、C、A
5. 一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为_________。
答案：DEBFCA
6. 有序线性表能进行二分查找的前提是该线性表必须是________存储。
答案：顺序
二、软件工程基础
计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。
软件由两部分组成：一是机器可执行的程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。
软件的分类
软件按功能可以分为：应用软件、系统软件、支撑软件(或工具软件)。
应用软件：是为解决特定领域的应用而开发的软件。
系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件。
支撑软件：是介于系统软件和应用软件之间，协助用户开发软件的工具性软件。
软件生命周期
通常将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。参见下图：
结构化分析方法
结构化分析的常用工具：
数据流图(DFD)：是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。
数据字典(DD)：是结构化分析方法的核心。
判定树
判定表
结构化设计方法
常见的过程设计工具：
图形工具：程序流程图，N-S图，PAD图(问题分析图)，HIPO
表格工具：判定表。
语言工具：PDL(伪码)
软件设计的基本原理
1) 抽象：是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。
2) 模块化：是指把一个待开发的软件分解成若干小的简单的部分。如高级语言中的过程、函数、子程序等。每个模块可以完成一个特定的子功能，各个模块可以按一定的方法组装起来成为一个整体，从而实现整个系统的功能。
3) 信息隐蔽：是指在一个模块内包含的信息(过程或数据)，对于不需要这些信息的其他模块来说是不能访问的。
4) 模块独立性：是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。
内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。
内聚性是信息隐蔽和局部化概念的自然扩展。一个模块的内聚性越强则该模块的模块独立性越强。作为软件结构设计的设计原则，要求每一个模块的内部都具有很强的内聚性，它的各个组成部分彼此都密切相关。
耦合性：耦合性是模块间相互连接的紧密程度的度量。
一个模块与其他模块的耦合性越强则该模块的模块独立性越弱。原则上讲，模块化设计总是希望模块间的耦合表现为非直接耦合方式。但是，由于问题所固
目录 二级公共基础知识考纲 (1) 第一章数据结构与算法 (2) 第二章程序设计基础 (19) 第三章软件工程基础 (23) 第四章数据库设计基础 (32) 全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、程序设计基础 1.程序设计方法与风格。 2.结构化程序设计。 3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工程基础 1.软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。 2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3.结构化设计方法，总体设计与详细设计。 4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5.程序的调试，静态调试与动态调试。 四、数据库设计基础 1.数据库的基本概念：数据库，数据库管理系统，数据库系统。 2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式 公共基础的考试方式为笔试，与C语言（V isualBASIC、V isual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。 公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 （一）算法 1．算法的基本概念 算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。 1）算法的基本特征 （1）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。
公共基础知识考试重点 公共基础知识考试重点 考情综述： 重点章节： 重点知识举例： 行政主体 一般认为，在我国，行政主体可以分为两大类：行政机关和法律、法规、规章授权的组织(又称为“被授权的组织”)。 2.法律、法规、规章授权的组织。是指法律、行政法规、地方性法规及规章授予行使行政权力的组织。 提示： 考情综述： 重点章节： 唯物辩证法、真理、社会存在与社会意识 重点知识举例： 质量互变规律 (1)质、量、度及其相互关系 任何事物都具有质和量这两种规定性，都是质和量的统一体。 质是一事物区别于其它事物的内在规定性，是与事物直接同一的。 量是事物存在和发展的数量、规模、大小、程度等方面的外在规定性。量和事物是不可分离的，但量与事物不是直接同一的。
度是质与量的统一，度是事物保持自己质的量的范围、幅度和限度。事物的度都有其关节点。所谓关节点指的是事物度的上限和下 限的两个极限。任何事物的度，都有两个关节点，要把握事物的度，必须找到它的关节点。 (2)量变、质变和质量互变规律 量变和质变，是事物变化发展的两种基本状态。量变是事物存在和发展的数量上的增减变化。质变是事物根本性质的变化。量变和 质变是相互区别，又相互联系、相互转化的，量变是质变的前提和 基础，质变是量变的必然结果。 同时，量变和质变是互相渗透的：①量变中渗透质变，在总的量变过程中包含着部分质变。②质变中渗透量变，这是指质变过程中 包含着新质在量上的扩张。 提示： 对基本哲学原理的理解力求透彻，达到能运用哲学知识解释生活中的一切现象的目的。学习过程中尽可能的联系实际，找寻“生活 中的哲学”。 三、毛泽东思想概论 考情综述： 毛泽东思想概论这部分内容，基础理论知识是考查的重点。同时毛泽东个人的著名作品也是常考点。 重点章节： 新民主主义革命的总路线和基本纲领、毛泽东思想活的灵魂 重点知识举例： 群众路线 3.群众路线的内涵是：一切为了群众、一切依靠群众;从群众中来、到群众中去是我党的根本领导方法和工作方法。
公共基础知识常识题及答案 常识部分涵盖政治、经济、法律、公共管理、人文、科技等方面、考察应试者在这些方面应知应会的基本知识以及运用基本知识分析判断的基本能力。以下是由整理关于公共基础知识常识题的内容，希望大家喜欢! 公共基础知识常识题(一) 1、自从核战略武器出现以后，各国都加紧研制，到目前为止已有好几个国家拥有了核武器。但是几乎所有拥有核武器的国家都签订了一系列禁核条约，这主要是因为：(C) A、无核国家舆论的压力 B、这些国家爱好和平 C、核武器具有毁灭性，一损俱损 D、经济实力不能支持核军备的扩张 2、用玻璃导管向澄清的石灰水中吹气，会出现什么现象?(A) A、石灰水变得浑浊 B、没有反应 C、石灰水沸腾 D、石灰水呈现淡紫色 3、由于外力的变化，物体的加速度逐渐减小，在其加速度变为零之前：(D) A、物体速度逐渐变慢，接近停止 B、物体保持匀速运动 C、物体速度匀速加快 D、物体速度越来越快，但变化速度减慢 4、迄今为止，科学家所发现的最远的天体距离我们一百多亿光
年，他们是如何观测到这么远的天体的呢?(C) A、使用高倍望远镜 B、向太空发射激光信号，然后通过计算其反射回来的时间来估算 C、使用特殊的光学望远镜，通过分析到达地球光线的衰变估算出来的 D、宇航员说的 5、在行政管理中有一条很重要的原则叫做回避原则，父子、夫妻等凡是具有直系或较近的旁系亲属关系的不得在同一地区或机关工作，涉及亲属的事件处理要由他人代为执行，实行这一原则的原因不可能包括：(D) A、为了保证公平、公正 B、为了防止家庭腐败 C、为了行政活动能够顺利进行 D、为了行政人员专心于工作 6、马尔萨斯的人口理论指出：人类财富是按算术级数增长的，而人口则是按几何级数增长的，地球会因发生人口爆炸而灭亡。然而，一百多年过去了，并没有发生什么人口爆炸，这主要是因为：(D) A、灾难、瘟疫、战争减缓了人口的增长 B、马尔萨斯的理论是错误的 C、时间还不够长 D、人口增长具有内在约束机制，而且科技的进步创造了大量的社会财富 7、国民生产总值是衡量一国经济实力的重要指标，而我国的国
公共基础训练题---行政管理公共基础知识[含答案] 一、单项选择题 1. 政府职能的发展变化，在很大程度上取决于 ( ) a. 社会制度的变化 b. 领导集团的变更 c. 社会经济形态的发展变化 d. 人民群众的一致要求 2. 中国目前正进行的行政管理体制和机构改革能否成功的关键是 ( ) a. 减少机构和部门的数量 b. 裁减人员的数量 c. 政府职能的转变 d. 行政效率的提高 分享一点个人的经验给大家（经验分享部分看过的人不用看了）。我的笔试成绩一直都是非常好的，不管是行测还是申论，每次都是岗位第一。其实很多人不是真的不会做，90%的人都是时间不够用，要是给足够的时间，估计很多人能够做出大部分的题。公务员考试这种选人的方式第一就是考解决问题的能力，第二就是考思维，第三考决策力（包括轻重缓急的决策）。非常多的人输就输在时间上，我是特别注重效率的。第一，复习过程中绝对的高效率，各种资料习题都要涉及多遍；第二，答题高效率，包括读题速度和答题速度都高效。我复习过程中，阅读和背诵的能力非常强，读一份一万字的资料，一般人可能要二十分钟，我只需要两分钟左右，读的次数多，记住自然快很多。包括做题也一样，读题和读材料的速度也很快，一般一份试卷，读题的时间一般人可能要花掉二十几分钟，我统计过，我最多不超过3分钟，这样就比别人多出20几分钟，这在考试中是非常不得了的。论坛有个帖子专门介绍速读的，叫做“得速读者得行测”，我就是看了这个才接触了速读，也因为速读，才获得了笔试的好成绩。其实，不只是行测，速读对申论的帮助更大，特别是那些密密麻麻的资料，看见都让人晕倒。学了速读之后，感觉有再多的书都不怕了。而且，速读对思维和材料组织的能力都大有提高，个人总结，拥有这个技能，基本上成功一半，剩下的就是靠自己学多少的问题了。平时要多训练自己一眼看多个字的习惯，慢慢的加快速度，尽可能的培养自己这样的习惯。当然，有经济条件的同学，千万不要吝啬，花点小钱在自己的未来上是最值得的，多少年来耗了大量时间和精力，现在既然势在必得，就不要在乎这一刻。建议有条件的同学到这里用这个软件训练速读，大概30个小时就能练出比较厉害的快速阅读的能力，这是给我帮助非常大的一个网站，极力的推荐给大家（给做了超链接，按住键盘左下角Ctrl 键，然后鼠标左键点击本行文字）。另外，还有一个不得不说的工具，一款公务员考试软件，对于我成功它绝对是功不可没的，超猛的一款软件，集成最新题库、大纲资料、模拟、分析、动态等等各种超赞的功能，性价比超高，是绝不可缺的一款必备工具，结合上速读的能力，如虎添翼，让整个备考过程效率倍增。到我推荐的这里搜索“公务员”就可以找到适合自己的科目（也给做了超链接，按住键盘左下角Ctrl键，然后鼠标左键点击本行文字）。最后，记得好好学习，只有自己帮助自己。祝愿每一位有梦想的同学早日实现自己的理想！帮大家祈福！加油！ 3. 下面（）是政府办事机构。 a. 中央办公厅 b. 县工商局 c. 乡工商所 d. 县驻京办事处 4. 我国政府机构与立法机构的关系是 c( )
法理 ●法的概念：特定物质生活条件决定的统治阶级意志的体现，由国家制定认可，由国家强制力保证实施的行为规范的综合 ●法的特征:1、调整人的行为或社会关系2、国家制定或认可、并具有普遍约束力3、以国家强制力保护实施4、规定权利和义务 ●法的本质：统治阶级意志的表现 ●法的规范作用：指引、评价、预测、教育和强制 法的作用 ●法的社会作用：维护统治阶级的阶级统治；执行社会公共事务。 ●法与经济基础的关系：经济基础决定法，法又反作用于经济基础。 ●法与生产力的关系：生产力发展的水平直接影响法的发展水平。法律离开社会生产力的发展，既无存在的可能，也无存在的必要。 ●法对市场经济宏观调控的作用：引导；促进；保障；制约。 ●法对微观经济的作用：确认经济活动主体的法律地位，调节经济活动中的各种关系，解决经济活动中哦的各种纠纷，维持正常的经济秩序 ●法与政治的关系：法受政治制约（政治关系发展、整体改革、政治活动的内容），法服务于政治（调节阶级间、阶级内关系，维护社会关系、社会秩序；打击制裁违法犯罪，调整公共事务关系，维护公共秩序） ●法与党的政策的关系： 相同点（内容实质方面联系）：阶级本质、指导思想、基本原则、经济基础、社会目标等 区别：意志属性、规范形式、调整范围（不尽同）、实施方式、稳定性程序化程度 ●法与党的政策相互作用： 一、法的制定：1、政策是立法的依据和指导思想 2、发将政策转为形式合理效力普遍的行为规范 二．发的实施：1、政策变法，使正统，又反之约束政治活动 2、法的实施借助政策作用 ●社会主义民主与法制是相互依存、相互作用、紧密联系、不可分割的。 ●民主是法制的前提和基础，因为：民主是法制产生的依据、力量源泉，决定了法制的性质和内容 ●法的渊源的专有含义：法律规范的形式上的来源和其外在表现形式 ●法律效力等级为：宪法－法律－行政法规－地方性法规－规章（部门和地方政府）。 ●宪法：根本大法，最高法律效力 ●法律：由全国人大或其常务委员会制定、颁布；全国范围内生效；规范性法律文件 ●行政法规：国务院为领导和管理国家各项行政事务根据为宪法、法律 国务院发布的决定、命令，凡具有规范性的也属于发的渊源 ●地方性法规：地方人大及常委会制定（省、自治区、直辖市、省政府所在市、国批的较大市），适用本地方。 ●规章：1、部门规章：指由国务院各部委+中银+审计署+具有行政管理职能的直属机构；依据为：宪法、法律、国务院的行政法规、决定、命令 2、地方规章：政府制定（省、自治区、直辖市、省自治区政府所在市、经济特区所在市、国的较大市）依据：宪法、法律、行政法规 ●自治条例和单行条例：民族自治地方人大制定，区域内生效 ●特别行政区法：在特别行政区内实行的制度由全国人大以法律规定。 ●国际条约：与民法规定不同的，适用国际条约，但声明保留的条款除外。 ●规定是规范性文件，不属于法律范畴，效力低于法律。 ●广义的法律包括法律、行政法规、地方性法规和规章。 ●法律关系三要素（法律规范在调整人们行为过程中形成的权利义务关系）：主体（法律关系的参加者）、客体（权利义务指向的对象：物、精神产品、人身、行为）、内容（权利义务） ●权利能力：能够才加一定的法律关系，依法享有权利承担义务的主体能力； 行为能力：法律关系的主体能够通过自己的行为实际取得权利和承担义务的能力 行为能力必须以权利能力为前提，无权利能力就无法谈行为能力。 ●法人的权利能力：生于成立，终于解体 公民的权利能力：始于出生，终于死亡 ●自然人有权利能力，未必有行为能力，根据年龄和精神状况，分为：完全、限制、无行为能力人
公共基础知识政治常识 1、不断完善党的执政方式，就是要坚持把人民意志和党的主张通过法定程序上升为国家意志。 ①坚持把人民意志和党的主张通过法定程序上升为国家意志，是党依法执政的重要表现。 ②依法执政不仅强调党要领导立法，还必须强调党要带头守法，保证执法，实施依法治国。 ③依法执政是中国共产党执政的基本方式，依法执政有利于保证党始终发挥总揽全局、协调各方的领导核心作用。不断完善党的执政方式，还需要坚持科学执政、民主执政。 附：运用政治学知识说明中国共产党领导、支持和保证人民当家做主的具体形式表现在哪些方面。 ①党领导人民通过人民代表大会制度掌握国家权力，以此维护人民的根本利益，保障人民当家做主; ②领导人民依照宪法和法律规定，管理国家事务、经济和文化事业，管理社会事务; ③领导人民实行基层民主，由群众依法办理自己的事情; ④领导人民严格贯彻公民在法律面前——律平等的原则，使公民享有法律上、事实上的广泛的自由和权利，尊重和保障人权，维护公平与正义。 2、人民政协是统一战线组织，它的作用是促进祖国统一。 (1)观点认为人民政协是统一战线组织，它的作用是促进祖国统一，有一定的合理性。但把它的作用仅归结为这一点是片面的 (2)人民政协是中国共产党领导的多党合作的重要机构，履行政治协商、民主监督和参政议政的职能为国家民主决策、科学决策发挥着重要作用 (3)人民政协是我国政治生活中发扬社会主义民主的重要形式。它围绕团结与民主两大主题，团结联合各党派各族群众，为党和政府广集民智，反映社情民意，对构建社会主义和谐社会做出重要贡献。 3、辨题：“开门立法”，就是要使广大人民群众直接行使立法权，确保了公民在法律面前一律平等。
1.1 算法 考点1 算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括“与”、“或”、“非”等运算； ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法 计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2)归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
公共基础知识文学常识The final revision was on November 23, 2020
1、《诗经》 《诗经》是我国第一部诗歌总集，共收入自西周初期（公元前十一世纪）至春秋中叶（公元前六世纪）约五百余年间的诗歌三百零五篇（《小雅》中另有六篇“笙诗”，有目无辞，不计在内），最初称《诗》，汉代儒者奉为经典，乃称《诗经》。 《诗经》分为《风》、《雅》、《颂》三部分。 2、《尚书》 《尚书》意为“上古之书”，是中国上古历史文件和部分追述古代事迹作品的汇编。春秋战国时称《书》，到了汉代，才改称《尚书》。儒家尊之为经典，故又称《书经》。 《尚书》包括虞、夏、商、周书。《虞书》、《夏书》非虞夏时所作，是后世儒家根据古代传闻编写的假托之作。 3、《春秋》 《春秋》是我国编年体史书之祖，它以鲁国十二公为序，起自鲁隐公元年（前722），迄于鲁哀公十四年（前48），记载了二百四十二年间的历史。它是纲目式的记载，文句极简短，几乎没有描写的成分。但它的语言表达，具有谨严精炼的特点，反映了文字技巧的进步。 4、《左传》
《左传》原名《左氏春秋》，后人将它配合《春秋》作为解经之书，称《春秋左氏传》，简称《左传》。它与《春秋公羊传》、《春秋谷梁传》合称“春秋三传”。 5、《战国策》 《战国策》是汇编而成的历史着作，作者不明。其中所包含的资料，主要出于战国时代，包括策士的着作和史臣的记载，汇集成书，当在秦统一以后。原来的书名不确定，西汉刘向考订整理后，定名为《战国策》。总共三十三篇，按国别记述，以策士的游说活动为中心，反映出这一时期各国政治、外交的情状。全书没有系统完整的体例，都是相互独立的单篇 6、孔丘与《论语》 孔丘（前551~前479）字仲尼，世称孔子，鲁国陬邑（今山东曲阜）人。《论语》是早期语录体散文，语言基本上是口语，明白易懂。 7、墨翟与《墨子》 墨翟，主张“兼爱”“非攻”“尚贤”。《墨子》为墨翟及其弟子、后学所着，是墨家学派的着作总汇，汉代有七十一篇，现存五十三篇。 8.孟轲与《孟子》 孟轲（约前372~约前289），邹（今山东邹县）人，生活于战国前期。《孟子》共七篇，记述孟轲的言行。
科技常识练习题 1. （单选题）以下属于低碳经济的做法是（）。 A. 秸秆粉碎沤沼一沼渣肥田一反哺农田作物 B. 发电厂对煤炭燃烧后产生的气体进行脱硫 C. 许多废弃物不填埋或焚烧，而是回收利用 D. 采用空气源热能或者地下水循环调节室温 2. （单选题）低碳经济的起点是（）。 A. 技术创新 B. 统计碳源和碳足迹 C. 制度创新 D. 发展观的改变 3. （多选题）下列符合低碳经济要求的是（）。 A. 无纸化办公 B. 大力发展公共交通 C. 减少使用一次性用品 D. 步行或骑自行车上班 E. 开私家车上班 4. （多选题）下列关于低碳经济的说法，正确的是（）。 A. 遵循可持续发展理念 B. 减少煤炭石油等消耗 C. 寻找新的可利用能源 D. 增加使用天然气能源 5. （单选题）下列生活方式中不符合低碳经济要求的是（）。 A. 建筑中使用中空玻璃 B. 电冰箱中保持较多的霜 C. 步行或骑自行车上班 D. 使用太阳能热水器 6. （单选题）下列关于PM2.5的说法不准确的是（）。 A. PM2.5是指环境空气中空气动力学当量直径小于或等于2.5微米的颗粒物 B. PM2.5源于一次颗粒物排放，也源于二次颗粒物排放 C. 当前，以臭氧(O3)、PM2.5和酸雨为特征的区域性复合型大气污染日益突出 D. 我国PM2.5监测的时间表即将正式出台 7. （单选题）霾和雾的区别在于（）。 A. 水汽含量的大小 B. 气象现象的颜色 C. 行程消散的时间 D. 细小颗粒物的成分 8. （多选题）下列关于“雾霾”说确的是（）。 A. 雾霾天气少开窗 B. 雾和霾没有区别
C. 机动车尾气的排放是雾霾天气形成的原因之一 D. 二氧化硫、氮氧化物和可吸人颗粒物这三项是雾霾主要组成 9.（单选题）2011年11月，环保部发布了《环境空气PM10和PM2.5的测定重量法》，由于提出了PM2.5的概念，引起了人们的广泛关注。下列关于PM2.5的说法有 误的一项是（）。 A. PM2.5是指大气中直径大于或等于2.5微米的颗粒物 B. PM2.5也称“可入肺颗粒物” C. 它的直径还不到人的头发粗细的1/20 D. PM2.5在地球大气成分中含量很少，但是它对空气质量和能见度等有重要的影响 10. （单选题）下列关于雾霾的说法，不正确的是（）。 A. 雾霾是“雾”和“霾”的组合词 B. 雾霾常出现在城市地区 C. 雾霾是特定气候条件与人类活动相互作用的结果 D. 雾霾即是PM2.5 11. （单选题）下列对世界科技革命的说法不成立的是（）。 A. 15世纪以来，世界科技大致发生了五次革命 B. 世界科技革命包括两次科学革命和三次技术革命 C. 第五次科技革命包括电子技术革命和信息技术革命两个阶段 D. 目前，信息技术革命尚未结束 12. （单选题）下列选项与第三次科技革命密切相关的是（） A. 燃机车 B. 网络购物 C. 按揭消费 D. 潮汐发电 13. （单选题）在人类社会的发展史上，经历了三次科技革命，其标志为（）。 A. 蒸汽机的发明、纺织机的发明、电子计算机的发明 B. 蒸汽机的发明、电力的发明、电子计算机的发明 C. 蒸汽机的发明、电力的发明、电子计算机的发明和原子能的发明和使用 D. 蒸汽机的发明、纺织机的发明、原子能的发明和使用 14. （单选题）在第二次科技革命中，导致汽车工业和石油工业兴起的发明是 （）。 A. 蒸汽机 B. 电动机 C. 汽轮机 D. 燃机 15. （单选题）过去5个世纪发生了5次科技革命。这些革命出现的顺序是（）。
全国计算机等级考试二级公共基础知识复习资料 全国计算机等级考试二级公共基础知识复习资料 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
2016年事业单位考试《公共基础知识》考点及复习建议 《公共基础知识》主要测试应试人员对公共基础知识的掌握程度和运用知识分析问题、解决实际问题的能力，以及履行公务员义务的必备能力和素质。考试内容主要包括：政治、经济、法律、管理、科技、人文、历史、公文写作、道德、国情市情、时事常识以及事业单位人事管理相关制度等方面的知识。主要为客观性 试题。题型主要为单项选择题、多项选择题、判断题、写作等。 政治。主要测查应试者对中国特色社会主义理论体系形成、发展过程及主要内容的理解和运用。主要包括：了解中国共产党的历史和党的建设理论；正确认识毛泽东思想、邓小平理论、三个代表”重要思想和科学发展观的历史地位；了解中国共产党建立社会主义的斗争及中国共产党探索中国特色社会主义道路的历程;掌握中国特色社会主义理论体系的形成、发展及特色；学习理解党的十八大和十八届二中、三中、四中全会等重要会议精神、党和国家新时期的方针政策以及时事政治等。 【重点】马列主义基础理论、中国特色社会主义理论、党和国家新时期的方针政策以及时事政治等。 【复习建议】政治部分是考试中的绝对重点，必考，占分最高，这一部分要重点练习和记忆，特别是中特、当代中国政府与政治部分，是重点，同时有一定难度，这部分的题目要多做几遍，把握命题的规律。 经济。主要测查应试者对市场经济基本原理、社会主义市场经济体系等内容的理解和运用。主要包括：了解市场经济、社会主义市场经济的含义及特征；正确认识社会主义市场经济的政府宏观调控体系、收入分配制度和社会保障制度认识了解社会主义市场经济国家的对外经济关系以及我国的对外开放格局、经济全球化与我国对外开放的关系。 【重点】经济学基础理论、社会主义市场经济基础知识以及财务管理的基础知识。 【复习建议】经济常识在近几年分值逐渐加大，与日常生活结合更加紧密，在本题库中已经把尽可能多的题型列出，做完即可保证高分。 法律。主要测查应试者对法学的基本理论、我国法律基础知识的了解以及法律在工作生活中的实际运用能力。主要包括正确认识我国国家性质、经济制度、国家结构形式、公民的基本权利和义务以及国家机构；熟悉刑法、行政法、民法、经济法、商法等主要实体法的基本概念和基本原则，理解刑事法律关系、行政法律关系、民事法律关系、经济领域的相关法律关系等；了解刑事诉讼法、行政诉讼法、民事诉讼法、仲裁法等主要程序法及其实际运用。 【重点】宪法、刑法、行政法、民法、经济法
第一章数据结构与算法 算法 1、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 2、算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的,此顺序将在有限的次数下终止。特征包括：（1）可行性;（2)确定性(3）有穷性（4）拥有足够的情报。 ３、算法的基本要素:一是对数据对象的运算和操作；二是算法的控制结构。 ４、指令系统:一个计算机系统能执行的所有指令的集合。 5、基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 ６、算法的控制结构：顺序结构、选择结构、循环结构。 7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 8、算法复杂度:算法时间复杂度和算法空间复杂度。 9、算法时间复杂度是指执行算法所需要的计算工作量。 10、算法空间复杂度是指执行这个算法所需要的内存空间。 数据结构的基本基本概念 1、数据结构研究的三个方面: (1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构; （2）在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构;（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。 ２、数据的逻辑结构包含:(1）表示数据元素的信息;(2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。 ３、线性结构条件：(1）有且只有一个根结点;(２）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 线性表及其顺序存储结构 １、线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 2、非空线性表的结构特征: (1）且只有一个根结点ａ1，它无前件；(2)有且只有一个终端结点an，它无后件; （3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当ｎ=0时，称为空表。 3、线性表的顺序存储结构具有以下两个基本特点：(１）线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 4、顺序表的运算:插入、删除。 栈和队列 1、栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO)或“后进先出”(LＩFO）组织数据,栈具有记忆作用。用ｔop表示栈顶位置，用ｂottoｍ 表示栈底。 2、栈的基本运算：(1）插入元素称为入栈运算；（2)删除元素称为退栈运算;（３）读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 3、队列是指允许在一端（队尾）进入插入,而在另一端(队头）进行删除的线性表。Ｒear指针指向队尾,frｏnt 指针指向队头。 4、队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。 线性链表
2020年公务员遴选考试公共基础知识要点精髓整理 总结（共220个） 1. 行政行为成立的要件有主体要件、内容要件、权限要件 2. 合法有效的行政执法行为具有确定力、约束力、执行力 3. 人民法院对犯罪分子的制裁包括判处徒刑、没收财产、剥夺政治权利 4. 公民在请求国家赔偿时，可以直接向赔偿义务机关提出；在行政诉讼中一并提出；在行政复议中一并提出 5. 物权的客体是物；物权和权利主体是特定的；物权是一种排他的权利反映了物权的法律特征 6. 《民法通则》根据公民的年龄、精神状态把公民的民事行为能力分为三种。 7. 工作报告的标题应包括的内容是发文机关、针对时间、内容、文种 8. 区别正文各层次的标注方法，常见的有用数量词标示、用小标题标示、用惯用语标法 9. 应在调查报告正文的开头部分撰写的有概述调查对象的情况，给读者以概貌的认识；告诉读者写作背景的有关情况；给读者展示前景，发出号召；以议论、提问的方式揭示全文主题 10. 条例的制发权属于国务院、党的中央组织 11. “静者，动之静也”的观点是认为静止是运动的特殊状态 12. 运动的主体是物质 13. 质变是事物根本性质的变化 14. 马克思主义哲学认为否定是辩证的否定。 15. “离开革命实践的理论是空洞的理论，而不以革命理论为指南的实践是盲目
的实践。”这段话强调的是要坚持理论和实践相结合的原则 16. 历史唯物主义的任务在于揭示社会发展的一般规律 17. 社会进步的内在根据是社会基本矛盾运动 18. 在社会主义建设新时期，中国共产党完成指导思想拨乱反正的标志是党的十一届六中全会通过《关于建国以来党的若干历史问题的决议》 19. 邓小平对党的思想路线的贡献在于强调解放思想 20. 党的十四大把社会主义初级阶段理论作为社会主义发展阶段问题 进行了新的论述，成为邓小平理论的重要基础。 21. 我国企业改革的目标是建立现代企业制度 22. 建立社会主义市场经济体制，就是要使市场在国家宏观调控下对生产力的配置起基础性作用 23. 当社会总需求大于社会总供给时，一般不宜采取松的货币政策 24. 劳动力市场是劳动力资源的交易和分配的场所 25. 根据现代企业制度的基本特征，企业拥有包括国家在内的出资者投资形成资产的全部法人财产权 26. 社会主义经济在资源的配置方面，最为有效的体制是社会主义市场经济体制 27. 社会保障体系的核心内容是：社会保险。 28. “两手抓，两手都要硬”是社会主义精神文明建设的战略方针 29. 社会主义要消灭贫穷,这是由社会主义的本质决定的。 30. 我国政府职能的实施主体是各级人民政府。 31. 国家公务员享有的权利提出申诉和控告 32. 公务员若对降职处理不服,申请复议或申诉必须在接到降职决定之日起30 日之内
公务员考试公共基础知识——文学常识 一、我国古典文学之最 1、《诗经》是我国最早的一部诗歌总集。 2、《史记》是我国第一部纪传体通史，作者是西汉著名史学家、文学家、思想家司马迁。 3、《资治通鉴》是我国第一部编年体史书，作者是北宋史学家司马光。 4、《离骚》是我国第一首优秀的长篇抒情诗，作者是战国时楚国的伟大诗人屈原。 5、《论语》是我国第一部语录体散文，作者是孔丘的弟子及再传弟子。 6、《春秋》是我国第一部私人编撰的史书，作者是春秋时代著名的思想家、教育家孔丘。 7、《三国演义》是我国第一部优秀的长篇历史小说，作者是明代著名的通俗小说家罗贯中。 8、《水浒传》是我国第一部优秀的描写农民革命斗争的小说，作者是元末明初著名的小说家施耐庵。 9、《西游记》是我国第一部长篇神话小说，作者是明代小说家吴承恩。 10、《梦溪笔谈》是我国第一部用笔记文体写成的综合性学术专著，作者是北宋科学家、政治家沈括。 11、《聊斋志异》是我国第一部优秀的文言短篇小说集，作者是清代著名小说家蒲松龄。 12、《儒林外史》是我国第一部优秀的长篇讽刺小说，作者是清代伟大的小说家吴敬梓。 13、《红楼梦》是我国艺术成就最高的早期白话小说，作者是清代伟大的小说家曹雪芹。 14、屈原是我国第一个伟大的诗人，作品收在《楚辞》里。 15、李清照是我国第一个女词人，作品收在《李清照集》里。 16、李白是盛唐时期最伟大的浪漫主义诗人，作品收在《李太白全集》里。 17杜甫是盛唐时期最伟大的现实主义诗人，作品收在《杜工部集》里。 18、白居易是中唐时期最伟大的现实主义诗人，作品收在《白氏长庆集》里。 二、作家作品并称 1、文章西汉两司马：司马相如、司马迁。 2、史界两司马：司马迁、司马光。 3、三曹：曹操、曹丕、曹植。 4、初唐四杰：王勃、杨炯、卢照邻、骆宾王。 5、唐宋八大家：韩愈、柳宗元、欧阳修、苏洵、苏轼、苏辙、王安石、曾巩。 6、三苏：苏洵、苏轼、苏辙。 7、元曲四大家：关汉卿、郑光祖、白朴、马致远。 8、欧美三大短篇小说家：莫泊桑、契诃夫、欧·亨利。 9、风骚：《诗经》和《楚辞》。 10、乐府双璧：《木兰诗》和《孔雀东南飞》。 11、三吏三别：《石壕吏》、《潼关吏》、《新安吏》和《新婚别》、《垂老别》、《无家别》。 12、中国小说四大名著：《三国演义》、《水浒传》、《西游记》、《红楼梦》。 13、莎士比亚四大悲剧：《哈姆雷特》、《李尔王》、《麦克白》、《奥赛罗》。 14、六艺：六种经书，即《诗》、《书》、《礼》、《易》、《乐》、《春秋》；六种技能：即礼、乐、射、御、书、数。 15、世界名著中四大吝啬鬼：《欧也妮·葛朗台》中的葛朗台、《威尼斯商人》中的夏洛克、《死魂灵》中的泼留希金、《悭吝人》中的阿巴贡。
公共基础知识复习资料：物理学常识 下面是事业单位考试网为考生整理的物理学常识，公共基础知识考试内容广泛，考生们一定要注意平时的知识积累。 1.哥白尼的日心地动说：是波兰天文学家哥白尼在《天体运行论》中阐述的观点。他认为，太阳是宇宙的中心，所有行星围绕太阳旋转，地球也是一颗普通的行星。指出，太阳的东升西落是地球自转的表现;天球上恒星位置每年所发生的周期性变化是地球绕太阳公转的结果。它从根本上纠正了自古流传并为基督教会所支持的地心和地静说的错误，动摇了教会的权威。 2.自由落体定律：伽利略通过实验发现：物体从静止开始的自由下落是一种匀加速运动，物体下落的速度与其经历的时间成正比，下落的距离与其经历的时间的平方成正比。即自由落体定律。根据这个定律，两轻重不同的物体从同一高度下落，应同时到达地面，物体下落速度与其质量无关，从而彻底批判了亚里士多德的错误观点。 3.惯性运动：伽利略通过实验得出结论，物体在没有外力作用的情况下保持原有运动状态，物体具有维持原有运动状态的特性，即惯性运动。也就是说，亚里士多德认为必须有外力才能维持物体运动的观点是站不住脚的。 4.开普勒第一定律：是德国天文学家开普勒通过观测发现的行星运动三条定律之一，亦称行星轨道定律。这一定律指出：行星运行的轨道不是正圆形而是椭圆形，它们围绕各自椭圆轨道的一个焦点运行，而这些焦点又都重合在一起，那就是太阳之所在。 5.开普勒第二定律：是德国天文学家开普勒通过观测发现的行星运动三条定律之一，亦称行星运动面积定律。它指出：在相等时间内行星与太阳联线所扫过的面积相等。 6.开普勒第三定律：是德国天文学家开普勒通过观测发现的行星运动三条定律之一，亦称行星运动周期定律。它指出：任何两颗行星公转周期的平方与它们轨道长半径的立方成正比。 7.万有引力：是牛顿揭示出来的力学定律。任何两个物体之间的引力与它们的质量的乘机成正比，与两物间距离的平方成反比。 8.运动第一定律：是牛顿最终揭示出来的力学基本定律。又称惯性定律。它指出：如果没有外力的作用，任何物体将保持其静止状态或匀速直线运动状态。即力是使物体的运动状态发生变化的原因。 9.运动第二定律：是牛顿最终揭示出来的力学基本定律。指出：碰撞运动中作用于一物体的 外力与它的运动量的变化成正比。 10.运动第三定律：是牛顿最终揭示出来的力学基本定律。指出：当物体A施力于物体B时，
二级公共基础知识分类模拟题43 单项选择题 1、下列叙述中正确的是______。 A．所谓算法就是计算方法 B．程序可以作为算法的一种描述方法 C．算法设计只需考虑得到计算结果 D．算法设计可以忽略算法的运算时间 2、下列叙述中正确的是______。 A．算法的复杂度包括时间复杂度与空间复杂度 B．算法的复杂度是指算法控制结构的复杂程度 C．算法的复杂度是指算法程序中指令的数量 D．算法的复杂度是指算法所处理的数据量 3、下列叙述中正确的是______。 A．算法的时间复杂度与计算机的运行速度有关 B．算法的时间复杂度与运行算法时特定的输入有关 C．算法的时间复杂度与算法程序中的语句条数成正比 D．算法的时间复杂度与算法程序编制者的水平有关 4、下列叙述中正确的是______。 A．非线性结构可以为空 B．只有一个根结点和一个叶子结点的必定是线性结构 C．只有一个根结点的必定是线性结构或二叉树 D．没有根结点的一定是非线性结构 5、设数据结构B=(D，R)，其中 D={a,b,c,d,e,f} R={(f,a),(d,b),(e,d),(c,e),(a,c)} 该数据结构为______。 A．线性结构 B．循环队列 C．循环链表 D．非线性结构 6、下列叙述中正确的是______。 A．矩阵是非线性结构 B．数组是长度固定的线性表 C．对线性表只能作插入与删除运算 D．线性表中各元素的数据类型可以不同 7、在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。 A．不同，但元素的存储顺序与逻辑顺序一致 B．不同，且其元素的存储顺序可以与逻辑顺序不一致 C．相同，元素的存储顺序与逻辑顺序一致 D．相同，但其元素的存储顺序可以与逻辑顺序不一致 8、下列叙述中正确的是______。 A．能采用顺序存储的必定是线性结构 B．所有的线性结构都可以采用顺序存储结构 C．具有两个以上指针的链表必定是非线性结构 D．循环队列是队列的链式存储结构 9、下列叙述中正确的是______。 A．在栈中，栈顶指针的动态变化决定栈中元素的个数
2020年公务员考试公共基础知识常识题库 及答案（一） 1.我国现存最早的纪传体史书是( ) A.《史记》 B.《春秋》 C.《论语》 D.《汉书》 2.第一部诗歌总集是( ) A.《诗经》 B.《汉书》 C.《诗歌总集》 D.《尔雅》 3.以下不是医学著作的是( ) A.《神农本草经》 B.《齐民要术》 C.《本草纲目》 D.《黄帝内经》; 4.下列哪一样茶不是半发酵的茶？( )1 A.包种茶 B.铁观音 C.冻顶茶 D.龙井茶碧螺春 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．哈雷彗星绕太阳运行的周期约为( ) A.75年 B.76年 C.77年 D.78年+ 11.世界银行集团的机构组成不包括( ); d8 d* h; A.国际货币基金组织 B.国际复兴开发银行 C.国际开发协会 D.国际金融公司 12.从党的十二大到十三大，是邓小平理论的( ) A.萌芽、酝酿阶段 B.初步形成阶段 C.逐步展开并形成轮廓阶段