(C语言)计算机二级公共基础2010.3(1).ppt

二级公共基础知识 2010年3月等级考试辅导 考试方式 1 公共基础的考试方式为笔试 与VB C的笔试部分合为一张试卷 公共基础部分占全卷的30分 2 公共基础知识有10道选择题和5道填空题 分值分布 学习方法 记忆和理解基本概念与基本原理多做练习适当记忆一些名词与所学的程序设计知识结合起来 以增加对知识的理解能力 第一章算法与数据结构 1 1算法 什么是算法 算法是指解题方案的准确而完整的描述算法的4个特性可行性确定性有穷性拥有足够的情报 拥有输入和输出 算法的两个基本要素对数据对象的运算和操作算法的结构 顺序结构 选择结构 循环结构 真题 2005 4 问题处理方案的正确而完整的描述称为 2008 4 算法的有穷性是指 A 算法程序的运行时间是有限的B 算法程序所处理的数据量是有限的C 算法程序的长度是有限的D 算法只能被有限的用户试用 算法 A 算法的复杂度 什么是算法的复杂度 算法的复杂度是衡量算法好坏的度量 分为时间复杂度和空间复杂度什么是算法的时间复杂度 指执行算法所需要的计算工作量 即算法执行过程中所需要的基本运算次数 什么是算法的空间复杂度 指执行算法所需要的内存空间 一般来说 求解同一个问题有若有多种算法 则执行时间短的算法效率高 占用存储空间少的算法较好 但是算法的时间开销和空间开销往往是相互制约的 对高时间效率和低存储占用的要求只能根据问题的性质折中处理 2007 9 下列叙述中正确的是 A 程序执行的效率与数据的存储结构密切相关B 程序执行的效率只取决于程序的控制结构C 程序执行的效率只取决于所处理的数据量D 以上三种说法都不对 A 算法的设计要求 好的算法应达到4个目标正确性 算法应该满足具体问题的需求 正确反映求解问题对输入 输出和加工处理等方面的需求可读性健壮性 当输入非法数据时 算法应该能够适当做出反应或进行处理 输出表示错误的信息并终止执行 时间效率和存储占用量 第一章算法与数据结构 1 2数据结构的基本概念 什么是数据结构 数据 凡是能被计算机识别 存取和加工处理的符号 字符 图形 图像 声音 视频信号 程序等一切信息 结构 数据之间的逻辑关系 数据结构指相互有关联的数据元素的集合 数据 数据元素之间的关系 数据元素是数据的基本单位 数据结构 数据的逻辑结构 数据的存储结构 数据的运算 线性结构 线性表 栈和队列非线性结构 树形结构 二叉树 树的遍历 顺序结构链式结构索引结构散列结构 插入删除查找 顺序查找 二分法查找排序 数据的逻辑结构 什么是数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系 与数据的存储无关 是独立于计算机的 数据的逻辑结构可分成2类线性结构非线性结构 春 夏 秋 冬 父亲 儿子 女儿 数据的存储结构 什么是数据的存储结构 数据的存储结构又称为物理结构 是指数据元素及其关系在计算机内存中的表示 即数据的逻辑结构在计算机存储空间中的存放形式 数据的存储结构可分为哪4类 顺序结构 链式结构 索引结构 散列结构数据的存储结构与逻辑结构的关系同一逻辑结构可以采用不同的存储结构 真题 2005 4 数据的存储结构是指 A 存储在外存中的数据B 数据所占的存储空间量C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 D 真题 2005 9 下列叙述中正确的是 A 一个逻辑数据结构只能有一种存储结构B 数据的逻辑结构属于线性结构 存储结构属于非线性结构C 一个逻辑数据结构可以有多种存储结构 且各种存储结构不影响数据处理的效率D 一个逻辑数据结构可以有多种存储结构 且各种存储结构影响数据处理的效率 D 数据结构 数据的逻辑结构 数据的存储结构 数据的运算 线性结构 线性表 栈和队列非线性结构 树形结构 二叉树 树的遍历 顺序结构链式结构索引结构散列结构 插入删除查找 顺序查找 二分法查找排序 1 3线性表及其顺序存储结构 线性表必须满足的3个条件 有且只有一个根节点a1 它无前件 有且只有一个终点an 它无后件 除了起点和终点 其余结点只有一个前件 也只有一个后件 1 3线性表的顺序存储结构 线性表顺序存储结构的2个特点 起始位置Lo Lo m Lo i 1 m 每个元素所占用的存储单元大小 Lo n 1 m 1 所有元素所占的存储空间是连续的2 各元素在存储空间中是按逻辑顺序存放的 结点个数n称为线性表的长度 当n 0时 称为空表 顺序表 线性表的顺序存储结构的插入运算 线性表的顺序存储结构的插入运算 插入运算的3步骤判断是否上溢 空出第i位位置 插入 插入算法的效率 数据元素的移动次数 最好情况 最坏情况 平均情况 0 n n 2 看数组下标是否越界 线性表的顺序存储结构的删除运算 线性表的顺序存储结构的删除运算 删除运算 要删除第i个元素 判断是否下溢从第i 1个元素开始向前移动直到最后一个元素元素个数减一删除算法的时间复杂度 数据元素的移动次数 最好情况 最坏情况 平均情况 0 n 1 n 1 2 1 4栈和队列 栈是一种特殊的线性表 是限定在一端进行插入和删除的线性表 FILO 栈顶和栈底入栈和出栈 入栈出栈 退栈 取栈顶元素 考点14栈的基本运算 真题 2006 4 按照 后进先出 原则组织数据的数据结构是A 队列C 双向链表D 二叉树 2005 9 下列关于栈的描述正确的是 A 在栈中只能插入元素而不能删除元素 B 在栈中只能删除元素而不能插入元素C 栈是特殊的线性表 只能在一端插入或删除元素D 栈是特殊的线性表 只能在一端插入元素 而在另一端删除元素 2005 4 下列关于栈的描述中错误的是 A 栈是先进后出的线性表C 栈具有记忆作用D 对栈的插入与删除操作中 不需要改变栈底指针下列关于栈的叙述正确的是 A 栈按 先进先出 组织数据C 只能在栈底插入数据D 不能删除数据 B 栈 B 栈只能顺序存储 B 栈按 先进后出 组织数据 2008 9 一个栈的初始状态为空 现将元素1 2 3 4 A B C D E依次入栈 然后再次出栈 则元素出栈的顺序是 A 1234ABCDEC ABCDE12345D 54321EDCBA 2009 3 支持子程序调用的数据结构是 A 栈 B 树 C 队列 D 二叉树 B EDCBA54321 队列 队列是一种特殊的线性表 允许在一端进行插入操作 在另一端进行删除操作 FIFO LILO 队头和队尾入队和出队 队列 可能出现假溢出现象解决 采用循环队列 依然为顺序存储 循环队列及其运算 什么是循环队列循环队列是队列的一种顺序存储结构形式 在队列最后一个位置已被使用 而第一个位置空闲的情况下 仍然能进行入队操作 循环队列3种基本运算入队 出队 读取数据元素判断循环队列是否为空 满 的条件循环队列为空 s 0循环队列为满 s 1且front rear s 0队列为空 s 1队列非空 rear front 真题 2008 4 设某循环队列的容量为50 头指针front 5 指向队头元素的前一位置 尾指针rear 29 指向队尾元素 则该循环队列中共有个元素 2008 9 下列叙述中正确的是 A 循环队列有队头和队尾两个指针 因此循环队列是非线性结构B 在循环队列中 只需要队头指针就能反映队列中元素的动态变化情况C 在循环队列中 只需要队尾指针就能反映队列中元素的动态变化情况D 循环队列中元素的个数是由队头指针和队尾指针共同决定 24 数据结构 数据的逻辑结构 数据的存储结构 数据的运算 线性结构 线性表 栈和队列非线性结构 树形结构 二叉树 树的遍历 顺序结构链式结构索引结构散列结构 插入删除查找 顺序查找 二分法查找排序 1536 元素2 1400 元素1 1346 元素3 元素4 1345 1 5线性表的链式存储结构 数据域 指针域 什么是结点 结点由哪两部分组成 链式存储结构方式有那些特点 结点的储存不一定连续各结点之间的存储顺序与数据元素的逻辑关系可以不一致链式存储适合于线性结构也适合于非线性结构 h h 空指针 链表 1345 h h 1 5链式存储结构 线性链表 什么是线性链表 线性表的链式存储结构线性链表有哪些基本运算 查找插入删除 h 查找结束 线性链表的查找操作 h 线性链表的插入操作 线性链表的删除操作 h 线性链表 真题 2005 4 下列对于线性链表的描述中正确的是 A 存储空间不一定是连续 且各元素的存储顺序是任意的B 存储空间不一定是连续 且前件元素一定存储在后件元素的前面C 存储空间必须连续 且前件元素一定存储在后件元素的前面D 存储空间必须连续 且各元素的存储顺序是任意的 A 真题 2006 9 数据结构分为线性结构和非线性结构 带链的队列属于 2007 9 线性表的存储结构主要分为顺序存储结构和链式存储结构 队列是一种特殊的线性表 循环队列是队列的 存储结构 2008 9 下列叙述中正确的是 A 顺序存储结构的存储一定是连续的 链式存储结构的存储空间不一定是连续的B 顺序存储结构只针对线性结构 链式存储结构只针对非线性结构C 顺序存储结构能存储有序表 链式存储结构不能存储有序表D 链式存储结构比顺序存储结构节省存储空间 线性结构 顺序 A 数据结构 数据的逻辑结构 数据的存储结构 数据的运算 线性结构 线性表 栈和队列非线性结构 树形结构 二叉树 树的遍历 顺序结构链式结构索引结构散列结构 插入删除查找 顺序查找 二分法查找排序 1 6树与二叉树 树 1 树是一种简单的非线性结构 所有元素之间具有明显的层次特性 2 在树结构中 每一个结点只有一个前件 驱 称为父结点 没有前件 驱 的结点只有一个 称为树的根结点 简称树的根 每一个结点可以有多个后件 继 称为该结点的子结点 没有后件 继 的结点称为叶子结点 3 在树结构中 一个结点所拥有的后件 继 的个数称为该结点的度 所有结点中最大的度称为树的度 树的最大层次称为树的深度 树 叶子结点 该树的度为3 度为3 度为2 该树的深度为4 真题 2006 9 下列软件系统结构图的宽度为 3 二叉树 二叉树的特点 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 左支树 右支树 根结点 满二叉树 完全二叉树 思考 给出完全二叉树有n个结点 问有多少个叶子结点 深度是多少呢 满二叉树 每一层结点数达到最大 完全叉树 除最后一层外 其余每一层结点数达到最大 最后一层结点或满 或右边连续缺少若干结点 二叉树性质 性质1 二叉树的第i层上至多有2i 1 i 1 个结点 满二叉树的第k层上有2k 1个结点 性质2 深度为h的二叉树中至多含有2h 1个结点 深度为h的满二叉树共有2h 1个结点 性质3 若在任意一棵二叉树中 有n0个叶子结点 有n2个度为2的结点 则 n0 n2 1 性质4 具有n个结点的二叉树 其深度至少为 log2n 1 其中 log2n 表示取log2n的整数部分 性质5 具有n个结点的完全二叉树的深度为 log2n 1 若完全二叉树有n个结点 那该二叉树有n n 2 个叶子结点 其中 n 2 表示对n 2取不大于n 2的最大整数 真题 2007 4 在深度为7的满二叉树中 度为2的结点个数为 2005 9 一棵二叉树第六层 根结点为第一层 的结点数最多为 个 2005 4 某二叉树中度为2的结点有18个 则该二叉树中有 个叶子结点 2007 9 一棵二叉树中共有70个叶子结点与80个度为1的结点 则该二叉树中的总结点数为 A 219B 221C 229D 231 2008 4 深度为5的满二叉树有叶子结点 32 19 63 A 16 设一棵完全二叉树共有699个结点 则在该二叉树中的叶子结点数为 2009 3 某二叉树有5个度为2的结点 则该二叉树中的叶子结点数是 A 10 B 8 C 6 D 4 350 二叉树的遍历 先序遍历 DLR 访问根结点 按先序遍历左子树 按先序遍历右子树中序遍历 LDR 按中序遍历左子树 访问根结点 按中序遍历右子树后序遍历 LRD 按后序遍历左子树 按后序遍历右子树 访问根结点 DLR 先序遍历序列 ABDC 先序遍历 LDR 中序遍历序列 BDAC 中序遍历 LRD 后序遍历序列 DBCA 后序遍历 真题 2006 9 对下列二叉树进行中序遍历的结果是 A ACBDFEGB ACBDFGEC ABDCGEFD FCADBEG A 真题 2006 4 对如下二叉树进行后序遍历的结果为 A ABCDEFB DBEAFCC ABDECFD DEBFCA D 2007 9 对下列二叉树进行中序遍历的结果为 ACBDFEHGP 2008 9 对下列二叉树进行中序遍历的结果是 数据结构 数据的逻辑结构 数据的存储结构 数据的运算 线性结构 线性表 栈和队列非线性结构 树形结构 二叉树 树的遍历 顺序结构链式结构索引结构散列结构 插入删除查找 顺序查找 二分法查找排序 1 7查找 1 7查找 什么是查找 查找是在一个给定的数据结构中 根据给定的条件查找满足条件的结点 不同的数据结构采用不同的查找方法 查找的效率直接影响数据处理的效率 查找的结果查找成功 找到满足条件的结点查找失败 找不到满足条件的结点 顺序查找 什么是顺序查找 从线性表第一个数据元素开始依次与被查找的数据进行比较 最好的查询次数 最坏的查询次数 平均查询次数 顺序查找的特点查找效率低适合无序线性表和有序的线性链表进行查找 1 n n 查找23的过程如下图 mid low high 2不进位取整 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 二分查找 二分查找 二分法查找 适合于顺序存储的有序表二分法查找的特点 查找效率比顺序查找高 对于长度为n的有序线性表 最坏情况下二分法只需要比较log2n次 而顺序查找需要比较n次 真题 2006 9 在长度为64的有序线性表中进行顺序查找 最坏情况下需要比较的次数为 A 63B