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

1、2018年9月全国计算机等级考试二级Web程序设计复习全书【核心讲义+历年 真题详解】THROUGH TRR/N 1最新资料，WORD格式，可编辑修改! TOC o 1-5 h z 第一部分备考指南3第1章考试概述3第2章复习技巧14第二部分 核心讲义1.7.【公共基础知识】 1.7.第1章 数据结构与算法 1.7.第2章 程序设计基础 36.第3章 软件工程基础 44第4章 数据库设计基础 73.【Web程序设计】 95.第1章 Web技术基础95.第2章 HTTP协议基础 1.16.第3章 HTML语言基础 1.35.第 4 章 CSS基础.1.6.0.第5章 JavaScript语言基础

2、1.79第6章动态网页技术概述21.2.第三部分历年真题及详解 2.39.全国计算机等级考试二级 Web程序设计真题精选（一）239全国计算机等级考试二级 Web程序设计真题精选（二）2.46第四部分 模拟试题及详解 2.53.全国计算机等级考试二级 Web程序设计模拟试题及详解（一） 2.53全国计算机等级考试二级 Web程序设计模拟试题及详解（二） 2.60第一部分备考指南 第1章考试概述一、考试简介全国计算机等级考试(National Computer Rank Examination ,简称 NCRE),是经原国家教育委员会(现教育部)批准，由教育部考试中心主办，面 向社会，用于考查应

3、试人员计算机应用知识与技能的全国性计算机水平考试体系。计算机技术的应用在我国各个领域发展迅速，为了适应知识经济和信息社会 发展的需要，操作和应用计算机已成为人们必须掌握的一种基本技能。许多单位、 部门已把掌握一定的计算机知识和应用技能作为人员聘用、职务晋升、职称评定、 上岗资格的重要依据之一。鉴于社会的客观需求，经原国家教委批准，原国家教 委考试中心于1994年面向社会推出了 NCRE,其目的在于以考促学，向社会推广 和普及计算机知识，也为用人部门录用和考核工作人员提供一个统一、客观、公 正的标准。、考试科目级别科目名称科目代码考试时间考核课程代码一级计算机基础及WPS Office应用149

4、0分钟114计算机基础及MS Office应用1590分钟115计算机基础及Photoshop应用1690分钟116二级C语百程序设计24120分钟201 、 224VB语百程序设计26120分钟201 、 226VFP数据库程序设计27120分钟201 、 227Java语百程序设计28120分钟201 、 228Access数据库程序设计29120分钟201 、 229C+语百程序设计61120分钟201、261MySQL数据库程序设计63120分钟201 、 263Web程序设计64120分钟201 、 264MS Office高级应用65120分钟201 、 265三级网络技术3512

5、0分钟335数据库技术36120分钟336软件测试技术37120分钟337信息安全技术38120分钟338嵌入式系统开发技术39120分钟339四级网络工程师4190分钟401 、 403数据库工程师4290分钟404、405软件测试工程师4390分钟401 、 405信息安全工程师4490分钟401 、 403嵌入式系统开发工程师4590分钟401 、 402说明:同次考试考生可报考多个级别或科目，但不允许重复报考同一个科目，具体 要求请想所在省级承办机构进行咨询。报考多个科目时需咨询考点，避免考场安排时冲突。如：考生同时报考了二 级C、三级网络技术、四级网络工程师三个科目，结果通过了三级网

6、络技术、四 级网络工程师考试，但没有通过二级 C考试，将不颁发任何证书，三级网络技术、 四级网络工程师两个科目成绩，自考试结束之日起可保留半年（按月计算）。下 一次考试考生报考二级C并通过，将一次获得三个级别的证书；若没有通过二级 C,将不能获得任何证书。同时，三级网络技术、四级网络工程师两个科目成绩自 动失效。三、报考条件.考生不受年龄、职业、学历等背景的限制，任何人均可根据自己学习和使 用计算机的实际情况，选考不同等级的考试。考生一次只能报考一个科目的考试。 考生一次考试只能在一个考点报名。考生可以不参加考前培训，直接报名参加考 试。.每次考试报名的具体时间由各省（自治区、直辖市）级承办机

7、构规定。考 生按照有关规定到就近考点报名。上次考试的笔试和上机考试仅其中一项成绩合 格的，下次考试报名时应出具上次考试成绩单，成绩合格项可以免考，只参加未 通过项的考试。.特殊人员报考条件：现役军人可使用军官证报考 NCRE考试，在其军官证号码前后各加入识别码， 此办法也适用于没有身份证的未成年人，识别码的编码有统一格式，前 6位后4 位。国务院和中央军事委员会联合下发的 510号令，已经公布现役军人和人民 武装警察居民身份证中领发放办法，该办法自 2008年1月1日起实施，现役 军人可以通过团以上单位集中向地方公安机关申请居民身份证。无身份证的学生可携带户口本参加报名，身份证丢失者凭公安机关

