全国计算机等级考试《二级MySQL数据库程序设计》复习全书核心讲义＋历年真题详解

目录

第一部分备考指南.................................................................................2

第1章考试概述...............................................................................2

第2章复习技巧...............................................................................8

第二部分核心讲义.................................................................................10

【公共基础知识】...............................................................................10

第1章数据结构与算法...................................................................10

第2章程序设计基础.....................................................................21

第3章软件工程基础......................................................................26

第4章数据库设计基础...................................................................42

【MySQL数据库程序设计】.....................................................................55

第1章数据库技术的基本概念与方法......................................................55

第2章MySQL概述......................................................................64

第3章数据库和表.......................................................................76

第4章表数据的基本操作.................................................................90

第5章数据库的查询......................................................................95

第6章索引...........................................................................111

第7章视图...........................................................................117

第8章数据完整性约束与表维护语句......................................................122

第9章触发器...........................................................................130

第10章田件..........................................................................133

第11章存储过程与存储函数..............................................................136

第12章访问控制与安全管理..............................................................145

第13章备份与恢复......................................................................152

第14章PHP的MySQL数据库编程.......................................................159

第15章开发实例........................................................................167

第三部分历年真题及详解.........................................................................181

全国计算机等级考试《二级MySQL数据库程序设计》真题精选（一）.............................181

全国计算机等级考试《二级MySQL数据库程序设计》真题精选（二）.............................185

第四部分模拟试题及详解.........................................................................190

全国计算机等级考试《二级MySQL数据库程序设计》模拟试题及详解（一）.......................190

全国计算机等级考试《二级MySQL数据库程序设计》模拟试题及详解（二）.......................194

第一部分备考指南

第1章考试概述

一、考试简介

全国计算机等级考试（NationalComputerRankExamination,简称NCRE）,是经原国家教育委员会（现教育

部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考

试体系。

计算机技术的应用在我国各个领域发展迅速，为了适应知识经济和信息社会发展的需要，操作和应用计算机

已成为人们必须掌握的一种基本技能。许多单位、部门已把掌握一定的计算机知识和应用技能作为人员聘用、职

务晋升、职称评定、上岗资格的重要依据之一。鉴于社会的客观需求，经原国家教委批准，原国家教委考试中心

于1994年面向社会推出了NCRE,其目的在于以考促学，向社会推广和普及计算机知识，也为用人部门录用和

考核工作人员提供一个统一、客观、公正的标准。

二、考试科目

级别科目名称科目代码考试时间考核课程代码

计算机基础及WPSOffice应用1490分钟114

一级计算机基础及MSOffice应用1590分钟115

计算机基础及Photoshop应用1690分钟116

C语言程序设计24120分钟201、224

VB语言程序设计26120分钟201、226

VFP数据库程序设计27120分钟201、227

Java语言程序设计28120分钟201、228

二级Access数据库程序设计29120分钟201、229

C++语言程序设计61120分钟201、261

MySQL数据库程序设计63120分钟201>263

Web程序设计64120分钟201、264

MSOffice高级应用65120分钟201、265

网络技术35120分钟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、三级网络技术、四级网络

工程师三个科目，结果通过了三级网络技术、四级网络工程师考试，但没有通过二级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月的考试。七、各级别考试介

绍

一级

科目一级WPSOffice一级MSOffice一级Photoshop

考试环境NCRE一级上机考试环境为Windows7简体中文版

PhotoshopCS5

考试软件WPSOffice2012办公软件MSOffice2010

（典型方式安装）

1.单项选择题，20题，20分1.单项选择题，20题，20分1.单项选择题，55题，55

题型及分

2.Windows操作系统的使用，2.Windows操作系统的使用，用分（含计算机基础知识部

值比例

10分分分20分）

3.WPS文字的操作，25分3.Word操作，25分2.Photoshop操作题，45

4.WPS表格的操作，20分4.Excel操作,20分分

5.WPS演示软件的操作，15分5.PowerPoint操作,15分

6.浏览器（IE）的简单使用和6.浏览器（IE）的简单使用和电

电子邮件收发，10分子邮件收发，10分

1.考核内容包括计算机基础知识和操作技能两部分。

2.各科目对基础知识的要求相同，以考查应知应会为主，题型为选择题，分数占全卷的20%（20

分）。

考核内容3.办公软件类考试，操作技能部分包括汉字录入、Windows系统使用、文字排版、电子表格、

演示文稿、正的简单应用及电子邮件收发。

3.Photoshop考试，要求了解数字图像的基本知识，熟悉Photosh叩的界面与基本操作方法，掌

握并熟练运用绘图工具进行图像的绘制、编辑、修饰，会使用图层蒙版、样式以及文字工具。

形式完全采取上机考试形式，各科上机考试时间均为90分钟，满分100分。

