公共基础知识复
习要点 2015-10
考题特点
1．涉及面广，但难度小
考试中有关公共知识部分的题目共有大约15道，涉及算法及数据结构、程序设计基础、软件工程基础和数据库设计基础等四门学科，但是从整体上分析，考核内容的难度不大，考点也相对集中
1
2．考核重点为基本概念、基本方法和基本运算。
3．考试中涉及的题目都是基本概念、基本方法和基本运算，考核以概念和认识性内容为主，理解性、应用性内容极少。
第一章
一、算法：
1、概念——解题方案的准确而完整的描述。
四个基本特征——可行性，确定性，有穷性，拥有足够的情报。
? 可行性——针对实际问题而设计的算法，执行后能够得到满意的结果。
? 确定性——算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。
? 有穷性——算法必须的有限时间内做完，即算法必须能在执行有限个步骤之后终止。
? 拥有足够的情报——要使算法有效必须为算法提供足够的情报。
算法的基本要素：
? 一是对数据对象的运算和操作——算数运算、逻辑运算、关系运算、数据传输。
2
? 二是算法的控制结构——顺序、选择、循环 三种基本结构。
? 算法基本设计方法——列举法、归纳法、递推、递归、减半递推技术、回溯法。
2、复杂度——时间复杂度和空间复杂度
? 时间复杂度——执行算法所需要的计算工作量,即所需基本运算的执行次数
? 空间复杂度——执行这个算法所需要的内存空间。
3
A D
4
5
D
B
二、数据结构：
6
1、数据逻辑结构——数据集合中各数据的逻辑关系——线性结构和非线性结构。
? 线性结构特点——只有一个根节点，最多只有一个前件也最多有一个后件。一根一前件一后件
? 线性结构（又称线性表）。在一个线性结构中插入或删除任何一个结点后还是线性结构。 ? 非线性结构——数据结构不是线性结构。
2、数据存储结构——是逻辑结构在计算机存储空间中的存放形式。也称数据的物理结构。
逻辑结构 分为顺序、链接，索引。不同的存储结构，数据处理的效率是不同的。
7
D
B
三、线性表及顺序存储结构
1、 线性表式——最简单、最常用的一种数据结构。 2、 非线性结构：不满足线性结构条件的数据结构
3、 顺序存储结构——存储空间是连续的和各数据元素在存储空间中按逻辑顺序依次存放的。
4、 顺序存储结构插入和删除运算不太方便，平均情况下要移
8
动一半的元素。
顺序存储结构适合小线性表和元素不常变动的线性表，不适合元素经常变动的大线性表。
四、栈和队列——都是线性表
1、栈限定在一端进行插入和删除的线性表。插入、删除的这一端为栈顶，另一端为栈底 采用顺序存储、链式存储。 特点：先进后出FILO 或 后进先出LIFO。 死胡同 3、 队列是允许在一端进行插入而在另一端进行删除的线性表 排队买票 特点：先进先出FIFO或后进后出FIFO。 9
4、 队列的顺序存储结构一般是循环队列的形式。
5、 队列中元素个数计算公式：
? 尾指针>头指针时，尾指针-头指针 例如：容量为15的循环队列中，头指针为6，尾指针为9，循环队列中共有（ ）个元素。 答:9-6=3
? 尾指针<头指针时，尾指针-头指针+容量. 例如：容量为15的循环队列中，头指针为6，尾指针为3，循环队列中共有（ ）个元素。 答:3-6+15=12
6、 栈中元素个数的计算——栈顶-栈底+1
10
答:8-1+1=8
例如：已知栈顶指针为8，栈底指针为1，栈中共有8个元素。
B
11
c
B
12
B
A
13
D
B\\C
14
B\\B D
15
D
五、线性链表
1、线性表的链式存储结构称为线性链表。
2、链式存储结构中存储空间可以不连续，存储顺序与逻辑关系可以不一致。逻辑关系可以不一致。 4、带链的栈和带链的队列。
3、链式存储方式既可以表示线性结构，也可以表示非线性结构。
A
六、树与二叉树
16
1、树：
考点： (1)结点个数 (2)遍历顺序 ? 是一种简单的非线性结构。
? 没有前件的节点叫根结点（A）。没有后件的节点叫叶子
结点。（CEDGH）
? 一个结点拥有的后件个数称为该结点的度
(度为0的
结点称为叶子结点)。
? 根结点在第
1层，所有子结点在下一层，树的最大层次称为树的深度（层数）。
二叉树的根结点所在的层数为1，根结点的孩子（子）结点所在的层数为2，以此类推。
2、二叉树： （1）基本性质： 性质1：第k层上最多2(16)个。
答：求第5层节点 共2=16个
17
k-1
个结点。
例如：深度为5的满二叉树中叶子结点的个数是
5-1
性质2：深度为m的二叉树最多有2-1个结点。
例：已知深度为2，节点数有2-1=3
性质3：度为0的节点（叶子结点）总是比度为2的节点多一个。
例：已知叶子结点50个，度为1的节点50个，求总结点数（50+50+49=149个）
性质4：n个结点的二叉树，深度至少为[log2n] +1
总结：总节点数一定是奇数。 分清：度（后件个数）、深度（层数）
2m
例：已知度为2的节点50个，求叶子结点数（51）
设内部节点数为x，那么2*x + 1 = 1001, 求得x＝500。 ? 乘2是因为每个内部节点有两个孩子。 ? 加1是为了计入根节点。 所以叶子＝1001-500=501.
（2）满二叉树和完全二叉树：
18
满二叉树：每一层上的节点数达到最大值，第K层上有2k-1个节点，
深度为m的满二叉树有2m-1个节点。
? 1到15都是结点 ? 8到15是叶子结点 ? 叶子结点就是最大的结点。
19
第一层 第二层 第三层 第四层
完全二叉树：除最后一层外，每一层上的节点数达到最大值，最后一层缺右边的若干节点。
完全二叉树中——已知总结点求叶子结点公式：总结点/2
例如：完全二叉树共有700个结点，则有（(349)个，度为1的节点（1）个
完全二叉树共有701个结点，则有（(350)个，度为1的节点（0）个
20
350）个叶子结点，度为351）个叶子结点，度为2
2
的节点的节点
A
46
B
47
C
48
A
49
B
7、结构图(SC)
8、数据流类型有变换型和事务型两种
变换型数据处理的工作过程一般分为三步：取得数据、
50
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库access公共基础知识复习要点在线全文阅读。
相关推荐：