8、开具的身 份证明，外籍人员凭护照参加报名。四、报考方式分为考点现场报名与网上报名。考生在考点现场报名时，需出示身份证以及缴纳相关的考试费。考生一定要 亲自到场，不能由任何单位、个人代劳。考生按要求进行信息采集，并逐一核实 报名表上的个人信息：姓名、身份证号、照片、报考科目、报考类别（是否补考） 等，发现信息不一致要立刻更改。报名完成后请妥善保管“考生报名登记表”防 止阻碍准考证的领取。考生采取网上报名方式，需先在所在省份的网上报名系统注册并填报相关基 本信息、上传正面免冠电子近照，然后网上缴费或至指定地点缴费并确认身份信 息，完成报名。一般情况下，每次考试每个考生只能在一个考点完成报名。考生报

9、名时缴纳的考试费的具体金额由各省级承办机构根据考试需要和当地 物价水平确定，并报当地物价部门核准。考点不得擅自加收费用。注：报名时依据的身份证明包括：居民身份证、军人的证件、护照、户口本五、报考时间考试安排第一场第二场第三场报名时间12月开始5月开始11月10日以后注：各地的报名时间由考生报考所在地的当地考试机构决定六、考试时间NCRE以往每年开考两次，从2014年开始每年开考次数由两次增为三次。2016年NCRE安排三次考试，考试时间分别为 3月21日24日、9月19日22日、12月12日13日，其中3月和9月考试开考全部级别全部科目，12月只开考一级和二级，由各省级承办机构根据实际情况确定

10、是否开考12月的考试。七、各级别考试介绍一级科目一级 WPS Office一级 MS Office一级 Photoshop考试环 境NCRE 一级上机考试环境为Windows 7简体中文版考试软 件WPS Office 2012 办公软件MS Office 2010Photoshop CS5（典型方式安装）题型及 分值比 例.单项选择题，20题，20 分. Windows操作系统的使 用，10分. WPS文字的操作，25分. WPS表格的操作，20分. WPS演示软件的操作，15分.浏览器（IE）的简单使用 和电子邮件收发，10分1 .单项选择题，20题,20 分Windows操作系统的使 用

11、，10分Word操作，25分Excel 操作,20 分PowerPoint 操作，15 分.浏览器（IE）的简单使用 和电子邮件收发，10分.单项选择题，55题， 55分（含计算机基础 知识部分20分）. Photoshop 操作题，45分考核内 容.考核内谷包括计算机基础知识和操作技能两部分。.各科目对基础知识的要求相同，以考查应知应会为主，题型为选择题，分数占全 卷的20% （20分）。.办公软件类考试，操作技能部分包括汉子录入、 Windows系统使用、文子排版、 电子表格、演示文稿、IE的简单应用及电子邮件收发。. Photoshop 考试，要求了解数字图像的基本知识，熟悉 Photo

12、shop 的界面与 基本操作方法，掌握并熟练运用绘图工具进行图像的绘制、编辑、修饰，会使用图 层蒙版、样式以及文字工具。形式完全采取上机考试形式，各科上机考试时间均为 90分钟，满分100分。获证条 件总分不低于60分。备注参加NCRE ”计算机基础及Photoshop 应用”科目考生，可以在 NCRE报名时自 愿申请免试取得“ Adobe Photoshop 产品工程师认证”证书，即：通过 NCRE “计 算机基础及Photoshop应用”科目考试实现一次考试，可以同时取得全国计算机等 级证书与 Adobe Photoshop广品工程师认证证书，即 考双证。二级语言程序设计类数据库程序设计类

13、办公软件高级应 用科目C语百C+ +JavaVBWebVFPAccessMySQL办公软件高级应 用考试 环境NCRE二级上机考试环境为 Windows 7 简体中文版考试软件VisualC+ 6.0Vis ual C+ +6.0Net- Bea ns 中国 教育 考试 版 200 7VB6 .0 简体 中义 专业 版NetBe ans中 国教育 考试 版，IE6.0 及以上VFP 6.0 简体 中义 专业 版MSAccess2010MySQL (Comm unity 5.5.16 )MS Office2010题型 及分 值比 例.单项选 择题，40 题，40分（含公共基础知识 部分10分）.

14、程序程1 .单项选择题，40题，40分（含公共基础知识部分10 分）.基本操作题，18分.简单应用题，24分.综合应用/操作题，18分.单项选择题，20分（含公共基 础知识部分10 分）.文字处理题（Word ） , 30分空题，3小 空，18分 3.程序改 错题，2个 错误，24 分4.程序设 计题，18 分.电子去格题(Excel) , 30分.演示文稿题(PowerPoint),20 分考核 内容二级定位为程序员，考核内容包括公共基础知识和程序设计。所有科目对基础知识作今 要求，使用今的公共基础知识考试大纲和教程。二级公共基础知识在各科考试选择题中 体现。程序设计部分，主要考查考生对程序

