C语言公共基础知识.ppt

公共基础知识 算法 算法的概念是一组有穷指令集 是解题方案的准确而完整的描述 通俗地说 算法就是计算机解题的过程 算法的基本特征确定性有穷性可行性输入 0个 输出 1个 算法 算法的三种基本控制结构顺序结构选择结构循环结构算法效率的度量 算法复杂度时间复杂度 指执行算法所需要的计算工作量 空间复杂度 指执行这个算法所需要的内存空间 2009 09 4 算法的空间复杂度是指 A A 算法在执行过程中所需要的计算机存储空间B 算法所处理的数据量C 算法程序中的语句或指令条数D 算法在执行过程中所需要的临时工作单元数 2008 04 5 算法的有穷性是指 A A 算法程序的运行时间是有限的B 算法程序所处理的数据量是有限的C 算法程序的长度是有限的D 算法只能被有限的用户使用 2006 09 7 下列叙述中正确的是 D A 一个算法的空间复杂度大 则其时间复杂度也必定大B 一个算法的空间复杂度大 则其时间复杂度必定小C 一个算法的时间复杂度大 则其空间复杂度必定小D 上述三种说法都不对 2005 09 算法复杂度主要包括时间复杂度和 空间 复杂度 2005 04 问题处理方案的正确而完整的描述称为 算法 数据结构 数据的逻辑结构线性结构 链表 队列 堆栈 非线性结构 树 图 数据的存储结构 物理结构 顺序存储 逻辑上相邻的结点存储在物理位置相邻的存储单元里 结点间的逻辑关系由存储单元的邻接关系来体现链式存储 不要求逻辑上相邻的结点在物理位置上亦相邻 结点间的逻辑关系是由附加的指针字段表示的 线性结构 存在唯一的被称为 第一个 的数据元素存在唯一的被称为 最后一个 的数据元素除第一个外 每个元素只有一个前驱除最后一个外 每个元素只有一个后继 线性表的顺序存储 数组 线性表的链式存储 链表 数据域 指针域 head head 图1单向链表 图2双向链表 栈 只允许在栈顶操作先进后出 栈底 栈顶 队列 队尾进 队首进先进先出 队尾 队首 2005 04 1 数据的存储结构是指 D A 存储在外存中的数据B 数据所占的存储空间量C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 2005 04 5 下列对于线性链表的描述中正确的是 A A 存储空间不一定是连续 且各元素的存储顺序是任意的B 存储空间不一定是连续 且前件元素一定存储在后件元素的前面C 存储空间必须连续 且前件元素一定存储在后件元素的前面D 存储空间必须连续 且各元素的存储顺序是任意的 2009 09 2 下列数据结构中 能够按照 先进后出 原则存取数据的是 B A 循环队列B 栈C 队列D 二叉树 2008 09 一个栈的初始状态为空 现将元素1 2 3 4 5 A B C D E依次入栈 然后再依次出栈 则元素出栈的顺序是 B A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA 树 一个结点的子节点数称为该结点的度所有结点中最大的度称为树的度树的最大层次称为树的深度 二叉树 每一个结点最多有两棵子树性质 在二叉树的第k层上 最多有2k 1 k 1 个结点 深度为m的二叉树最多有2m 1个结点 叶子结点总是比度为2的结点多一个 增加度为1的结点不会影响二叉树的叶子结点数 每增加一个度为2的结点便会增加一个叶子结点 满二叉树 最后一层外 每一层上的所有结点有两个子结点 则k层上有2k 1个结点 深度为m的满二叉树有2m 1个结点 往年真题 2006 04 7 在深度为7的满二叉树中 叶子结点的个数为 C A 32B 31C 64D 63 2009 03 3 某二叉树有5个度为2的结点 则该二叉树中的叶子结点数是 C A 10B 8C 6D 4 解析 叶子结点总是比度为2的结点多一个 2007 09 8 一棵二叉树中共有70个叶子结点与80个度为1的结点 则该二叉树中的总结点数为 A A 219B 221C 229D 231 2007 04 某二叉树中有n个度为2的结点 则该二叉树中的叶子结点数为 A A n 1B n 1C 2nD n 2 二叉树的遍历 先序遍历访问根结点先序遍历左子树先序遍历右子树中序遍历中序遍历左子树访问根结点中序遍历右子树后序遍历后序遍历左子树后序遍历右子树访问根结点 根 左 右根节点访问在前面 左 根 右根节点访问在中间 左 右 根根节点访问在后面 往年真题 2007 04 A DYBEAFCZXB YDEBFZXCAC ABDYECFXZD ABCDEFXYZ 2006 09 A ACBDFEGB ACBDFGEC ABDCGEFD FCADBEG 2006 04 A ABCDEFB DBEAFCC ABDECFD DEBFCA 结构化程序设计方法 自顶向下逐步求精模块化 高内聚 低耦合 耦合性是模块间相互连接的紧密程度的度量 内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量 两个或两个以上模块之间关联的紧密程度称为A 耦合度B 内聚度C 复杂度D 数据传输特性在结构化程序设计中 模块划分的原则是 A 各模块应包括尽量多的功能B 各模块的规模应尽量大C 各模块之间的联系应尽量紧密D 模块内具有高内聚度 模块间具有低耦合度 下列选项中不属于结构化程序设计方法的是A 自顶向下B 逐步求精C 模块化D 可复用 2007 09 4 下列叙述中 不符合良好程序设计风格要求的是A 程序的效率第一 清晰第二B 程序的可读性好C 程序中要有必要的注释D 输入数据前要有提示信息 2009 09 下列选项中不属于结构化程序设计原则的是A 可封装B 自顶向下C 模块化D 逐步求精软件设计中模块划分应遵循的准则是A 低内聚低耦合B 高内聚低耦合C 低内聚高耦合D 高内聚高耦合 软件工程基本概念 计算机软件是包括程序 数据及相关文档的完整集合 软件工程 以工程的思想管理软件过程软件工程包括3个要素 方法 工具和过程 软件生命周期分三个阶段 软件定义 软件开发 运行维护 软件分析 确定 做什么 软件设计 从工程管理角度来看 软件设计分两步 概要设计详细设计 确定 怎么做 软件测试 软件测试 检验软件是否满足规定的需求白盒测试 在程序内部进行黑盒测试 是在软件接口处进行程序调试 诊断和改正程序中的错误 下列叙述中正确的是A 程序设计就是编制程序B 程序的测试必须由程序员自己去完成C 程序经调试改错后还应进行再测试D 程序经调试改错后不必进行再测试下列描述中正确的是A 软件工程只是解决软件项目的管理问题B 软件工程主要解决软件产品的生产率问题C 软件工程的主要思想是强调在软件开发过程中需要应用工程化原则D 软件工程只是解决软件开发中的技术问题 下列叙述中正确的是A 软件交付使用后还需要进行维护B 软件一旦交付使用就不需要再进行维护C 软件交付使用后其生命周期就结束D 软件维护是指修复程