C语言公共基础知识.ppt

《C语言公共基础知识.ppt》由会员分享，可在线阅读，更多相关《C语言公共基础知识.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 公共基础知识公共基础知识算法算法算法的概念算法的概念是一组有穷指令集，是解题方案的准确而完整的描是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。述。通俗地说，算法就是计算机解题的过程。算法的基本特征算法的基本特征确定性确定性有穷性有穷性可行性可行性输入输入(=0个个)，输出，输出(=1个个)。算法算法算法的三种基本控制结构算法的三种基本控制结构顺序结构顺序结构选择结构选择结构循环结构循环结构算法效率的度量算法效率的度量算法复杂度算法复杂度时间复杂度：指执行算法所需要的计算工作量。时间复杂度：指执行算法所需要的计算工作量。空间复杂度：指执行这个算法所需要的内

2、存空间。空间复杂度：指执行这个算法所需要的内存空间。（2009-09-4）算法的空间复杂度是指（）算法的空间复杂度是指（A ）。）。A）算法在执行过程中所需要的计算机存储空间）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量）算法所处理的数据量C）算法程序中的语句或指令条数）算法程序中的语句或指令条数 D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数（2008-04-5）算法的有穷性是指（）算法的有穷性是指（A ）。）。A）算法程序的运行时间是有限的）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的）算法程序所处理的数据量是有限的C

3、）算法程序的长度是有限的）算法程序的长度是有限的 D）算法只能被有限的用户使用）算法只能被有限的用户使用（2006-09-7）下列叙述中正确的是（）下列叙述中正确的是（D）。）。A）一个算法的空间复杂度大，则其时间复杂）一个算法的空间复杂度大，则其时间复杂度也必定大度也必定大B）一个算法的空间复杂度大，则其时间复杂）一个算法的空间复杂度大，则其时间复杂度必定小度必定小C）一个算法的时间复杂度大，则其空间复杂）一个算法的时间复杂度大，则其空间复杂度必定小度必定小D）上述三种说法都不对）上述三种说法都不对（2005-09）算法复杂度主要包括时间复）算法复杂度主要包括时间复杂度和杂度和【空间空间】复

4、杂度。复杂度。（2005-04）问题处理方案的正确而完整）问题处理方案的正确而完整的描述称为的描述称为【算法算法】。数据结构数据结构数据的逻辑结构数据的逻辑结构线性结构（链表、队列、堆栈）线性结构（链表、队列、堆栈）非线性结构（树、图）非线性结构（树、图）数据的存储结构数据的存储结构(物理结构物理结构)顺序存储：顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单元逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现里，结点间的逻辑关系由存储单元的邻接关系来体现 链式存储：链式存储：不要求逻辑上相邻的结点在物理位置上亦相邻，结不要求逻辑上相邻的结点在物理位

5、置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的点间的逻辑关系是由附加的指针字段表示的 线性结构线性结构存在唯一的被称为存在唯一的被称为“第一个第一个”的数据元素的数据元素存在唯一的被称为存在唯一的被称为“最后一个最后一个”的数据元素的数据元素除第一个外，每个元素只有一个前驱除第一个外，每个元素只有一个前驱除最后一个外，每个元素只有一个后继除最后一个外，每个元素只有一个后继线性表的顺序存储线性表的顺序存储数组数组线性表的链式存储线性表的链式存储-链表链表数据数据域域指针指针域域headhead图图1 1 单向链表单向链表图图2 2 双向链表双向链表栈栈只允许在栈顶操作只允许在栈顶操作先进后

6、出先进后出栈底栈底栈顶栈顶队列队列队尾进，队首进队尾进，队首进先进先出先进先出队尾队尾队首队首（2005-04-1）数据的存储结构是指（）数据的存储结构是指（D ）。）。A）存储在外存中的数据）存储在外存中的数据 B）数据所占的存储空间量）数据所占的存储空间量C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示（2005-04-5）下列对于线性链表的描述中正确的是（）下列对于线性链表的描述中正确的是（A ）A）存储空间不一定是连续）存储空间不一定是连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的B）存储空间