15、设计谛言使用和编程调试等基本能力，在选择 题和操作题中1口以体现。形式完全采取上机考试形式。各科上机考试时间均为 120分钟，满分100分。获证条件总分不低于60分三级科目网络技 术数据库技 术软件测试技术信息安全技 术嵌入式系统开发技 术考试环境 与软件. NCRE三级上机考试环境为 Windows 7 简体中文版.数据库技术考核C谛言程序设计，使用 Visual C+ 6.0题型及分 值比例.单选题，40题,40分.综合题，40分.应用题，20分考核内容.网络技术。网络规划与设计、局域网组网技术、计算机网络信息服务 系统的建立及计算机网络安全与管理。.数据库技术。数据库应用系统分析及规划、

16、数据库设计及实现、数据 库存储技术、并发控制技术、数据库管理与维护、数据库技术的发展及 新技术。.软件测试技术。软件测试的基本概念、软件测试技术、软件测试过程和管理方法。.信息安全技术。信息安全保障概论、信息安全基础技术与原理、系统 安全、网络安全、应用安全、信息安全管理、信息安全标准与法规。.嵌入式系统开发技术。嵌入式系统的概念与基础知识、嵌入式处理器、 嵌入式系统硬件组成、嵌入式系统软件、嵌入式系统的开发等相关知识 和技能。形式完全采取上机考试形式。各科上机考试时间均为120分钟，满分100分。获证条件.总分不彳氐于60分，并已经（或同时）获得二级相关证书。.三级数据库技术证书要求已经（或

17、同时）获得二级数据库程序设计类 证书；网络技术、软件测试技术、信息安全技术、嵌入式系统开发技术 等四个证书要求已经（或同时）获得二级语言程序设计类证书。.考生早期获得的证书（如 Pascal、FoxBase等），不严格区分谛言程 序设计和数据库程序设计，可以直接报考并获得证书。备注当口 NCRE ”计算机基础及Photoshop 应用”科目考生，可以在 NCRE 报名时自愿申请免试取得“ Adobe Photoshop 产品工程师认证”证书， 即：通过NCRE ”计算机基础及Photoshop应用”科目考试实现一次考 试，可以同时取得全国计算机等级证书与 “Adobe Photoshop 产品

18、工程 师认证”证书，即“一考双证”。四级科目网络工程 师数据库工程 师软件测试工程 师信息安全工 程师嵌入式系统 开发工程师考试环境NCRE四级上机考试环境为 Windows 7 简体中文版。题型及分 值比例.单选题，60题,60分.多选题，20题,40分考核内容.网络工程师。考核计算机网络、操作系统原理两门课程。测试内容包 括网络系统规划与设计的基础知识及中小型网络的系统组建、设备配置 调试、网络系统现场维护与管理的基本技能。.数据库工程师。考核数据库原理、软件工程两门课程。测试内容包括 数据库系统的基本理论以及数据库设计、维护、管理与应用开发的基本能力。.软件测试工程师。考核操作系统原理、

19、软件工程两门课程。测试内容 包括软件测试的基本理论、软件测试的规范及标准，以及制定测试计划、 设计测试用例、选择测试工具、执行测试并分析评估结果等软件测试的 基本技能。.信息安全工程师。考核计算机网络、操作系统原理两门课程。测试内 容包括网络攻击与保护的基本理论与技术，以及操作系统、路由设备的 安全防范技能。.嵌入式系统开发工程师。考核操作系统原理、计算机组成与接口两门 课程。测试内容包括嵌入式系统基本理论、逻辑电路基础以及嵌入式系 统中的信息表示与运算、评价方法等基本技能。形式.无纸化考试，考试总时间为 90分钟，单课程考试没有时间要求。.四级考试科目由五门专业基础课程中指定的两门课程组成，

20、总分100分，两门课程各占50分。.专业基础课程为计算机专业核心课程，包括：操作系统原理、计算机 组成与接口、计算机网络、数据库原理、软件工程。获证条件两门课程分别达到30分及以上，并已经（或同时）获得三级相关证书。 2013年3月及以前状得的三级各科目证书，不区分科目，可以作为四级 任一科目的获证条件。备注当口 NCRE ”计算机基础及Photoshop 应用”科目考生，可以在 NCRE 报名时自愿申请免试取得“ Adobe Photoshop 产品工程师认证”证书， 即：通过NCRE ”计算机基础及Photoshop应用”科目考试实现一次考 试，可以同时取得全国计算机等级证书与 “Adob

