c语言基础知识复习笔记.doc

c语言基础知识复习笔记.doc第1X:全部的基本概念Point1:W的基本概念・5■考点精讲1、 算法:是指解题方案的准确而完整的描述。(1) 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。程序也可以作为算法的一种描述,但程序通常还要考虑程序运行时的环境限制等。(2) 算法,是一组严谨地定义运算顺序的规则,并目•每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。2、 算法的基木特征:(1) 可行性,例如1012+1-1012的问题(2) 确定性,算法屮每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性;例在特殊情况时,数学公式是正确的,但计算机就是无法操作。(3) 有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义。例如1/3的无理数问题。(4) 拥有足够的情报。所有的各种可能悄况都要考虑到。3、 一个算法的优劣将影响到算法乃至程序的效率。算法分析的口的在丁选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度來考虑。(1) 算法的时间复杂度是指执行算法所需要的计算匸作量,可以执行算法的过程屮所需要的皋本运算的执行次数来度虽。分析算法工作虽的方法冇:平均性态分析、最坏情况分析。(2) 算法的空间复杂度是指执行这个算法所需要的内存空间。主要包括:算法程序所占的空间;输入的初始数据所占的空间;算法执行过程中所需要的额外空间。真题分析【真题1】算法的有穷性是指 c(2008年4月)A) 算法程序的长度是有限的B) 算法只能被有限的用户使用C)算法程序的运行时间是有限的D)算法程序所处理的数据最是有限的解析:算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。答案:C【真题2】问题处理方案的正确而完整的描述称为_【5】_。(2005年4月)解析:算法是问题处理方案正确而完整的描述。答案:算法【真题3】算法的空间复杂度是指 o(2009年9月)A) 算法程序中的语句或指令条数B) 算法在执行过程中所需要的临时工作单元数C) 算法在执行过程中所需要的计算机内部存储空间D) 算法所处理的数据量・6■解析:算法的空间复杂度是指执行这个算法所需要的计算机内部存储空间(简称内存空间)。答案:C【真题4]下列叙述中正确的是 o(2007年3月)A) 数据的逻辑结构与存储结构是一一对应的B) 算法的时间复杂度与空间复杂度一定相关C) 算法的效率只与问题的规模有关,而与数据的存储结构无关D) 算法的时间复杂度是指执行算法所需要的计算工作量解析:1、算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基木运算次数来度虽,而算法所执行的基木运算次数是问题规模的函数;算法的空间复杂度一般是指执行这个算法所需要的内存空间。2、 算法的时间复杂度与空间复杂度并不相关。3、 数据的逻辑结构就是数据元索之间的逻辑关系,它是从逻辑上描述数据元索Z间的关系,是独立于计算机的;数据的存储结构是硏•究数据元素和数据元素Z间的关系如何在计算机屮表示,它们并非一一对应。4、 算法的执行效率不仅与问题的规模有关,还与数据的存储结构有关。答案:D【真题5】下列叙述屮正确的是 o(2006年9