全国计算机二级(笔试)考前辅导材料
第一部分 公共基础知识（30 分） 第二部分 Visual FoxPro（70 分）
第一部分 公共基础知识
包括 10 道单选题，5 道填空题，每题 2 分，共 30 分。 公共基础知识考试内容涉及： 第一部分：数据结构与算法 第二部分：程序设计基础 第三部分：软件工程基础 第四部分：数据库设计基础（参考 Visual FoxPro 课程第一章）
重点讲解前三部分的内容，并整理考点与近年真题、模拟题，以 及解析。 希望对同学们的复习有帮助。
第一部分：数据结构与算法
重点学习知识点： 1．算法的概念、算法时间复杂度及空间复杂度的概念 2．数据结构的定义、数据逻辑结构及物理结构的定义 3．栈的定义及其运算、线性链表的存储方式 4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的 遍历 考点 1 算法的基本概念
考点 1 在笔试考试中考核的几率为 30%， 此考点为识记内容， 主要涉及算法复杂度问题较多。 所谓算法是指解题方案的准确完整的描述。 计算机解题的过程实际上是在实施某种算 法，这种算法称为计算机算法。 软件的主体是程序， 程序的核心是算法。 用计算机解决问题的过程可以分成三个阶段： 分析问题、设计算法和实现算法（编程） 。 Pascal 之父——Nicklaus Wirth（尼克劳斯·威茨） ，提出的著名公式： “算法+数据结构=程序”。
可参考《大学计算机信息 技术》教程第 3 章 3.3 节 1．算法的基本特征： 可行性——针对实际问题而设计的算法， 执行后能够得到满意的结果， 必须有一个或 者多个输出，有 0 个或者多个输入。即使在数学理论上是正确的，如果在 实际的计算机上不能执行，则该算法不具有可行性。 确定性——算法每一步都有明确定义，不能有歧义。 有穷性——算法在有限的时间内完成。 拥有足够的情报——算法的执行结果与输入的初始数据有关，不同的输入将会导致 不同的结果输出。当算法有足够的情报，此算法才是有效的。 当提供的情报不够时，算法可能无效。
2．算法的基本要素： 一个算法由两种基本要素组成： （1）对数据对象的运算和操作； 在一般的计算机系统中，基本的运算和操作有以下 4 类：算术运算、逻辑运算、 关系运算和数据传输（多用于插入，删除操作） 。 （2）算法的控制结构。 算法中各操作之间的执行顺序称为算法的控制结构（顺序，选择和循环） 。 3.算法的基本设计方法 列举发、归纳法、递推法、递归法、减半递推技术和回溯法。 4. 描述算法的工具 通常有传统流程图、N-S 结构化流程图、算法描述语言等。
【典型真题】
（2011 年 9 月）下列叙述中正确的是______ A)算法就是程序 B)设计算法时只需考虑数据结构的设计 C)设计算法时只需考虑结果的可靠性 D)以上三种说法都不对
解析：算法不等同于程序，参考《大学计算机信息技术》第 3.3 节，设计一个计算机算法需要注意以下几 点：①必须完整考虑整个问题所有可能的情况；②算法每一步必须是可执行的；③必须在有限步骤内求出 预定的结果。设计算法时要考虑数据结构、数据运算与操作、以及算法的可行性、确定性、有穷性等特征。
考点 2
算法复杂度
考点 2 在笔试考试中，在笔试考试中出现的几率为 70%，主要是以选择的形式出现，分 值为 2 分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。 1. 算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机 上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些 与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依赖于 问题的规模（通常用整数 n 表示） ，它是问题规模的函数。即：算法的工作量=f（n） 2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空 间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作 单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常 数，则称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常 采用压缩存储技术，以便尽量减少不必要的额外空间。 疑难解答：算法的工作量用什么来计算？ 算法的工作量用算法所执行的基本运算或基本操作次数来计算， 而算法所执行的基本 运算次数是问题规模 n 的函数，即算法的工作量=f（n） ，其中 n 是问题的规模。 复杂度通常表示为 O（f(n)） ，O（f(n)）代表一种量度（级别） 。 时间复杂度 T(n)= O（f(n)） 空间复杂度 S(n) = O（f(n)） 举例说明: For i=1 to int（n/2） Do x=x+i end 此算法的基本操作为 x+i，问题规模为 n，执行 x+i 的次数大约为 n/2，所以， 时间复杂度 T(n)= O（n/2） ，该算法的复杂度在数量级别上是 n 的线性方程。
经典习题
【例题1】对某个问题处理方案的正确而完整的描述称为______。 【例题2】算法复杂度主要包括时间复杂度和 复杂度。 (答案:算法) （答案：空间）
解析： 算法的时间复杂度是指执行算法所需要的计算工作量。 通常以基本操作执行的次数来计算， 执行的.
次数与问题规模n有关，一般用O(f(n))表示。算法的空间复杂度是指执行这个算法所需要的内存空间。
【例题3】算法的时间复杂度是指 A)算法的执行时间 B)算法所处理的数据量 C)算法程序中的语司或指令条数 D)算法在执行过程中所需要的基本运算次数 【例题4】算法的时间复杂度取决于_______。 A）问题的规模 B）待处理的数据的初态 C）问题的难度 D）A）和 B）
解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入 数据所有的可能取值范围、输入各种数据或数据集的概率有关。
【例题5】算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数 C)算法程序所占的存储空间 D)算法执行过程中所需要的存储空间 【例题6】下列叙述正确的是______。 A) 算法的效率只与问题的规模有关,而与数据的存储结构无关 B) 算法的时间复杂度是指执行算法所需要的计算工作量 C) 数据的逻辑结构与存储结构是一一对应的 D) 算法的时间复杂度与空间复杂度一定相关
考点 3
数据结构的基本概念
考点 3 在笔试考试中，在笔试考试中出现的几率为 70%，主要是以选择的形式出现，分 值为 2 分，此考点为识记内容，还应该识记数据的逻辑结构和存储结构的概念。 1.数据结构的基本概念 数据结构是指相互有关联的数据元素的集合，即数据的组织形式。主要研究和讨论以 下三个方面的问题： ① 数据的逻辑结构； ② 数据的存储结构； ③ 对各种数据结构进行的运算。(例如：插入、删除) 研究数据结构主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要 包括两个方面：一是提高数据处理的速度，降低时间复杂度；二是尽量节省在数据处理过 程中所占用的计算机存储空间 (降低空间复杂度) 。 2．什么是数据结构 ？ （1）数据的逻辑结构 所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。 （2）数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称为数据的 物理结构) 3.常见的逻辑结构与存储结构 常见的逻辑结构：集合结构 （各种元素之间无任何关系，仅仅同属于一个集合） 线性结构（线性表，栈，队列，线性链表等） 树状结构（树，二叉树，等） 图状结构或网状结构 常用的存储结构：顺序存储结构、链式存储结构、索引结构
注意：一种数据的逻辑结构根据需要可以表示成多种存储结构，而采用不同的存储结 构，其数据处理的效率是不同的。 4. 逻辑数据结构的图形表示
图1
经典习题
【例题 1】在数据结构中，从逻辑上可以把数据结构分成_______。 A）内部结构和外部结构 B）线性结构和非线性结构 C）紧凑结构和非紧凑结构 D）动态结构和静态结构
解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构 表示数据元素之间为一对多或者多对一的关系，所以答案为B） 。
【例题 2】下列叙述中正确的是______。 A．一个逻辑数据结构只能有一种存储结构 B．数据的逻辑结构属于线性结构,存储结构属于非线性结构 C．一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率 D．一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率 【例题 3】下列描述中正确的是（ ） 。 （2007 年 9 月） A）程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量 D）以上三种说法都不对
解析：数据的存储结构对程序的执行效率有较大影响，例如在有序存储的表中查找某个元素比无序存储的 表中查找运算快得多。除此之外，程序的执行效率也与算法有关。
【例题 4】下列叙述中正确的是（ ） 。 （2008 年 9 月） A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间
解析：顺序存储结构是一种物理结构，表示各个元素在内存单元中的存放地址是连续的。链式存储结构也 是一种物理结构，表示各个元素在内存中存放的位置不一定是连续的。借助一个指针，指向下一元素的位
置。如下图所示：
顺序存储 图2
链式存储
另：顺序存储结构可以存放（表示）线性结构，也可以表示非线性结构。链式存储结构可以存放（表 示）线性结构，也可以表示非线性结构。链式存储结构比顺序存储结构未必节省存储空间。
考点 4
线性结构与非线性结构
考点 4 在笔试考试中，虽然说不是考试经常考查的内容，但读者还是对此考点有所了 解，在笔试考试中出现的几率为 30%，主要是以填空题出现的形式出现，分值为 2 分，此考 点为识记内容。 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类 型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个直接前件，也最多有一个直接后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一 个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。 疑难解答：空的数据结构是线性结构还是非线性结构？ 一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确 定。如果对该数据结构的算法是按线性结构的规则来处理的，则属于线性结构；否则属于 非线性结构。
经典习题
【例题 1】 下列叙述中正确的是 A.有一个以上根结点的数据结构不一定是非线性结构 B.只有一个根结点的数据结构不一定是线性结构 C.循环链表是非线性结构 D.双向链表是非线性结构
（2011 年 3 月）
解析： （非空的）线性结构必须同时满足2个条件：①有且只有一个根节点；②每一个节点最多有一个前驱， 最多有一个后继。所以，B选项是对的，只满足其中条件①，不一定是线性结构。线性结构包括：线性表，
栈，队列，链表结构（单向链表，双向链表，循环链表） ，所以C,D选项是错的。A选项有一个以上根结点 的数据结构一定是非线性结构。
【例题 2】一个空的数据结构是按线性结构处理的，则属于_______。 （答案：线性结构）
解析：一个空的数据结构是线性结构或是非线性结构，要根据具体情况而定。如果对数据结构的运算是按 线性结构来处理的，则属于线性结构，否则属于非线性结构。
考点 5
线性表的概念与基本运算
考点 5 在笔试考试中，在笔试考试中出现的几率为 50%，主要是以选择的形式出现，分 值为 2 分，此考点为识记内容 1. 线性表的基本概 线性表是由 n (n≥0)个数据元素 a1，a2，…，an 组成的一个有限序列，表中的每一个 数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即 线性表或是一个空表（当 n=0） ，或可以表示为(a1,a2,…,ai,…,an) . 非空线性表有如下一些结构特征： ① 有且只有一个根结点 a1，它无前件； ② 有且只有一个终结点 an，它无后件； ③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 2. 线性表的顺序存储结构 在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点： ① 线性表中所有元素据所占的存储空间是连续的； ② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 假设线性表中的第一个数据元素的存储地址为 ADR(a1)，每一个数据元素占 K 个字节， 则线性表中第 i 个元素 ai 在计算机存储空间中的存储地址为 ADR(a1)=ADR(a1)+(i-1)K 3. 线性表的插入运算 在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在 线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。 在 表 的 第 i (1 ≤ i ≤ n+1) 个位 置 ， 插 入一 个 新 元素 X ， 使 长 度 为 n 的 线 性 表 (a1,a2,…,ai,…,an)变成长度为 n+1 的线性表(a1,a2,…ai-1,X,ai+1,…,an+1). 用顺序表作为线性表的存储结构时， 由于结点的物理顺序必须和结点的逻辑 顺 序保持一致， 因此我们必须将原表中位置 n， n-1， …， i 上的结点， 依次后移到位置 n+1， n，…，i+1 上，空出第 i 个位置，然后在该位置上插入新结点 X。 当 i=n+1 时，是指在线性表的末尾插入结点，所以无需移动结点，直接将 X 插入表的 末尾即可。
图3 4. 线性表的删除运算 在平均情况下，要在线性表中删除一个元素，需要移动表中表中一半的元素。因此， 在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的。 是指将表的第 i(1≤i≤n)个元素删去，使长度为 n 的线性表(e1，…, ei-1，ei，ei+1，…， en)变成长度为 n-1 的线性表(e1，…, ei-1， ei+1，…，en)。 例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第 5 个元素， 则需将 第 6 个元素到第 10 个元素依次向前移动一个位置.
图4 由线性表在存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线 性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这 种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入删除的效率 比较低。 注意：线性表也可以采用链式存储结构。见考点7.
经典习题
【例题 1】 在长度为 n 的线性表中， 寻找最大项至少需要比较______次。 (答案:n) 【例题 2】在长度为 n 的顺序存储的线性表中删除一个元素，最坏情况下需要移动表中的元 素个数为 n-1 。 2012 年 3 月 【例题 3】在长度为 n 的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中 n 个元素。 2011 年 9 月
考点 6
栈及队列
考点 6 在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为 100%，主要是 以选择的形式出现，分值为 2 分，此考点为重点掌握内容，应该掌握栈的运算 。 1．栈的基本概念 栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另 一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先 被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈是 按照"先进后出"或"后进先出"的原则组织数据的。
图5 2．栈的顺序存储及其运算 用一维数组 S（1∶m）作为栈的顺序存储空间，其中 m 为最大容量。 在栈的顺序存储空间 S（1∶m）中，S（bottom）为栈底元素，S（top）为栈顶元素。top=0 表示栈空；top=m 表示栈满。 栈的基本运算有三种：入栈、退栈与读栈顶元素。 （1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一（即 top 加 1） ，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最 后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈"上溢"错误。 （2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈 顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减 1（即 top 减 1） 。当栈顶指 针为 0 时，说明栈空，不可进行退栈操作。这种情况称为栈的"下溢"错误。 （3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除 栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为 0 时，说明栈 空，读不到栈顶元素。 小技巧：栈是按照"先进后出"或"后进先出"的原则组织数据，但是出栈方式有多种选择， 在考题中经常考查各种不同的出栈方式。 3. 队列的基本概念 队列（Queue）是运算受到限制的一种线性表。只允许在表的一端进行插入，而在另一 端进行删除元素的，且先进先出（First In First Out，简称 FIFO 结构）或后进后出（Last In Last Out）的线性表，简称 LILO 结构。队尾（rear）是允许插入的一端。队头（front） 是允许删除的一端。空队列是不含元素的空表。 基本运算:入队运算和退队运算
图6 4. 循环队列 把队列的存储空间设想成一个头尾相接的环状结构，最后一个位置连接第一个位置:
图7
怎样计算循环队列的元素个数？ 队列头指针为 front， 队列尾指针为 rear， 队列容量为 M， 则元素个数为|rear-front+M|%M, 注意，这个%是求余运算。 例如：设循环队列的存储空间为 Q(1：30)，初始状态为 front=rear=30。现经过
一系列入队与退队运算后，front=16，rear=15，则循环队列中有 素。 经典习题
【例题 1】下列关于栈叙述正确的是 A. 栈顶元素最先能被删除 B. 栈顶元素最后才能被删除 C. 栈底元素永远不能被删除 D. 以上三种说法都不对
解析：栈（stack）是限定在一端进行插入和删除的线性表。在栈顶允许插 入和删除元素，在栈底不允许插入和删除数据元素。栈顶的元素是最后被插 入的，从而也是最先被删除的元素，遵循“后进先出”或“先进后出”的原 则。
个元
（2011 年 3 月）
【例题2】下列关于栈的叙述正确的是______。 A．栈是非线性结构 B．栈是一种树状结构 C．栈具有"先进先出"的特征 D．栈具有"后进先出"的特征 【例题3】下列叙述中正确的是 A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D）上述三种说法都不对 【例题4】一个栈的初始状态为空。首先将元素5，4，3，2，1 依次入栈，然后退栈一次， 再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的 元素） 的顺序为____。 （答案： 1DCBA2345） 【例题5】一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依 次退队，则元素退队的顺序为 。 （答案：ABCDEF54321） 【例题6】以下_______不是栈的基本运算。 A）判断栈是否为素空 B）将栈置为空栈 C）删除栈顶元素 D）删除栈底元素
解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶 元素等，对栈的操作都是在栈顶进行的。
【例题 7】下列叙述中正确的是 。 （2008 年 9 月） A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 B）在循环队列中，只需要队头指针就能反映队列的中元素的动态变化情况 C）在循环队列中，只需要队尾指针就能反映队列的中元素的动态变化情况 D）循环队列中元素的个数是由队头指针和队尾指针共同决定
考点 7
线性链表的基本概念
考点 7 在笔试考试中出现的几率为 30%，主要是以选择的形式出现，分值为 2 分，此考 点为识记内容。重点识记结点的组成。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称 为数据域，另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后 一个结点（即前件或后件） 。 链式存储方式既可用于表示线性结构，也可用于表示非线性结构。 （1）线性链表 线性表的链式存储结构称为线性链表。 在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向 其前件结点；另一个称为右指针，用以指向其后件结点。这样的表称为双向链表。
图9 （2）带链的栈 栈也是线性表，也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中 所有空闲的存储结点，这种带链的栈称为可利用栈。 疑难解答：在链式结构中，存储空间位置关系与逻辑关系是什么？ 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与 数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
经典习题
【例题 1】下列叙述中正确的是
A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D）上述三种说法都不对
【例题 2】设某循环队列的容量为 50，如果头指针 front=45（指向队头元素的前一位置） ， 尾指针 rear=10（指向队尾元素） ，则该循环队列中共有 个元素。 （答案 15） 【例题 3】链表不具备的特点是_______。 A）可随机访问任意一个结点 B）插入和删除不需要移动任何元素 C）不必事先估计存储空间 D）所需空间与其长度成正比
解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所以 答案为A） 。
【例题 4】下列对于线性链表的描述中正确的是（ ） 。 A）存储空间不一定连续，且各元素的存储顺序是任意的 B）存储空间不一定连续，且前件元素一定存储在后件元素的前面
C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的
解析：见图2.
【例题 2011-9】下列关于线性链表叙述中，正确的是 A)各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致 B)各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续 C)进入插入与删除时，不需要移动表中的元素 D)以上三种说法都不对 【例题 13】下列描述中正确的是（ ） 。 A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构
解析: 线性表，栈，队列，线性链均为线性结构,二叉树是非线性结构
考点 8：树与二叉树
考点 8 在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为 100%，主要是 以选择的形式出现，有时也有出现在填空题中，分值为 2 分，此考点为重点掌握内容。重 点识记树及二叉树的性质。 误区警示： 满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。应该注意二者的区别。
1.树的基本概念 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点， 简称为树的根。 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结 点。 在树结构中，一个结点所拥有的后件个数称为该结点的度 在树中，所有结点中的最大的度称为树的度。 根结点在第 1 层。 树的最大层次称为树的深度。 2. 二叉树及其基本性质 二叉树具有以下两个特点： ① 非空二叉树只有一个根结点； ② 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 3. 二叉树的基本性质 (★★★) 性质 1 在二叉树的第 K 层上，最多有 2
m K-1
(K≥1)个结点。
性质 2 深度为 m 的二叉树最多有 2 -1 个结点。 性质 3 在任意一棵二叉树中，度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个。 性质 4：具有 N 个结点的二叉树，其深度至少为［log2N］+1，其中［log2N］表示取 log2N 的整数部分。 4. 满二叉树与完全二叉树 (1)满二叉树
所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点，这就是 说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第 K 层上有 2K-1 个结点，且深度 为 m 的满二叉树有 2m-1 个结点。 (2)完全二叉树 所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上 只缺少右边若干结点。 满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。 性质 5: 具有 n 个结点的完全二叉树的深度为［log2n］+1。 性质 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；否则该结点无右子结点。 5. 二叉树的存储结构 ——在计算机中，二叉树通常采用链式存储结构。 6.二叉树的遍历 (★★★) 二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。 （1）前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时， 仍然先访问根结点，然后遍历左子树，最后遍历右子树。 （2）中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时， 仍然先遍历左子树，然后访问根结点，最后遍历右子树。 （3）后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时， 仍然先遍历左子树，然后遍历右子树，最后访问根结点。
经典习题
【例题 1】某二叉树共有 7 个结点,其中叶子结点只有 1 个,则该二叉树的深度为(假设根结 点在第 1 层) . （2011 年 3 月） A)3 B)4 C)6 D)7
解析：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相 交的左右子树组成，并且左右子树都是二叉树。二叉树的子树有左右之分，其次序不能任意颠倒； （a）～ （e）是二叉树的5种形式：
（a）是空树，(b)只有一个根结点的二叉树；(c)只有左子树；(d)只有右子树；(e)完全二叉树；没有非 空子树的结点称为叶结点，例如B,C节点，即没有下层左右子树的节点； 该题的结构图为： 二叉树中由叶子节点、度为1的结点和度为2的结点组成。叶子节点比度为2的结点多一 个，因此该二叉树没有度为2的结点，所以全由度为1的结点构成，就像一条线，无分叉， 因此深度为7。
A B C D E F G
【例题 2】一棵二叉树的中序遍历结果为 DBEAFC,前序遍历结果为 ABDECF 则后序遍历结果 为 。 （答案：DEBFCA）
解析：根据前序判断根节点，根据中序判断左，右子树，构建正确的树结构，如下：
A B D E F C
【例题 3】一棵二叉树有 10 个度为 1 的结点，7 个度为 2 的结点，则该二叉树共有_____个 结点。 (答案:25)
解析:本题考查二叉树的性质,度为0的叶子节点总是比度为2的节点多一个;二叉树中总的节点数=叶子节 点数+度为1的节点个数+度为2的节点个数.
【例题 4】设二叉树如下：
A
B
C
D
F
E 对该二叉树进行后序遍历的结果为
G 。
H
（答案：EDBGHFCA ）
【例题 5】已知某二叉树的后序遍历序列是 DACBE，中序遍历序列是 DEBAC，则它的前序遍 历序列是_______。 A）ACBED B）DEABC C）DECAB D）EDBAC
解析：后序遍历的顺序是"左子树－右子树－根结点"；中序遍历顺序是"左子树－根结点－右子树"；前序 遍历顺序是"根结点－左子树－右子树"。根据各种遍历算法，不难得出前序遍历序列是EDBAC。所以答案 为D） 。
【例题6】一棵二叉树第6层(根结点为第1层)的结点数最多为______个。
（答案：32 ）
【例题7】设树Ｔ的度为４，其中度为１、２、３和４的结点的个数分别为４、２、１、１， 则Ｔ中叶子结点的个数为_______。
答案：8
解析：根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和加１。 因此树的结点数为１×４＋２×２＋３×１＋４×１＋１＝16。叶子结点数目等于树结点总数减去度不为 ０的结点数之和，即16－（４＋２＋１＋１）＝８。
【例题8】一棵二叉树中共有 70 个叶子结点与 80 个度为１的结点，则该二叉树中的总结 点数为（ ） 。 A）219 B）221 C）229 D）231
解析：根据二叉树的性质：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个， 即有71个度为2的结点，二叉树中总的节点数=叶子节点数+度为1的节点个数+度为2的节点个数.所以，结 点总数为70+80+69=219.
【例题9】下列关于二叉树的叙述中，正确的是 （2011年9月） A)叶子结点总是比度为2的结点少一个 B)叶子结点总是比度为2的结点多一个 C)叶子结点数是度为的结点数的两倍 D)度为2的结点数是度为1的结点数的两倍 【例题 10】一棵二叉树共有 25 个结点，其中 5 个是叶子结点，则度为 1 的结点数为___ A)4 B)16 C)10 D)6 （2012 年 3 月）
考点 9
顺序查找
考点 9 在笔试考试中考核几率在 30%，一般出现选择题中，分值为 2 分，读者应该具体 掌握顺序查找的算法。
查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始，依次将线性表 中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了 比较但都不相等，则表示查找失败。 在下列两种情况下也只能采用顺序查找： （1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。 （2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 补充：最好情况下，比较 1 次，最差比较 n 次，平均情况下比较（n+1）/2 次。
考点 10
二分法查找
考点 10 在笔试考试中考核几率为 30%，一般出现填空题中，分值为 2 分，考核比较多 查找的比较次数，读者应该具体掌握二分查找法的算法。
二分法只适用于顺序存储的，按非递减排列的有序表，其方法如下： 设有序线性表的长度为 n，被查找的元素为 i， （1）将 i 与线性表的中间项进行比较； （2）若 i 与中间项的值相等，则查找成功； （3）若 i 小于中间项，则在线性表的前半部分以相同的方法查找； （4）若 i 大于中间项，则在线性表的后半部分以相同的方法查找。 疑难解答：二分查找法适用于哪种情况？ 二分查找法只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即 从小到大，但允许相邻元素值相等） 。 这个过程一直进行到查找成功或子表长度为 0 为止。 对于长度为 n 的有序线性表， 最好情况下， 比较 1 次，在最坏情况下， 二分查找只需要比较 log2n 次。 平均比较 log2（n+1）-1 次。显然，当有序线性表为顺序存储时都能采用二分查找，并且，二分查找的效 率要比顺序查找高得多。 可以证明， 对于长度为 n 的有序线性表， 在最坏情况下， 二分查找只需要比较 log2n 次，而顺序查找需要比较 n 次。
经典习题
【例题 1】有序线性表能进行二分查找的前提是该线性表必须是 存储的。 （答案：顺序） 【例题 2】设有一个已按各元素的值排好序的线性表（长度大于 2） ，对给定的值 k，分别用 顺序查找法和二分查找法查找一个与 k 相等的元素，比较的次数分别是 s 和 b，在查找不成 功的情况下，s 和 b 的关系是_______。 A）s=b B）s>b C）s解析：对于顺序查找，查找不成功时和给定关键字比较的次数为 n。二分查找查找不成功的关键字比
较次数为［log2n］+1。当 n≥2 时，显然 n>［log2n］ 。
【例题 3】二分法查找的存储结构仅限于_______且是有序的。答案：顺序存储结构
解析：二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须 用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可） 。
第二部分：程序设计基础
详细重点学习知识点：
1．结构化程序设计方法的四个原则 2．对象、类、消息、继承的概念、类与实例的区别
考点 1
结构化程序设计的原则
考点 1 在笔试考试中出现的几率为 30%，主要是以选择题的形式出现，分值为 2 分，此 考点为识记内容，读者应该识记结构化程序设计方法的四个主要原则。 20 世纪 70 年代提出了"结构化程序设计"的思想和方法。 结构化程序设计方法引入了工 程化思想和结构化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方 法的主要原则为：自顶向下、逐步求精、模块化和限制使用 goto 语句。 疑难解答：如何进行自顶向下设计方法？ 程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标；不要 一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。
经典习题
【例题 1】结构化程序所要求的基本结构不包括 （2011 年 3 月） A)顺序结构 B)GOTO 跳转 C)选择(分支)结构 D)重复(循环)结构 【例题 2】在结构化设计方法中生成的结构图(SC)中，带有箭头的连线表示 。 A．模块之间的凋用关系 B．程序的组成成分 C．控制程序的执行顺序 D．数据的流向
【参考解析】 【命题目的】让考生对常用的软件结构设计工具要有较深入的了解。 ： 【解题要点】常用的软件结构设计工具是结构图(SC-Structure Chart)、也称程序结构图。其中，矩形内 用于注明模块的功能和名字；箭头表示模块间的调用关系，带实心圆的箭头表示传递的是控制信息，带空 心圆的箭头表示传递的是数据。 【考点链接】根据结构图设计思想，了解结构图构成的基本形式。
【例题 3】仅由顺序、选择（分支）和重复（循环）结构构成的程序是___程序。 (答案: 结构化) 【例题 4】下列程序段的输出结果是 ACCEPT TO A IF A=[123] S=0 ENDIF S=1 ？S A)0 B)1 C)123 D)由 A 的值决定 【例5】结构化程序设计方法提出于_______。 （考点1） A）20世纪50年代 B）20世纪60年代
C）20世纪70年代
D）20世纪80年代
解析：20世纪70年代提出了"结构化程序设计（structured programming）"的思想和方法。结构化程 序设计方法引入了工程化思想和结构化思想，使大型软件的开发和编程得到了极大的改善。
【例6】结构化程序设计方法的主要原则有下列4项，不正确的是_______。 A）自下向上 B）逐步求精 C）模块化 D）限制使用goto语句
解析：结构化程序设计方法的主要原则为： （1）自顶向下：即先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。 （2）逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。 （3）模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标 称为一个模块。 （4）限制使用goto语句。
考点 2
面向对象方法的基本概念
考点 2 在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为 70%，主要 是以填空题的形式出现，分值为 2 分，此考点为重点识记内容，读者应该识记几个基本要 素的定义、对象的特征以及消息、继承、类的定义。 误区警示： 当使用"对象"这个术语时，既可以指一个具体的对象，也可以泛指一般的对象，但是 当使用"实例"这个术语时，必须是指一个具体的对象。 面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 （1）对象 通常把对对象的操作也称为方法或服务。 属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改 变。属性值应该指的是纯粹的数据值，而不能指对象。 操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。 对象具有如下特征：标识惟一性、分类性、多态性、封装性、模块独立性。 （2）类和实例 类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的 性质，而一个对象则是其对应类的一个实例。 类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法 操作。 （3）消息 消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统 一了数据流和控制流。 一个消息由三部分组成：接收消息的对象的名称、消息标识符（消息名）和零个或多 个参数。 （4）继承 广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。在面向 对象的软件技术中，集成是指子类自动地共享基类中定义的数据和方法的机制。 继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树 形结构。多重继承是指，一个类允许有多个父类。 （5）多态性 对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同 的行动，该现象称为多态性。 疑难解答：能举一下现实中的对象及其属性和操作吗？
一辆汽车是一个对象，它包含了汽车的属性（如颜色、型号等）及其操作（如启动、 刹车等）。一个窗口是对象，它包含了窗口的属性（如大小、颜色等）及其操作（如打开、 关闭等）。
典型习题
【例题 1】 定义无符号整数类为 UInt,下面可以作为类 T 实例化值的是 A)-369 B)369 C)0.369 D)整数集合｛1,2,3,4,5｝
的实例。选择 B。 （2011 年 3 月）
解析：UInt 是一个无符号整数类，描述所有无符号整数的性质。因此任何无符号整数都是该类的一个具体
【例题 2】面向对象方法中，继承是指 （2010 年 9 月） A）一组对象所具有的相似性质 B）一个对象具有另一个对象的性质 C）各对象之间的共同性质 D）类之间共享属性和操作的机制 【例题 3】在 Visual FoxPro 中，下面关于属性、事件、方法叙述错误的是 A)属性用于描述对象的状态 B)方法用于表示对象的行为 C)事件代码也可以象方法一样被显式调用 D)基于同一个类产生的两个对象的属性不能分别设置自己的属性值 【例题4】面向对象的开发方法中，类与对象的关系是_______。 （考点2） A）抽象与具体 B）具体与抽象 C）部分与整体 D）整体与部分
解析：现实世界中的很多事物都具有相似的性质，把具有相似的属性和操作的对象归为类，也就是说 类是具有共同属性、共同方法的对象的集合，是对对象的抽象。它描述了该对象类型的所有对象的性质， 而一个对象则是对应类的一个具体实例。所以本题正确答案为A）项。
【例题 5】在面向对象方法中，______描述的是具有相似属性与操作的一组对象。 答案:类 【例题 6】在面向对象方法中，类的实例称为______。 答案:对象 【例题 7】在面向对象方法中，使用已经存在的类定义作为基础建立新的类定义，这样的技 术叫做_______。 （答案：继承）
解析：继承是面向对象方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已 有的类可当作基类来引用，则新类相应地可当作派生类来引用。
【例题 8】对象的基本特点包括_______、分类性、多态性、封装性和模块独立性好等 5 个 特点。 （答案：标识惟一性）
解析：对象具有如下的基本特点： （1）标识惟一性。对象是可区分的，并且由对象的内在本质来区分； （2）分类性。可以将具有相同属性和操作的对象抽象成类； （3）多态性。同一个操作可以是不同对象的行为； （4）封装性。只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法； （5）模块独立性。面向对象是由数据及可以对这些数据施加的操作所组成的统一体。
【例题 9】对象根据所接收的消息而做出动作，同样的消息被不同的对象所接收时可能导致 完全不同的行为，这种现象称为_______。 （答案：多态性）
解析：对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为， 该现象称为多态性。
第三部分：软件工程基础
详细重点学习知识点：
1．软件的概念、软件生命周期的概念及各阶段所包含的活动 2．概要设计与详细设计的概念、模块独立性及其度量的标准、详细设计常用的工具 3．软件测试的目的、软件测试的4个步骤 4．软件调试的任务
考点解读 考点1 软件定义与软件特点
考点 1 在笔试考试中，是一个经常考查的内容，考核的几率为 70%，主要是以选择题的 形式出现，分值为 2 分，此考点为识记内容，读者应该识记软件的定义，特点及其分类。 1.软件的定义 软件指的是计算机系统中与硬件相互依存的另一部分，包括程序、数据和相关文档的 完整集合。程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算 机执行的指令序列。数据是使程序能正常操纵信息的数据结构。文档是与程序的开发、维 护和使用有关的图文资料。可见，软件由两部分组成： （1）机器可执行的程序和数据； （2）机器不可执行的，与软件开发、运行、维护、使用等有关的文档。 2. 软件的特点： （1）软件是逻辑实体，而不是物理实体，具有抽象性； （2）没有明显的制作过程，可进行大量的复制； （3）使用期间不存在磨损、老化问题； （4）软件的开发、运行对计算机系统具有依赖性； （5）软件复杂性高，成本昂贵； （6）软件开发涉及诸多社会因素。 根据应用目标的不同，软件可分应用软件、系统软件和支撑软件（或工具软件）。
小提示：应用软件是为解决特定领域的应用而开发的软件；系统软件是计算机管理自身资源，提高计 算机使用效率并为计算机用户提供各种服务的软件；支撑软件是介于两者之间，协助用户开发软件的工具 性软件。
考点2
软件工程过程与软件生命周期
考点 2 在笔试考试中，在笔试考试中出现的几率为 30%，主要是以选择题的形式出现， 分值为 2 分，此考点为识记内容，应该识记软件生命周期的定义，主要活动阶段及其任务。 软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。一般包 括可行性分析研究与需求分析、设计、实现、测试、交付使用以及维护等活动，如图 3－1 所示。
还可以将软件生命周期分为如上图所示的软件定义、软件开发和软件运行维护 3 个阶 段。 生命周期的主要活动阶段是：可行性研究与计划制定、需求分析、软件设计、软件实 施、软件测试及运行与维护。
典型习题
【例题 1】 在软件开发中,需求分析阶段产生的主要文档是 A)软件集成测试计划 B)软件详细设计说明书 C) 用户手册 D)软件需求规格说明书
（2011 年 3 月）
解析：需求分析阶段编写软件需求规格说明书；软件实现阶段编写用户手册；软件设计阶段编写概要 设计说明书、详细设计说明书和软件测试计划初稿；软件测试阶段编写软件集成测试分析报告；
【例题 2】软件生命周期是指 A）软件产品从提出、实现、使用维护到停止使用退役的过程 B）软件从需求分析、设计、实现到测试完成的过程 C）软件的开发过程 D）软件的运行维护过程
解析：本题考核软件生命周期的定义：软件产品从提出、实现、使用维护到停止使用退役的过程称为 软件生命周期。一般包括可行性分析研究与需求分析、设计、实现、测试、交付使用以及维护等活动。所 以选项为A） 。
【例题3】下列描述中正确的是______。 A．软件工程只是解决软件项目的管理问题 B．软件工程主要解决软件产品的生产率问题 C．软件工程的主要思想是强调在软件开发过程中需要应用工程化原则 D．软件工程只是解决软件开发中的技术问题 【例题 4】软件按功能可以分为：应用软件、系统软件和支撑软件(或工具软件)。下面属于 系统软件的是 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.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件；
四川省中小学公开招聘教师教育公共基础笔试和复习大纲（详解） 本大纲仅供参加四川省中小学公开招聘教师公共科目——《教育公共基础笔试》的考生复习和考试时参考。请考生重点掌握以下知识内容。《教育公共基础笔试》题型包括选择、判断简析、案例分析、阅读分析和论述五种类型。 第一部分教育学基础 一、教育与教育学 （一）*1．教育的概念：广义教育，泛指凡是能够增长人的知识和技能，正面影响人的思想品德，提高人的认识能力，增强人的体质，完善人的个性的一切活动。 狭义教育，即学校教育，是教育者根据社会发展的要求，在特定的教育场所，有目的、有计划、有组织的对受教育者的身心施加影响，以使他们的身心朝着社会期望的方向发展的过程。（组织性、计划性、目的性，专业的师资和场地，系统的教育与教学组织的规范） P3 *2.教育的要素：教育者、受教育者、教育影响P3 2.2三者关系：教育的三要素之间既相互独立，又相互制约，构成完整的教学实践系统，缺一不可。教育者按一定的目的和要求改变受教育者，教育者与受教育者之间相互作用；教育者与受教育者之间在作用与联系是以一定的教育影响为中介的；三者之间相互联系和作用的结果使受教育者发生合乎目的的变化。 3.教育的形态：制度化教育与非制度化教育；社会教育、家庭教育和学校教育；原始社会的教育、古代社会的教育与近代社会的教育。 P4 4.教育的本质：教育的本质是有目的、有计划、有组织地培养人的社会实践活动，即根据一定的社会需要进行的培养人的活动，也是教育的质的规定性。P5 5.教育的基本规律：教育最基本规律有两条。一条是关于教育与社会发展关系的规律，我们称之为教育的外部关系规律；一条是关于教育和人的发展关系的规律，我们称之为教育的内部关系规律。 P6 （二）6.教育发展的历史阶段：*[教育的起源：1）神话起源说2）生物起源说：法国利托尔诺；英国沛西〃能3）心理起源说：美国孟禄4）劳动起源说]（1）原始社会（无阶级性、水平低下、传递生产经验、言传身教、耳口相传），（2）古代社会（鲜明的阶级性、道统性、专制性、刻板性、教育的象征功能占主导地位），（3）现代教育（国家加强了对教育的重视和干预，公立教育崛起、初等义务教育的普及、教育的世俗化、重视教育立法，以法治教） P7 7.教育改革和发展的趋势：终身化、全民化、民主化、多元化、手段和技术现代化P8 （三）教育学的产生和发展 8．教育学：教育学是通过对教育现象和教育问题的研究，去揭示教育规律的一门科学。 P9 9.教育学的基本问题：（1）教育本质，解释教育与社会的关系问题，（2）教育与人的发展关系问题，（3）教育目的问题，（4）教育制度问题，（5）教育过程的规律性问题，（6）思想品德教学过程的基本规律性问题，（7）学校管理问题。P10 *10.教育学的产生与发展：（1）萌芽时期：奴隶社会和封建社会的教育学（《学记》世界上最早的教育专著，昆体良的《雄辩术原理》（《论演说家的教育》）是西方第一部教育著作）。（2）独立形态时期：夸美纽斯的《大教学论》标志独立
第一章数据结构 一、选择题 （1）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 【答案】A 【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大．但允许相邻元素值相等)的。选项A正确。 （2）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 【答案】C 【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项A、选项B和选项D错误，正确答案是选项C。 （3）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 【答案】D 【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。 (4)算法执行过程中所需要的存储空间称为算法的 A）时间复杂度B）计算工作量C）空间复杂度D）工作空间 【答案】c 【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。 (5)下列关于队列的叙述中正确的是 A）在队列中只能插入数据B）在队列中只能删除数据 C）队列是先进先出的线性表D）队列是先进后出的线性表 【答案】c 【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。 (6)设有下列二叉树： A
全国计算机二级考试公共基础知识总结 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由
2016 年最新四川教师招聘考试备考资料：教育公共基础知识点重点、 记忆难点汇总（一） 第一章教育与教育学 1、实用主义教育学是在批判以赫尔巴特为代表的传统教育学的基础上提出是发展起来的。实用主义教育学是以实用主义作为哲学基础和理论依据。 2、教育学研究的对象是教育现象，重点是研究教育问题，目的是揭示教育规 律。 3、学校教育在人的发展中起主导作用。 4、教育史上最早出现的的教学组织形式是个别教学制。其显着优点是教师能根据学生的特点因材施教，使教学内容、进度较好地适应于每一个学生的接受能力。但是教学规模小、教学成本高、教学效益低。 5、教育内容是教育者与受教育者共同认识的客体。 6、教育学的研究对象是以“教育事实”为基础，在教育价值观引导下形成的“教育问题”。 7、教育的历史时代性是指在不同社会或者同一社会的不同历史时期，教育的性质、目的、内容等各不相同。教育学萌芽阶段及人物思想： 8、孔子的教育思想记载在《论语》中。具体有： a “有教无类”；b、“非礼 勿视，非礼勿听，非礼勿言，非礼勿动”；c、“博学于文，约之以礼”；d、不愤不启，不悱不发（启发一词的来源）；A e、“学而不思则罔，思而不学则殆”；f、因材施教（“孔子施教，各因其材”一一朱熹）；g、知之为知之，不知为不知，是知也一一求学要实事求是；h、学而时习之、温故而知新一一巩固性原则。
9、《礼记》中的《学记》是人类历史上最早出现专门论述教育问题的着作，被 a、“化民成俗，其必由学”“建国军民，教学为先”，指出 称为“教育学的雏形” 教育的重要性和教育与政治的关系；b、“时教必有正业，退息必有居学” “臧息 相辅”指出了课内与课外相结合；c 、“道而弗牵，强而弗抑，开而弗达”启发教学；d、“学不躐等”“不陵节而施循序渐进；e、教学相长新课程师生关系；f、 长善救失利用积极因素克服消极因素原则。 10、荀子言：“师术有四，而博习不予焉。严师而惮，可以为师；耆艾而信，可以为师；诵说而不陵不犯，可以为师；知微而论，可以为师”。 11 、苏格拉底是历史上最早的专家治国论者，提出了“苏格拉底教学法”，又称“问答法” 和“产婆术”，是一种启发式教学。“苏格拉底教学法”可分为四步：讥讽、助产术、归纳和下定义。提出了美德是否可教； 12、柏拉图，《理想国》。 13、亚里士多德不仅最早明确地提出了体育、德育和智育的划分，而且也是最早根据儿童身心发展的特点提出按年龄划分教育阶段的主张。他把每一个人的教育阶段按每七年为一个阶段来划分，这也成为后来强调注重人的发展的思想渊源。认为追求理性就是追求美德。《政治学》。 14、古罗马昆良体，《演说家的教育》（又译为《雄辩术原理》），是西方最早的教育论着。教育学创立或初步建立阶段及人物思想： 15、培根，在《论科学的价值和发展》（1623）一文中，首次把“教育学”作为一门独立的学科提出。 16、1632 年捷克教育家夸美纽斯在《大教学论》书中，提出了系统的教育目的论、方法
1.1 算法 考点1 算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括“与”、“或”、“非”等运算； ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法 计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2)归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
公共基础知识总结 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。
线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 1．4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 循环队列：s=0表示队列空，s=1且front=rear表示队列满 1．5 线性链表 数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
教育公共基础知识整理 教育公共基础知识整理 (1) 第一部分教育学基础 (3) 第一章教育与教育学 (3) 第一节教育概述 (3) 第二节教育的发展 (4) 第三节教育学的产生和发展 (5) 第二章教育的功能 (7) 第一节教育功能概述 (7) 第二节影响教育功能发挥的因素 (7) 第三章教育的目的 (8) 第一节教育目的的含义及其功能 (8) 第二节教育目的的确立 (8) 第三节我国的教育目的 (8) 第四章教师与学生 (9) 第一节教师 (9) 第二节学生 (10) 第三节教育过程中的教师与学生 (10) 第四节教育过程中的师生关系 (10) 第五章课程 (11) 第一节课程概述 (11) 第二节课程改革 (13) 第三节新课程带来的变革 (14) 第六章、课堂教学 (15) 第一节教学 (15) 第二节课堂教学设计 (17) 第三节教学策略 (18) 第七章、学校德育 (19) 第一节德育的含义、功能及地位 (19) 第三节德育过程 (19) 第三节德育的任务、目标、内容与课程 (20) 第四节德育的原则、方法与途径 (20) 第八章、班级管理与班主任工作 (21) 第一节班级概述 (21) 第二节班级管理的内容与原则 (21) 第三节班主任工作 (22) 第二部分教育心理学 (22) 第一章心理发展与教育 (22) 第一节心理发展概述 (22) 第二节心理发展理论 (22) 第三节心理发展与教育 (24)
第四节儿童、青少年的心理发展与教育 (24) 第二章学习与学习理论 (25) 第一节学习概述 (25) 第二节学习理论 (25) 第三章学习迁移、记忆和遗忘 (30) 第一节学习迁移 (30) 第二节记忆 (31) 第三节遗忘 (32) 第四章学习策略与不同类型的学习 (33) 第一节学习策略 (33) 第二节知识 (34) 第三节技能 (36) 第四节问题解决 (36) 第五节品德 (37) 第五章影响学习的心理因素 (38) 第一节学习动机 (38) 第二节归因 (39) 第三节注意 (40) 第六章个别差异与教育 (40) 第一节人格差异 (40) 第二节认知差异 (41) 第三节学困生 (41) 第七章学生心理健康教育 (42) 第一节心理健康概述 (42) 第二节学校心理健康教育的基本内容和具体方法 (42) 第三部分教育法学 (44) 第一章法与教育法 (44) 第一节法的概述 (44) 第二节教育法与教育法规 (44) 第二章教育法律关系 (45) 第一节教育法律关系的含义及其特征、类型 (45) 第二节教育法律关系的产生、变更和消灭 (46) 第三节教育法律关系的主体和客体 (46) 第四节教育法律关系的内容、权利和义务 (46) 第三章教育法律规范 (47) 第一节教育法律规范的含义及其类型 (47) 第二节教育法规与教育道德 (47) 第三节教育法规与教育政策 (48) 第四章教育法制过程 (48) 第一节教育立法 (48) 第二节教育法规实施 (48) 第三节教育行政执法 (49) 第四节法律制裁 (49) 第五章教育法律责任 (50)
全国计算机等级考试二级公共基础知识复习资料 全国计算机等级考试二级公共基础知识复习资料 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
第一章数据结构与算法 算法 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)的线性表。 线性链表
全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 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、制度化教育阶段开始于：近代。 2、各国的学校教育系统基本形成于：19世纪末。 3、现在世界上大多数国家的义务教育年限在：9年或9年以上。 4、“不愤不启，不悱不发”启发教学法的最早倡导者是：孔子。 5、“建国君民，教学为先”提示了教育的重要性和教育与政治的关系。 6、建国初期，对我国教育理论体系影响较大的苏联教育家是：凯洛夫。 7、狭义的教育主要是指：学校教育。产生于奴隶社会初期。 8、古代中国学校教育的主要内容是六艺，它包括：礼、乐、射、御、书、数。 9、在古代印度，能够享受最好教育的是当时的最高种姓——婆罗门。 10、制度化教育或正规教育形成的主要标志是形成近代的：学校教育系统。 11、中国的科举制度开始于：隋唐时期。 12、战国后期，我国出现的具有世界影响的教育文献——《学记》。
13、在古希腊，最早提出发现法的大教育家——苏格拉底。 14、古希腊著名思想家柏拉图的教育代表作：《理想国》。 15、在人类教育史上首次提出“教育遵循自然”学说的教育思想家是古希腊——亚里士多德。 16、教育学作为一门独立的学科萌芽于：资本主义社会初期夸美纽斯的《大教育学论》。(首先提出普及教育思想的教育家及其著作) 17、强调教育学的心理学和伦理学基础，奠定了科学教育学基础的教育家：赫尔巴特。 18、资产阶级传统教育学的代表人物：赫尔巴特。 19、20世纪初实用主义教育学的代表人物和作品：杜威《民本主义与教育》。 20、主张教师应以学生的发展为目的，以儿童中心主义著称的美国教育家：杜威。实用主义 21、制度化的教育是指具有：层次结构和年龄分级的教育制度。 22、普通教育主要是指以升学为目标，以（基础科学知识）为主要教学内容的学校教育。 23、职业教育是以生产劳动知识和技能为主要教学内容，以（就业）为主要目标的学校教育。
2017计算机二级公共基础知识完整
第一章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。 详细重点学习知识点： 1．算法的概念、算法时间复杂度及空间复杂度的概念 2．数据结构的定义、数据逻辑结构及物理结构的定义 3．栈的定义及其运算、线性链表的存储方式 4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5．二分查找法 6．冒泡排序法 1.1 算法 考点1 算法的基本概念 考试链接： 考点1在笔试考试中考核的几率为30% ，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法的基本要素：
（1）算法中对数据的运算和操作一个算法由两种基 本要素组成：一是对数据对象的运算和操作；二是算 法的控制结构。在一般的计算机系统中，基本的运算 和操作有以下4类：算术运算、逻辑运算、关系运算 和数据传输。 （2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接： 考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70% ，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度算法的时间复杂度是指执行算 法所需要的计算 工作量。 同一个算法用不同的语言实现，或者用不同的编译 程序进行编译，或者在不同的计算机上运行，效率均不 同。这表明使用绝对的时间单位衡量算法的效率是不合 适的。撇开这些与计算机硬件、软件有关的因素，可 以认为一个特定算法" 运行工作量" 的大小，只依赖 于问题的规模（通常用整数n表 示），它是问题规模的函数。即算法的工作量=f（n） 2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存
二级公共基础知识分类模拟题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.当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性 表，在最坏的情况下二分法查找只需要比较log2n次，而顺序查找需要比较n次。 4.链式存储结构既可以针对线性结构也可以针对非线性结构。 链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间。 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。 5.数据流图中带箭头的线段表示的是数据流，即沿箭头方向传送数据的通道一般在旁边标 注数据流名。 程序流程图中带有箭头的线段表示的是控制流。 6.在软件开发中，需求分析阶段可以使用的工具有数据流图DFD图，数据字典DD，判定 树与判定表。 7.“对象”有如下一些基本特点：标识唯一性，分类型，多态性，封装性，模块独立性好。 8.数据管理发展至今已经历了三个阶段：人工管理阶段，文件系统阶段和数据库系统阶段。 其中最后一个阶段结构简单，使用方便，逻辑性强，物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位。 9.自然链接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性 组，并且在结果中把重复的属性列去掉。 10.内存又称主存，是CPU能直接寻址的存储空间，由半导体器件制成。内存的特点是存取 速率快。所以微机中访问速度最快的存储器是内存。 11.计算机能直接识别和执行的语言是机器语言，机器语言是用二进制代码表示的计算机能 直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活，直接执行和速度快等特点。 12.1MB=1024KB=1024*1024B=220B 13.Internet的四层结构分别是：网络接口层，网络层，传输层和应用层。 14.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 15.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表。 16.二叉树的基本性质：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一 个。 例如:某二叉树有五个度为2的结点，则该二叉树中的叶子结点数是5+1=6个。 17.冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n-1)/2次，而堆 排序在最坏的情况下需要比较的次数是nlog2n，即在排序方法中，最坏情况下比较次数最少的是堆排序。 18.软件按功能可分为：应用软件，系统软件和支撑软件（或工具软件）。 19.软件测试的目的是为了发现错误而执行程序的过程，并不涉及改正错误。 程序调试的基本步骤有：错误定位，修改设计和代码，以排除错误进行回归测试，防止引进新的错误。程序调试通常称为Debug,即排错。 20.软件测试的基本准则有：所有测试都应追溯到需求，严格执行测试计划，排除测试的随 意性，充分注意测试中的群集现象，程序员应避免检查自己的程序，穷举测试不可能，
教育公共基础知识——基本知识 1、制度化教育阶段开始于：近代。 2、各国的学校教育系统基本形成于：19世纪末。 3、现在世界上大多数国家的义务教育年限在：9年或9年以上。 4、“不愤不启，不悱不发”启发教学法的最早倡导者是：孔子。 5、“建国君民，教学为先”提示了教育的重要性和：教育与政治的关系。 6、建国初期，对我国教育理论体系影响较大的苏联教育家是：凯洛夫。 7、狭义的教育主要是指：学校教育。 8、古代中国学校教育的主要内容是六艺，它包括：礼、乐、射、御、书、数。 9、在古代印度，能够享受最好教育的是当时的最高种姓：婆罗门。 10、制度化教育或正规教育形成的主要标志是形成近代的：学校教育系统。 11、中国的科举制度开始于：隋唐时期。 12、战国后期，我国出现的具有世界影响的教育文献是：《学记》。 13、在古希腊，最早提出发现法的大教育家是：苏格拉底。 14、古希腊著名思想家柏拉图的教育代表作是：《理想国》。 15、在人类教育史上首次提出“教育遵循自然”学说的教育思想家是古希腊的：亚里士多德。 16、教育学作为一门独立的学科萌芽于：夸美纽斯的《大教育学论》。 17、强调教育学的心理学和伦理学基础，奠定了科学教育学基础的教育家是：赫尔巴特。 18、资产阶级传统教育学的代表人物是：赫尔巴特。 19、20世纪初实用主义教育学的代表人物和作品是：杜威《民本主义与教育》。 20、主张教师应以学生的发展为目的，以儿童中心主义著称的美国教育家是：杜威。 21、制度化的教育是指具有：层次结构和年龄分级的教育制度。 22、普通教育主要是指以升学为目标，以（基础科学知识）为主要教学内容的学校教育。 23、职业教育是以生产劳动的知识和技能为主要教学内容，以生产劳动的知识和技能为主要教学内容，以（就业）为主要目标的学校教育。 24、英国教育家洛克将那种既有贵族气派，又有资产阶级创业精神和才干，还有强健的体魄的人称之为（绅士）。 25、教育区别于其他事物和现象的根本特征，教育的质的规定性是指教育是一种（培养人）的社会活动。 26、规定着一个国家各级各类学校教育的系统，包括各级各类学校的性质、任务、入学条件、企业年限以及它们之间关系的制度中（学校教育制度）。 27、西欧中世纪早期的教会学校主要学习神学和七艺，七艺包括（修词、音乐、算术、几何、文法、天文、辨证法） 28、中国近代制度化教育兴起的标志是清朝末年的（“废科举，兴学校”）。 29、中国近代完备的学制系统产生于1902年的“壬寅学制”以及1903年的（“癸卯学制”）。 30、宋代以后，作为教学的基本教材和科举考试依据的是（四书五经）。 31、欧洲中世纪用于对普通贫民子弟传授宗教及读写知识的教会学校中（教区学校）。 32、中国古代最伟大的教育家孔子的教育思想主要反映在他的言行记载〈论语〉中。 33、教育学是一门以教育现象、教育问题为研究对象，探索（教育规律）的科学。 34、文艺复兴时期人文主义教育思想家有意大利的（维多里诺）、法国的蒙田和（拉伯雷）等。 35、主张让儿童顺其自然，甚至摆脱社会影响而发展的教育家是法国启蒙思想家（卢梭）。 36、苏格拉底的问答法分为三步，第一步称为苏格拉底讽刺，第二步叫定义，第三步是助产术。 37、古代埃及教育的一大特征是“以曾为师”，“以吏为师”。 38、瑞士教育家裴斯泰洛齐的教育代表作是《林哈德和葛笃德》。 39、法国启蒙思想家卢梭的教育思想集中体现在《爱弥儿》一书中。