21、e Photoshop 产品工程 师认证”证书，即“一考双证”。2015年NCRE继续实施2013年版考试大纲，教材参见全国计算机等级考试 教材目录（2015年版）。八、考试要求.理解Web工作原理，了解 Web技术基础。.理解超文本传输协议HTTP的基本概念和模型，掌握 HTTP的消息格式、 常用消息头、请求消息和常用请求方法、响应消息和常用响应状态。.熟练掌握超文本标记语言 HTML文档的结构、常用文档元素的含义和基 本使用方法。.理解样式表语言CSS的基本概念和作用，掌握 CSS的基本语法和使用方 法。.掌握脚本语言JavaScript的基本概念和语法，掌握 JavaScript对常用

22、HTML文档元素的操作方法；了解文档对象模型 DOM的基本概念和作用。. 了解主要动态网页技术的基本概念。九、考试内容（一）Web技术基础.Internet与 Web技术的基本概念Web技术的主要组成Web浏览器与服务器的基本概念和工作原理Web应用开发构架和开发技术（二）HTTP协议基础. HTTP的基本概念与交互模型HTTP消息格式HTTP请求消息和常用请求方法HTTP响应消息和常用响应状态HTTP常用消息头（三）HTML基础. HTML文档的基本结构和语法HTML常用元素及其基本属性HTML表单与常用控件（四）CSS基础. CSS的基本概念和作用CSS的基本语法和基本使用方法CSS的层次

23、及其作用优先级（五）JavaScript程序设计基础. JavaScript的基本概念和作用. JavaScript的基本语法. JavaScript常用内置对象.浏览器对象模型BOM的基本概念和作用.文档对象模型DOM的基本概念和作用(六)动态网页技术概述Java Servlet和JSP基本概念和原理ASP.NET基本概念和原理PHP基本概念和原理. AJAX基本概念和原理十、成绩及证书NCRE实行百分制计分，但以等第通知考生成绩。等第共分优秀、及格、 不及格三等。90100分为优秀、6089分为及格、059分为不及格。一般在 考后30个工作日内由教育部考试中心将成绩处理结果下发给各省级承办

24、机构。考后50个工作日，考生可登录教育部考试中心综合查询网( ) 进行成绩查询。部分省市如江苏、黑龙江等也可通过省市考试院或者人事考试中 心进行查询。NCRE成绩在及格以上者，由教育部考试中心颁发合格证书。考后 45个 工作日教育部考试中心将证书发给各省级承办机构，然后由各省级承办机构逐级 转发给考生。考生证书若丢失，可登录教育部考试中心综合查询网补办合格证明 书。补办合格证明书收费21元，其中制证、邮寄费用20元，银行收取手续费1 元。NCRE合格证书式样按国际通行证书式样设计，用中、英两种文字书写， 证书编号全国统一，证书上印有持有人身份证号码。该证书全国通用，是持有人 计算机应用能力的证

25、明，也可供用人部门录用和考核工作人员时参考。一级证书表明持有人具有计算机的基础知识和初步应用能力，掌握 Office办 公自动化软件的使用及因特网应用， 或掌握基本图形图像工具软件(Photoshop ) 的基本技能，可以从事政府机关、企事业单位文秘和办公信息化工作。二级证书表明持有人具有计算机基础知识和基本应用能力，能够使用计算机 高级语言编写程序，可以从事计算机程序的编制、初级计算机教学培训以及企业 中与信息化有关的业务和营销服务工作。三级证书表明持有人初步掌握与信息技术有关岗位的基本技能，能够参与软 硬件系统的开发、运维、管理和服务工作。四级证书表明持有人掌握从事信息技术工作的专业技能，

26、并有系统的计算机 理论知识和综合应用能力。第2章复习技巧一、备考指导.勇往直前进入下午考试，也许有疲劳或不好的感觉，自信心就会下降；当看到题干很 长，操作较复杂的题时，就有想回避或焦虑、急燥的情绪。这是典型的“两军未 战，兵先屈”的败兴思绪。要知道两对手相遇勇者胜，勇者相遇智者胜。抛开所 有不必要的想法，相信自己的实力，做到心无旁鹫，勇往直前。.审清题干题干包含了整个题目的条件和要求，若题干比较复杂，就要注意将题干“分 段”来阅读，前后注意衔接，必要时在草稿纸上记载下关键点。有时候题干很长, 看似很复杂，让很多人望而却步。其实，这种题更好解，因题干长了则提示信息 也就多了。主要是考你有没有勇气