获证条件总分不低于60分。

参加NCRE“计算机基础及Photoshop应用”科目考生，可以在NCRE报名时自愿申请免试取得

“AdobePhotoshop产品工程师认证”证书，即：通过NCRE”计算机基础及Photoshop应用”

备注

科目考试实现一次考试，可以同时取得全国计算机等级证书与“AdobePhotoshop产品工程师认

证”证书，即“一考双证”。

二级

语言程序设计类数据库程序设计类办公软件高级应用

科目C语言C++JavaVBWebVFPAccessMySQL办公软件高级应用

考试

NCRE二汲上机考试环境为Windows7简体中文版

环境

Net-

NetBea

BeansVB6.VFP6.

Visuns中国

中国0简0简MSMySQL

考试Visualal教育考

教育体中体中Access20(CommuniMSOffice2010

软件C++6.0C++试版，

考试文专文专10ty5.5.16)

6.0IE6.0

版业版业版

及以上

2007

1.单项选择

题，40题，

1.单项选择题，20

40分（含公

分（含公共基础知

共基础知识

识部分10分）

部分10分）

题型单项选择题，题，分（含公共基础知识部分分）2.文字处理题

2.程序填空1.404010

及分基本操作题，分（Worel）,30分

题，3小空，2.18

简单应用题，分3.电子表格题

值比18分3.24

综合应用/操作题，分（Excel）,30分

例3.程序改错4.18

4.演示文稿题

题，2个错误，

（PowerPoint）,20

24分

分

4.程序设计

题，18分

二级定位为程手员，考核内容包括公共基础知识和程序设计。所有科目对基础知识作统一要求，使用统

考核

一的公共基础-知识考试大纲和教程。二级公共基础知识在各科考试选择题中体现。程序设计部分，主要

内容

考查考生对程序设计语言使用和编程调试等基本能力，在选择题和操作题中加以体现。

形式完全采取上机考试形式。各科上机考试时间均为120分钟，满分100分。

三级

信息安全技

科目网络技术数据库技术软件测试技术嵌入式系统开发技术

术

考试环境1.NCRE三级上机考试环境为Windows7简体中文版

与软件2.数据库技术考核C语言程序设计，使用VisualC++6.0

1.单选题，40题，40分

题型及分

2.综合题，40分

值比例

3.应用题，20分

1.网络技术。网络规划与设计、局域网组网技术、计算机网络信息服务系统的建

立及计算机网络安全与管理。2.数据库技术。数据库应用系统分析及规划、数

据库设计及实现、数据库存储技术、并发控制技术、数据库管理与维护、数据库

技术的发展及新技术。3.软件测试技术。软件测试的基本概念、软件测试技

术、软件测试过程和管理方法。4.信息安全技术。信息安全保障概论、信息安

考核内容

全基础技术与原理、系统安全、网络安全、应用安全、信息安全管理、信息安全

标准与法规。5.嵌入式系统开发技术。嵌入式系统的概念与基础知识、嵌入式

处理器、嵌入式系统硬件组成、俄入式系统软件、嵌入式系统的开发等相关知识

和技能。

形式完全采取上机考试形式。各科上机考试时间均为120分钟，满分100分。

1.总分不低于60分，并己经（或同时）获得二级相关证书。

2.三级数据库技术证书要求已经（或同时）获得二级数据库程序设计类证书；网

络技术、软件测试技术、信息安全技术、嵌入式系统开发技术等四个证书要求已

获证条件

经

（或同时）获得二级语言程序设计类证书。

3.考生早期获得的证书（如Pascal.FoxBase等），不严格区分语言程序设计和数

备注无

四级

⑼]]程数据座口程炜S在则临信息安全工程嵌入式系统开

科目轨件测试工程师师发工程师

考试环境NCRE四级上方（考试环境为Windows7简体中文版。

题型及分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.掌握数据库技术的基本概念和方法。

2.熟练掌握MySQL的安装与配置。

3.熟练掌握MySQL平台下使用SQL语言实现数据库的交互操作。

4.熟练掌握MySQL的数据库编程。

5.熟悉PHP应用开发语言，初步具备利用该语言进行简单应用系统开发的能力。

6.掌握MySQL数据库的管理与维护技术。

九、考试内容

（一）基本概念与方法

1.数据库的基本概念和特点

2.数据库系统的结构

3.数据模型

4.数据库设计方法

（二）MySQL平台下的SQL交互操作

1.数据库、表、索引和视图的相关概念

2.数据库、表、索引和视图的创建及维护方法

3.数据完整性约束的概念、定义及使用方法

4.表和视图的查询及数据更新操作

（三）MySQL的数据库编程

1.触发器、事件、存储过程和存储函数的概念及作用

2.触发器的创建及使用

3.事件的创建及使用

