全国计算机等级考试《二级C＋＋语言程序设计》复习全书【核心讲义＋历年真题详解】.docx

第一部分备考指南2第1章考试概述2第2章复习技巧9第二部分 核心讲义11【公共基础知识】 11第1章数据结构与算法11第2章程序设计基础22第3章软件工程基础27第4章数据库设计基础43【C+语言程序设计】56第1章C+语言概述56第2章数据类型、运算符和表达式61第3章基本控制结构70第4章数组、指针与引用77第5章函数81第6章类和对象84第7章继承和派生89第8章运算符重载94第9章模板97第10章 C+流98第三部分历年真题及详解104全国计算机等级考试二级C+语言程序设计真题及详解（一）104全国计算机等级考试二级C+语言程序设计真题及详解（二）130全国计算机等级考试二级C+语言程序设计真题及详解（三）148全国计算机等级考试二级C+语言程序设计真题及详解（四）166第四部分模拟试题及详解184全国计算机等级考试二级C+语言程序设计模拟试题及详解（一）184全国计算机等级考试二级C+语言程序设计模拟试题及详解（二）199第一部分备考指南第1章考试概述一、考试简介全国计算机等级考试（National Computer Rank Examination,简称NCRE）,是经原国家教育委员会（现教育 部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考 试体系。计算机技术的应用在我国各个领域发展迅速，为了适应知识经济和信息社会发展的需要，操作和应用计算机 已成为人们必须掌握的一种基本技能。许多单位、部门已把掌握一定的计算机知识和应用技能作为人员聘用、职 务晋升、职称评定、上岗资格的重要依据之一。鉴于社会的客观需求，经原国家教委批准，原国家教委考试中心 于1994年面向社会推出了 NCRE,其目的在于以考促学，向社会推广和普及计算机知识，也为用人部门录用和 考核工作人员提供一个统一、客观、公正的标准。二、考试科目级别科目名称科目代码考试时间考核课程代码一级计算机基础及WPS Office应用1490分钟114计算机基础及MS Office应用1590分钟115计算机基础及Photoshop应用1690分钟116二级C语言程序设计24120分钟20k 224VB语言程序设计26120分钟20k 226VFP数据库程序设计27120分钟201、 227Java语言程序设计28120分钟20k 228Access数据库程序设计29120分钟201> 229C+语言程序设计6120分钟201、 261MySQL数据库程序设计63120分钟201、 263Web程序设计64120分钟201、 264MS Office高级应用65120分钟201、 265三级网络技术35120分钟335数据库技术3620分钟336软件测试技术37120分钟337信息安全技术38120分钟338嵌入式系统开发技术39120分钟339四级网络工程师4190分钟401> 403数据库工程师4290分钟404、 405软件测试工程师4390分钟401、 405信息安全工程师4490分钟401、 403嵌入式系统开发工程师4590分钟401> 402说明:同次考试考生可报考多个级别或科目，但不允许重复报考同一个科目，具体要求请向所在省级承办机构进行 咨询。报考多个科目时需咨询考点，避免考场安排时冲突。如：考生同时报考了二级C、三级网络技术、四级网络 工程师三个科目，结果通过了三级网络技术、四级网络工程师考试，但没有通过二级C考试，将不颁发任何证 书，三级网络技术、四级网络工程师两个科目成绩，自考试结束之日起可保留半年（按月计算）。下一次考试考 生报考二级C并通过，将一次获得三个级别的证书；若没有通过二级C,将不能获得任何证书。同时，三级网络 技术、四级网络工程师两个科目成绩自动失效。三、报考条件1 .考生不受年龄、职业、学历等背景的限制，任何人均可根据自己学习和使用计算机的实际情况，选考不 同等级的考试。考生一次只能报考一个科目的考试。考生一次考试只能在一个考点报名。考生可以不参加考前培 训，直接报名参加考试。2 .每次考试报名的具体时间由各省（自治区、直辖市）级承办机构规定。考生按照有关规定到就近考点报 名。上次考试的笔试和上机考试仅其中一项成绩合格的，下次考试报名时应出具上次考试成绩单，成绩合格项可 以免考，只参加未通过项的考试。3 .特殊人员报考条件：现役军人可使用军官证报考NCRE考试，在其军官证号码前后各加入识别码，此办法也适用于没有身份证 的未成年人，识别码的编码有统一格式，前6位后4位。国务院和中央军事委员会联合下发的510号令，已经公 布现役军人和人民武装警察居民身份证申领发放办法，该办法自2008年1月1日起实施，现役军人可以通过 团以上单位集中向地方公安机关申请居民身份证。无身份证的学生可携带户口本参加报名，身份证丢失者凭公安机关开具的身份证明，外籍人员凭护照参加报 名。四、报考方式分为考点现场报名与网上报名。考生在考点现场报名时，需出示身份证以及缴纳相关的考试费。考生一定要亲自到场，不能由任何单位、个 人代劳。考生按要求进行信息采集，并逐一核实报名表上的个人信息：姓名、身份证号、照片、报考科目、报考 类别（是否补考）等，发现信息不一致要立刻更改。报名完成后请妥善保管“考生报名登记表”防止阻碍准考证 的领取。考生采取网上报名方式，需先在所在省份的网上报名系统注册并填报相关基本信息、上传正面免冠电子近照， 然后网上缴费或至指定地点缴费并确认身份信息，完成报名。一般情况下，每次考试每个考生只能在一个考点完成报名。考生报名时缴纳的考试费的具体金额由各省级承办机构根据考试需要和当地物价水平确定，并报当地物价部门核准。考点不得擅自加收费用。注：报名时依据的身份证明包括：居民身份证、军人的证件、护照、户口本 等。五、报考时间考试安排第一场第二场第三场报名时间12月开始5月开始11月io S以后注:各地的报名时间由考生报考所在地的当地考试机构决定。六、考试时间NCRE以往每年开考两次，从2014年开始每年开考次数由两次增为三次。2016年NCRE安排三次考试，考试时间分别为3月21日24日、9月19日22日、12月12日13日， 其中3月和9月考试开考全部级别全部科目，12月只开考一级和二级，由各省级承办机构根据实际情况确定是 否开考12月的考试。七、各级别考试介绍一级科目一级 WPS Office一级 MS Office级 Photoshop考试环境NCRE 一级上机考试环境为Windows 7简体中文版考试软件WPS Office 2012办公软件MS Office 2010Photoshop CS5 （典型方式安装）题型及分 值比例1. 单项选择题，20题，20分2. Windows操作系统的使用，10分3. WPS文字的操作，25分4. WPS表格的操作，20分5. WPS演示软件的操作，15分1. 单项选择题，20题，20分2. Windows操作系统的使用，10 分3. Word操作，25分4. Excel 操作，20 分5. PowerPoint 操作，15 分1 .单项选择题，55题，55 分（含计算机基础知识部 分20分）2 . Photoshop 操作题，45 分6.浏览器（IE）的简单使用和 电子邮件收发，10分6.浏览器（IE）的简单使用和电 子邮件收发，10分考核内容1 .考核内容包括计算机基础知识和操作技能两部分。2 .各科目对基础知识的要求相同，以考查应知应会为主，题型为选择题，分数占全卷的20% （20 分）»3 .办公软件类考试，操作技能部分包括汉字录入、Windows系统使用、文字排版、电子表格、 演示文稿、IE的简单应用及电子邮件收发。3. Photoshop考试，要求了解数字图像的基本知识，熟悉Photoshop的界面与基本操作方法，掌 握并熟练运用绘图工具进行图像的绘制、编辑、修饰，会使用图层蒙版、样式以及文字工具。形式完全采取上机考试形式，各科上机考试时间均为90分钟，满分100分。获证条件总分不低于60分。备注参加NCRE “计算机基础及Photoshop应用”科目考生，可以在NCRE报名时自愿申请免试取得 “Adobe Photoshop产品工程师认证”证书，即：通过NCRE “计算机基础及Photoshop应用” 科目考试实现一次考试，可以同时取得全国计算机等级证书与“Adobe Photoshop产品工程师认 证”证书，即“一考双证”。二级语言程序设计类数据库程序设计类办公软件高级应 用科 目1 g 口C+JavaVBWebVFPAccessMySQL办公软件高级应用考 试 环 境NCRE二级上机考试环境为Windows 7简体中文版考 试 软 件VisualC-H- 6.0VisualC+ 6.0Net-Beans 中国 教育 考试 版 2007VB6.0 简体 中文 专业 版NetBeans 中国教 育考试 版，IE6.0 及以上VFP6.0 简体中 文专业 版MSAccess2010MySQL(Community5.5.16)MS Office 2010题 型 及 分 值 比 例1.单项 选择 题，40 题，40 分（含 公共基 础知识 部分10 分）2.程序 填空 题，3小 空，18 分3.程序 改错1 .单项选择题，40题，40分（含公共基础知识部分10分）2 .基本操作题，18分3 .简单应用题，24分4 .综合应用/操作题，18分1 .单项选择题， 20分（含公共基 础知识部分10 分）2 .文字处理题 （Word） , 30 分3 .电子表格题 （Excel） , 30 分4 .演示文稿题 （PowerPoint）,20分题，2个 错误， 24分4.程序 设计 题，18 分考 核 内 容二级定位为程序员，考核内容包括公共基础知识和程序设计。所有科目对基础知识作统一要求，使用统一的公 共基础知识考试大纲和教程。二级公共基础知识在各科考试选择题中体现。程序设计部分，主要考查考生对程 序设计语言使用和编程调试等基本能力，在选择题和操作题中加以体现。形式完全采取上机考试形式。各科上机考试时间均为120分钟，满分100分。获证 条总分不低于60分件三级科目网络技术数据库技术软件测试技术信息安全技 术嵌入式系统开发技术考试环境 与软件1 . NCRE三级上机考试环境为Windows 7简体中文版2 .数据库技术考核C语言程序设计，使用Visual C+6.0题型及分 值比例1.单选题，40题，40分2.综合题，40分3.应用题，20分考核内容1 .网络技术。网络规划与设计、局域网组网技术、计算机网络信息服务系统的建 立及计算机网络安全与管理。2.数据库技术。数据库应用系统分析及规划、数 据库设计及实现、数据库存储技术、并发控制技术、数据库管理与维护、数据库 技术的发展及新技术。3.软件测试技术。软件测试的基本概念、软件测试技 术、软件测试过程和管理方法。4.信息安全技术。信息安全保障概论、信息安 全基础技术与原理、系统安全、网络安全、应用安全、信息安全管理、信息安全 标准与法规。5.嵌入式系统开发技术。嵌入式系统的概念与基础知识、嵌入式 处理器、嵌入式系统硬件组成、嵌入式系统软件、嵌入式系统的开发等相关知识 和技能。形式完全采取上机考试形式。各科上机考试时间均为120分钟，满分100分。获证条件1 .总分不低于60分，并已经（或同时）获得二级相关证书。2 .三级数据库技术证书要求已经（或同时）获得二级数据库程序设计类证书；网 络技术、软件测试技术、信息安全技术、嵌入式系统开发技术等四个证书要求已 经（或同时）获得二级语言程序设计类证书。3 .考生早期获得的证书（如Pascal. FoxBase等），不严格区分语言程序设计和数备注无四级科目网络工程 师数据库工程师软件测试工程师信息安全工程 师嵌入式系统开 发工程师考试环境NCRE四级上机考试环境为Windows 7筒体中文版。题型及分 值比例1 .单选题，60题，60分2 .多选题，20题，40分考核内容1.网络工程师。考核计算机网络、操作系统原理两门课程。测试内容包括网络系 统规划与设计的基础知识及中小型网络的系统组建、设备配置调试、网络系统现 场维护与管理的基本技能。2.数据库工程师。考核数据库原理、软件工程两门 课程。测试内容包括数据库系统的基本理论以及数据库设计、维护、管理与应用 开发的基本能力。3.软件测试工程师。考核操作系统原理、软件工程两门课 程。测试内容包括软件测试的基本理论、软件测试的规范及标准，以及制定测试 计划、设计测试用例、选择测试工具、执行测试并分析评估结果等软件测试的基 本技能。4.信息安全工程师。考核计算机网络、操作系统原理两门课程。测试 内容包括网络攻击与保护的基本理论与技术，以及操作系统、路由设备的安全防 范技能。5.嵌入式系统开发工程师。考核操作系统原理、计算机组成与接口两 门课程。测试内容包括嵌入式系统基本理论、逻辑电路基础以及嵌入式系统中的 信息表示与运算、评价方法等基本技能。形式1 .无纸化考试，考试总时间为90分钟，单课程考试没有时间要求。2 .四级考试科目由五门专业基础课程中指定的两门课程组成，总分100分，两门 课程各占50分。3.专业基础课程为计算机专业核心课程，包括：操作系统原 理、计算机组成与接口、计算机网络、数据库原理、软件工程。获证条件两门课程分别达到30分及以上，并已经（或同时）获得三级相关证书。2013年3月及以前获得的三级各科目证书，不区分科目，可以作为四级任一科目的 获证条件。备注无 2015年NCRE继续实施2013年版考试大纲，教材参见全国计算机等级考试教材目录（2015年版）。八、考试要求1 .掌握C+语言的基本语法规则。2 .熟练掌握有关类与对象的相关知识。3 .能够阅读和分析C+程序。4 .能够采用面向对象的编程思路和方法编写应用程序。5 .能熟练使用VisualC+6.0集成开发环境编写和调试程序。九、考试内容（-）C+语言概述1 . 了解C+语言的基本符号。2 . 了解C+语言的词汇（关键字、标识符、常量、运算符、标点符号等）。3 .掌握C+程序的基本框架。4 .能够使用VisualC+6.0集成开发环境编辑、编译、运行与调试程序。（-）数据类型、表达式和基本运算1 .掌握C+数据类型（基本类型，指针类型）及其定义方法。2 . 了解C+的常量定义（整型常量，字符常量，逻辑常量，实型常量，地址常量，符号常量）。3 .掌握变量的定义与使用方法（变量的定义及初始化，全局变量，局部变量）。4 .掌握C+运算符的种类、运算优先级和结合性。5 .熟练掌握C+表达式类型及求值规则（赋值运算，算术运算符和算术表达式，关系运算符和关系表达式, 逻辑运算符和逻辑表达式，条件运算，指针运算，逗号表达式）。（三）C+的基本语句1 .掌握C什的基本语句，例如赋值语句、表达式语句、复合语句、输入、输出语句和空语句等。2 .用if语句实现分支结构。3 .用switch语句实现多分支选择结构。4 .用fbr语句实现循环结构。5 .用while语句实现循环结构。6 .用do. .while语句实现循环结构。7.转向语句（goto,continue,break和return）。8.掌握分支语句和循环语句的各种嵌套使用。（四）数组、指针与引用1 .掌握一维数组的定义、初始化和访问，了解多维数组的定义、初始化和访问。2 . 了解字符串与字符数组。3.熟练掌握常用字符串函数（strlen,strcpy,strcat,strcmp,strstr 等）。4.指针与指针变量的概念，指针与地址运算符，指针与数组。5 .引用的基本概念，引用的定义与使用。（五）掌握函数的有关使用12345678.函数的定义方法和调用方法。，.函数的类型和返回值。.形式参数与实际参数，参数值的传递。,变量的作用域和生存周期。.递归函数。，.函数重载。1.内联函数。.带有默认参数值的函数。（六）熟练掌握类与对象的相关知识1.类的定义方式、数据成员、成员函数及访问权限（public.private,protected） o 2.对象和对象指针的定义与使用。3 .构造函数与析构函数。4 .静态数据成员与静态成员函数的定义与使用方式。5 .常数据成员与常成员函数。6 . this指针的使用。7.友元函数和友元类。8.对象数组与成员对象。（七）掌握类的继承与派生知识1 .派生类的定义和访问权限。2 .继承基类的数据成员与成员函数。3 .基类指针与派生类指针的使用。4 .虚基类。5 .子类型关系。（八）了解多态性概念1 .虚函数机制的要点。2 .纯虚函数与抽象基类，虚函数。3 . 了解运算符重载。（九）模板1 .简单了解函数模板的定义和使用方式。2 .简单了解类模板的定义和使用方式。（十）输入输出流1 .掌握C+流的概念。2 .能够使用格式控制数据的输入输出。3 .掌握文件的I/O操作。十、成绩及证书1. NCRE实行百分制计分，但以等第通知考生成绩。等第共分优秀、及格、不及格三等。90100分为优 秀、6089分为及格、059分为不及格。一般在考后30个工作日内由教育部考试中心将成绩处理结果下发给 各省级承办机构。考后50个工作日，考生可登录教育部考试中心综合查询网()进行成绩查 询。部分省市如江苏、黑龙江等也可通过省市考试院或者人事考试中心进行查询。2. NCRE成绩在及格以上者，由教育部考试中心颁发合格证书。考后45个工作日教育部考试中心将证书发 给各省级承办机构，然后由各省级承办机构逐级转发给考生。考生证书若丢失，可登录教育部考试中心综合查询 网补办合格证明书。补办合格证明书收费21元，其中制证、邮寄费用20元，银行收取手续费1元。3. NCRE合格证书式样按国际通行证书式样设计，用中、英两种文字书写，证书编号全国统一，证书上印 有持有人身份证号码。该证书全国通用，是持有人计算机应用能力的证明，也可供用人部门录用和考核工作人员 时参考。一级证书表明持有人具有计算机的基础知识和初步应用能力，掌握Office办公自动化软件的使用及因特网应 用，或掌握基本图形图像工具软件(Photoshop)的基本技能，可以从事政府机关、企事业单位文秘和办公信息 化工作。二级证书表明持有人具有计算机基础知识和基本应用能力，能够使用计算机高级语言编写程序，可以从事计 算机程序的编制、初级计算机教学培训以及企业中与信息化有关的业务和营销服务工作。三级证书表明持有人初步掌握与信息技术有关岗位的基本技能，能够参与软硬件系统的开发、运维、管理和 服务工作。四级证书表明持有人掌握从事信息技术工作的专业技能，并有系统的计算机理论知识和综合应用能力。第2章复习技巧一、备考指导1 .勇往直前进入下午考试，也许有疲劳或不好的感觉，自信心就会下降；当看到题干很长，操作较复杂的题时，就有想 回避或焦虑、急燥的情绪。这是典型的“两军未战，兵先屈”的败兴思绪。要知道两对手相遇勇者胜，勇者相遇 智者胜。抛开所有不必要的想法，相信自己的实力，做到心无旁鹫，勇往直前。2 .审清题干题干包含了整个题目的条件和要求，若题干比较复杂，就要注意将题干“分段”来阅读，前后 注意衔接，必要时在草稿纸上记载下关键点。有时候题干很长，看似很复杂，让很多人望而却步。其实，这种题更好解，因题 干长了则提示信息也就多了。主要是考你有没有勇气和耐心。3 .解读试题首先，要翻阅一下全部试卷，注意试题的时间及分数的分配情况，做到心中有数。其次，要弄清题意，明确题目要求。因为考试要求可能与自己习惯的答题要求有所不同，所以一定要按题意 和要求去回答。最后，要特别注意题目中比较隐蔽的条件。一般而言，条件隐蔽的问题难度较大，考生必须看清有关的线索， 找出隐蔽条件，问题才能迎刃而解。4 .相信自己当题做得非常顺利时，心里不要太得意，因为越是看似容易的题目越是错的多，当然也不要逆 向思维，觉得这题这么简单是不是做错了，要相信自己，说到底还是要审清题目的意思；二、题型分析1.选择题选择题为单选题，是客观性试题，试题覆盖面广，一般情况下考生不可能做到对每个题目都有把 握答对。这时，就需要考生学会放弃，即不确定的题目不要在上面花费太多的时间，应该在此题上做上标记，立即转移注意 力，作答其他题目。最后有空余的时间再回过头来仔细考虑此题。但要注意，对于那些实在不清楚的题目，就不 要浪费时间了，放弃继续思考，不要因小失大。绝大多数选择题的设问是正确观点，称为正面试题；如果设问是错误观点，称为反面试题。考生在作答选择 题时可以使用一些答题方法，以提高答题准确率。（1）正选法（顺选法）：如果对题支中的4个选项，一看就能肯定其中的1个是正确的，就可以直接得出答 案。注意，必须要有百分之百的把握才行。（2）逆选法（排谬法）：逆选法是将错误答案排除的方法。对题支中的4个选项，一看就知道其中的1个（或 2个、3个）是错误的，可以使用逆选法，即排除错误选项。（3）比较法（蒙猜法）：这种办法是没有办法的办法，在有一定知识基础上的蒙猜也是一种方法。2.操作 题上机考试重点考察考生的基本操作能力，要求考生具有综合运用基础知识进行实际操作的能力。上机操作 题综合性强、难度较大。上机考试的评分是以机评为主，人工复查为辅的。机评当然不存在公正性的问题，但却存 在呆板的问题，有时还可能因为出题者考虑不周出现错评的情况。考生做题时不充分考虑到这些情况，就有可能 吃亏。掌握好上机考试的应试技巧，可以使考生的实际水平在考试时得到充分发挥，从而取得较为理想的成绩。历 次考试均有考生因为忽略了这一点，加之较为紧张的考场气氛影响了水平的发挥，致使考试成绩大大低于实际水 平。因此每个考生在考试前，都应有充分的准备。总结以下几点供考生在复习和考试时借鉴：（1）对于上机考试的复习，切不可“死记硬背”根据以往考试经验，有部分考生能够通过笔试，而上机考 试却不能通过，主要原因是这部分考生已经习惯于传统考试的“死记硬背”，而对于真正的知识应用，却显得束手无策。为了克服这个弊病，考生一定要在熟记基 本知识点的基础上，加强上机训练，从历年试题中寻找解题技巧，理清解题思路，将各类典型试题反复练习。（2）在考前，一定要重视等级考试模拟软件的使用在考试之前，应使用等级考试模拟软件进行实际的上机 操作练习，尤其要做一些具有针对性的上机模拟题，以便熟悉考试题型，体验真实的上机环境，减轻考试时的紧张程度。（3）学会并习惯使用帮助系统大部分软件都有较全面的帮助系统，熟练掌握帮助系统，可以使考生减少记忆量，解决解题中的疑难问题。(4)熟悉考试场地及环境尤其是要熟悉考场的硬件情况和所使用的相关软件的情况。考点在正式考试前， 会给考生提供一次模拟上机的机会。模拟考试时，考生重点不应放在把题做出来，而是放在熟悉考试环境，相应软件的使用方法，考试系统 的使用等方面。(5)做上机题时要不急不燥，认真审题先分析，后操作。明白了问题是什么以后，先把问题在脑海里过一 遍，考虑好如何操作后，再依思路从容做答。而不要手忙脚乱、毛毛躁躁、急于作答。对于十分了解或熟悉的问题，切忌粗心大意、得意忘形、而应认真 分析，必须将题目给出的全部内容逐字看清楚后针对具体问题进行操作。常言道“熟能生巧”、“打铁还得本身硬”，再好的方法与技巧若没有基础，是发挥不了作用的；如若有了一 定的功底，再差的招式也会产生很大的威力，就像金席小说中杨过的那柄钝剑。但是如果只看不练，不会有提高。 建议大家多做模拟试题和历年试题，锻炼解题的能力与节奏。第二部分核心讲义【公共基础知识】第1章 数据结构与算法一、算法1 .算法的基本概念(1)算法的定义算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。它是 一组严谨定义运算顺序的规则，且每个规则都是明确有效的，此顺序将在有限的次数下终止。需要注意的是：算法不等于程序，也 不等于计算方法。(2)算法的基本特征可行性a.算法中的每一步骤都必须能够实现；b.算法执行的结果要能够达到预期的目的。确定性确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多 义性。有穷性有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤之后终止，且必须有合理 的执行时间。拥有足够的情报算法是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法有足够的情报时, 此算法有效，而当提供的情报不够时，算法可能无效。2 .算法设计基本方法(1)列举法基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需 要的。常用于解决“是否存在”或“有多少种可能”等类型的问题。主要特点算法比较简单，但列举情况较多时，算法工作量很大。注意事项例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、完备化、系统化，并 从中找出规律，或对所有可能的情况进行分类，从而引出一些有用的信息，减少列举量。(2)归纳法基本思想通过列举少量的特殊情况，经过分析，最后找出一般的关系。主要特点a.比列举法更能反映问题的本质，可解决列举量为无限的问题；b.可操作性低，不易归纳出一个具体数学模型；c.归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。(3)递推基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。主要特点a.初始条件或问题本身已给定，或通过对问题的分析化简得到：b.递推本质上属于归纳法，递推关系式往往是归纳的结果：c.数值型递推算法计算过程中必须注意数值计算的稳定性问题。(4)递归基本思想将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着原来分解的逆过程逐步进行综合。 主要特点a.递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求 解；b.在可计算性理论和算法设计中占有重要地位；c.递归算法比递推算法清晰易 读，结构简练；d.设计递归算法比递推算法容易，但是其执行效率较低。分类a.直接递归。一个算法P显式地调用自己。b.间接递归。算法P调用另一个算法Q,而算法Q又调用算法P。递归与递推的区别递归与递推的区别主要在于二者实现方法的不同，表现为：a.递归是从算法本身到达递归的边界的；b.递推是从初始条件出发，逐次推出所需求的结果。(5)减半递推技术减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性 质不变：“递推”指重复“减半”的过程。(6)回溯法回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试 探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。3 .算法复杂度(1)时间复杂度定义算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f (n)其中，n是问题的规模。在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量: a.平均性态平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。算法 的平均性态定义为：A(n) = X P(x)t(x)XDn其中，X是所有可能输入中的某个特定输入，p(X)是X出现的概率，即输入为X的概率，t(X)是算法在 输入为x时所执行的基本运算次数，Dn表示当规模为n时，算法执行时所有可能输入的集合。b.最坏情况复杂性最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义为：W(n) = maxt(x)(2)空间复杂度定义算法的空间复杂度一般是指执行这个算法所需要的内存空间。存储空间组成一个算法的存储空间包括以下几种：a.算法程序占用的空间；b.输入的初始数据占用的存储空间；c.算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，若额外空间相对于 问题规模来说是常数，则称该算法是原地工作的。二、数据结构的基本概念1 .概述（1）数据处理概述定义数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也 包括对数据元素进行分析。关键问题大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这 是进行数据结构处理的关键问题。（2）数据结构研究概述研究问题a.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b.在对数据进行处理时，各数据 元素在计算机中的存储关系，即数据的存储结构：c.对各种数据结构进行的运算。研究目的数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包括：a.提高数据处理的速度；b.尽 量节省在数据处理过程中所占用的计算机存储空间。2 .数据结构的概念（1）数据结构的定义数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系的数据元 素集合的表示。简言之，数据结构是指带有结构的数据元素的集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含 以下两方面内容：表述数据元素的信息；表示各数据元素之间的前后件关系。（2）数据的逻辑结构定义数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。要素：a.数据元素的集合，通常记为D；b. D上的关系，通常记为R,它反映了 D中各数据元素之间的前后件关系。表示一个数据结构B可表示为：B= （D, R）为反映D中个数据元素之间的前后件关系，一般用二元组来表示。（3）数据的存储结构定义数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储空间中的存放形式。在数据 的存储结构中，不仅要存放各数据元素的信息，而且要存放各数据元素之间的前后件信息。常用的存储结构：a.顺序；b.链接；c.索引。采用不同的存储结构，数据处理的效率是不同的。3.数据结构的图形表示（1）在数据结构的图形表示中，数据集合D中每个元素用中间标有元素值的方框表示，称为数据结点（简 称结点）；对关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。（2）在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（也称叶子结点），其余结 点都称为内部结点。（3）数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数量的增减以及各结点之间的前后 件关系的动态变化上。4.线性结构与非线性结构根据数据结构中各数据元素之间的前后件关系的复杂程度， 可将数据结构分为：(1)线性结构(线性表)一个非空的数据结构满足下列两个条 件时，称其为线性结构：有且只有一个根结点；每个结点最多只有一个前件，也最多只有一个后件。线性结构中插入或删除任何一个结点还应是线性结构，如果不满足这个条件就不能称之为线性结构。(2)非线性结构如果一个数据结构不是线性结构，则称之为非线性结构。注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属于线性结构还是非线性结构，需要 根据对该数据结构的运算是否按照线性结构的规则来处理进行判断。三、线性表及其顺序存储结构1.线性表的基本概念(1)线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决 于它们自己的序号，即数据元素之间的相时位置是线性的。(2)非空线性表的结构特征：有且只有一个根结点它无前件；有且只有一个终端结点a”，它无后件：除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。2.线性表的顺序存储结构(1)概述顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。(2)特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个 元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。(3)运算在线性表的顺序存储结构下，可对线性表进行以下运算：插入：在线性表的指定位置处加入一个新的元素；删除：在线性表中删除指定的元素；查找：在线性表中查找某个(或某些)特定的元素：排序：对线性表中的元素进行整序；分解：按要求将一个线性表分解成多个线性表；合并：按要求将多个线性表合并成一个线性表；复制：复制一个线性表；逆转：逆转一个线性表等。3 .顺序表的插入运算假设线性表的存储空间为V (1： m),线性表的长度为n (n<m),插入的位置为i (表示在第i个位置插入 元素)，则顺序表插入新元素过程如下：(1)首先处理以下三种异常情况：当存储空间已满(即n=m)时为“上溢”错误，不能进行插入，算法结束；当i>n时，认为在最后一个元素之后(即第n+1个元素之前)插入；当i<l时，认为在第1个元素之前插入。(2)从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。(3)最后将新元素插入到第i个位置，并且将线性表的长度增加1。4.顺序表的删除运算