208年9月全国计算机等级考试《二级web程序设计》复习全书【核心讲义+历年真题详解】268p.doc

2018年9月全国计算机等级考试
《二级Web程序设计》复习全书【核心讲义＋历年真题详解】

最新资料，WORD格式，可编辑修改！

目　录
第一部分　备考指南 5
第1章　考试概述 5
第2章　复习技巧 11
第二部分　核心讲义 13
【公共基础知识】 13
第1章　数据结构与算法 13
第2章　程序设计基础 23
第3章　软件工程基础 28
第4章　数据库设计基础 44
【Web程序设计】 56
第1章　Web技术基础 56
第2章　HTTP协议基础 68
第3章　HTML语言基础 79
第4章　CSS基础 96
第5章　JavaScript语言基础 107
第6章　动态网页技术概述 128
第三部分　历年真题及详解 144
全国计算机等级考试《二级Web程序设计》真题精选（一） 144
全国计算机等级考试《二级Web程序设计》真题精选（二） 148
第四部分　模拟试题及详解 152
全国计算机等级考试《二级Web程序设计》模拟试题及详解（一） 152
全国计算机等级考试《二级Web程序设计》模拟试题及详解（二） 156
第一部分　备考指南
第1章　考试概述
一、考试简介
全国计算机等级考试（National Computer Rank Examination，简称NCRE），是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系。
计算机技术的应用在我国各个领域发展迅速，为了适应知识经济和信息社会发展的需要，操作和应用计算机已成为人们必须掌握的一种基本技能。许多单位、部门已把掌握一定的计算机知识和应用技能作为人员聘用、职务晋升、职称评定、上岗资格的重要依据之一。鉴于社会的客观需求，经原国家教委批准，原国家教委考试中心于1994年面向社会推出了NCRE，其目的在于以考促学，向社会推广和普及计算机知识，也为用人部门录用和考核工作人员提供一个统一、客观、公正的标准。
二、考试科目
级别
科目名称
科目代码
考试时间
考核课程代码
一级
计算机基础及WPS Office应用
14
90分钟
114
计算机基础及MS Office应用
15
90分钟
115
计算机基础及Photoshop应用
16
90分钟
116
二级
C语言程序设计
24
120分钟
201、224
VB语言程序设计
26
120分钟
201、226
VFP数据库程序设计
27
120分钟
201、227
Java语言程序设计
28
120分钟
201、228
Access数据库程序设计
29
120分钟
201、229
C++语言程序设计
61
120分钟
201、261
MySQL数据库程序设计
63
120分钟
201、263
Web程序设计
64
120分钟
201、264
MS Office高级应用
65
120分钟
201、265
三级
网络技术
35
120分钟
335
数据库技术
36
120分钟
336
软件测试技术
37
120分钟
337
信息安全技术
38
120分钟
338
嵌入式系统开发技术
39
120分钟
339
四级
网络工程师
41
90分钟
401、403
数据库工程师
42
90分钟
404、405
软件测试工程师
43
90分钟
401、405
信息安全工程师
44
90分钟
401、403
嵌入式系统开发工程师
45
90分钟
401、402
说明:
同次考试考生可报考多个级别或科目，但不允许重复报考同一个科目，具体要求请想所在省级承办机构进行咨询。
报考多个科目时需咨询考点，避免考场安排时冲突。如：考生同时报考了二级C、三级网络技术、四级网络工程师三个科目，结果通过了三级网络技术、四级网络工程师考试，但没有通过二级C考试，将不颁发任何证书，三级网络技术、四级网络工程师两个科目成绩，自考试结束之日起可保留半年（按月计算）。下一次考试考生报考二级C并通过，将一次获得三个级别的证书；若没有通过二级C，将不能获得任何证书。同时，三级网络技术、四级网络工程师两个科目成绩自动失效。
三、报考条件
1．考生不受年龄、职业、学历等背景的限制，任何人均可根据自己学习和使用计算机的实际情况，选考不同等级的考试。考生一次只能报考一个科目的考试。考生一次考试只能在一个考点报名。考生可以不参加考前培训，直接报名参加考试。
2．每次考试报名的具体时间由各省（自治区、直辖市）级承办机构规定。考生按照有关规定到就近考点报名。上次考试的笔试和上机考试仅其中一项成绩合格的，下次考试报名时应出具上次考试成绩单，成绩合格项可以免考，只参加未通过项的考试。
3．特殊人员报考条件：
现役军人可使用军官证报考NCRE考试，在其军官证号码前后各加入识别码，此办法也适用于没有身份证的未成年人，识别码的编码有统一格式，前6位后4位。国务院和中央军事委员会联合下发的510号令，已经公布《现役军人和人民武装警察居民身份证申领发放办法》，该办法自2008年1月1日起实施，现役军人可以通过团以上单位集中向地方公安机关申请居民身份证。
无身份证的学生可携带户口本参加报名，身份证丢失者凭公安机关开具的身份证明，外籍人员凭护照参加报名。
四、报考方式
分为考点现场报名与网上报名。
考生在考点现场报名时，需出示身份证以及缴纳相关的考试费。考生一定要亲自到场，不能由任何单位、个人代劳。考生按要求进行信息采集，并逐一核实报名表上的个人信息：姓名、身份证号、照片、报考科目、报考类别（是否补考）等，发现信息不一致要立刻更改。报名完成后请妥善保管“考生报名登记表”防止阻碍准考证的领取。
考生采取网上报名方式，需先在所在省份的网上报名系统注册并填报相关基本信息、上传正面免冠电子近照，然后网上缴费或至指定地点缴费并确认身份信息，完成报名。
一般情况下，每次考试每个考生只能在一个考点完成报名。
考生报名时缴纳的考试费的具体金额由各省级承办机构根据考试需要和当地物价水平确定，并报当地物价部门核准。考点不得擅自加收费用。
注：报名时依据的身份证明包括：居民身份证、军人的证件、护照、户口本等。
五、报考时间
考试安排
第一场
第二场
第三场
报名时间
12月开始
5月开始
11月10日以后
注：各地的报名时间由考生报考所在地的当地考试机构决定。
六、考试时间
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 2010
Photoshop CS5
（典型方式安装）
题型及分值比例
1．单项选择题，20题，20分
2．Windows操作系统的使用，10分
3．WPS文字的操作，25分
4．WPS表格的操作，20分
5．WPS演示软件的操作，15分
6．浏览器（IE）的简单使用和电子邮件收发，10分
1．单项选择题，20题，20分
2．Windows操作系统的使用，10分
3．Word操作，25分
4．Excel操作，20分
5．PowerPoint操作，15分
6．浏览器（IE）的简单使用和电子邮件收发，10分
1．单项选择题，55题，55分（含计算机基础知识部分20分）
2．Photoshop操作题，45分
考核内容
1．考核内容包括计算机基础知识和操作技能两部分。
2．各科目对基础知识的要求相同，以考查应知应会为主，题型为选择题，分数占全卷的20%（20分）。
3．办公软件类考试，操作技能部分包括汉字录入、Windows系统使用、文字排版、电子表格、演示文稿、IE的简单应用及电子邮件收发。
3．Photoshop考试，要求了解数字图像的基本知识，熟悉Photoshop的界面与基本操作方法，掌握并熟练运用绘图工具进行图像的绘制、编辑、修饰，会使用图层蒙版、样式以及文字工具。
形式
完全采取上机考试形式，各科上机考试时间均为90分钟，满分100分。
获证条件
总分不低于60分。
备注
参加NCRE“计算机基础及Photoshop应用”科目考生，可以在NCRE报名时自愿申请免试取得“Adobe Photoshop产品工程师认证”证书，即：通过NCRE“计算机基础及Photoshop应用”科目考试实现一次考试，可以同时取得全国计算机等级证书与“Adobe Photoshop产品工程师认证”证书，即“一考双证”。
二级

