《全国计算机二级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