27、和耐心。.解读试题首先，要翻阅一下全部试卷，注意试题的时间及分数的分配情况，做到心中 有数。其次，要弄清楚题意，明确题目要求。因为考试要求可能与自己习惯的答题 要求有所不同，所以一定要按题意和要求去回答。最后，要特别注意题目中比较隐蔽的条件。一般而言，条件隐蔽的问题难度 较大，考生必须看清有关的线索，找出隐蔽条件，问题才能迎刃而解。.相信自己当题做得非常顺利时，心里不要太得意，因为越是看似容易的题目越是错的 多，当然也不要逆向思维，觉得这题这么简单是不是做错了，要相信自己，说到 底还是要审清题目的意思；二、题型分析.选择题选择题为单选题，是客观性试题，试题覆盖面广，一般情况下考生不可能做 到对

28、每个题目都有把握答对。这时，就需要考生学会放弃，即不确定的题目不要 在上面花费太多的时间，应该在此题上做上标记，立即转移注意力，作答其他题 目。最后有空余的时间再回过头来仔细考虑此题。但要注意，对于那些实在不清 楚的题目，就不要浪费时间了，放弃继续思考，不要因小失大。绝大多数选择题的设问是正确观点，称为正面试题；如果设问是错误观点， 称为反面试题。考生在作答选择题时可以使用一些答题方法，以提高答题准确率。(1)正选法(顺选法)：如果对题支中的 4个选项，一看就能肯定其中的1 个是正确的，就可以直接得出答案。注意，必须要有百分之百的把握才行。(2)逆选法(排谬法)：逆选法是将错误答案排除的方法。

29、对题支中的4个选项，一看就知道其中的1个(或2个、3个)是错误的，可以使用逆选法，即 排除错误选项。(3)比较法(蒙猜法)：这种办法是没有办法的办法，在有一定知识基础上 的蒙猜也是一种方法。.操作题上机考试重点考察考生的基本操作能力，要求考生具有综合运用基础知识进 行实际操作的能力。上机操作题综合性强、难度较大。上机考试的评分是以机评 为主，人工复查为辅的。机评当然不存在公正性的问题，但却存在呆板的问题， 有时还可能因为出题者考虑不周出现错评的情况。考生做题时不充分考虑到这些 情况，就有可能吃亏。掌握好上机考试的应试技巧，可以使考生的实际水平在考试时得到充分发挥， 从而取得较为理想的成绩。历次

30、考试均有考生因为忽略了这一点，加之较为紧张 的考场气氛影响了水平的发挥，致使考试成绩大大低于实际水平。因此每个考生 在考试前，都应有充分的准备。总结以下几点供考生在复习和考试时借鉴：(1)对于上机考试的复习，切不可“死记硬背”根据以往考试经验，有部分考生能够通过笔试，而上机考试却不能通过，主 要原因是这部分考生已经习惯于传统考试的“死记硬背”，而对于真正的知识应 用，却显得束手无策。为了克服这个弊病，考生一定要在熟记基本知识点的基础 上，加强上机训练，从历年试题中寻找解题技巧，理清解题思路，将各类典型试 题反复练习。(2)在考前，一定要重视等级考试模拟软件的使用在考试之前，应使用等级考试模拟软

31、件进行实际的上机操作练习，尤其要做 一些具有针对性的上机模拟题，以便熟悉考试题型，体验真实的上机环境，减轻 考试时的紧张程度。(3)学会并习惯使用帮助系统大部分软件都有较全面的帮助系统，熟练掌握帮助系统，可以使考生减少记 忆量，解决解题中的疑难问题。(4)熟悉考试场地及环境尤其是要熟悉考场的硬件情况和所使用的相关软件的情况。考点在正式考试 前，会给考生提供一次模拟上机的机会。模拟考试时，考生重点不应放在把题做 出来，而是放在熟悉考试环境，相应软件的使用方法，考试系统的使用等方面。(5)做上机题时要不急不燥，认真审题先分析，后操作。明白了问题是什么以后，先把问题在脑海里过一遍，考虑 好如何操作后

32、，再依思路从容做答。而不要手忙脚乱、毛毛躁躁、急于作答。对 于十分了解或熟悉的问题，切忌粗心大意、得意忘形、而应认真分析，必须将题 目给出的全部内容逐字看清楚后针对具体问题进行操作。常言道“熟能生巧”、“打铁还得本身硬”，再好的方法与技巧若没有基础, 是发挥不了作用的；如若有了一定的功底，再差的招式也会产生很大的威力，就 像金庸小说中杨过的那柄钝剑。但是如果只看不练，不会有提高。建议大家多做 模拟试题和历年试题，锻炼解题的能力与节奏。第二部分核心讲义【公共基础知识】第1章数据结构与算法一、算法.算法的基本概念(1)算法的定义算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一 种

33、描述。它是一组严谨定义运算顺序的规则，且每个规则都是明确有效的，此顺 序将在有限的次数下终止。需要注意的是：算法不等于程序，也不等于计算方法.(2)算法的基本特征可行性a.算法中的每一步骤都必须能够实现；b.算法执行的结果要能够达到预期的目的。确定性确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的 解释，也不允许有多义性。有穷性有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤之 后终止，且必须有合理的执行时间。拥有足够的情报算法是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法有 足够的情报时，此算法有效，而当提供的情报不够时，算法可能无效。.算法设

