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）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA,树,一个结点的子节点数称为该结点的度 所有结点中最大的度称为树的度 树的最大层次称为树的深度。,二叉树,每一个结点最多有两棵子树 性质： 在二叉树的第k层上，最多有2k-1(k1)个结点； 深度为m的二叉树最多有2m-1个结点； 叶子结点总是比度为2的结点多一个,增加度为1的结点不会影响二叉树的叶子结点数，每增加一个度为2的结点便会增加一个叶子结点,满二叉树,最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点,深度为m的满二叉树有2m-1个结点。,往年真题,（2006-04-7）在深度为7的满二叉树中，叶子结点的个数为（C ）。 A）32 B）31 C）64 D）63,（2009-03-3）某二叉树有5个度为2的结点,则该二叉树中的叶子结点数是（C ）。 A）10 B）8 C）6 D）4,解析：叶子结点总是比度为2的结点多一个,（2007-09-8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（ A ） A）219 B）221 C）229 D）231 （2007-04）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（ A）。 A）n+1 B）n-1 C）2n D）n/2,二叉树的遍历,先序遍历 访问根结点 先序遍历左子树 先序遍历右子树 中序遍历 中序遍历左子树 访问根结点 中序遍历右子树 后序遍历 后序遍历左子树 后序遍历右子树 访问根结点,根左右 根节点访问在前面,左根右 根节点访问在中间,左右根 根节点访问在后面,往年真题,（2007-04） A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ,（2006-09） A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG,（2006-04） A）ABCDEF B）DBEAFC C）ABDECF D）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软件维护是指修复程序中