7、不一定是连续）存储空间不一定是连续,且前件元素一定存储在后件元素的前面且前件元素一定存储在后件元素的前面C）存储空间必须连续）存储空间必须连续,且前件元素一定存储在后件元素的前面且前件元素一定存储在后件元素的前面D）存储空间必须连续）存储空间必须连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的（2009-09-2）下列数据结构中）下列数据结构中,能够按照能够按照“先先进后出进后出”原则存取数据的是（原则存取数据的是（B ）。）。A）循环队列）循环队列 B）栈）栈 C）队列）队列 D）二叉树）二叉树（2008-09）一个栈的初始状态为空。现将）一个栈的初始状态为空。现将元素元素1、2、

8、3、4、5、A、B、C、D、E依依次入栈，然后再依次出栈，则元素出栈的次入栈，然后再依次出栈，则元素出栈的顺序是（顺序是（B ）。）。A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA树树根节根节点点子节子节点点子节子节点点子节子节点点叶子节叶子节点点叶子节叶子节点点叶子节叶子节点点叶子节叶子节点点叶子节叶子节点点叶子节叶子节点点一个结点的子节点数称为该结点的度一个结点的子节点数称为该结点的度所有结点中最大的度称为树的度所有结点中最大的度称为树的度树的最大层次称为树的深度。树的最大层次称为树的深度。二叉树二叉树每一个结点最多有两棵子树每一个结

9、点最多有两棵子树性质：性质：在二叉树的第在二叉树的第k层上，最多有层上，最多有2k-1(k1)个结点；个结点；深度为深度为m的二叉树最多有的二叉树最多有2m-1个结点；个结点；叶子结点总是比度为叶子结点总是比度为2的结点的结点多一个多一个 根节根节点点增加度为增加度为1的结点不会影响二叉树的的结点不会影响二叉树的叶子结点数，每增加一个度为叶子结点数，每增加一个度为2的结的结点便会增加一个叶子结点点便会增加一个叶子结点 满二叉树满二叉树最后一层外，每一层上最后一层外，每一层上的所有结点有两个子结的所有结点有两个子结点，则点，则k层上有层上有2k-1个结个结点点,深度为深度为m的满二叉树的满二叉树

10、有有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的结点，则该二叉树中的总结点数为（的结

11、点，则该二叉树中的总结点数为（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二叉树的遍历二叉树的遍历先序遍历先序遍历访问根结点访问根结点先序遍历左子树先序遍历左子树先序遍历右子树先序遍历右子树中序遍历中序遍历中序遍历左子树中序遍历左子树访问根结点访问根结点中序遍历右子树中序遍历右子树后序遍历后序遍历后序遍历左子树后序遍历左子树后序遍历右子树后序遍历右子树访问根结点访问根结点根根左左右右 根节点访问在前面根节

12、点访问在前面左左根根右右 根节点访问在中间根节点访问在中间左左右右根根 根节点访问在后面根节点访问在后面往年真题往年真题（2007-04）A）DYBEAFCZX B）YDEBFZXCAC）ABDYECFXZ D）ABCDEFXYZ（2006-09）A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG（2006-04）A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA结构化程序设计方法结构化程序设计方法自顶向下自顶向下逐步求精逐步求精模块化（高内聚，低耦合模块化（高内聚，低耦合）耦合性耦合性是模块间相互连接的紧密程度的度量。是模块间相互连接的紧密程度

13、的度量。内聚性内聚性是一个模块内部各个元素间彼此结合是一个模块内部各个元素间彼此结合的紧密程度的度量。的紧密程度的度量。两个或两个以上模块之间关联的紧密程度称为两个或两个以上模块之间关联的紧密程度称为A)耦合度耦合度B)内聚度内聚度C)复杂度复杂度D)数据传输特性数据传输特性在结构化程序设计中，模块划分的原则是（在结构化程序设计中，模块划分的原则是（）A）各模块应包括尽量多的功能）各模块应包括尽量多的功能B）各模块的规模应尽量大）各模块的规模应尽量大C）各模块之间的联系应尽量紧密）各模块之间的联系应尽量紧密D）模块内具有高内聚度、模块间具有低耦合度）模块内具有高内聚度、模块间具有低耦合度下列选