34、计基本方法(1)列举法基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是 需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型 的问题。主要特点 算法比较简单，但列举情况较多时，算法工作量很大。注意事项例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、 完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出一 些有用的信息，减少列举量。(2)归纳法基本思想通过列举少量的特殊情况，经过分析，最后找出一般的关系。主要特点a .比列举法更能反映问题的本质，可解决列举量为无限的问题；b.可操作性低，不易归纳出一个具体数学模型；c.

35、归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。(3)递推基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。主要特点a.初始条件或问题本身已给定，或通过对问题的分析化简得到；b.递推本质上属于归纳法，递推关系式往往是归纳的结果；c .数值型递推算法计算过程中必须注意数值计算的稳定性问题。(4)递归基本思想将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着 原来分解的逆过程逐步进行综合。主要特点a.递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求解;b .在可计算性理论和算法设计中占有重要地位；c.递归算法比递推算法清晰易读，结构简练；d.

36、设计递归算法比递推算法容易，但是其执行效率较低。分类a.直接递归。一个算法P显式地调用自己。b.间接递归。算法P调用另一个算法Q,而算法Q又调用算法P。递归与递推的区别递归与递推的区别主要在于二者实现方法的不同，表现为：a.递归是从算法本身到达递归的边界的；b.递推是从初始条件出发，逐次推出所需求的结果。(5)减半递推技术减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半， 而问题的性质不变；“递推”指重复“减半”的过程。(6)回溯法回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线 索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路 线再进

37、行试探。.算法复杂度(1)时间复杂度定义算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运 算次数是问题规模的函数，即算法的工作量=f (n)其中，n是问题的规模。在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以 下两种方法来分析算法的工作量：a.平均性态平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算 法的工作量。算法的平均性态定义为：A(n) = p(x) t(x)x 二Dn其中，x是所有可能输入中的某个特定输入，p (x)是x出现的概率，即输 入为x的概率，t (x)是算法在输入为x时所执行

38、的基本运算次数，Dn表示当规 模为n时，算法执行时所有可能输入的集合。b.最坏情况复杂性最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义 为：W(n) = max 1t(x)(2)空间复杂度定义算法的空间复杂度一般是指执行这个算法所需要的内存空间。存储空间组成一个算法的存储空间包括以下几种：a.算法程序占用的空间；b.输入的初始数据占用的存储空间；c.算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附 加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。二、数据结构的基本概念.概述(1)数据处理概述定义数据处

39、理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、 查找、更改等运算，也包括对数据元素进行分析。关键问题大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计 算机的存储空间，这是进行数据结构处理的关键问题。(2)数据结构研究概述研究问题a.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储 结构；c.对各种数据结构进行的运算。研究目的数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率， 包括: a.提高数据处理的速度；b .尽量节省在数据处理过程中所占用的计算机存储空 问。.数据结

40、构的概念(1)数据结构的定义数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系 的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的集合，这 里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方面内 容：表述数据元素的信息；表示各数据元素之间的前后件关系。(2)数据的逻辑结构定义数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。要素：a.数据元素的集合，通常记为 D;b. D上的关系，通常记为R,它反映了 D中各数据元素之间的前后件关系。表小一个数据结构B可表示为：B= (D, R)为反映D中个数据元素之间的前后件关系，一般用二元组来表示。(3)数据

41、的存储结构定义数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储空 间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而且要 存放各数据元素之间的前后件信息。常用的存储结构：a.顺序；b.链接；c.索引。采用不同的存储结构，数据处理的效率是不同的。3.数据结构的图形表示(1)在数据结构的图形表示中，数据集合D中每个元素用中间标有元素值的 方框表示，称为数据结点(简称结点)；对关系 R中的每一个二元组，用一条有 向线段从前件结点指向后件结点。(2)在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端 结点(也称叶子结点)，其余结点都称为内部结点。(3)数据结

42、构中的元素结点可能是在动态变化的，这种变化体现在结点数量 的增减以及各结点之间的前后件关系的动态变化上。4.线性结构与非线性结构根据数据结构中各数据元素之间的前后件关系的复杂程度，可将数据结构分 为：(1)线性结构(线性表)一个非空的数据结构满足下列两个条件时，称其为线性结构：有且只有一个根结点；每个结点最多只有一个前件，也最多只有一个后件。线性结构中插入或删除任何一个结点还应是线性结构，如果不满足这个条件 就不能称之为线性结构。(2)非线性结构如果一个数据结构不是线性结构，则称之为非线性结构。注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属于 线性结构还是非线性结构，需要根据

