全国计算机等级考试二级公共基础知识考点
公共基础知识
基本要求
1．掌握算法的基本概念。
2．掌握基本数据结构及其操作。
3．掌握基本排序和查找算法。
4．掌握逐步求精的结构化程序设计方法。
5．掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。
6．掌握数据库的基本知识，了解关系数据库的设计。
考试内容
一、基本数据结构与算法
1．算法的基本概念；算法复杂度的概念和意义(时间复杂度与空间复杂度）。
2．数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3．线性表的定义；线性表的顺序存储结构及其插入与删除运算。
4．栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
5．线性单链表、双向链表与循环链表的结构及其基本运算。
6．树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7．顺序查找与二分法查找算法；基本排序算法(交换类排序，选择类排序，插入类排序)。
二、数据库设计基础
1．数据库的基本概念：数据库，数据库管理系统，数据库系统。
2．数据模型，实体联系模型及E―R图，从E―R图导出关系数据模型。
3．关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。
4．数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略
三、程序设计基础
1．程序设计方法与风格
2．结构化程序设计。
3．面向对象的程序设计方法，对象，方法，属性及继承与多态性。
四、软件工程基础
1．软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。
2．结构化分析方法，数据流图，数据字典，软件需求规格说明书。
3．结构化设计方法，总体设计与详细设计。
4．软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。
5．程序的调试，静态调试与动态调试。
全国计算机等级考试二级公共基础讲义之一
算法与数据结构
本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。
1.1算法
1、算法的基本概念：
是指解题方案的准确而完整的描述。
算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。
2、算法的基本特征
（1）可行性针对实际问题而设计的算法，执行后能够得到满意的结果。
（2）确定性每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。
（3）有穷性算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。
（4）拥有足够的情报算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。
*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
3、算法复杂度主要包括时间复杂度和空间复杂度。
（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。
同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。即算法的工作量=f（n）（2）算法空间复杂度是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
【算法习题】
1、算法的时间复杂度是指C
A) 执行算法程序所需要的时间B) 算法程序的长度
C) 算法执行过程中所需要的基本运算次数D) 算法程序中的指令条数
2、算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。
3、算法的空间复杂度是指C
A) 算法程序的长度B) 算法程序中的指令条数
C) 算法程序所占的存储空间D) 执行过程中所需要的存储空间
4、在计算机中，算法是指B
A) 加工方法B) 解题方案的准确而完整的描述
C) 排序方法D) 查询方法
5、算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】时间复杂度和空间复杂度
1.2 数据结构的基本概念
1、数据结构是指相互有关联的数据元素的集合。
2、数据结构主要研究和讨论以下三个方面的问题：
（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。
数据的逻辑结构有两个要素：一是数据元素的集合；二是此集合上的关系，它反映了数据元素之间的前后件关系
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
数据的存储结构有顺序、链接、索引等。
1）顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里。由此得到的存储表示称为顺序存储结构。
2）链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
3）索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
同一种逻辑结构的数据可以采用不同的存储结构，而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。
（3）对各种数据结构进行的运算。
3、数据结构的图形表示
一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。
4、根据数据结构中各数据元素之间前后件关系的复杂程度，数据结构分为两大类型：线性结构和非线性结构。
（1）线性结构（非空的数据结构）条件：
有且只有一个根结点[wx3]；
每一个结点最多有一个前件，也最多有一个后件。
*：常见的线性结构有线性表（栈、队列是线性表的特例）
（2）非线性结构：不满足线性结构条件的数据结构。
*：常见的非线性结构有树、二叉树和图等。
【数据结构基本概念习题】
1、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成
A) 动态结构和静态结构B) 紧凑结构和非紧凑结构
C)线性结构和非线性结构D) 内部结构和外部结构
2、数据结构包括数据的逻辑结构、数据的【2】以及对数据的操作运算。存储结构
3、数据的基本单位是【5】。数据元素
4、下列叙述中，错误的是
A) 数据的存储结构与数据处理的效率密切相关
B)数据的存储结构与数据处理的效率无关
C) 数据的存储结构在计算机中所占的空间不一定是连续的
D) 一种数据的逻辑结构可以有多种存储结构
5、数据的存储结构是指
A）数据所占的存储空间C）数据在计算机中的顺序存储方式
B）数据的逻辑结构在计算机中的表示D）存储在外存中的数据
6、顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。相邻
7、数据处理的最小单位是
A) 数据B) 数据元素C) 数据项D) 数据结构
8、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及
A) 数据的存储结构B) 计算方法C) 数据映象D) 逻辑存储
9、数据结构中，与所使用的计算机无关的是数据的
A) 存储结构B) 物理结构
C)逻辑结构D) 物理和存储结构
10、数据的逻辑结构有线性结构和【1】两大类。非线性结构
1.3 线性表及其顺序存储结构
1、线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个和最后一个外，有且只有一个前件、后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。
*：线性表有两种存储方式：顺序和链式。
2、线性表的顺序存储结构（也称为顺序表）具有两个基本特点：
（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，即顺序表中逻辑上相邻的元素的物理位置必定紧邻。（即逻辑结构和物理存储结构是一致的、一一对应的）
3、顺序表的插入、删除运算
（1）顺序表的插入运算：在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。
*：插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。
（2）顺序表的删除运算：在一般情况下，要删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。
*：删除运算时也需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。
插入、删除运算不方便。在长度为n的顺序表中插入、删除一个元素的时间复杂度都为O(n)。
（3）即查找操作：可实现随机访问、随机存取元素
在顺序表中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，即顺序存储结构通过元素的相对存储地址来表示元素之间的关系，可以通过计算机直接确定第i个结点的存储地址。
a i的存储地址为：ADR(a i)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。
线性表顺序存储的优点是可以随机访问、随机存取元素即实现查找操作比较方便，换句话说，顺序表是一种随机存取的存储结构。
线性表顺序存储的缺点：（1）插入或删除数据元素时需要移动大量的数据元素，运算效率很低。；（2）顺序表的存储空间不便于扩充；（3）不便于对存储空间的动态分配
1.4 线性链表
线性表的链式存储结构称为线性链表，是一种物理存储单元上非连续、非顺序的存储结构（存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致），数据元素的逻辑关系是通过链表中的指针链接来实现的。因此，在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域；另一部分用于存放指针，称为指针域，用于指向该结点的前一个或后一个结点（即前件或后件）。
线性链表分为单链表、双向链表和循环链表三种类型。
在单链表（如下图）中，每一个结点只有一个指针域，由这个指针只能找到其后件结点，而不能找到其前件结点。
因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针，指向其前件结点；另一个称为右指针，指向其后件结点，这种链表称为双向链表，如下图所示：
3、线性链表的基本运算
（1）在线性链表中包含指定元素的结点之前插入一个新元素。
*：在线性链表中插入元素时，不需要移动数据元素，只需要修改相关结点指针即可。
（2）在线性链表中删除包含指定元素的结点。
*：在线性链表中删除元素时，也不需要移动数据元素，只需要修改相关结点指针即可。
（3）将两个线性链表按要求合并成一个线性链表。
（4）将一个线性链表按要求进行分解。
（5）逆转线性链表。（6）复制线性链表。
（7）线性链表的排序。（8）线性链表的查找。
4、循环链表及其基本运算
在线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。为了克服线性链表的这个缺点，可以采用另一种链接方式，即循环链表。
与前面所讨论的线性链表相比，循环链表具有以下两个特点：1）在链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点，而循环链表的头指针指向表头结点；2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
下图a是一个非空的循环链表，图b是一个空的循环链表：
循环链表的优点主要体现在两个方面：一是在循环链表中，只要从表中任何一个结点出发就访问到表中其他所有的结点，而线性单链表做不到这一点；二是由于在循环链表中设置了一个表头结点，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
*：循环链表是在单链表的基础上增加了一个表头结点，其插入和删除运算与单链表相同。
链式存储结构的特点（优缺点）
插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。链表的查找只能从头指针开始顺序查找。
【线性表习题】
1、线性表的顺序存储结构和线性表的链式存储结构分别是
A) 顺序存取的存储结构、顺序存取的存储结构
B) 随机存取的存储结构、顺序存取的存储结构
C) 随机存取的存储结构、随机存取的存储结构
D) 任意存取的存储结构、任意存取的存储结构
2、链表不具有的特点是
A) 不必事先估计存储空间B) 可随机访问任一元素
C) 插入删除不需要移动元素D) 所需空间与线性表长度成正比
3、数据结构分为逻辑结构与存储结构，线性链表属于【1】。逻辑结构
4、顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。相邻
5、长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【1】。n/2
6、线性表L=(a1,a2,a3,…ai，…an)，下列说法正确的是
A) 每个元素都有一个直接前件和直接后件
B) 线性表中至少要有一个元素
C) 表中诸元素的排列顺序必须是由小到大或由大到小
D)除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件
7、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成
A) 动态结构和静态结构B)紧凑结构和非紧凑结构
C) 线性结构和非线性结构D) 内部结构和外部结构
8、当线性表采用顺序存储结构实现存储时，其主要特点是【1】。所有元素所占的存储空间是连续的；顺序表中逻辑上相邻的元素的物理位置必定紧邻
9、线性表若采用链式存储结构时，要求内存中可用存储单元的地址
A) 必须是连续的B) 部分地址必须是连续的
C) 一定是不连续的D)连续不连续都可以
10、下列叙述中，错误的是
A) 数据的存储结构与数据处理的效率密切相关
B)数据的存储结构与数据处理的效率无关
C) 数据的存储结构在计算机中所占的空间不一定是连续的
D) 一种数据的逻辑结构可以有多种存储结构
11、用链表表示线性表的优点是
A) 便于随机存取B) 花费的存储空间较顺序存储少
C)便于插入和删除操作D) 数据元素的物理顺序与逻辑顺序相同
12、在单链表中，增加头结点的目的是
A)方便运算的实现B) 使单链表至少有一个结点
C) 标识表结点中首结点的位置D) 说明单链表是线性表的链式存储实现
13、循环链表的主要优点是
A) 不再需要头指针了
B) 从表中任一结点出发都能访问到整个链表
C) 在进行插入、删除运算时，能更好的保证链表不断开
D) 已知某个结点的位置后，能够容易的找到它的直接前件
1.5 栈和队列（特殊的线性表）
1、栈及其基本运算
栈是限定在一端进行插入与删除运算的线性表。
在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。由此看出，栈具有记忆作用。
栈的基本运算：
1）插入元素称为入栈运算——首先将栈顶指针加一（即top加1），然后将新元素插入到栈顶指针指向的位置；
2）删除元素称为退栈运算——首先将栈顶指针指向的元素赋给一个指定的变量，然后将栈顶指针减一（即top减1）
3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
栈的存储方式和线性表类似，也有两种，即顺序栈（插入和删除是不需要移动栈中其它数据元素）和链式栈。
2、队列及其基本运算
队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。尾指针（Rear）指向队尾元素，头指针（front）指向排头元素的前一个位置（队头）。
队列是“先进先出”或“后进后出”的线性表。
队列运算包括：1）入队运算：从队尾插入一个元素；2）退队运算：从队头删除一个元素。
循环队列：是队列的顺序存储结构常用形式。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素均为队列中的元素。
【栈和队列习题】
1、栈和队列的共同特点是
A)都是先进先出B) 都是先进后出
C) 只允许在端点处插入和删除元素D) 没有共同点
2、如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是
A) e3,e1,e4,e2 B) e2,e4,e3,e1
C) e3,e4,e1,e2 D) 任意顺序
3、一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。而实现递归调用中的存储分配通常用
A)栈B) 堆C) 数组D) 链表
4、栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是
A) ABCED B) DCBEA C) DBCEA D) CDABE
5、栈通常采用的两种存储结构是
A)线性存储结构和链表存储结构B) 散列方式和索引方式
C) 链表存储结构和数组D) 线性存储结构和非线性存储结构
6、栈和队列通常采用的存储结构是【1】。链式存储和顺序存储
7、下列数据结构中，按先进后出原则组织数据的是
A) 线性链表B) 栈C) 循环链表D) 顺序表
8、当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为【2】。上溢
9、下列关于栈的叙述中正确的是
Ａ）在栈中只能插入数据B）在栈中只能删除数据
C）栈是先进先出的线性表D）栈是后进先出的线性表
10、下列关于队列的叙述中正确的是
Ａ）在队列中只能插入数据B）在队列中只能删除数据
C）队列是先进先出的线性表D）队列是后进先出的线性表
1.6 树与二叉树
1、树的基本概念
树是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。
在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
2、二叉树及其基本性质
（1）什么是二叉树
二叉树是一种很有用的非线性结构，它具有以下两个特点：1）非空二叉树只有一个根结点；2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。（五种基本形态：空树、只有根结点的二叉树、右子树为空的二叉树、左子树为空的二叉树、左、右子树均非空的二叉树）
*：根据二叉树的概念可知，二叉树的度可以为0（叶结点）、1（只有一棵子树）或2（有2棵子树）。
（2）二叉树的基本性质
性质1 在二叉树的第i层上，最多有2i-1个结点（i≥1）。
性质2 深度为k的二叉树最多有2K —1个结点(K≥1）。
满二叉树：如果一个深度为K的二叉树拥有2 K -1个结点，则将它称为满二叉树。即除最后一层外，每一层上的所有结点都有两个子结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
完全二叉树的特点
叶子结点只可能在层次最大的两层上出现
对任意结点，若其右分支下的子孙的最大层次是l ，则其左分支下的子孙的最大层次必是l 或l+1
完全二叉树还具有如下两个特性：
性质5 具有n个结点的完全二叉树深度为?log2n?+1，其中?log2n?取log2n的整数部分。
性质6 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k=1，2，…，n）的结点有以下结论：
①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点的编号为INT(k/2)。
②若2k≤n，则编号为k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
③若2k+1≤n，则编号为k的右子结点编号为2k+1；否则该结点无右子结点。
<注意>一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。
下图a表示的是满二叉树，下图b表示的是完全二叉树：
性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。（如果度为0的结点（叶子）个数为n0，度为2的结点个数为n2，则n0=n2+1。）
性质4 具有n个结点的二叉树，其深度至少为?log2n?+1，其中?log2n?
取log2n的整数部分。
3、二叉树的存储结构
在计算机中，二叉树通常采用链式存储结构。
与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。
*：一般二叉树通常采用链式存储结构，对于满二叉树与完全二叉树来说，可以[wx6]。
5、二叉树的遍历
所谓遍历二叉树是指按某种顺序访问二叉树中的每个结点一次且仅一次的过程，即不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：
（1）前（先）序遍历（DLR）：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
（2）中序遍历（LDR）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
（3）后序遍历（LRD）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
1.7 查找技术
查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找结果：（查找成功：找到；查找不成功：没找到。）
平均查找长度：查找过程中关键字和给定值比较的平均次数。
1、顺序查找
基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。
在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况下需要比较n次。
顺序查找一个具有n个元素的线性表，其平均复杂度为O（n）。
下列两种情况下只能采用顺序查找：
1）如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
2、二分法查找：
二分法查找只适用于顺序存储的有序表，且表中元素必须按[wx7]。
思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。
查找过程：
1）若中间项（中间项mid=(n-1)/2，mid的值四舍五入取整）的值等于x，则说明已查到；
2）若x小于中间项的值，则在线性表的前半部分查找；
3）若x大于中间项的值，则在线性表的后半部分查找。
特点：比顺序查找方法效率高。在长度为n的有序线性表中进行二分法查找，最坏的情况下，需要比较log2n次，其时间复杂度为O（log2n）。
1.8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列，即是将无序的记录序列调整为有序记录序列的一种操作。
交换类排序法：冒泡排序法，最坏情况下需要比较的次数为n(n-1)/2，
快速排序法，最坏情况下需要比较的次数为n(n-1)/2；
插入类排序法：简单插入排序法，最坏情况需要n(n-1)/2次比较，
希尔排序法，最坏情况需要O(n1.5)次比较；
选择类排序法：简单选择排序法，最坏情况需要n(n-1)/2次比较，
堆排序法，最坏情况需要O(nlog2n)次比较。
全国计算机等级考试二级公共基础讲义之二
数据库设计基础
4.l 数据库系统的基本概念
考点1 数据、数据库
1数据
数据(Data)是数据库中存储的基本对象。
数据的定义：描述事物的符号记录。
计算机中的数据一般分为两部分，其中一部分存放于计算机内存中，与程序仅有短时间的交互关系，随着程序的结束而消亡，它们被称为临时性数据；而另一部分数据则对系统起着长期持久的作用，它们被称为持久性数据。数据库系统属于持久性数据。
数据的种类：文字、图形、图像和声音。
数据有型(Type)与值(Value)之分，数据的型给出了数据的表示类型，如整型、实型、字符型等。
数据的特点：数据与其语义是不可分的。
2数据库
数据库(DataBase，DB)是长期储存在计算机内、有组织的、可共享的大量数据集合。数据库存放数据是按数据所提供的数据模式存放的，它能构造复杂的数据结构，以建立数据间的内在联系与复杂的关系，从而构成数据的全局结构模式。
数据库的特点：
(1)数据按一定的数据模型组织、描述和储存；
(2)可为各种用户共享；
(3)冗余度较小；
(4)数据独立性较高；
(5)易扩展。
考点2 数据库管理系统
1数据库管理系统的概念
数据库管理系统(DataBase Management System，DBMS)是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操作、数据维护、数据控制及保护和数据服务等。数
据库管理系统有如下功能：
(l)数据模式定义。数据库管理系统负责为数据库构建模式；
(2)数据存取的物理构建。数据库管理系统负责为数据模式的物理存取及构建提供有效的存取方法与手段；
(3)数据操纵。数据库管理系统一般提供查询、插入、修改以及删除数据的功能。它还具有做简单算术运算及统计的能力和强大的过程性操作能力；
(4)数据的完整性、安全性定义与检查。数据库中的数据具有内在语义上的关联性与一致性，它们构成了数据的完整性；
(5)数据库的并发控制与故障恢复。数据库管理系统必须对多个应用程序的并发操作做必要的控制以保证数据不受破坏，这就是数据库的并发控制；数据库中的数据一旦遭受破坏，数据库管理系统必须有能力及时进行恢复，这就是数据库的故障恢复；
(6)数据的服务。数据库管理系统提供对数据库中数据的多种服务功能，如数据拷贝、转储、重组、性能监测、分析等。
为完成数据库管理系统的功能，数据库管理系统提供相应的数据语言(Data Language)：(l)数据定义语言(Data Definition Language，DDL)。该语言负责数据的模式定义与数据的物理存取构建。
(2)数据操纵语言(Data Manipulation Language，DML )。该语言负责数据的操纵，包括查询及增加、删除、修改等操作。
(3)数据控制语言(Data Control Language，DCL)。该语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。
上述数据语言按其使用方式可分为交互式命令语言和宿主型语言两种结构形式。
2数据库管理员
数据库管理员(DataBase Administrator，DBA)是指对数据库的规划、设计、维护、监视等的人员。
数据库管理员的主要工作如下：
(1)数据库设计(Database Design)。DBA的主要任务之一是数据库设计，具体地说是进行数据模式的设计；
(2)数据库维护。DBA必须对数据库中的数据安全性、完整性、并发控制及系统恢复、数据定期转储等进行实施与维护；
(3)改善系统性能，提高系统效率。DBA必须随时监视数据库的运行状态，不断调整内部结构，使系统保持最佳状态与效率。
考点3 数据库系统
1数据库系统
数据库系统(DataBase System，DBS)是指在计算机系统中引入数据库后的系统构成。在不引起混淆的情况下常常把数据库系统简称为数据库。
数据库系统的构成：数据库系统由数据库(数据)、数据库管理系统(及其开发工具)、应用系统、数据库管理员、系统平台之一――硬件平台(硬件)、系统平台之二――软件平台(软件)5部分构成。
硬件平台包括以下两项：
(l)计算机：它是系统中硬件的基础平台；
(2)网络：数据库系统今后将以建立在网络上为主，而其结构形成又以客户/服务器(C/S)方式与浏览器/服务器(B/S)方式为主。
软件平台包括以下3项：
(l)操作系统：它是系统的基础软件平台；
(2)数据库系统开发工具：它包括过程性程序设计语言(如C，C++等)，也包括可视化开发工具VB，PB、Delphi等，它还包括近期与Internet有关的HTML和XML等。
(3)接口软件：在网络环境下数据库系统中数据库与应用程序，数据库与网络间存在着多种接口，它们需要接口软件进行连接，这些接口软件包括ODBC、JDBC、OLEDB、COBBA、COM及DOOM等。
2数据库应用系统
数据库应用系统(DataBase Application System，DBAS )是数据库再加上应用软件及应用界面这三者所组成，具体包括数据库、数据库管理系统、数据库管理员，硬件平台、应用软件及应用界面。
数据库的7个部分以一定的逻辑结构方式组成一个有机的整体，如图4-1所示。
图4-1数据库系统的软硬件层次结构
下面以一个用户读取某数据记录为例，展示在数据库中访问数据的具体执行过程，该过程如图4-2所示。
(1)用户程序中有一条读数据库记录的DML语句，当计算机执行到该语句时，即向DBMS发出读取相应记录的命令。
(2) DBMS接到该命令后，首先访问该用户对应子模式，检查该操作是否在合法授权范围内及欲读记录的正确性、有效性，若不合法则拒绝执行，并向应用程序状态返回区发出回答状态信息；反之执行下一步。
(3)DBMS读取模式描述并从子模式映射到全局模式，从而确定所需的逻辑记录类型。
(4)DBMS从逻辑模式映射到存储模式，从而确定读入哪些物理记录以及具体的地址信息。
(5)DBMS向操作系统发出从指定地址读取记录的命令。
(6)操作系统执行读命令，按指定地址从数据库中把记录读入系统缓冲区，并在操作结束后向DBMS作出回答。
(7) DBMS按照模式将读入系统缓冲区中内容映射成用户要求读取的逻辑记录。
(8) DBMS将导出的逻辑记录送入用户工作区，并将操作执行情况的状态信息返回给用户。
(9) DBMS将已执行的操作载入运行日志。
(10)应用程序根据返回的状态信息决定是否利用该数据进行操作等。
图4-2 数据库系统访问数据的步骤考点4 数据库系统的发展
数据管理技术的发展经历了3个阶段，见表4-1：
(1)人工管理阶段(20世纪40年代中~20世纪50年代中)；
(2)文件系统阶段(20世纪50年代末~20世纪60年代中)；
(3)数据库系统阶段(20世纪60年代末~现在)。
表4-1 各阶段特点的详细说明
人工管理阶段的特点：
(1)数据的管理者：应用程序，数据不保存；
(2)数据面向的对象：某一应用程序；
(3)数据的共享程度：无共享、冗余度极大；
(4)数据的独立性：不独立，完全依赖于程序；
(5)数据的结构化：无结构；
(6)数据控制能力：应用程序自己控制。
人工管理阶段应用程序与数据对应关系如图4-3所示。
图4-3 人工管理阶段应用程序与数据之间的关系
文件管理阶段的特点：
(1)数据的管理者：文件系统，数据可长期保存；
(2)数据面向的对象：某一应用程序；
(3)数据的共享程度：共享性差、冗余度大；
(4)数据的结构化：记录内有结构，整体无结构；
(5)数据的独立性：独立性差，数据的逻辑结构改变必须修改应用程序；
(6)数据控制能力：应用程序自己控制。
文件阶段应用程序与数据之间的对应关系如图4-4所示。
图4-4 文件阶段应用程序与数据之间的对应关系
数据库系统阶段的特点：
(1)数据的管理者：DBMS;
(2)数据面向的对象：现实世界；
(3)数据的共享程度：共享性高；
(4)数据的独立性：高度的物理独立性和一定的逻辑独立性；
(5)数据的结构化：整体结构化；
(6)数据控制能力：由DBMS统一管理和控制。
一、数据库系统的基本概念
数据、数据库、数据库管理系统
1.数据处理的最小单位是(C)。
A.数据
B.数据元素
C.数据项
D.数据结构
2.下列有关数据库的描述，正确的是(C)。
A.数据库是一个DBF文件
B.数据库是一个关系
C.数据库是一个结构化的数据的集合
D.数据库是一组文件
3.下述关于数据库系统的叙述中正确的是(A)
A.数据库系统减少了数据冗余
B.数据库系统避免了一切冗余
C.数据库系统避免了一切数据的重复
D.数据库系统比文件系统能管理更多的数据
4.下列有关数据库的描述．正确的是(D)。
A.数据处理是将信息转化为数据的过程
B.数据的物理独立性是指当数据的逻辑结构改变时，数据的存储结构不变
C.关系中的每一列称为元组，一个元组就是一个字段
D.如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键字，则称其为本关系的外关键字
5.下列4项说法中不正确的是(C)。
A.数据库减少了数据冗余
B.数据库中的数据可以共享
C.数据库避免了一切数据的重复
D.数据库具有较高的数据独立性
6.下列叙述中。不属于数据库系统的是(D)。
A.数据库
B.数据库管理系统
C.数据库管理员
D.数据库应用系统
7.数据库系统的核心是(数据库管理系统)。
8.数据库、数据库系统和数据库管理系统之间的关系是(数据库系统包括数据库和数据库管理系统)。
9.为用户与数据库系统提供接口的语言是(数据操纵语言(DML))。
数据库管理系统一般提供的数据语言有：
数据库定义语言(DDL)：负责数据的模式定义与数据的物理存取构建
数据操纵语言(DML)：负责数据的操纵，包括查询及增、删、改变等操作
数据库控制语言(DCL)：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等2. 数据库系统的发展
10.在数据管理技术的发展过程中．经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是(数据库系统)。
11.在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有(A)。
A.特定的数据模型
B.数据无冗余
C.数据可共享
D.专门的数据管理软件
12.相对于数据库系统，文件系统的主要缺陷有数据关联差、数据不一致性和(冗余性)。
13.分布式数据库系统不具有的特点是( D)。
A.数据分布性和逻辑整体性
B.位置透明性和复制透明性
C.分布性
D.数据冗余
3.数据库系统的基本特点
数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。也就是说，数据的逻辑结构、存储结构和存取方式的改变都不会影响应用程序。数据独立性包括物理独立性和逻辑独立性两个含义。
当数据的物理结构(存储结构、存取方式等)改变时，不影响数据库的逻辑结构．从而不致引起应用程序的变化，这是指数据的物理独立性。
4.数据库系统的内部结构
数据库系统在其内部具有三级模式及二级映射，三级模式分别是概念级模式、内部级模式与外部级模式，二级映射分别是概念级到内部级的映射以及外部级到概念级的映射。这种三级模式与二级映射构成了数据库系统内部抽象结构体系。
14.单个用户使用的数据视图的描述称为(外模式)。索引属于(内模式)。
二、数据模型
1．数据模型的基本概念
数据模型是数据库设计的核心。其内容有三个部分：数据结构、数据操作和数据约束
数据模型按不同应用层次分3种类型，它们是概念数据模型、逻辑数据模型和物理数据模型。
概念数据模型简称概念模型，是面向客观世界、面向用户的模型；是整个数据模型的基础。与具体的数据库管理系统无关，着重于对客观事件的结构描述以及它们之间的内在联系的刻画。常用的有E-R模型、扩充的E-R模型等。
逻辑数据模型又称数据模型，是面向数据库系统的模型，着重于数据库系统一级的实现。概念模型只有在转换成数据模型后才有可能在数据库中得以表示。常见的有层次模型、网状模型和关系模型。
数据库管理系统常见的数据模型有层次模型、网状模型和关系模型3种。
15.下列数据模型中，具有坚实理论基础的是(C)。
A.层次模型
B.网状模型
C.关系模型
D.以上3个都是
16.下列说法中，不属于数据模型所描述的内容的是(C)。
A.数据结构
B.数据操作
C.数据查询
D.数据约束
17.实体是信息世界中广泛使用的一个术语，它用于表示(C)。
A.有生命的事物
B.无生命的事物
C.实际存在的事物
D.一切事物
18.E-R模型由实体、联系和属性三个基本概念组成。
19.将E—R图转换到关系模式时，实体与联系都可以表示成(关系)。
20.下列叙述中，正确的是(A)。
A.用E—R图能够表示实体集间一对一的联系、一对多的联系和多对多的联系
B.用E—R图只能表示实体集之问一对一的联系
C.用E—R图只能表示实体集之间一对多的联系
D.用E—R图表示的概念数据模型只能转换为关系数据模型
21.公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从职员到部门的联系类型是(多对一)。
22.在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系
23.最常用的一种基本数据模型是关系数据模型，它的表示应采用(二维表)。
24.由关系数据库系统支持的完整性约束是指实体完整性和参照完整性。
25.关系模型允许定义3类数据约束，下列不属于数据约束的是(C)。
A.实体完整性约束
B.参照完整性约束
C.域完整性约束
D.用户自定义的完整性约束
26.“年龄在18岁一25岁之间”这种约束是属于数据库中的( C )。
A.原子性措施
B.一致性措施
C.完整性措施
D.安全性措施
27.关系模型的数据操纵是建立在关系上的数据操纵，一般有查询、增加、删除和修改四种操作。
28.下列4项中．必须进行查询优化的是( A)。
A.关系数据库
B.网状数据库
C.层次数据库
D.非关系模型的数据视图的描述称为(外模式)。索引属于(内模式)。
目录 二级公共基础知识考纲 (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）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。
1. 一个细胞在人工操作下分裂繁殖从而形成细胞群，在细胞群中每个细胞的基因彼此相同，这种操作被称作( ) A.基因工程 B.蛋白质工程 C.克隆技术 D.转基因技术 2. 唯心主义的两种基本类型是指( )。 A.辩证的唯心主义和形而上学的唯心主义 B.宗教唯心主义和历史唯心主义 C.主观唯心主义和客观唯心主义 D.可知论唯心主义和不可知论唯心主义 3. 毛泽东提出，生产资料私有制的社会主义改造基本完成后，国家政治生活的主题是( )。 A.正确处理人民内部矛盾 B.集中力量进行社会主义建设 C.调动国内外一切积极力量 D.正确处理两类不同性质的矛盾 4. 毛泽东思想达到成熟的标志是( )。 A.以农村包围城市的革命理论的形成 B.社会主义革命和建设理论的形成 C.实事求是思想路线的形成 D.新民主主义理论科学体系的形成 5. 我国刑法规定，对已满14岁不满18岁的人犯罪的( )。 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.火炬计划 B.星火计划 C.丰收计划 D.燎原计划 11. 认为决策是一个动态的过程，这一思想来源于( )。 A.理查德·施奈德 B.伊斯顿和拉斯维尔 C.西蒙 D.林德布罗姆 12. 从决策的基本属性来看，决策是( )。 A.不以人的意志为转移的活动 B. 以人的意志为转移的活动 C.客观规律的真实描述 D.客观规律的正确反映 13. 两点论和重点论的关系是( )。 A.重点论以两点论为前提，两点论内在地包含着重点论 B.两点论以重点论为前提，重点论内在地包含着两点论 C.重点论以两点论为内容，两点论以重点论为形式 D.两点论以重点论为内容，重点论以两点论为形式 14. 酸雨对水生植物的危害很大，特别严重时还会危害人类健康，它的主要成分是( ) A.硫酸和盐酸 B.盐酸和高氯酸 C.高氯酸和硝酸 D.硝酸和硫酸 15. 发展揭示了新陈代谢这一宇宙间普遍的、永远不可抗拒的客观规律，发展的本质是( )。 A.变化 B.增加 C.创新 D.运动
二级公共基础知识分类模拟题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．在栈中，栈顶指针的动态变化决定栈中元素的个数
法理 ●法的概念：特定物质生活条件决定的统治阶级意志的体现，由国家制定认可，由国家强制力保证实施的行为规范的综合 ●法的特征:1、调整人的行为或社会关系2、国家制定或认可、并具有普遍约束力3、以国家强制力保护实施4、规定权利和义务 ●法的本质：统治阶级意志的表现 ●法的规范作用：指引、评价、预测、教育和强制 法的作用 ●法的社会作用：维护统治阶级的阶级统治；执行社会公共事务。 ●法与经济基础的关系：经济基础决定法，法又反作用于经济基础。 ●法与生产力的关系：生产力发展的水平直接影响法的发展水平。法律离开社会生产力的发展，既无存在的可能，也无存在的必要。 ●法对市场经济宏观调控的作用：引导；促进；保障；制约。 ●法对微观经济的作用：确认经济活动主体的法律地位，调节经济活动中的各种关系，解决经济活动中哦的各种纠纷，维持正常的经济秩序 ●法与政治的关系：法受政治制约（政治关系发展、整体改革、政治活动的内容），法服务于政治（调节阶级间、阶级内关系，维护社会关系、社会秩序；打击制裁违法犯罪，调整公共事务关系，维护公共秩序） ●法与党的政策的关系： 相同点（内容实质方面联系）：阶级本质、指导思想、基本原则、经济基础、社会目标等 区别：意志属性、规范形式、调整范围（不尽同）、实施方式、稳定性程序化程度 ●法与党的政策相互作用： 一、法的制定：1、政策是立法的依据和指导思想 2、发将政策转为形式合理效力普遍的行为规范 二．发的实施：1、政策变法，使正统，又反之约束政治活动 2、法的实施借助政策作用 ●社会主义民主与法制是相互依存、相互作用、紧密联系、不可分割的。 ●民主是法制的前提和基础，因为：民主是法制产生的依据、力量源泉，决定了法制的性质和内容 ●法的渊源的专有含义：法律规范的形式上的来源和其外在表现形式 ●法律效力等级为：宪法－法律－行政法规－地方性法规－规章（部门和地方政府）。 ●宪法：根本大法，最高法律效力 ●法律：由全国人大或其常务委员会制定、颁布；全国范围内生效；规范性法律文件 ●行政法规：国务院为领导和管理国家各项行政事务根据为宪法、法律 国务院发布的决定、命令，凡具有规范性的也属于发的渊源 ●地方性法规：地方人大及常委会制定（省、自治区、直辖市、省政府所在市、国批的较大市），适用本地方。 ●规章：1、部门规章：指由国务院各部委+中银+审计署+具有行政管理职能的直属机构；依据为：宪法、法律、国务院的行政法规、决定、命令 2、地方规章：政府制定（省、自治区、直辖市、省自治区政府所在市、经济特区所在市、国的较大市）依据：宪法、法律、行政法规 ●自治条例和单行条例：民族自治地方人大制定，区域内生效 ●特别行政区法：在特别行政区内实行的制度由全国人大以法律规定。 ●国际条约：与民法规定不同的，适用国际条约，但声明保留的条款除外。 ●规定是规范性文件，不属于法律范畴，效力低于法律。 ●广义的法律包括法律、行政法规、地方性法规和规章。 ●法律关系三要素（法律规范在调整人们行为过程中形成的权利义务关系）：主体（法律关系的参加者）、客体（权利义务指向的对象：物、精神产品、人身、行为）、内容（权利义务） ●权利能力：能够才加一定的法律关系，依法享有权利承担义务的主体能力； 行为能力：法律关系的主体能够通过自己的行为实际取得权利和承担义务的能力 行为能力必须以权利能力为前提，无权利能力就无法谈行为能力。 ●法人的权利能力：生于成立，终于解体 公民的权利能力：始于出生，终于死亡 ●自然人有权利能力，未必有行为能力，根据年龄和精神状况，分为：完全、限制、无行为能力人
1.1 算法 考点1 算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括“与”、“或”、“非”等运算； ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法 计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2)归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
公共基础知识必背政治常识考点 导读：我根据大家的需要整理了一份关于《公共基础知识必背政治常识考点》的内容，具体内容：公共基础涉及的方面很广，学习的时候要有自己的方法。下面是我为大家整理的公共基础知识必背政治常识考点，一起来看看吧!公共基础知识必背政治常识考点：社会管理1、社会管理格局...公共基础涉及的方面很广，学习的时候要有自己的方法。下面是我为大家整理的公共基础知识必背政治常识考点，一起来看看吧! 公共基础知识必背政治常识考点：社会管理 1、社会管理格局：党委领导、政府负责、社会协同、公众参与 2、社会管理：是政府职能的重要组成部分，作为政府职能之一的社会管理，是指国家通过制定一系列社会政策和法律规范，对社会组织和社会事务进行规范和引导，促进政治经济社会文化和自然协调发展的一系列活动以及这些活动的过程。 内容包括： 培育和健全社会结构调整各类社会利益关系回应社会诉求 化解社会矛盾维护社会公正、社会秩序和社会稳定维护和健全社会内外部环境 3、创新社会管理需要在以下方面切实提高政府行政效能 A、深化行政管理体制改革，加快政府职能转变，努力建设服务型社会 B、深化行政审批制度改革，精简行政审批事项 C、进一步提高公务员素质，推进政府绩效管理
D、大兴求真务实之风，讲实话、办实事、求实效，提倡讲短话、开短会、行短文，坚决摒弃形式主义、官僚主义 社会管理练习题： 1、为提高社会管理科学化水平，全国各地积极出台加强和创新社会管理的措施，下列措施中不属于创新社会管理的是(B) A、组织社会志愿者开展邻里互动活动 B、提高临床一线医护人员的待遇水平 C、通过微博向群众提供政务服务资讯 D、设奖鼓励市民投诉举报食品安全问题 解析：本题考查政治常识，社会管理创新是指在现有社会管理条件下，用现有的资源和经验，据政治经济和社会的发展态势，尤其是依据社会自身运行规律乃至社会管理的相关理念和规范，研究并运用新的社会管理理念，知识，技术，方法，和机制的，对传统管理模式及相应的管理方式和方法进行改造改建不改革，建构新的社会管理机制和制度，以实现社会管理新目标，或者这些活动的过程.社会管理创新既是活动,也是活动的过程，是以社会管理存在为前提的，其目的在于使社会能够形成更为良好的秩序，产生更为理想的政治经济和社会效益，2004年6月我党的十六届四中全会提出要加强社会建设和管理推进社会管理体制创新，2007年党的十七大报告提出要建立健全党委领导、政府负责社会协同公众参与的社会管理格局，ACD，都有公众参与，B选项只涉及特定群体，不属于社会管理创新，故本题正确答案为B选项。 2、某市120余政府机构集体入驻微博，打造政务微博群其中7个官方
全国计算机等级考试二级公共基础知识练习题 及答案 全国计算机二级考试主要考核使用一种高级计算机语言编写程序以及 上机调试的基本技能，以下是由我整理关于的内容，希望大家喜欢! (一) 1、域名是ISP的计算机名，域名中的后缀、gov表示机构所属类型为( )。 A、政府机构 B、教育机构 C、商业机构 D、军事机构考试用书 答案：A 2、中文EXCEL的分类汇总方式不包括( )。 A、乘积 B、平均值 C、值 D、求和 答案：A 3、地址为202、18、66、5的IP地址属于( )类IP地址。 A、A B、C C、D
D、B 答案：B 4、微型计算机硬件系统中最核心的部件是( )。 A、硬件 B、I/O 设备 C、内存储器 D、CPU 答案：D 5、在计算机技术指标中，MIPS用来描述计算机的( )。 A、运算速度 B、时钟频率 C、存储容量 D、字长 答案：A (二) 1、Excel的主要功能是( )。 A、表格处理，文字处理，文件管理 B、表格处理，网络通讯，图表处理 C、表格处理，数据库管理，图表处理 D、表格处理，数据库管理，网络通讯 答案：C 2、关于Word中的文本框，下列说法( )是不正确的。
A、文本框可以做出冲蚀效果 B、文本框可以做出三维效果 C、文本框只能存放文本，不能放置图片 D、文本框可以设置底纹 答案：C 3、局域网的英文缩写是( )。 A、WAN B、LAN C、MAN D、Internet 答案：B 4、在WORD编辑状态下，当前编辑文档中的字体是宋体，选择了一段文字使之反显，先设定了楷体，又设定了黑体，则( )。 A、文档全文都是楷体 B、被选择的内容仍是宋体 C、被选择的内容便成了黑体 D、文档全部文字字体不变 答案：C 5、下列叙述中，正确的是( )。 A、CPU 能直接读取硬盘上的数据 B、CPU 能直接存取内存储器中的数据 C、CPU 由存储器和控制器组成
全国计算机等级考试二级公共基础知识复习资料 全国计算机等级考试二级公共基础知识复习资料 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
政治全套知识点总结 经济 1、商品的含义？商品的基本属性？ 商品是用于交换的劳动产品。商品的基本属性是使用价值（商品能满足人们某种需要的属性）和价值（凝结在商品中的无差别的人类劳动） 2、货币的含义？货币的本质？货币的基本职能？ 从商品中分离出来固定地充当一般等价物的商品，就是货币。货币的本质是一般等价物。 货币的基本职能是价值尺度（货币本身有价值，是商品，货币执行价值尺度的形式是只需要观念上的货币，并不需要现实的货币）和流通手段（货币充当商品交换的媒介，货币执行流通手段的形式是只能用现实上的货币，而不能用观念上的货币）。 3、货币流通规律？公式？ 商品价格总额待售商品量*价格 流通中所需要的货币量= = 4、我国为什么要保持人民币币值稳定？ （1）对内保持物价总水平稳定；（2）对外保持人民币汇率稳定； （3）有利于人民生活安定、国民经济持续快速健康发展； （4）有利于世界金融的稳定和经济的发展； （5）有利于实现扩大就业，缓解我国的就业货币流通次数货币流通次数 5、汇率的含义？什么叫外汇汇率升高和外汇汇率跌落？ 汇率又称汇价，是两种货币之间的兑换比率。 如果用100单位外币兑换成更多的人民币，说明外币的汇率升高；反之，则说明外币汇率跌落。压力； （6）有利于实现经济增长，国际收支平衡等宏观经济目标。 6、供求对价格的影响？ 供不应求，价格升高---------卖方市场供过于求，价格降低---------买方市场 7、价格和价值的关系？ 价值是价格的基础，价格是价值的货币表现。 8、商品的价值量与社会必要劳动时间称正比，商品的价值量与社会劳动生产率成反比。 9、价值规律的内容和形式？ 价值规律的基本内容是商品的价值量由生产该商品的社会必要劳动时间决定，商品交换以价值量为基础实行等价交换。 价值规律的表现形式是商品价格受供求关系的影响，围绕价值上下波动。 10、价格变动会产生哪些影响？ （1）对人们生活的影响： ①一般说来，价格上升，购买减少；价格下降，购买增加。 ②不同商品的需求量对价格变动的反应程度是不同的。价格变动对生活必需品需求量的影响 比较小，对高档耐用品需求量的影响比较大。 ③消费者对既定商品的需求还会受到相关商品价格变动的影响。互为替代品的价格变动对双 方的影响是同向的，互补商品的价格变动对双方的影响是反向的。 （2）对生产经营的影响：
第一章数据结构与算法 算法 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)的线性表。 线性链表
2018年9月计算机二级公共基础知识必背考点66条 1.算法的有穷性是指算法必须能执行有限个步骤之后终止. 2.算法的时间复杂度是指算法在执行过程中所需要的基本运算次数 3.队列、栈、线性表属于线性数据结构，二叉树不属于 4.数据的存储结构是指：数据的逻辑结构在计算机中的表示 5.一个逻辑数据结构可有多种存储结构，且各种存储结构影响数据处理的效率 6.线性链表是线性表的链式存储结构 7.栈是先进后出、后进先出的线性链表，具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针，是特殊的线性表，只能在一端插入或者删除元素 8.线性链表存储空间不一定连续，且各元素的存储顺序是任意的 9.在深度为7的满二叉树中，叶子节点的个数为：64 10.能用二分法查找的是顺序存储的有序线性表 11.对长度为N的线性表进行顺序查找，在最坏的情况下需要比较的次数为：N 12.对于长度为N的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是：快速排序为N(N-1)/2 13.算法的复杂度包括时间复杂度和空间复杂度 14.算法在执行过程中所需要的存储空间称为算法的空间复杂度 15.问题处理方案的正确而完整的描述称为算法 16.数据的逻辑结构在计算机存储控件中的存放方式称为数据的存储结构或者物理结构或者物理存储结构 17.按照逻辑结构分类，数据结构可以分为线性结构和非线性结构，二叉树属于非线性结构 18.数据结构分为逻辑结构和存储结构，循环队列属于存储结构 19.某二叉树中度为2的结点有18个，则该二叉树中共有19个叶子结点
21.对长度为10的线性表进行冒泡排序，最坏的情况下需要比较的次数为45 22.程序经调试改错后还应进行再调试 23.符合结构化程序设计风格的是使用顺序、选择和重复三种基本控制结构标示程序的控制结构 24.结构化程序设计的一种基本方法是逐步求精法、自顶向下、模块法 25.在面向对象的方法中，一个对象请求另一个对象为其服务的方式是通过发送消息 26.在软件工程学中，我们把一组具有相同的数据结构和相同的行为特征的对象的集合定义为类 27.面向对象的方法有对象/继承/类 28.在面向对象的方法中，类的实例称为对象 9.在面向对象的方法中，类描述的是具有相同属性与操作的一组对象 30.结构化程序设计的3种基本逻辑机构为顺序、选择和重复（循环） 31.在面向对象的方法中，类之间共享属性和操作的机制称为继承 32.软件是程序、数据与相关文档的集合 33.在软件开发中，属于设计阶段的是：数据结构设计、给出系统模块结构、定义模块算法 34.软件工程的主要思想是强调在软件开发的过程中需要应用工程化原则 35.软件交付使用后还应进行维护 36.在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是需求分析 37.软件设计的原则有抽象、模块化、信息隐蔽 38.为了是模块尽可能独立，需求模块的内聚程度要尽量高，且各模块的耦合程度要尽量弱 39.在软件设计中，属于过程设计工具的是：PDL过程设计语言、PAD图、N-S图 40.软件测试的目的是尽可能多地发现程序中的错误 41.软件需求阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书和需求评审 42.在结构化方法中，软件功能分解属于总体设计阶段
计算机二级公共基础 2009-09-14 15:13第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据元素之间的前后件关系是指他们的逻辑关系（反映数据元素之间逻辑关系的数据结构），而与他们在计算机中的存储位置无关。 数据的逻辑结构有两个要素：一、数据元素的集合，通常记为D;二、D上的关系，它反映D中各数据元素之间的前后间关系，通常记为R；即一个数据结构可以表示成 B=(D,R)其中B表示数据结构。未反应数据元素间的前后件关系，一般用二元组表示。a,b是D中的两个数据，二元组（a,b）表示a是b的前件，b是a 的后件。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（数据的物理结构）。数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。
事业单位考试公共基础知识必考点及常考点总结 事业单位考试公共基础知识试卷中，考试题型通常为单项选择题、多项选择题、判断题，有的地方还会考察公文实务题、案例分析题、综合分析题、材料处理题，但是一般比较少。可以说考查题型丰富，考查范围广泛，涉及法律、政治、哲学、经济、国情、公文、人文、历史、科技、语文基础知识、生活常识等方面，意在测查考生各方面的综合能力。 具体而言，华图事业单位招聘网总结各地事业单位考试公共基础知识考试中的必考点和常考点特点如下： 一、十八大必考 事业单位考试《公共基础知识》一直热衷于对时政热点的考察，尤其是今年我们一直强调的十八大，成为必考点，而且同一知识点在一张试卷中反复出现。比如在2013年江苏公务员考试《公共基础知识》A类第1、6、38题都考到了十八大，由此可以看出，十八大的重要性。 例题：党的十八大把科学发展观列入党的指导思想，科学发展观最鲜明的精神实质是（）。 A.解放思想、实事求是、与时俱进、求真务实 B.以人为本、全面协调可持续发展 C.科学发展、和谐发展、和平发展 D.发展为了人民、发展依靠人民、发展成果为人民共享 【解读】A。解析：党的十八大报告指出：“解放思想、实事求是、与时俱进、求真务实，是 科学发展观最鲜明的精神实质。”学习领会科学发展观，必须深刻把握这个精神实质。故本题答案是A。 二、以时政为背景，综合性较强 从2013年各地事业单位考试公共基础知识中我们可以看出，时政方面涉及面很广，有十八大、2013中央1号文件、2013中央经济工作会议、歼—15总指挥罗阳等。但题目大多数以间接考察为主，以时政热点为背景，结合经济、哲学、职业道德等知识点来出题，综合性较强。对此，事业 1
计算机二级公共基础知识试题及答案 一、选择题 1.在深度为7的满二叉树中，叶子结点的个数为() A.32 B.31 C.64 D.63 参考答案：C 参考解析：在满二叉树中每层的结点数都达到最大值，而且叶子结点全部出现在最底层。第1层(根结点所在的层)有20个结点，第 2层有21个结点，……第n层有2n-1个结点。在深度为7的满二 叉树中，第7层有27-1=64个结点(全部是叶子结点)、在深度为7 的满二叉树中，共有2^(7-1)=64个结点、因此本题的正确答案是C。 2.下列叙述中正确的是() A.程序执行的效率与数据的存储结构密切相关 B.程序执行的效率只取决于程序的控制结构 C.程序执行的效率只取决于所处理的数据量 D.以上三种说法都不对 参考答案：A 参考解析：程序的执行效率与算法和数据结构有密切的关系，瑞士科学家沃士说过“程序=算法+数据结构”。所以程序执行的效率 与数据的存储结构密切相关;程序执行的效率与程序的控制结构、所 处理的数据量有关，但不绝对相关。因此本题的正确答案是A。 3.下列工具为需求分析常用工具的是 A.PAD B.PFD C.N-S D.DFD
参考答案：D 4.以下算法设计基本方法中基本思想不属于归纳法的.是() A.递推法 B.递归法 C.减半递推技术 D.回溯法 参考答案：D 5.对长度n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是() A.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序 参考答案：D 参考解析：排序技术有：①交换类排序法(冒泡排序法、快速排序法);②插入类排序法(简单插入排序、希尔排序);③选择类排序法(简单选择排序法、堆排序法)。在最坏情况下，希尔排序需要的比较次数是O(nl.5)、堆排序需要的比较次数是O(nlog2n)、其它排序方法需要的比较次数都是n(n.1)/2。因此本题的正确答案是D。 6.按软件的功能划分，需求分析工具软件属于 A.应用软件 B.系统软件 C.支撑软件 D.专用软件 参考答案：C 7.对右下图二叉树进行后序遍历的结果为() A.ABCDEF B.DBEAFC C.ABDECF D.D.EBFCA 参考答案：D 参考解析：后序遍历的方法是：若二叉树为空，则结束返回。否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。本题
全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1、算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2、数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3、线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5、线性单链表、双向链表与循环链表的结构及其基本运算。 6、树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7、顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、程序设计基础 1、程序设计方法与风格。 2、结构化程序设计。 3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工程基础 1、软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。 2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3、结构化设计方法，总体设计与详细设计。 4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统 测试。 5、程序的调试，静态调试与动态调试。 四、数据库设计基础 1、数据库的基本概念：数据库，数据库管理系统，数据库系统。 2、数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4、数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式：公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 （一）算法 1．算法的基本概念：算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且
1.1 算法 考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1 算法的基本特征 (1) 可行性(effectiveness):针对实际问题而设计的算法，执行后能够得到满意的结果。 (2) 确定性(definiteness):算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 ⑶有穷性(finiteness):算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2 算法的基本要素 (1) 算法中对数据的运算和操作:每个算法实际上是按解题要求从环境能进行的所 有操作中选择合适的操作所组成的一组指令序列。计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下 4 类: ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算:主要包括“与” 、“或”、“非”等运算； ③关系运算:主要包括“大于” 、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2) 算法的控制结构:一个算法的功能不仅仅取决于所选用的操作，而且还与各操 作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且 也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3 种基本控制结构组合而成。 (3) 算法设计的基本方法 计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1) 列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2) 归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从 本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。 (3) 递推递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推 关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。
第八课二级公共基础知识总结 本课主要知识点 知识点1.数据结构与算法 算法：是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 算法是一组严谨地定义运算顺序的规则，每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。所 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3 结点个数n n=0
线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 元素ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k， ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：查找、插入、删除。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为 (1) 非空二叉树只有一个根结点； 二叉树基本性质：
（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点； （2）深度为m的二叉树最多有2m-1个结点； （3）度为0的结点（即叶子结点）总是比度为2的结点多一个； （4）具有n个结点的二叉树，其深度至少为[log n]+1,其中[log2n]表示 2 取log n的整数部分 2 (5) 具有n个结点的完全二叉树的深度为[log2n]+1； (6) 设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1,2,…n给结点进行编号（ 插入类排序法：（1）简单插入排序法，最坏情况需要（2）希尔排序法，最坏情况需要 较。 选择类排序法：（1）简单选择排序法, 最坏情况需要（2）堆排序法，最坏情况需要 较。 相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。 知识点2.程序设计基础 2.1 程序设计设计方法和风格