2013年C语言公共基础知识(无基础)资料

计算机等级考试公共基础知识第2页全国计算机等级考试介绍全国计算机等级考试（NationalComputerRankExamination，简称NCRE），是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系。二级考核计算机基础知识和使用一种高级计算机语言编写程序以及上机调试的基本技能。考试科目：C、C++、Java、VB、Delphi、VF。第3页考试形式及题型考试方式：1笔试：90分钟，满分100分，其中公共基础（30分），C语言（70分）2上机：90分钟，满分100分；3上机操作包括：程序填空（30分）程序改错（30分）编程题（40分）4上机应用软件为VisualC++6.0第4页笔试内容分析C语言笔试考点平均分布7%15%17%26%28%7%1）C语言程序的结构2）数据类型及其运算、基本语句3）程序的三种基本结构4）数组、函数、编译预处理5）指针、结构体6）文件和位运算第5页培训方案理论辅导（40课时）公共基础知识10课时C语言程序的结构：1课时数据类型及其运算、基本语句：3课时程序的三种基本结构：4课时数组、函数、编译预处理：10课时指针、结构体：10课时文件和位运算：2课时真题训练与上机辅导（20课时）真题训练上机题讲解上机题辅导（机房）真题练习及辅导（机房）第6页如何复习－坚定信心，多验证和真题演练，不要太拘泥于语法细则；（1）读透谭浩强的C语言课本，至少读3遍，关键的章节（指针，结构体等）要读5遍，对书上的重要算法要背下来，如：最大公约数和最小公倍数，求闰年等等。排序：选择排序、冒泡排序判断素数的算法计算倒序数的算法：如输入4321，则转换成：1234最大值、最小值求法书上所有关于字符串操作的例子，要非常熟悉，字符串是重点考察的地方指针：理解各种指针操作。（常考）链表的操作（建立，插入，删除等）也要背下来第7页（2）适当的完成书后的习题，并加强上机实践。学习语言最好的方法就是上机编程。做错的题也要上机调试。（3）历年的真题务必要认真完成。考察自己掌握的程度，如果还是很生疏，再看书，直到理解了知识点为止。（4）善于总结，把错误的题记在本子上，以后就不会犯同样的错误归结如下：看书做题上机看书总结如何复习－坚定信心，多验证和真题演练，不要太拘泥于语法细则第8页C语言考试大纲一：C语言程序的结构二：数据类型及其运算三：基本语句四：选择结构程序设计五：循环结构的设计六：数组的定义和引用七：函数八：编译预处理九：指针十：结构体十一：位运算十二：文件操作第9页计算机二级考试公共基础知识大纲数据结构与算法程序设计基础软件工程基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30％，是一个不小的比例。第10页计算机二级考试公共基础知识试卷分析章节考试时间数据结构与算法程序设计基础软件工程基础数据库设计基础2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年9月10分2分8分10分2010年3月10分0分10分10分第11页算法⒈算法的基本概念2.算法复杂度的概念和意义一、基本数据结构与算法数据结构⒈数据结构的概念⒉线性表⒊栈和队列⒋树与二叉树⒌查找技术⒍排序技术对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。第12页算法的定义对解题方案准确而完整的描述称为算法。算法是程序设计的核心⒈算法的基本概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。例：解方程：f(x)=0在区间[a,b]上有实根且f(a)与f(b)异号，求该方程在区间[a,b]上的实根。有多种解法，常用的是用二分法求方程实根。第13页2.算法的基本特征一个算法应该具有以下五个重要的特征：有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成第14页算法与计算机程序算法____是一组逻辑步骤程序——用计算机语言描述的算法3.算法的表示INPUTrS=3.14*r*rPTINTS开始输入RS=3.14*R*R输出S结束问题：输入园的半径，计算园的面积一个算法的表示需要使用一些语言形式。传统的算法-------图形法，如“流程图”和N-S图目前常用的方法-------使用伪码描述算法。第15页冒泡排序的方法：1.扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；2.除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；3.重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。算法举例：n个数排序第16页4.算法的两个基本要素：基本运算和操作算术运算关系运算逻辑运算数据传输控制结构顺序选择循环一是对数据对象的运算和操作；二是算法的控制结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法第17页5.算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分第18页一、算法对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法评价：时间复杂度：执行这个算法所需要的计算工作量空间复杂度：执行这个算法所需要的内存空间第19页(1)在计算机中，算法是指______。A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法(2)下列叙述中正确的是（07年4月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指(08年4月)A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用(c)(B)算法习题:(A)第20页(4)算法的时问复杂度是指(2010年3月)A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指(09年9月)A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是(06年9月)A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对(D)计算工作量(A)(D)第21页计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。二、数据结构程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。第22页二.数据结构数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。第23页1.逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。例：1.一年四季的数据结构B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成员的数据结构B=(D,R)D={父亲，儿子，女儿}R={(父亲，儿子),(父亲，女儿)}春夏秋冬数据结构的图形表示父亲儿子女儿第24页常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结构①线性结构结构中的每个元素之间存在一个对一个的关系；②树形结构结构中的每个元素之间存在一个对多个的关系；③图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。第25页2.存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：一年四季家庭成员计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：顺序存储结构链式存储结构索引存储结构第26页•只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。•一种数据结构可以根据需要表示成一种或多种存储结构。数据的逻辑结构数据的存储结构思考:与所使用的计算机无关的是哪种结构？第27页3.数据的运算检索插入删除更新排序通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：数据的逻辑结构数据的存储结构数据的运算下一页上一页停止放映第28|92页常见的数据结构1.线性表2.栈和队列3.树第29页１．线性表（LinearList）线性表是由n（n≥0）个数据元素a1，a2，…，ai，…，an组成的一个有限序列。简单的线性表春夏秋冬复杂的线性表记录102011001张三男…记录202011003李四女…记录3记录4第30页线性表的存储结构线性表的存储结构有两种：顺序存储结构链式存储结构注意：数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处理的效率。第31页线性表的顺序存储结构顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关