43、对该数据结构的运算是否按照线性结构的规 则来处理进行判断。三、线性表及其顺序存储结构.线性表的基本概念(1)线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元 素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是 线性的。(2)非空线性表的结构特征：有且只有一个根结点a1，它无前件；有且只有一个终端结点an,它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n = 0时，称为空表。.线性表的顺序存储结构(1)概述顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。(2)特点：线性表

44、中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。(3)运算在线性表的顺序存储结构下，可对线性表进行以下运算：插入：在线性表的指定位置处加入一个新的元素；删除：在线性表中删除指定的元素；查找：在线性表中查找某个(或某些)特定的元素；排序：对线性表中的元素进行整序；分解：按要求将一个线性表分解成多个线性表；合并：按要求将多个线性表合并成一个线性表；复制：复制一个线性表；逆转：逆转一个线性表等。.顺序表的插入运算假设线性表的存储空间为 V (1 : m),线性表

45、的长度为n ( n & m),插入的 位置为i (表示在第i个位置插入元素)，则顺序表插入新元素过程如下：(1)首先处理以下三种异常情况：当存储空间已满(即n = m)时为“上溢”错误，不能进行插入，算法结束；当in时，认为在最后一个元素之后(即第 n + 1个元素之前)插入；当i1时，认为在第1个元素之前插入。(2)从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一 个位置。(3)最后将新元素插入到第i个位置，并且将线性表的长度增加 1。.顺序表的删除运算假设线性表的存储空间为 V (1 : m),线性表的长度为n ( n & m),删除的 位置为i (表示删除第i个元素)，则顺

46、序表删除元素的过程如下：(1)首先处理以下两种异常情况：当线性表为空(即n = 0)时为“上溢”错误，不能进行插入，算法结束；当in时，认为在最后一个元素之后(即第 n + 1个元素之前)插 入。(2)然后从第i + 1个元素开始，直到最后一个元素，其中每一个元素均依 次往前移动一个位置。(3)最后将线性表的长度减小1。四、栈和队列.栈及其基本运算(1)栈的定义栈是限定在一端进行插入与删除的线性表。(2)栈的特点：允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈 顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插 入也是最后被删除的。栈遵循“先进后出”或“后

47、进先出”的原则，具有记忆功能。通常用指针top来指示栈顶位置，用指针bottom 指向栈底，栈顶指针top 动态反映了栈中元素的变化情况。(3)栈的顺序存储及其运算在栈的顺序存储空间S (1:m)中，top =0表示栈空；top =m表示栈满。栈的三种运算：入栈运算人栈运算是指在栈顶位置插入一个新元素。操作过程如下：a.首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说 明栈空间已满，不可能再进行入栈操作(这种情况称为栈“上溢”错误)，算法结束。b .然后将栈顶指针进一(即top加1)。c.最后将新元素x插入栈顶指针指向的位置。退栈运算退栈运算是指取出栈顶元素并赋给一个指定的变量

48、。操作过程如下：a.首先判断栈顶指针是否为0o如果是，则说明栈空，不可能进行退栈操作 （这种情况称为栈“下溢”错误），算法结束。b.然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。c.最后将栈顶指针退一（即top减1）。读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：a.首先判断栈顶指针是否为0o如果是，则说明栈空，读不到栈顶元素，算 法结束。b .然后将栈顶元素赋给指定的变量 y。这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。.队列及其基本运算（1）什么是队列队列（Queue ）是指允许在一端进行插入、而在另一端进行删除的线性表。（2）队列的特

49、点允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称 为队头，用排头指针指向排头元素的前一个位置。最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先 出”或“后进后出”原则。队尾指针rear和排头指针front共同反映队列中元素变动情况。入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front变 化。（3）循环队列及其运算循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的 环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素，用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置 到队尾指针

50、rear指向的位置均是队列中元素。队列空的条件是s=0;队列满的条 件是 s = 1 且 front = rear。队列的两种运算假设循环队列的初始状态为空，即：s=0,且front =rear=m。入队运算入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：a.首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头 指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。b .然后将队尾指针进一（即rear = rear + 1）,并当rear = m + 1时置rear =1。c.最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。退队运

51、算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作 过程如下：a.首先判断循环队列是否为空。当循环队列为空（s= 0）时，不能进行退队 运算。这种情况称为“下溢”。此时算法结束。b .然后将排头指针进一（即front = front + 1）,并当front = m + 1时置front =1。c.再将排头指针指向的元素赋给指定的变量。d.最后判断退队后循环队列是否为空。当 front = rear时置循环队列空标志 （即 S= 0） o五、线性链表.线性链表的基本概念（1）线性表的顺序存储结构存在的缺陷：在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量 移动