4.存储过程和存储函数的创建及使用

（四）MySQL的管理与维护

1.MySQL的安装与配置

2.MySQL用户账号管理的作用及方法

3.MySQL账户权限管理的作用及方法

4.MySQL数据库备份与恢复的概念及方法

5.二进制日志文件的使用

（五）MySQL的应用编程

1.PHP语言的基本使用方法

2.MySQL平台下编制PHP简单应用程序十、

成绩及证书

1.NCRE实行百分制计分，但以等第通知考生成绩。等第共分优秀、及格、不及格三等。90〜100分为优

秀、60〜89分为及格、0〜59分为不及格。一般在考后30个工作日内由教育部考试中心将成绩处理结果下发给

各省级承办机构。考后50个工作日，考生可登录教育部考试中心综合查询网()进行成绩查

询。部分省市如江苏、黑龙江等也可通过省市考试院或者人事考试中心进行查询。

2.NCRE成绩在及格以上者，由教育部考试中心颁发合格证书。考后45个工作日教育部考试中心将证书发

给各省级承办机构，然后由各省级承办机构逐级转发给考生。考生证书若丢失，可登录教育部考试中心综合查询

网补办合格证明书。补办合格证明书收费21元，其中制证、邮寄费用20元，银行收取手续费1元。

3.NCRE合格证书式样按国际通行证书式样设计，用中、英两种文字书写，证书编号全国统一，证书上印

有持有人身份证号码。该证书全国通用，是持有人计算机应用能力的证明，也可供用人部门录用和考核工作人员

时参考。

一级证书表明持有人具有计算机的基础知识和初步应用能力，掌握Office办公自动化软件的使用及因特网应

用，或掌握基本图形图像工具软件(Photoshop)的基本技能，可以从事政府机关、企事业单位文秘和办公信息

化工作。

二级证书表明持有人具有计算机基础知发和基本应用能力，能够使用计算机高级语言编写程序，可以从事计

算机程序的编制、初级计算机教学培训以及企业中与信息化有关的业务和营销服务工作。

三级证书表明持有人初步掌握与信息技术有关岗位的基本技能，能够参与软硬件系统的开发、运维、管理和

服务工作。

四级证书表明持有人掌握从事信息技术工作的专业技能，并有系统的计算机理论知识和综合应用能力。

第2章复习技巧

一、备考指导

I.勇往直前进入下午考试，也许有疲劳或不好的感觉，自信心就会下降；当看到题干很长，操作较复杂的

题时，就有想

回避或焦虑、急燥的情绪。这是典型的“两军未战，兵先屈”的败兴思绪。要知道两对手相遇勇者胜，勇者相遇

智者胜。抛开所有不必要的想法，相信自己的实力，做到心无旁鹫，勇往直前。

2.审清题干题干包含了整个题目的条件和要求，若题干比较复杂，就要注意将题干“分段”来阅读，前后

注意衔接，必

要时在草稿纸上记载下关键点。有时候题干艰长，看似很复杂，让很多人望而却步。其实，这种题更好解，因题

干长了贝J提示信息也就多了。主要是考你有没有勇气和耐心。

3.解读试题首先，要翻阅一下全部试卷，注意试题的时间及分数的分配情况，做到心

中有数。

其次，要弄清题意，明确题目要求。因为考试要求可能与自己习惯的答题要求有所不同，所以一定要按题意

和要求去回答。

最后，要特别注意题目中比较隐蔽的条件。一般而言，条件隐蔽的问题难度较大，考生必须看清有关的线索，

找出隐蔽条件，问题才能迎刃而解。

4.相信自己当题做得非常顺利时，心里不要太得意，因为越是看似容易的题目越是错的多，当然也不要逆

向思维，觉得

这题这么简单是不是做错了，要相信自己，说到底还是要审清题目的意思；

二、题型分析

I.选择题选择题为单选题，是客观性求题，试题覆盖面广，一般情况下考生不可能做到对每个题目都有把

握答对。这

时，就需要考生学会放弃，即不确定的题目不要在上面花费太多的时间，应该在此题上做上标记，立即转移注意

力，作答其他题目。最后有空余的时间再回过头来仔细考虑此题。但要注意，对于那些实在不清楚的题目，就不

要浪费时间了，放弃继续思考，不要因小失大。

绝大多数选择题的设问是正确观点，称为正面试题；如果设问是错误观点，称为反面试题。考生在作答选择

题时可以使用一些答题方法，以提高答题准确率。

（1）正选法（顺选法）：如果对题肢中的4个选项，一看就能肯定其中的1个是正确的，就可以直接得出答

案。注意，必须要有百分之百的把握才行。

（2）逆选法（排谬法）：逆选法是将错误答案排除的方法。对题肢中的4个选项，一看就知道其中的1个（或