语言程序设计类
数据库程序设计类
办公软件高级应用
科目
C语言
C++
Java
VB
Web
VFP
Access
MySQL
办公软件高级应用
考试环境
NCRE 二级上机考试环境为 Windows 7 简体中文版
考试软件
Visual
C++ 6.0
Visual
C++ 6.0
Net-
Beans
中国教育考试版2007
VB6.0 简体中文专业版
NetBeans中国教育考试版，IE6.0 及以上
VFP6.0 简体中文专业版
MS Access2010

MS Office 2010
题型及分值比例
1．单项选择题，40题，40分（含公共基础知识部分10分）
2．程序填空题，3小空，18分
3．程序改错题，2个错误，24分
4．程序设计题，18分
1．单项选择题，40题，40分（含公共基础知识部分10分）
2．基本操作题，18分
3．简单应用题，24分
4．综合应用/操作题，18分
1．单项选择题，20分（含公共基础知识部分10分）
2．文字处理题（Word），30分
3．电子表格题（Excel），30分
4．演示文稿题（PowerPoint），20分
考核内容
二级定位为程序员，考核内容包括公共基础知识和程序设计。所有科目对基础知识作统一要求，使用统一的公共基础知识考试大纲和教程。二级公共基础知识在各科考试选择题中体现。程序设计部分，主要考查考生对程序设计语言使用和编程调试等基本能力，在选择题和操作题中加以体现。
形式
完全采取上机考试形式。各科上机考试时间均为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“计算机基础及Photoshop应用”科目考生，可以在NCRE报名时自愿申请免试取得“Adobe Photoshop产品工程师认证”证书，即：通过NCRE“计算机基础及Photoshop应用”科目考试实现一次考试，可以同时取得全国计算机等级证书与“Adobe Photoshop产品工程师认证”证书，即“一考双证”。
四级
科目
网络工程师
数据库工程师
软件测试工程师
信息安全工程师
嵌入式系统开发工程师
考试环境
NCRE四级上机考试环境为Windows 7简体中文版。
题型及分值比例
1．单选题，60题，60分
2．多选题，20题，40分
考核内容
1．网络工程师。考核计算机网络、操作系统原理两门课程。测试内容包括网络系统规划与设计的基础知识及中小型网络的系统组建、设备配置调试、网络系统现场维护与管理的基本技能。
2．数据库工程师。考核数据库原理、软件工程两门课程。测试内容包括数据库系统的基本理论以及数据库设计、维护、管理与应用开发的基本能力。
3．软件测试工程师。考核操作系统原理、软件工程两门课程。测试内容包括软件测试的基本理论、软件测试的规范及标准，以及制定测试计划、设计测试用例、选择测试工具、执行测试并分析评估结果等软件测试的基本技能。
4．信息安全工程师。考核计算机网络、操作系统原理两门课程。测试内容包括网络攻击与保护的基本理论与技术，以及操作系统、路由设备的安全防范技能。
5．嵌入式系统开发工程师。考核操作系统原理、计算机组成与接口两门课程。测试内容包括嵌入式系统基本理论、逻辑电路基础以及嵌入式系统中的信息表示与运算、评价方法等基本技能。
形式
1．无纸化考试，考试总时间为90分钟，单课程考试没有时间要求。
2．四级考试科目由五门专业基础课程中指定的两门课程组成，总分100分，两门课程各占50分。
3．专业基础课程为计算机专业核心课程，包括：操作系统原理、计算机组成与接口、计算机网络、数据库原理、软件工程。
获证条件
两门课程分别达到30分及以上，并已经（或同时）获得三级相关证书。
2013年3月及以前获得的三级各科目证书，不区分科目，可以作为四级任一科目的获证条件。
备注
参加NCRE“计算机基础及Photoshop应用”科目考生，可以在NCRE报名时自愿申请免试取得“Adobe Photoshop产品工程师认证”证书，即：通过NCRE“计算机基础及Photoshop应用”科目考试实现一次考试，可以同时取得全国计算机等级证书与“Adobe Photoshop产品工程师认证”证书，即“一考双证”。
·2015年NCRE继续实施2013年版考试大纲，教材参见全国计算机等级考试教材目录（2015年版）。
八、考试要求
1．理解Web工作原理，了解Web技术基础。
2．理解超文本传输协议HTTP的基本概念和模型，掌握HTTP的消息格式、常用消息头、请求消息和常用请求方法、响应消息和常用响应状态。
3．熟练掌握超文本标记语言HTML文档的结构、常用文档元素的含义和基本使用方法。
4．理解样式表语言CSS的基本概念和作用，掌握CSS的基本语法和使用方法。
5．掌握脚本语言JavaScript的基本概念和语法，掌握JavaScript对常用HTML文档元素的操作方法；了解文档对象模型DOM的基本概念和作用。
6．了解主要动态网页技术的基本概念。
九、考试内容
（一）Web技术基础
1．Internet与Web技术的基本概念
2．Web技术的主要组成
3．Web浏览器与服务器的基本概念和工作原理
4．Web应用开发构架和开发技术
（二）HTTP协议基础
1．HTTP的基本概念与交互模型
2．HTTP消息格式
3．HTTP请求消息和常用请求方法
4．HTTP响应消息和常用响应状态
5．HTTP常用消息头
（三）HTML基础
1．HTML文档的基本结构和语法
2．HTML常用元素及其基本属性
3．HTML表单与常用控件
（四）CSS基础
1．CSS的基本概念和作用
2．CSS的基本语法和基本使用方法
3．CSS的层次及其作用优先级
（五）JavaScript程序设计基础
1．JavaScript的基本概念和作用
2．JavaScript的基本语法
3．JavaScript常用内置对象
4．浏览器对象模型BOM的基本概念和作用
5．文档对象模型DOM的基本概念和作用
（六）动态网页技术概述
1．Java Servlet和JSP基本概念和原理
2．ASP.NET基本概念和原理
3．PHP基本概念和原理
4．AJAX基本概念和原理
十、成绩及证书
1．NCRE实行百分制计分，但以等第通知考生成绩。等第共分优秀、及格、不及格三等。90～100分为优秀、60～89分为及格、0～59分为不及格。一般在考后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．平均性态
平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。算法的平均性态定义为：
其中，x是所有可能输入中的某个特定输入，p（x）是x出现的概率，即输入为x的概率，t（x）是算法在输入为x时所执行的基本运算次数，Dn表示当规模为n时，算法执行时所有可能输入的集合。
b．最坏情况复杂性
最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义为：
（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）非空线性表的结构特征：
①有且只有一个根结点a1，它无前件；
②有且只有一个终端结点an，它无后件；
③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表中结点的个数n称为线性表的长度。当n＝0时，称为空表。
2．线性表的顺序存储结构
（1）概述
顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。
（2）特点：
①线性表中所有元素所占的存储空间是连续的；
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
（3）运算
在线性表的顺序存储结构下，可对线性表进行以下运算：
①插入：在线性表的指定位置处加入一个新的元素；
②删除：在线性表中删除指定的元素；
③查找：在线性表中查找某个（或某些）特定的元素；
④排序：对线性表中的元素进行整序；
⑤分解：按要求将一个线性表分解成多个线性表；
⑥合并：按要求将多个线性表合并成一个线性表；
⑦复制：复制一个线性表；
⑧逆转：逆转一个线性表等。
3．顺序表的插入运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），插入的位置为i（表示在第i个位置插入元素），则顺序表插入新元素过程如下：
（1）首先处理以下三种异常情况：
①当存储空间已满（即n＝m）时为“上溢”错误，不能进行插入，算法结束；
②当i>n时，认为在最后一个元素之后（即第n＋1个元素之前）插入；
③当i<1时，认为在第1个元素之前插入。
（2）从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。
（3）最后将新元素插入到第i个位置，并且将线性表的长度增加1。
4．顺序表的删除运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素），则顺序表删除元素的过程如下：
（1）首先处理以下两种异常情况：
①当线性表为空（即n＝0）时为“上溢”错误，不能进行插入，算法结束；
②当i<1或i>n时，认为在最后一个元素之后（即第n＋1个元素之前）插入。
（2）然后从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。
（3）最后将线性表的长度减小1。
四、栈和队列
1．栈及其基本运算
（1）栈的定义
栈是限定在一端进行插入与删除的线性表。
（2）栈的特点：
①允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。
②栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。
③通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top动态反映了栈中元素的变化情况。
（3）栈的顺序存储及其运算
在栈的顺序存储空间S（1:m）中，top＝0表示栈空；top＝m表示栈满。
栈的三种运算：
①入栈运算
人栈运算是指在栈顶位置插入一个新元素。操作过程如下：
a．首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
b．然后将栈顶指针进一（即top加1）。
c．最后将新元素x插入栈顶指针指向的位置。
②退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
a．首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