作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
2017年9月全国计算机等级考试《二级MS Office高级应用》复习全书【核心讲义＋历年真题详解】试读：
第一部分 备考指南
第1章 考试概述
一、考试简介
全国计算机等级考试（National Computer Rank Examination，简称NCRE），是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系。
计算机技术的应用在我国各个领域发展迅速，为了适应知识经济和信息社会发展的需要，操作和应用计算机已成为人们必须掌握的一种基本技能。许多单位、部门已把掌握一定的计算机知识和应用技能作为人员聘用、职务晋升、职称评定、上岗资格的重要依据之一。鉴于社会的客观需求，经原国家教委批准，原国家教委考试中心于1994年面向社会推出了NCRE，其目的在于以考促学，向社会推广和普及计算机知识，也为用人部门录用和考核工作人员提供一个统一、客观、公正的标准。
二、考试科目级科目代考试时考核课程科目名称别码间代码计算机基础及WPS 1490分钟114Office应用一计算机基础及MS Office1511590分钟级应用计算机基础及Photoshop1611690分钟应用120分C语言程序设计24201、224钟二级120分VB语言程序设计26201、226钟120分VFP数据库程序设计27201、227钟120分Java语言程序设计28201、228钟120分29201、229Access数据库程序设计钟120分61201、261C++语言程序设计钟120分MySQL数据库程序设计63201、263钟120分Web程序设计64201、264钟120分MS Office高级应用65201、265钟120分网络技术35335钟120分36336数据库技术钟三120分37337软件测试技术级钟120分信息安全技术38338钟120分嵌入式系统开发技术39339钟网络工程师4190分钟401、403数据库工程师4290分钟404、405四级软件测试工程师4390分钟401、40544401、403信息安全工程师90分钟嵌入式系统开发工程师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月的考试。
七、各级别考试介绍一级科一级WPS Office一级MS Office一级Photoshop目考试NCRE一级上机考试环境为Windows 7简体中文版环境考Photoshop CS5试WPS Office 2012办MS Office 2010软公软件（典型方式安装）件1．单项选择题，1．单项选择题，2020题，20分题，20分2.Windows操作系2.Windows操作系统统的使用，10分的使用，10分题3.Word操作，251．单项选择题，3.WPS文字的操型分55题，55分（含作，25分及计算机基础知识4.Excel操作，20分部分20分）4.WPS表格的操分值作，20分2.Photoshop操作比5.PowerPoint操题，45分5.WPS演示软件的例作，15分操作，15分6．浏览器（IE）6．浏览器（IE）的的简单使用和电简单使用和电子邮子邮件收发，10件收发，10分分1．考核内容包括计算机基础知识和操作技能两部分。2．各科目对基础知识的要求相同，以考查应知应会为主，题型为选择题，分数占全卷的20%（20分）。考3．办公软件类考试，操作技能部分包括汉字录入、Windows核系统使用、文字排版、电子表格、演示文稿、IE的简单应用及内电子邮件收发。容3.Photoshop考试，要求了解数字图像的基本知识，熟悉Photoshop的界面与基本操作方法，掌握并熟练运用绘图工具进行图像的绘制、编辑、修饰，会使用图层蒙版、样式以及文字工具。形完全采取上机考试形式，各科上机考试时间均为90分钟，满式分100分。获证总分不低于60分。条件参加NCRE“计算机基础及Photoshop应用”科目考生，可以在NCRE报名时自愿申请免试取得“Adobe Photoshop产品工备程师认证”证书，即：通过NCRE“计算机基础及Photoshop注应用”科目考试实现一次考试，可以同时取得全国计算机等级证书与“Adobe Photoshop产品工程师认证”证书，即“一考双证”。二级数据库程序办公软件高语言程序设计类设计类级应用MAVyC科JaVWcc办公软件高C语言FS+目vaBebes级应用PQ+sL考试NCRE 二级上机考试环境为 Windows 7 简体中文版环境NeNtBMeteay-nsVSV中FQBBVi国PLM6.easu教6.（S 0 nsal育0 C考A简Visual考简o试ccMS Office 中C体试体m软es2010国C++ 6.0+中版中m件s2教+ 文，文un01育6.专IE专ity0考0业6.业 5.试版0 版5.版及1620以）07上1．单项选择题，20分1．单项选（含公共基择题，40础知识部分题，40分10分）（含公共基础知识部分2．文字处题1．单项选择题，40题，40分10分）理题型（含公共基础知识部分10分）（Word），及2．程序填2．基本操作题，18分30分分空题，3小值空，18分3．简单应用题，24分3．电子表比格题3．程序改4．综合应用/操作题，18分例（Excel），错题，2个30分错误，24分4．演示文4．程序设稿题计题，18分（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四级上机考试环境为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．掌握计算机基础知识及计算机系统组成。
2．了解信息安全的基本知识，掌握计算机病毒及防治的基本概念。
3．掌握多媒体技术基本概念和基本应用。
4．了解计算机网络的基本概念和基本原理，掌握因特网网络服务和应用。
5．正确采集信息并能在文字处理软件Word、电子表格软件Excel、演示文稿制作软件PowerPoint中熟练应用。
6．掌握Word的操作技能，并熟练应用编制文档。
7．掌握Excel的操作技能，并熟练应用进行数据计算及分析。
8．掌握PowerPoint的操作技能，并熟练应用制作演示文稿。
九、考试内容（一）计算机基础知识
1．计算机的发展、类型及其应用领域。
2．计算机中数据的表示、存储与处理。
3．多媒体技术的概念与应用。
4．计算机病毒的概念、特征、分类与防治。
5．计算机网络的概念、组成和分类；计算机与网络信息安全的概念和防控。
6．因特网网络服务的概念、原理和应用。（二）Word的功能和使用
1．Microsoft Office应用界面使用和功能设置。
2.Word的基本功能，文档的创建、编辑、保存、打印和保护等基本操作。
3．设置字体和段落格式、应用文档样式和主题、调整页面布局等排版操作。
4．文档中表格的制作与编辑。
5．文档中图形、图像（片）对象的编辑和处理,文本框和文档部件的使用，符号与数学公式的输入与编辑。
6．文档的分栏、分页和分节操作，文档页眉、页脚的设置，文档内容引用操作。
7．文档审阅和修订。
8．利用邮件合并功能批量制作和处理文档。
9．多窗口和多文档的编辑，文档视图的使用。
10．分析图文素材，并根据需求提取相关信息引用到Word文档中。（三）Excel的功能和使用
1.Excel的基本功能，工作簿和工作表的基本操作，工作视图的控制。
2．工作表数据的输入、编辑和修改。
3．单元格格式化操作、数据格式的设置。
4．工作簿和工作表的保护、共享及修订。
5．单元格的引用、公式和函数的使用。
6．多个工作表的联动操作。
7．迷你图和图表的创建、编辑与修饰。
8．数据的排序、筛选、分类汇总、分组显示和合并计算。
9．数据透视表和数据透视图的使用。
10．数据模拟分析和运算。
11．宏功能的简单使用。
12．获取外部数据并分析处理。
13．分析数据素材，并根据需求提取相关信息引用到Excel文档中。（四）PowerPoint的功能和使用
1.PowerPoint的基本功能和基本操作，演示文稿的视图模式和使用。
2．演示文稿中幻灯片的主题设置、背景设置、母版制作和使用。
3．幻灯片中文本、图形、SmartArt、图像（片）、图表、音频、视频、艺术字等对象的编辑和应用。
4．幻灯片中对象动画、幻灯片切换效果、链接操作等交互设置。
5．幻灯片放映设置，演示文稿的打包和输出。
6．分析图文素材，并根据需求提取相关信息引用到PowerPoint文档中。
十、成绩及证书
1.NCRE实行百分制计分，但以等第通知考生成绩。等第共分优秀、及格、不及格三等。90～100分为优秀、60～89分为及格、0～59分为不及格。一般在考后30个工作日内由教育部考试中心将成绩处理结果下发给各省级承办机构。考后50个工作日，考生可登录教育部考试中心综合查询网（chaxun.neea.edu.cn）进行成绩查询。部分省市如江苏、黑龙江等也可通过省市考试院或者人事考试中心进行查询。
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时所执行的基本运算次数，D表示当规模为n时，算法执行时所有可能输入的集合。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）非空线性表的结构特征：
①有且只有一个根结点a它无前件；1，
②有且只有一个终端结点a，它无后件；n
③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表中结点的个数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。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。
b．然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
c．最后将栈顶指针退一（即top减1）。
③读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
a．首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。
b．然后将栈顶元素赋给指定的变量y。
这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。
2．队列及其基本运算（1）什么是队列
队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。（2）队列的特点
①允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称为队头，用排头指针指向排头元素的前一个位置。
②最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先出”或“后进后出”原则。
③队尾指针rear和排头指针front共同反映队列中元素变动情况。
④入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front变化。（3）循环队列及其运算
循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素，用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置到队尾指针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插入队尾指针指向的位置，并且置循环队列非空标志。
②退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
a．首先判断循环队列是否为空。当循环队列为空（s＝0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。
b．然后将排头指针进一（即front＝front＋1），并当front＝m＋1时置front＝1。
c．再将排头指针指向的元素赋给指定的变量。
d．最后判断退队后循环队列是否为空。当front＝rear时置循环队列空标志（即s＝0）。
五、线性链表
1．线性链表的基本概念（1）线性表的顺序存储结构存在的缺陷：
①在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量移动数据元素，效率很低。
②在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。
③线性表的顺序存储结构不便于对存储空间的动态分配。（2）链式存储结点组成：
①数据域：用于存放数据元素值；
②指针域：用于存放指针。
指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。（3）线性链表
①定义：线性链表是线性表的链式存储结构。
②特点
a．各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻辑关系也不一致；
b．各数据元素之间的前后件关系是由各结点的指针域来指示的；
c．每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前件结点，只能顺指针向链尾进行扫描。
为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指针，左指针用以指向其前件结点，右指针指向其后件结点。（4）带链的栈
带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。
与顺序栈一样，带链栈的基本操作有以下几个：
①栈的初始化：建立一个空栈的顺序存储空间；
②入栈运算：在栈顶位置插入一个新元素；
③退栈运算：取出栈顶元素并赋给一个指定的变量；
④读栈顶元素：将栈顶元素赋给一个指定的变量。（5）带链的队列
与顺序队列一样，带链队列的基本操作有以下几个：
①队列的初始化：建立一个空队列的顺序存储空间；
②入队运算：在循环队列的队尾加入一个新元素；
③退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。
2．线性链表的基本运算（1）常见的线性表的运算
线性链表的运算主要有以下几个：
①在线性链表中包含指定元素的结点之前插入一个新元素；
②在线性链表中删除包含指定元素的结点；
③将两个线性链表按要求合并成一个线性链表；
④将一个线性链表按要求进行分解；
⑤逆转线性链表；
⑥复制线性链表；
⑦线性链表的排序；
⑧线性链表的查找。（2）在线性链表中查找指定元素
非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法：
从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。（3）线性链表的插入
①定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。
②插入过程：
在线性链表中包含元素x的结点之前插入一个新元素b。
a．从可利用栈取得一个结点，设该结点号为p，并置结点p的数据域为插入的元素值b。 b．在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。
c．最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结点的指针域内容：
第一，使结点P指向包含元素x的结点；
第二，使结点q的指针域内容改为指向结点p。
③插入特点：
a．不会发生上溢现象；
b．可方便实现存储空间动态分配；
c．不发生数据元素移动现象，只改变结点指针，提高插入效率。（4）线性链表的删除
①定义：线性链表的删除是指在链式储存结构下的线性表中删除包含指定元素的结点。
②删除过程：
在线性链表中删除包含元素x的结点。
a．在线性链表中寻找包含元素x的前一个结点，设该结点序号为q；
b．将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的结点p的指针指向的结点；
c．将包含元素x的结点p送回可利用栈。
在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。
3．循环链表（1）与线性链表相比，循环链表具有的特点：
①在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
②循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。（2）与线性单链表相比，循环链表具有两方面优点：
①在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。而线性单链表做不到这一点。
②由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
循环链表的插入与删除运算要比一般单链表简单，不用考虑在空链表和在第一个结点前插入以及空链表的删除等特殊情况，从而实现了空表与非空表运算的统一。
六、树与二叉树
1．树的基本概念（1）树是一种简单的非线性结构，在这种结构中，所有数据元素之间的关系具有明显的层次特性。在树的图形表示中，上端结点是前件，下端结点是后件。（2）在树结构中，每个结点只有一个前件（父结点），没有前件的结点只有一个，称为树的根结点。每个结点都可以有多个后件（子结点），没有后件的结点称为叶子结点。（3）一个结点拥有的后件个数称为该结点的度。某结点的度为n，表示该结点有n个分支，每个分支指向一个后件，除根结点外，每个结点都有一个唯一的分支指向它。树中的结点数为树中所有结点的度之和再加1。（4）根结点在第1层，同一层上所有结点的所有子结点都在下一层，树的最大层次称为树的深度（5）在树中，叶子结点没有子树。（6）用树来表示算术表达式的原则：
①表达式中的每一个运算符在树中对应一个结点，称为运算符结点；
②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）；
③运算对象中的单变量均为叶子结点。
在树中，叶子结点没有子树。
2．二叉树及其基本性质（1）二叉树定义
二叉树是一种很有用的非线性结构，与树结构很相似，树结构的所有术语都可以用到叉树这种数据结构上。（2）二叉树的两个特点
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。（3）二叉树的基本性质k-1
①在二叉树的第k层上，最多有2（k≥1）个结点。m
②深度为m的二叉树最多有2-1个结点。
③在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
④具有n个结点的二叉树，其深度至少为[logn]＋1，其中[[logn]22表示取logn的整数部分。2（4）满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。
①满二叉树
除最后一层外，每一层上的所有结点都有两个子结点。
②完全二叉树
a．除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
b．更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。
对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为P，则其左分支下的子孙结点的最大层次或为P，或为p＋1。
c．满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。
完全二叉树具有以下两个性质：
a．具有n个结点的完全二叉树的深度为[logn]＋1。2
b．设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k＝1，2，…，n）的结点有以下结论：
第一，若k＝1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT（k/2）。
第二，若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
第三，若2k＋1≤n，则编号为k的结点的右子结点编号为2k＋1；否则该结点无右子结点。
根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。
3．二叉树的存储结构（1）在计算机中，二叉树采用链式存储结构。（2）用于存储二叉树中各元素的存储结点由两部分组成：
①数据域
②指针域
a．左指针：用于指向该结点的左子结点的存储地址；
b．右指针：指向该结点的右指结点的存储地址。
4．二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树结点中遵循先左后右的原则。二叉树的遍历可分为三种：（1）前序遍历（DLR）
在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。该过程是一个递归的过程。（2）中序遍历（LDR）
在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。（3）后序遍历（LRD）
在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。
如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树，如果知道了某二叉树的后序序列和中序序列，则也可以唯一地恢复该二叉树。但如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。
七、查找技术
1．顺序查找（顺序搜索）（1）基本方法
从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。（2）以下两种情况只能采用顺序查找：
①线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。（3）顺序查找的缺陷：效率太低
2．二分法查找（对分查找）（1）适用范围
只适用于顺序存储的有序表，在此所说的有序表是指线性表中元素按值非递减排列。（2）具体方法
设有序线性表的长度为n，被查元素为x，则：
①将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；
②若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找
③若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找
④这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
八、排序技术
1．交换类排序法（1）冒泡排序法
①定义：冒泡排序法是一种最简单的交换类排序方法，通过相邻数据元素的交换逐步将线性表变成有序。
②基本过程：
a．从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。
b．从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。
c．对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。
③在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n（n-1）/2。（2）快速排序法
①基本思想
从线性表中选取一个元素T，将线性表后面小于T的元素移到前面，前面大于T的元素移到后面，这样就以T为分割线将线性表分割成前后两个子表。再将得到的子表按照这个过程继续下去，直到所有子表为空为止。
②快速排序在最坏情况下需要进行n（n-1）/2次比较，但实际的排序效率要比冒泡排序高得多。
2．插入类排序法（1）简单插入排序法
①定义:所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
②插入过程：
将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。
③这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n（n-1）/2次比较。（2）希尔排序法
①基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。
②子序列的分割方法：
将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完k成。增量序列一般取h＝n/2（k＝1，2，…，[logn]），其中n为待排t2序序列的长度。
③如果选取上述增量序列，则在最坏情况下，希尔排序所需要的1.5比较次数为0（n）。
3．选择类排序法（1）简单选择排序法
①基本思想：
扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。
②简单选择排序法在最坏情况下需要比较n（n-1）/2次。（2）堆排序法
试读结束[说明：试读内容隐藏了图片]