52、数据元素，效率很低。在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。线性表的顺序存储结构不便于对存储空间的动态分配。（2）链式存储结点组成：数据域：用于存放数据元素值；指针域：用于存放指针。指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以 不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据 元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式 结构表示较复杂的非线性结构时，其指针域的个数要多一些。(3)线性链表定义：线性链表是线性表的链式存储结构。特点a.各数据结点的存储序号是不连续的，各结

53、点在存储空间中的位置关系与逻 辑关系也不一致；b .各数据元素之间的前后件关系是由各结点的指针域来指示的；c.每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前 件结点，只能顺指针向链尾进行扫描。为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指 针，左指针用以指向其前件结点，右指针指向其后件结点。(4)带链的栈带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。与顺序栈一样，带链栈的基本操作有以下几个：栈的初始化：建立一个空栈的顺序存储空间；入栈运算：在栈顶位置插入一个新元素；退栈运算：取出栈顶元素并赋给一个指定的变量；读栈顶元素：将栈顶元素赋给一个指定的变

54、量。(5)带链的队列与顺序队列一样，带链队列的基本操作有以下几个：队列的初始化：建立一个空队列的顺序存储空间；入队运算：在循环队列的队尾加入一个新元素；退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。.线性链表的基本运算(1)常见的线性表的运算线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前插入一个新元素；在线性链表中删除包含指定元素的结点；将两个线性链表按要求合并成一个线性链表；将一个线性链表按要求进行分解；逆转线性链表；复制线性链表；线性链表的排序；线性链表的查找。(2)在线性链表中查找指定元素非空线性链表中寻找包含指定元素值 x的前一个结点p的基本方法：从头指

55、针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点 p有两种可能：当线性 链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一 个结点序号；当线性链表中不存在包含元素 x的结点时，则找到的p为线性链表 中的最后一个结点号。(3)线性链表的插入定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。 插入过程：在线性链表中包含元素x的结点之前插入一个新元素boa.从可利用栈取得一个结点，设该结点号为 p,并置结点p的数据域为插入 的元素值b。 b.在线性链表中寻找包含元素x的前一个结点，设该结点的存储序 号为

56、q。c.最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结 点的指针域内容：第一，使结点P指向包含元素x的结点；第二，使结点q的指针域内容改为指向结点p。插入特点：a.不会发生上溢现象；b.可方便实现存储空间动态分配；c.不发生数据元素移动现象，只改变结点指针，提高插入效率。(4)线性链表的删除定义：线性链表的删除是指在链式储存结构下的线性表中删除包含指定元 素的结点。删除过程：在线性链表中删除包含元素x的结点。a.在线性链表中寻找包含元素x的前一个结点，设该结点序号为 q；b.将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元 素x的结点p的指针指向的结点；c.将包

57、含元素x的结点p送回可利用栈。在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元 素所在结点的前一个结点的指针域即可。.循环链表(1)与线性链表相比，循环链表具有的特点：在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置， 指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环 链表中，所有结点的指针构成了一个环状链。(2)与线性单链表相比，循环链表具有两方面优点：在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问 到表中其他所有的结点。而线性单链表做不到这一点。由于在循环

58、链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。循环链表的插入与删除运算要比一般单链表简单，不用考虑在空链表和在第 一个结点前插入以及空链表的删除等特殊情况，从而实现了空表与非空表运算的 统一。六、树与二叉树.树的基本概念(1)树是一种简单的非线性结构，在这种结构中，所有数据元素之间的关系 具有明显的层次特性。在树的图形表示中，上端结点是前件，下端结点是后件。(2)在树结构中，每个结点只有一个前件(父结点)，没有前件的结点只有 一个，称为树的根结点。每个结点都可以有多个后件(子结点)，没有后件的结 点称为叶子结点。(3) 一个结点拥有的后

59、件个数称为该结点的度。某结点的度为n,表示该结点有n个分支，每个分支指向一个后件，除根结点外，每个结点都有一个唯一的 分支指向它。树中的结点数为树中所有结点的度之和再加1。(4)根结点在第1层，同一层上所有结点的所有子结点都在下一层，树的最 大层次称为树的深度(5)在树中，叶子结点没有子树。(6)用树来表示算术表达式的原则：表达式中的每一个运算符在树中对应一个结点，称为运算符结点；运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为 从左到右)；运算对象中的单变量均为叶子结点。在树中，叶子结点没有子树。.二叉树及其基本性质(1)二叉树定义二叉树是一种很有用的非线性结构，与树结构很相

60、似，树结构的所有术语都 可以用到叉树这种数据结构上。(2)二叉树的两个特点非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。(3)二叉树的基本性质在二叉树的第k层上，最多有2k-1 ( k 1)个结点。深度为m的二叉树最多有2m-1个结点。在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为 2的结点 多一个。具有n个结点的二叉树，其深度至少为log 2n + 1,其中log 2n表示取 log 2n的整数部分。(4)满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。满二叉树除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树a.除最