14、项中下列选项中不属于不属于结构化程序设计方法的是结构化程序设计方法的是A)自顶向下自顶向下B)逐步求精逐步求精C)模块化模块化D)可复用可复用（2007-09-4）下列叙述中，不符合良好程序设计）下列叙述中，不符合良好程序设计风格要求的是风格要求的是A）程序的效率第一，清晰第二）程序的效率第一，清晰第二 B）程序的可读性好）程序的可读性好C）程序中要有必要的注释）程序中要有必要的注释 D）输入数据前要有提示信息）输入数据前要有提示信息（2009-09）下列选项中不属于结构化程）下列选项中不属于结构化程序设计原则的是序设计原则的是A）可封装）可封装 B）自顶向下）自顶向下 C）模块化）模块化 D

15、）逐步求精）逐步求精软件设计中模块划分应遵循的准则是软件设计中模块划分应遵循的准则是 A）低内聚低耦合）低内聚低耦合 B）高内聚低耦合）高内聚低耦合 C）低内聚高耦合）低内聚高耦合 D）高内聚高耦合）高内聚高耦合 软件工程基本概念软件工程基本概念 计算机软件是包括程序、数据及相关文档的完计算机软件是包括程序、数据及相关文档的完整集合。整集合。软件工程：以工程的思想管理软件过程软件工程：以工程的思想管理软件过程软件工程包括软件工程包括3个要素：方法、工具和过程。个要素：方法、工具和过程。软件生命周期分三个阶段：软件定义、软件开软件生命周期分三个阶段：软件定义、软件开发、运行维护，发、运行维护，软

16、件分析软件分析 确定确定“做什么做什么”软件设计软件设计从工程管理角度来看，软件设计分两步：从工程管理角度来看，软件设计分两步：概要设计概要设计详细设计。详细设计。确定确定“怎么怎么做做”软件测试软件测试软件测试软件测试：检验软件是否满足规定的需：检验软件是否满足规定的需求求白盒测试：在程序内部进行白盒测试：在程序内部进行黑盒测试：是在软件接口处进行黑盒测试：是在软件接口处进行程序调试程序调试:诊断和改正程序中的错误诊断和改正程序中的错误 下列叙述中正确的是下列叙述中正确的是 A程序设计就是编制程序程序设计就是编制程序 B程序的测试必须由程序员自己去完成程序的测试必须由程序员自己去完成 C程序

17、经调试改错后还应进行再测试程序经调试改错后还应进行再测试 D程序经调试改错后不必进行再测试程序经调试改错后不必进行再测试 下列描述中正确的是下列描述中正确的是 A软件工程只是解决软件项目的管理问题软件工程只是解决软件项目的管理问题 B软件工程主要解决软件产品的生产率问题软件工程主要解决软件产品的生产率问题 C软件工程的主要思想是强调在软件开发过程中软件工程的主要思想是强调在软件开发过程中需要应用工程化原则需要应用工程化原则 D软件工程只是解决软件开发中的技术问题软件工程只是解决软件开发中的技术问题 下列叙述中正确的是下列叙述中正确的是 A软件交付使用后还需要进行维护软件交付使用后还需要进行维护

18、 B软件一旦交付使用就不需要再进行维护软件一旦交付使用就不需要再进行维护 C软件交付使用后其生命周期就结束软件交付使用后其生命周期就结束 D软件维护是指修复程序中被破坏的指令软件维护是指修复程序中被破坏的指令 下列叙述中正确的是（下列叙述中正确的是（）A）软件测试的主要目的是发现程序中的错误）软件测试的主要目的是发现程序中的错误B）软件测试的主要目的确定程序中错误的位置）软件测试的主要目的确定程序中错误的位置C）为了提高软件测试的效率，最好由程序编制者）为了提高软件测试的效率，最好由程序编制者自己来完成软件测试的工作自己来完成软件测试的工作D）软件测试是证明软件没有错误）软件测试是证明软件没有错误软件是指软件是指A）程序）程序 B）程序和文档）程序和文档C）算法加数据结构）算法加数据结构 D）程序、数据与相关文档的完整集合）程序、数据与相关文档的完整集合