《全国计算机二级c语言公共基础知识》由会员分享，可在线阅读，更多相关《全国计算机二级c语言公共基础知识（18页珍藏版）》请在金锄头文库上搜索。
1、全国计算机二级 C 语言公共基础知识.txt45 想洗澡吗？不要到外面等待下雨；想成功吗？ 不要空等机遇的到来。摘下的一瓣花能美丽多久？一时的放纵又能快乐多久？有志者要为一 生的目标孜孜以求。少年自有少年狂，藐昆仑，笑吕梁；磨剑数年，今将试锋芒。自命不凡 不可取，妄自菲薄更不宜。 本文由 caizhenweisfd 贡献ppt 文档可能在 WAP 端浏览体验不佳。建议您优先选择 TXT，或下载源文件到本机查看。二级公共基础知识辅导主讲人： 主讲人：符钰知识点分布第一章 数据结构与算法 第二章 程序设计基础 第三章 软件工程基础 第四章 数据库 设计基础第一章 数据结构与算法扬州大学计算机中心
2、1.1 算法1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问 、算法是指解 题方案的准确而完整的描述。换句话说， 题求解步骤的一种描述。 题求解步骤的一种描述。*算法不等于程序，也不等于计算方法。 算法不等于程序，也不等于计算方法。 算法不等 于程序 2、算法的基本特征 、 可行性 确定性 有穷性 拥有足够的情报08 年 4 月选择题第 题 年 月选择题第 月选择题第 5 题 算法的有穷性是指_A 算法的 有穷性是指 A）算法程序的运行时间是有限的 ） B）算法程序所处理的数据量是有限的 ） C）算法程序的长度是有限的 ） D）算法只能被有限的用户使用 ）扬州大学计算机中心 1
3、.1 算法3、算法复杂度主要包括时间复杂度和空间复杂度。 算法复杂度主要包括时间复杂度和 空间复杂度。 时间复杂度 算法时间复杂度是指执行算法所需要的计算工作量 计算工作量，（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过 程中所需 基本运算的执行次数来度量。 基本运算的执行次数来度量 程中所需基本运算的执行次数来 度量。 算法空间复杂度是指执行这个算法所需要的内存空间。 （2）算法空间复杂度是指 执行这个算法所需要的内存空间。 06 年 月选择题第 7 06 年 9 月选择题第 7 题 下列叙述 中正确的是 D_ 下列叙述中正确的是 D_ 一个算法的空间复杂度大， A）
4、一个算法的空间 复杂度大，则其时间复杂度也必定大 一个算法的空间复杂度大， B）一个算法的空间复杂 度大，则其时间复杂度必定小 一个算法的时间复杂度大， C）一个算法的时间复杂度大， 则其空间复杂度必定小 D）上述三种说法都不对扬州大学计算机中心 1.2 数据结构的基本概念1、数据结构是指相互有关联的数据元素的集合。 数据结构是指相互有关联的数据元素 的集合。 数据结构主要研究和讨论以下两个方面的问题： 2、数据结构主要研究和讨论以 下两个方面的问题： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结 构。 数据集合中各数据元素之间所固有的逻辑关系， 数据的逻辑结构。 在对数据进
5、行处理时，各数据元素在计算机中的存储关系， （2）在对数据进行处理时，各数据元素在计算 机中的存储关系，即数据的存储 结构。 结构。 数据的存储结构有顺序、链接、索引等。 数据的存储结构有顺序、链接、索引等。 *：数据的逻辑结构反映数据元素之间的逻辑关系， 数据的存储结构（也称数据 数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结 构（ 的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。 的物理结构）是数 据的逻辑结构在计算机存储空间中的存放形式。同一种逻 辑结构的数据可以采用不同的存 储结构，但影响数据处理效率。 辑结构的数据可以采用不同的存储结构，但影响数据处理 效率。 除建
6、立存储结点信息外，还建立附加的索引表来标识结点的地址。 它不要求逻辑上 相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加 它是把逻辑上相邻的结点存 储在物理位置相邻的存储单元里，结点间的逻辑关 的指针字段表示的。由此得到的存储表 示称为链式存储结构。 系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存 储结构。扬州大学计算机中心 1.2 数据结构的基本概念07 年 月选择题第 1 07 年 4 月选择题第 1 题 下列叙述中正确的是_B 下列叙述中正确 的是_B 算法的效率只与问题的规模有关， A）算法的效率只与问题的规模有关，而与数据 的存储结构无关 B）算法的时间复杂度是指执
7、行算法所需要的计算工作量 C）数据的逻辑结 构与存储结构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关 3、数据结构分为 两大类型：线性结构和非线性结构。 数据结构分为两大类型：线性结构和非线性结构。 （1）线性结构（非空的数据结构）条件：1）有且只有一个根结点；2）每一个 线性结构 （非空的数据结构）条件： 有且只有一个根结点； 结点最多有一个前件，也最多有一个后 件。 结点最多有一个前件，也最多有一个后件。 常见的线性结构有线性表、 队列和线性 链表等。 *：常见的线性结构有线性表、栈、队列和线性链表等。 非线性结构：不满足线 性结构条件的数据结构。 （2）非线性结构：不满足线性结
8、构条件的数据结构。 常见的非 线性结构有树、二叉树和图等。 *：常见的非线性结构有树、二叉树和图等。扬州大学计算机中心 1.2 数据结构的基本概念07 年 9 月选择题第 6 题 07 年 月选择题第 6 下列叙述中正确的是_D 下列叙述中正确 的是_D A）数据的逻辑结构与存储结构必定是一一对应的 由于计算机存储空间是向量式的 存储结构，因此， B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一 定是线 性结构 程序设计语言中的数组一般是顺序存储结构，因此， C）程序设计语言中的 数组一般是顺序存储结构，因此，利用数组只能处理线性 结构 D）以上三种说法都不对扬州大学计算机中心
9、 1.3 栈和队列1、栈及其基本运算 栈是限定在一端进行插入与删除运算的线性表。 栈是限定在一端进行插入与删除运算的线性表。 在栈中，允许插入与删除的一端称为栈顶，不允许插入与 删除的另一端称为 在栈中，允许插入与删除的一端称为栈顶， 栈底。栈顶元素总是最后被 插入的元素，栈底元素总是最先被插入的元素。 栈底。栈顶元素总是最后被插入的元素， 栈底元素总是最先被插入的元素。 后进先出”的原则组织数据的。 即栈是按照“先进后出”即栈是按照“先进后出”或“后进先出”的原则组织数据的。 栈具有记忆作用。 栈具有 记忆作用。 06 年 月填空题第 4 06 年 9 月填空题第 4 题 先进后出”原则组织
10、数据的数据 结构是_ 。 按“先进后出”原则组织数据的数据结构是_栈。扬州大学计算机中心 1.3 栈和队列2、队列及其基本运算 队列是指允许在一端（队尾）进入插入，而在另一端（队头） 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的 线性表。尾指针 （Rear）指向队尾元素，头指针（front） 线性表。尾指针（Rear）指向队尾元素，头指针 （front）指向排头元素的 前一个位置（队头） 。 前一个位置（队头） 。 队列是“先进先出”后进后出”的线性表。 队列是“先进先出”或“后进后出”的线性表。 06 年 月填空题 第 5 06 年 9 月填空题第 5 题 数据结构分为线
11、性结构和非线性结构，带链的队列属于 。 数 据结构分为线性结构和非线性结构，带链的队列属于。 07 年 月选择题第 5 07 年 4 月选择 题第 5 题 下面对队列的叙述正确的是_ 下面对队列的叙述正确的是_ A) 队列属于非线性 表 队列按“先进后出” B) 队列按“先进后出”原则组织数据 C) 队列在队尾删除数据 队 列按“先进先出” D) 队列按“先进先出”原则组织数据扬州大学计算机中心 1.3 栈和队列循环队列及其运算：所谓循环队列， 循环队列及其运算：所谓循环队列，就是将队列 存储空间的最后一个位置 绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。 绕 到第一个位置，形成逻辑
12、上的环状空间，供队列循环使用。 循环队列中元素的个数=rear front。 =rear*：循环队列中元素的个数=rear-front。 08 年 月填空题第 3 08 年 4 月填 空题第 3 题 设某循环对列的容量为 50 头指针 front=5 指向对头元素的前一位置） ， 50， front=5（ 设某循环对列的容量为 50，头指针 front=5（指向对头元素的前一位置） ， 尾指 针 rear=29 指向队尾元素） ，则该循环队列中共有_个元素。 rear=29（ ） ，则该循 环队列中共有 _个元素 尾指针 rear=29（指向队尾元素） ，则该循环队列中共有_个 元素。 07
13、年 9 月填空题第 3 题 07 年 月填空题第 3 线性表的存储结构主要分为顺序存储 结构和链式存储结构。 线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是 一种特 殊的线性表，循环队列是队列的_链式_ 存储结构。 _链式 殊的线性表，循环队 列是队列的_链式_ 存储结构。扬州大学计算机中心 1.4 树与二叉树1、树的基本概念 树是一种简单的非线性结构。 树是一种简单的非线性结构。 没有前 件的结点只有一个，称为树的根结点，简称树的根。 没有前件的结点只有一个，称为树的 根结点，简称树的根。没有后件的结 点称为叶子结点。 点称为叶子结点。 在树结构中， 一个结点所拥有的后件的个数称
14、为该结点的度， 在树结构中，一个结点所拥有的后件的个 数称为该结点的度，所有结点中 最大的度称为树的度。树的最大层次称为树的深度。 最大 的度称为树的度。树的最大层次称为树的深度。 06 年 月填空题第 1 06 年 9 月填空题第 1 题 下列软件系统结构图的宽度为 。 下列软件系统结构图的宽度为。ABCDEF扬州大学计算机中心 1.4 树与二叉树2、二叉树及其基本性质 （1）什么是二叉树 二叉树是一种很有用的非线性结构，它具 有以下两个特点： 二叉树是一种很有用的非线性结构，它具有以下两个特点：1）非空二叉 树只有一个根结点； 每一个结点最多有两棵子树， 树只有一个根结点；2）每一个结点最
15、 多有两棵子树，且分别称为该结点 的左子树与右子树。 的左子树与右子树。 根据二叉树 的概念可知，二叉树的度可以为 0 叶结点） 、 ） 、1 *：根据二叉树的概念可知，二叉树的 度可以为 0（叶结点） 、1（只有一棵子 棵子树） 。 树）或 2（有 2 棵子树） 。 （2）二叉树 的基本性质 k ?1 性质 1 在二叉树的第 k 层上， 个结点。 性质 1 在二叉树的第 k 层上， 最多有 2 ( k 1)个结点。 m 性质 2 深度为 m 个结点。 性质 2 深度为 m 的二叉树最多 有个 2 ? 1 个结点。 性质 3 在任意一棵二叉树中，度数为 0 的结点（即叶子结点）总比度 为 2
16、性质 3 在任意一棵二叉树中，度数为 0 的结点（即叶子结点）总比度为 2 的结点多一 个。 的结点多一个。 性质 4 具有 n 个结点的二叉树， 性质 4 具有 n 个结点的二叉树，其 深度至少为 log2 n +1 ，其中 log 2 n 的整数部分。 表示取 的整数部分。 log 2 n扬州大学计算机中心 1.4 树与二叉树07 年 月选择题第 7 07 年 4 月选择题第 7 题 某二叉树中有 n 个度为 2 的结点, 某二叉 树中有 n 个度为 2 的结点,则该二叉树中的叶子结点数为 A B)n(A)n+1 B)n-1 C)2n D)n/2 07 年 月选择题第 8 07 年 9 月选择题第 8 题 一颗二叉树中共有 70 个叶子结点与 80 个度为 1 的结点， 70 个叶子结点与 80 个度为 一颗二叉树中共有 70 个叶子结点与 80 个度为 1 的 结点，则该二叉树中的总结 点数为 点数为 B） C） D） A）219 B）221 C）229 D）231