2个、3个）是错误的，可以使用逆选法，即排除错误选项。

（3）比较法（蒙猜法）：这种办法是没有办法的办法，在有一定知识基础上的蒙猜也是一种方法。2.操作

题上机考试重点考察考生的基本操作能力，要求考生具有综合运用基础知识进行实际操作的能力。上机操作

题

综合性强、难度较大。上机考试的评分是以矶评为主，人工复查为辅的。机评当然不存在公正性的问题，但却存

在呆板的问题，有时还可能因为出题者考虑不周出现错评的情况。考生做题时不充分考虑到这些情况，就有可能

吃亏。

掌握好上机考试的应试技巧，可以使考生的实际水平在考试时得到充分发挥，从而取得较为理想的成绩。历

次考试均有考生因为忽略了这一点，加之较为紧张的考场气氛影响了水平的发挥，致使考试成绩大大低于实际水

平。因此每个考生在考试前，都应有充分的准备。总结以下几点供考生在复习和考试时借鉴：

（1）对于上机考试的复习，切不可“列记硬背”根据以往考试经验，有部分考生能够通过笔试，而上机考

试却不能通过，主要原因是这部分考生已经习惯于

传统考试的“死记硬背”，而对于真正的知识应用，却显得束手无策。为了克服这个弊病，考生一定要在熟记基

本知识点的基础上，加强上机训练，从历年试题中寻找解题技巧，理清解题思路，将各类典型试题反复练习。

（2）在考前，一定要重视等级考试模拟软件的使用在考试之前，应使用等级考试模拟软件进行实际的上机

操作练习，尤其要做一些具有针对性的上机模拟题，

以便熟悉考试题型，体验真实的上机环境，减轻考试时的紧张程度。

（3）学会并习惯使用帮助系统大部分软件都有较全面的帮助系统，熟练掌握帮助系统，可以使考生减少记

忆量，解决解题中的疑难问题。

（4）熟悉考试场地及环境尤其是要熟悉考场的硬件情况和所使用的相关软件的情况。考点在正式考试前，

会给考生提供一次模拟上机

的机会。模拟考试时，考生重点不应放在把题做出来，而是放在熟悉考试环境，相应软件的使用方法，考试系统

的使用等方面。

（5）做上机题时要不急不燥，认真审题先分析，后操作。明白了问题是什么以后，先把问题在脑海里过一

遍，考虑好如何操作后，再依思路从容做

答。而不要手忙脚乱、毛毛躁躁、急于作答.对于十分了解或熟悉的问题，切忌粗心大意、得意忘形、而应认真

分析，必须将题目给出的全部内容逐字看清楚后针对具体问题进行操作。

常言道“熟能生巧”、“打铁还得本身硬”，再好的方法与技巧若没有基础，是发挥不了作用的；如若有了一

定的功底，再差的招式也会产生很大的威力，就像金庸小说中杨过的那柄钝剑。但是如果只看不练，不会有提高。

建议大家多做模拟试题和历年试题，锻炼解题的能力与节奏。

第二部分核心讲义

【公共基础知识】

第1章数据结构与算法

一、算法

i.算法的基本概念

(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)=Zp(x)t(x)

X€D„

其中，x是所有可能输入中的某个特定输入，p(X)是X出现的概率，即输入为X的概率，t(X)是算法在

输入为X时所执行的基木运算次数，D”表示当规模为n时，算法执行时所有可能输入的集合.

b.最坏情况复杂性

最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义为：

W(n)=max{t(x)}

.«Dn

(2)空间复杂度

①定义算法的空间复杂度一般是指执行这个算法所需要的内存空

间。

②存储空间组成一个算法的存储空间包括以下几

种：a.算法程序占用的空间；b.输入的初始

数据占用的存储空间；c.算法执行过程中所需

要的额外空间.

额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，若额外空间相对于

问题规模来说是常数，则称该算法是原地工作的。

二、数据结构的基本概念

1.概述

（1）数据处理概述

①定义数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也

包括对

数据元素进行分析。

②关键问题大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这

是进行数据

结构处理的关键问题。

（2）数据结构研究概述

①研究问题

a.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b.在对数据进行处理时，各数据

元素在计算机中的存储关系，即数据的存储结构：c.对各种数据结构进行的运算。

②研究目的

数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包括：a,提高数据处理的速度；b.尽

量节省在数据处理过程中所占用的计算机存储空间。

2.数据结构的概念

（I）数据结构的定义数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系的数据元

素集合的表示。简言之，

数据结构是指带有结构的数据元素的集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含

以下两方面内容：

①表述数据元素的信息；

②表示各数据元素之间的前后件关系。

（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）非空线性表的结构特征：

①有且只有一个根结点ai.它无前件；

②有且只有一个终端结点所，它无后件；

③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。