作者：G.li
出版社：信息技术第一出版分社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
软件测试工程师面试秘籍试读：
前言
本书是测试工程师应聘指南。通过使用本书，同学们能够了解应聘初、中级测试工程师需要撑握的必要知识，带着技巧去应聘，同学们会多几分把握。
本书作者收集并分析了近两年来十多家公司共650道笔试、面试题。从应聘流程、计算机基础知识、测试基础、面试技巧及注意事项4个方面帮助测试菜鸟应聘者复习、总结已学过和未学过的知识。
涵盖面广。本书不仅涵盖了数据结构、数据库、网络、设计模式、C++、Java、C#以及智力测试等计算机专业基础知识和近两年的笔试、面试题，还覆盖了测试理论、测试基础、自动化测试、性能测试、测试管理、测试职业规划等测试行业的专业知识。本书提供的知识点足以使读者武装自己，灵活应对初、中级测试工程师岗位面试。
理论和实际练习相结合。本书在每个知识点后都有部分知名企业笔试、面试题讲解，帮助读者以最快速度消化知识点，是应聘前的“磨刀石”。
真题丰富、答案准确。本书共使用了650道笔试、面试题，试题答案都是一线测试工程师及面试官提供，答案准确，信息及时。
本书主要由李江编著，51testing测试组参与校对。
编辑联系邮箱：zhangtao@ptpress.com.cn。第一章知己知彼，百战不殆
求职，类似于打仗，是一场挑战自己的战斗，是一场跟用人单位的博弈，更是一场千人过独木桥的厮杀、混战。《孙子·谋攻篇》中说：“知己知彼，百战不殆；不知彼而知己，一胜一负；不知彼，不知己，每战必殆。”。在当今竞争激烈的职场中，同学们想谋一份令他人羡慕、让自己欣喜若狂的岗位，事先充分准备是十分必要的。若能在笔试、面试中不断认识并提高自己，不断了解用人单位和面试对手、判官，不断改进进攻对策，那么你离理想的职位不远了。1.1 初出校园
每年9月到第二年1月、3月到6月，都有一大批毕业生涌入求职大军的队伍。可是，现在应届毕业生找工作很辛苦、艰难。为什么呢？
• 学校没有专门针对找工作测试的专业课，基本功不扎实。
• 缺乏面试经验，软素质面试没有通过。
• 扛不住找工作造成的心理压力，缺乏自信心。
……
事前充分准备，提高自信心，端正工作态度，规划好自己的职业，定位目标岗位，这些将对打好一场求职战有百利而无一害。
那我们就一点点开始吧，先了解一下应聘的整个流程。1.1.1 应聘渠道
现在的应聘渠道有很多，包括：校园宣讲会，各个企业自己的招聘网站，各类招聘门户网站，猎头类网站，内部推荐等。
民营企业一般在 10～12月份、4～6月份陆陆续续开始招聘。应聘这类企业效率最高的方式就是内部推荐和参加校园宣讲会，简历被刷的概率相对来说低一些。
对于自己十分钟爱、向往的企业，可以到官网的“人才招聘”栏目去看看是否有合适的岗位，或者到猎头类网站找猎头咨询相关信息。不过官网上的招聘信息，可能更新并不及时，相比来说，直接找猎头靠谱一些。IT猎头类网站有猎聘网、中国猎头网、精英前程、淘猎网等。
对于自己选定的目标岗位，可以到相关论坛找寻招聘信息。软件开发岗位，可以到CSDN上看看；测试岗位，可以到51testing网站上看看。
还有一些大型招聘门户网站，如中华英才网、招聘网、若邻网、智联招聘、前程无忧、建筑英才网等。1.1.2 应聘流程
一般情况下，完整的应聘流程如图1.1所示。图1.1 应聘流程
民营企业、国企、央企3类企业招聘的时间段略有不同。对于应届毕业生来说，每年10～12月份是大型名企发放大量Offer、大牛挑选Offer的时候，这段时间，可能会令一部分同学丧失自信心。此时保持良好的心态，抗住压力过个好年是很重要的，呵呵，屡败屡战嘛。过完年回来，2月份左右，大量国企、央企开始招聘，它们一般提前一个月发放招聘岗位，招聘流程时间跨度也较短。因此在这段时间去应聘的同学，竞争压力相对小一些，毕竟很多大牛已经选择了名企了。同学可以根据自己的目标公司，选择性备战。1.2 第一印象
简历是用人单位了解你的窗口，是应聘的敲门砖。如何用一份优秀的简历来打动用人单位，给对方一个良好的第一印象呢？跟随本章，我们一起来打扮打扮您的简历吧。1.2.1 打扮简历
我们来看一下简历中应该包括哪些内容：个人资料、工作经历、项目经历、教育背景、技能特长、自我评价等。
1．个人资料
用最简练的语言、最短的篇幅说明，不必描述。姓名、联系地址、电话、E-mail就足够了，性别、出生年月、民族、籍贯等都没必要，除非岗位有要求。是否贴照片，是个有风险的行为，完全看运气了，建议别画蛇添足。即使长得标致，遇上蛇蝎心肠的简历筛选员，也会被扣分。
2．项目经历
用效果说话，切忌将项目经历写成项目的简单罗列。每个项目最好包含：（1）简单、精练的项目介绍。（2）项目当前的使用情况或者成果。（3）你在这个项目中充当什么角色，有什么贡献。（4）你的工作成果。这里的成果可以是发表论文、提升效率、得到好评等。用事实说话。类似于“善于交际”等文字，倒不如“组织了一次成功的活动”打动人心。
3．教育经历
用时间倒序列出教育经历。获奖学金、荣誉称号，特别的文章与论文、曾发表的文章题目、发表的刊物名称、在职培训、假期间的国际交流等学习生涯中的闪光点，都可以写上，表明你的出类拔萃。在描述成绩时，对成绩最好有个对比。比如，大学成绩9.4分（排名3/80），或者二等奖学金（占比15/80）等，让招聘人员对这个成绩有个清晰的认识。
4．技能特长
首先，一定要针对应聘岗位的要求把关键的、对方关注的点写进去。比如，应聘测试岗，要求php脚本熟练，如果你在技能里写法语流利、篮球很棒就没用了，占篇幅，吃力不讨好。其次，别太谦虚，实事求是。最好别用“初学”，“一般”等表达含糊的词语，尽量使用“熟练”，“精通”，或者不写。
5．自我评价
不偏不倚地描述、总结自己的优点和缺点。但是记住，缺点千万别有硬伤。比如，对方招测试人员，若自我评价里写粗心大意，总是漏测，或者不喜欢加班之类的，我想简历进垃圾桶的命运就是定数了。缺点，可以挑选一些软素质说，或者不一定要说；如果说了，最好能附上现在或者以后在这方面做出的努力。
关于篇幅：中文简历不超过2页，最好饱满的1页，第2页可能就没人去看了。要求中英文的简历，中英文各1页最佳。
关于排版：切忌太花哨，排版混乱。重点部分用黑体、不同的颜色标注出来，醒目。1.2.2 优秀简历模板
下面给出较优秀的中英文简历模板给大家参考。
李四
北京市西城区新街口外大街28号 电子楼412B 100876
13934345432 byls@163.com
实践经验：____________________
研究生阶段：北京邮电大学软件工程研究中心“数字影像处理系统”项目成员2007.11-现在
• 本项目是国防科工委 863 项目，系统已交付使用。
• 独立完成模块设计，实现了界面与数据层分离，易于维护，获得导师好评。
• 参与彩色图像处理关键算法研究和实现，发表国际论文《ColorImageProccessing》Fourth International Conference on Image and Graphics0-7695-2929-1/07 © 2007 IEEEDOI 10.1109/ICIG.2007.98。
本科生阶段：神经网络在测试监控中的应用研究 主持人 2005年至2006年底
• 北京师范大学本科生基金项目，组织安排项目的研究工作。
• 参与专利申请，专利号：aa123。
教育背景：____________________
研究生：北京邮电大学，平均分：90/100，排名：3/200。
本科：北京师范大学计算机科学与技术学士学位，平均分：87.38/100，排名：9/81。
奖励情况：____________________
• 2009年：上半年获得国家软件设计师（中级）证书，编号：08018059。
• 2007年：毕业设计“基于 Retinex 的彩色图像处理”获得校优秀荣誉证书（一个系 2个名额）。
• 2005年：获得专业 2 等奖学金（10%）。
• 2004年：获得专业 3 等奖学金（20%）。
专业技能：____________________
• 精通：C#语言 | VS 开发平台 | Oracle 数据库 | AQtime 测试软件
• 熟悉：C、C++、Java | VC6.0 开发平台| Matlab 等常用平台
• 英语：CET-6
我的优势：____________________
• 精通 C#，有三年C# + Oracle 项目开发经验，熟悉面向对象,并担任项目主要负责人。
• 对图像处理有深入研究，曾在国际会议上发表论文。
• 本科期间通过 CET-6, 英语实际应用能力强。
• 善于利用网络来解决问题，团队合作精神强。
Wang Li（李王）
BeiJing Normal University 100875
86-010-62206433 / 18219283848 bjsdlw@163.com
PROFESSIONAL EXPERIENCE
1．Image Processing System 2007-Present BeiJing
• This is 863 project, and the system has been put into use.
• I completed two main modules of this project which part of the program go up in client and teachers’estimation.
2．Detailed investigation of geological disasters in the national system
• This project includes 3 modules data Input\Data Manage\Data Check.
• I finished the entire document related to test task, such as test plan, test cases and reports.
EDUCATION
BeiJing Normal University Depr. Of Computer 2003-2007
Squad leader GPA:87.38/100 Rank:9/81
Publications《Investigation an aerial-image multipurpose processing system》ICEMI© 2009 IEEE（Accept）
HONORS
1．Scholarship on Computer Subject in 2005 (awarded to only 10 among 100 students)
2．Scholarship on Computer Subject in 2004(awarded to only 10 among 100 students)
3．Access to the “National Software Engineer”certificates at 2009-8
IT SKILLS
Languages:
• Proficient in: C#.
• Familiar with: Microsoft Visual C++ and C and Java.
Algorithm:
• basic Image Processing.
• Object recognition.
English Skill
College English Test Band 6 (CET-6) Pass1.3 过关斩将
当你顺利通过简历的筛选后，就正式进入闯关模式了。每个公司设置的流程关卡不尽相同，但大体上都包含以下几步：笔试、电话面试、面试（1～3 轮）、签订意向书、签约（毁约）。接下来将会按次序逐一介绍各关卡的基本情况、注意事项以及一些闯关小技巧。1.3.1 第一关：笔试
笔试，作为筛选简历后的第一关，由于参加人数较多，成本较高，非每家公司都会涉及，目前校园招聘安排较多，社招较少。
笔试可分为纸上笔试和机试，通常大型的校园招聘都采用纸上笔试；而小型的招聘，部门招聘实习生或者社招有可能用机试。
笔试一般包含三个方面的内容：基础知识、心理性格测试、智力测试。题型包含主观题、客观选择题、编程题。
下面简单介绍下笔试的注意事项，让考生们对笔试有所了解和准备。当然，笔试的成绩好坏更多取决于考生的基础以及复习的质量，第二、三章的海量笔试题将对考生复习有很大帮助，这里仅谈应考事项。
① 考前准备
• 笔试前，公司的 HR 会通过短信、电话、邮件的方式告知笔试时间、地点，有时会有考试座位号。只要确保简历上留着的是常用联系方式，应该就没问题。
• 收到笔试通知后，到网上收集该公司的笔试题型、出题范围以及历年来前辈们留下的笔试经验和教训，如果找到该公司历年的笔试题就最好不过了，练练手，心理踏实。
• 笔试当天，准备好可能用到的文具。最重要的是笔试时间，千万别迟到，因为很多公司在考试时间超过15分钟，笔试座位没有坐满的情况下，允许笔霸们入场。何谓笔霸？就是由于各种原因未收到笔试邀请的同学们。当然，若你的简历不幸未被看重，也可以当一次笔霸，成绩优秀的话，很多公司不会介意你是否有笔试资格的。
② 考试注意
• 对于纸上做题来说，有一点需要注意，纸上写编程题，如果语法不熟练，可以考虑写为代码，关注思路，批改试卷的人看得不会太仔细。
• 对于机上编程，就没办法了，靠硬功夫，所以在考前了解对方公司考试的语言类型，临时磨刀，也会对你有所帮助。
• 关注基础，校园招聘里没有针对笔试设计的题目，大多数是面向整个程序员的，开发和测试的在一起。1.3.2 第二关：电话面试
电话面试内容主要有：（1）告知薪水、工作时间。（2）面试日期、地点。（3）面试时间（一般一个小时）。
若应聘者是外地的，第一次面试通常是电话面试，并且是技术面试，面试内容跟笔试差不多，以考核知识为主。相对于笔试，岗位针对性更加强一些。
接到这类面试电话的应聘者，需要跟 HR 约好电话面试的时间，建议选择时间时，给自己留1、2天做好复习的准备。面试时，最好找个安静的、手机信号较好的座位，旁边放好纸、笔以及一台电脑（有的面试官会让你远程编程）。
面试时，不要太谦虚，也不要太自大，诚实、沉着应对。在遇到不知道的地方时，更不要百度里搜答案或者找旁边同学帮忙。如果电话那头听到键盘声音或者起了怀疑，要么直接把你除名，要么后面的面试题会狠狠加大难度考核你的真实性。
总之，面试环境、面试态度、本身的技术基础决定了这关的结果。1.3.3 第三关：面试
面试，按形式分，有多对一面试、一对一面试和一对多面试；按内容分，有一面（基础技术面）、二面（岗位专业面）、三面（hr面）。
面试考核的内容包含：仪表、人际交往能力、专业知识、应变能力等。
面试流程一般如下。（1）应聘者自我介绍。（2）针对简历提问，了解真实性。（3）基础知识/岗位要求的专业知识考核/心理素质考核等。（4）应聘者向面试官提问。
大型校园招聘，面试通过后一到两星期会有下轮面试通知。毕业生也可以通过短信、网络等方式询问面试官面试结果，表达对该职位的重视程度。
关于如何在面试中较好地表现会在本书第四章中详细描述。1.3.4 第四关：意向书·就业协议
1．意向书
在笔试、面试全部通过之后，公司会跟应聘者签订一个《就业意向书》。该意向书不像协议、合同那样一经签约不能随意更改，它比较灵活，在协商过程中，当事人各方均可按各自的意图和目的提出意见，在正式签订协议、合同前亦可随时变更或补充，最终达成协议。
一般来说，仅仅签订了意向书，还未正式签订合同，是可以单方告知终止意向书的。但要根据所签订的意向书的有关约定而定。因此，需要注意的是，其中关于违约金的事项，可以在签约的时候就拒绝此项，即使签署了也没太大关系，公司一般都不会追究。莫留下任何证件，可以留下证件的复印件。
2．就业协议《就业协议》也叫《三方协议》，代表毕业生、用人单位和学校，里面规定了三者的权利和义务，是具有法律效益的。《就业协议》每个学生只有一份，是很重要的，有固定编号，经教育部门严格批示，在签订《就业协议》的时候就要想清楚了。如果《就业协议》弄丢了，可以申请补办，但是比较麻烦，还可能受处分，所以尽量保管好。《就业协议》签订流程一般是：单位签字、毕业生签字、学校签字。学校是最后把关的，为了保障学生的利益。
关于违约金。因为《就业协议》具有法律效力，在签订时要关注是否附带了违约协议，违约金一般在2000～5000元比较正常，可以协商，通常不得超过5000元。《就业协议》中还会涉及户籍，是否解决户口问题，在签订协议时就商量好，避免以后麻烦。
关于试用期。劳动法的规定是“劳动合同期限3个月以上不满一年的，试用期不得超过一个月；劳动合同期限一年以上不满 3年的，试用期不得超过两个月；3年固定期限和无固定期限的劳动合同，试用期不得超过6个月”。
关于工资。要跟hr沟通清楚，税前还是税后。税前包含了你依法应该承担的个人所得税，实际拿到的工资还要扣除个人所得税。如果用人单位答应给税后工资，建议在《就业协议》中明确说明，不然发生争议时，法律默认为税前工资。
关于社保。需要明确社保项目，一般包括五险（养老保险、失业保险、工伤保险、医疗保险、生育保险）或者四险（北京无户口者生育保险一般没有），以及每种保险个人和单位分别缴纳的比例。
关于住房公积金。住房公积金个人需要缴纳的部分一般是单位代扣的。签订协议时要明确个人和单位的缴纳比例。1.3.5 其他：五险一金“五险”指的是五种保险，包括养老保险、医疗保险、失业保险、工伤保险和生育保险；“一金”指的是住房公积金。其中养老保险、医疗保险和失业保险是由企业和个人共同缴纳的保费，工伤保险和生育保险是由企业完全承担的，个人不需要缴纳。这里要注意的是“五险”是法定的，而“一金”不是法定的。
对于五险一金的缴纳额度，每个地区的规定都不同，基数是工资总额。有的企业在发放时有基本工资，有一些相关补贴，但有的企业在缴纳时，只是基本工资，这是违反法律规定的。具体比例要向当地的劳动部门咨询，各地缴纳比例不一样。
养老保险缴费比例：单位20%（全部划入统筹基金），个人8%（全部划入个人账户）。
医疗保险缴费比例：单位8%，个人2%+3元。
失业保险缴费比例：单位2%，个人1%。
工伤保险缴费比例：单位每个月为你缴纳1%，你自己一分钱也不用缴。
生育保险缴费比例：单位每个月为你缴纳1%，你自己一分钱也不用缴。
公积金缴费比例：根据企业的实际情况，选择住房公积金缴费比例。但原则上最高缴费额不得超过职工平均工资的10%。2010年下半年起，统一规定所有用人单位按工资的12%办理缴纳住房公积金。单位和个人都是工资的12%。
其中个人出的是右边的部分，即 8%+1%+2%+7%=18%，公司出的是左边的部分，即20%+2%+1%+1%+8%+7%=39%。也就是说扣除四金后的工资为：X=工人工资—基数×18%；而公司付出的总资金为：Y=工人工资+基数×39%。四金的缴费比例，不一定等于你的工资，也就是说如果税前工资4000元，缴费基数不一定是4000元，有可能低于这个数。“四金”是社会保险金和住房公积金的简称，其中上海市社会保险金包括养老保险、医疗保险、失业保险、生育保险、工伤保险。目前，在上海市就业的人员是否能在上海市劳动和社会保障局缴纳并享受社会保险金和住房公积金主要是看其户籍情况，一般有以下情况：一般四金基数就是当月的工资，不过如果工资很高（比如超过了上年你所在城市社会月平均工资的3倍），那么基数就到顶了。而如果工资特别低的话（比如低于上年你所在城市月社会平均工资的60%），那么基数也有封底。1.3.6 其他：违约
毕业生违约，是指签订《就业协议》之后，毕业生不去用人单位。这会带来以下后果。（1）本人要支付违约金，也有比较慈善的单位不要求支付，可以沟通解决。（2）本人有可能成为该单位的黑名单成员，身份证号记录在案，以后再想跳槽来这家单位可能就比较难了，因为违约给用人单位带来的招聘成本浪费也是很大的。（3）本人重新签约下家，需要征得用人单位同意并缴纳违约金后才行，还要办理与原单位的解约手续，将《就业协议》交还给招生就业处，换新的《就业协议》。这个流程很麻烦，所以在签订《就业协议》的时候要想清楚了再签。第二章磨刀霍霍，有备无患
本章对大量名企测试岗位的笔试面试题进行分析，按照测试工程师的技术难度，在数据结构、操作系统、数据库、网络、设计模式、Java、C++、C#等基础知识上做了总结。2.1 数据结构
数据结构，是历年来笔试面试考试热点之一，至少会有2、3个数据结构的大题。
数据结构包括线性结构和非线性结构两种。线性结构中的线性表、栈、队列、串和非线性结构中二叉树是考试热点。本章备考知识点为考生总结归纳了需要熟练掌握的要点，并在最后一节提供了大量数据结构方面的面试题、解题方法思路供考生参考。2.1.1 线性表
考点
1．线性表的两种存储结构及其特点
2．线性链表基本操作：新增、删除
3．链表逆序等算法
线性表分两种存储结构：顺序存储和链式存储，分别如图2.1和图2.2所示。图2.1 线性表的顺序存储结构
顺序存储结构的特点如下。（1）前后两个元素的存储空间是紧邻的。（2）空间利用率高，但实现要预估容量。（3）查找操作时间复杂度为O(n)，读取操作为O(1)。（4）新增节点，需要移动n-i+1个元素，删除节点需要移动n-i个元素。图2.2 线性表的链式存储结构
链表存储结构的特点如下。（1）可以连续，也可以不连续。（2）需要格外控件存放后续节点的地址，动态申请空间。（3）查找操作时间复杂度为O(n)，读取操作为O(n)。（4）新增和删除操作简单，仅需变化两次指针。
链表的新增节点的过程：（1）新增节点指向下一节点。（2）上一节点指向新增节点。流程如图2.3所示。图2.3 新增节点过程
链表删除节点的过程：上一节点指向下一节点。此流程较简单，就不画示意图。
顺序链表的逆序如图2.4所示。图2.4 链表逆序的过程
链表反转过程如下。（1）设置3个辅助指针，分别指向头3个节点。（2）头两个指针指向的节点反转。（3）3个辅助指针后移两个位置，循环过程2，直到链表结尾。2.1.2 栈、队列、串
考点
1．栈、队列的概念及特点
2．函数如何压栈
3．栈、队列运用到算法中
4．字符串拷贝、反转等操作
栈，又称为后进先出（LIFO: last in first out）线性表，是限制在表的一端进行插入或者删除的操作，每次出栈的元素都是栈顶所在的元素，也就是最后进栈的元素，如图2.5所示。图2.5 栈
按照存储方式，栈分为顺序栈和链式栈。顺序栈一般是由一维数组和栈顶变量组成。链式栈不会出现满栈溢出的情况。
函数通过栈来辅助完成调用过程。例如，Z函数调用A函数，首先会先将传给A的参数压栈，将现在这个指令〔就是 A(…)〕的下一个指令的地址压入栈中，以便 A 函数完后返回到 Z 中继续执行。然后进入 A 函数的内存空间，先调用 PUSH EBP，也就是将Z 的 EPB 的内容（地址 0x000f）压入栈中，接着再 MOV EBP ESP，让 EBP 有一个新的栈顶。最后再将A函数的局部变量压入栈中，开始执行A函数的代码。这时，栈和EBP的情况如图2.6所示。图2.6 函数在栈的存储结构
函数的参数入栈时，按照从右到左的压栈顺序，并注意高地址和低地址，压栈时以机器字为单位且所有参数字对齐。
队列，又称为先进先出（FIFO:first in first out）线性表，它的所有插入操作（又叫入队）在队列的一端，而删除操作（又叫出队）在队列的另一端，如图2.7所示。
队列同样也有顺序存储和链式存储，需要两个变量或指针来指示队头和队尾。在顺序队列中，由于队列的队头和队尾位置是时刻变化着的，可能会存在队头到顶了，而队尾后面空出来很多新的空闲区域，因此，循环队列利用假溢出解决了该问题。队头到顶之后，重新回到最底部，当头指针绕上一圈赶上尾指针，视为满队。
循环队列个数＝（队尾－队头＋数组大小）mod数组大小。图2.7 队列
字符串也是面试中常考的内容，也是实际工作中最实用的技术。下面列出所有字串面试题。
试题1．不调用库函数地实现strCpy。
strCpy (char * src , const char * des)。有几点需要注意。
• src 长度为空〔len(src)==0〕。
• src 和 des 地址相同(src==des)。
代码如下。
char *strcpy(char *strDest,const char *strSrc)
{
if(strDest＝＝NULL||strSrc＝＝NULL)
return NULL
if(strDest==strSrc)
return strDest
char*tempptr=strDest
while((*strDest++=*strSrc++)!='⁄0')
retum tempptr
}
int strlen( const char*str)
{
assert( strt!=NULL);//断言字符串地址非 0
int len;
while((*str++)!='\0')
{ len++; }
return len;
}
试题2．自写函数实现数字与字符串之间的相互转化。
思路：整数转化成字符串，可以采用加‘0’，然后再逆序，整数加’0’就会隐性转化为 char 类型的数。字符串转化成整数，可以采用减‘0’，再乘以 10 累加的方法，字符串减‘0’就会隐性转化为int类型的数。
试题3．不调用库函数实现字符串反转。
代码如下。
package com.others;
publicclassrevertStr {
publicstaticvoid main(String[] args) {
System.out.println(inverse("liuling"));
}
publicstatic String inverse(String str){
char[] chars = str.toCharArray(); //得到字符数组
for (int i = 0; i < chars.length/2; i++) {
char temp = chars[i];
chars[i] = chars[chars.length-i-1];
chars[chars.length-i-1] = temp;
}
return String.copyValueOf(chars);
}
}2.1.3 树、二叉树、图的遍历
考点
1．树的深度优先、广度优先遍历算法
2．二叉树先序、中序、后序遍历；满二叉树、完全二叉树的定义
3．图的深度优先、广度优先遍历算法
树的遍历方式有深度优先和广度优先两种。
深度优先搜索就是在搜索树的每一层始终只扩展一个子节点，不断地向下一层前进（到达叶子结点或受到深度限制）时，才从当前节点返回到上一级节点，沿着另一个方向继续前进。广度优先搜索是深度越大的节点越先得到扩展，本层的节点没有搜索处理完时，不能对下层节点进行处理。图2.8 搜索树（1）
如图2.8 所示的搜索树，深度遍历结果为 ABCDEFGHK ，广度遍历结果为ABECFDGHK。
深度优先遍历算法中，采用栈来实现非递归算法，以二叉树为例，代码如下。
1．public void depthOrderTraversal(){
2． if(root==null){
3． System.out.println("empty tree");
4． return;
5． }
6． ArrayDeque
7． stack.push(root);
8． while(stack.isEmpty()==false){
9． TreeNode node=stack.pop();
10． System.out.print(node.value+" ");
11． if(node.right!=null){
12． stack.push(node.right);
13． }
14． if(node.left!=null){
15． stack.push(node.left);
16． }
17． }
18． System.out.print("\n");
19． }
20．
广度优先是利用队列来实现非递归算法，以二叉树为例，代码如下。
1． public void levelOrderTraversal(){
2． if(root==null){
3． System.out.println("empty tree");
4． return;
5． }
ArrayDeque
7． queue.add(root);
8． while(queue.isEmpty()==false){
9． TreeNode node=queue.remove();
10． System.out.print(node.value+" ");
11． if(node.left!=null){
12． queue.add(node.left);
13． }
14． if(node.right!=null){
15． queue.add(node.right);
16． }
17． }
18． System.out.print("\n");
19． }
二叉树是树的一种，它的每个节点最多只有2个叶子结点，并且左右节点次序不能对调。二叉树的5个特性如下。i-1（1）在二叉树的第i层上至多有2个节点（i≥1）。k（2）深度为k的二叉树上至多含2-1个节点（k≥1）。（3）对任何一棵二叉树，若它含有n个叶子结点、n个度为2的01节点，则必存在关系式：n=n+1。01（4）具有n个结点的完全二叉树的深度为logn+1。2（5）如果对一棵有n个节点的完全二叉树的节点按层序编号，则对任一节点i（1≤i≤n）有如下规律。
① 若 i=1，则节点 i 是二叉树的根；若 i>1，则双亲是节点 i/2。
② 若 2i>n，则节点 i 无左孩子；否则，左孩子是节点 2i。
③ 若 2i+1>n，则节点 i 无右孩子；否则，右孩子是节点 2i+1。
二叉树有三种遍历方式：先根遍历法，中根遍历法，后根遍历法。二叉树遍历是笔试中的常见考题。
先根遍历法步骤如下。（1）访问根节点。（2）先序遍历左子树。（3）先序遍历右子树。
中根遍历法步骤如下。（1）中序遍历左子树。（2）访问根节点。（3）中序遍历右子树。
后根遍历法步骤如下。（1）后序遍历左子树。（2）后序遍历右子树。（3）访问根节点。
试题1．写出如图2.9所示搜索树的先根、中根、后根遍历结果。图2.9 搜索树（2）
先根遍历结果：ABDCEFGHK。
中根遍历结果：BDCAEHGKF。
后根遍历结果：DCBAHKGFEA。
试题2．根据先根遍历结果ABDCEFGHK、中根遍历结果BDCAEHGKF，写出后根遍历结果。
分析如下。（1）根据先根遍历结果可以找出整个树的根节点是A。（2）从中根遍历结果得到A左边的BDC是左子树，EHGKF是右子树。（3）BDC作为左子树先序，说明B是子树的根，又由于中序BDC，说明DC是在B的右子树上。（4）的先根遍历结果和中根遍历结果都一样，说明根为D，C是D的右子树。（5）再回到A的右子树EHGKF几个节点，先根遍历结果为E，子树根为E。（6）中根遍历结果为EHGKF，说明HGKF在E的右子树。（7）HGKF的先根遍历结果为FGHK，则F为根节点；中根遍历结果HGKF，则HGK为F的左子树。（8）HGK 的先根遍历结果为 GHK，则 G 为根节点；中根遍历结果 HGK，则 H 为左子树，K为右子树。这样把树形结构还原之后，就可以很容易得出后根遍历结果排列为DCBAHKGFEA。k
满二叉树：一棵深度为 k，且有 2-1 个节点的二叉树，每一层上的结点数都是最大结点数。
完全二叉树的定义：深度为 k，有 n 个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为 l，则其左分支下子孙的最大层次必为l或l+1。
图遍历又称图的遍历，指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。
图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。
深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G 的某个顶点 v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与 vi 相邻且未被访问的顶点 vj 进行访问，依此类推。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下。
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc（ ）是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v visited[v] = FALSE; //访问标志数组初始化 for(v=0; v if(!visited[v]) DFS(G, v); //对尚未访问的顶点调用 DFS（函数） } void DFS(Graph G, int v){ //从第 v个顶点出发递归地深度优先遍历图G visited[v]=TRUE; VisitFunc(v); //访问第 v个顶点 for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)) //FirstAdjVex返回 v的第一个邻接顶点，若顶点在 G中没有邻接顶点，则返回空（0） //若 w是 v的邻接顶点，NextAdjVex返回 v的（相对于 w的）下一个邻接顶点 //若 w是 v的最后一个邻接点，则返回空（0） if(!visited[w]) DFS(G, w); //对 v的尚未访问的邻接顶点 w调用 DFS（函数） } 图的广度优先搜索法是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问，接着访问vi的所有未被访问的邻接点vi1，vi2，……，vit，并均标记已访问。然后再按照vi1，vi2，……，vit的次序，访问每一个顶点的所有未被访问的邻接点，并均标记为已访问，依此类推，直到图中所有和初始点vi有路径相通的顶点都被访问为止。其非递归算法如下。 Boolean visited[MAX_VERTEX_NUM]; //访问标志数组 Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数 void BFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit; for(v=0; v visited[v] = FALSE; initQueue(Q); //置空辅助队列 Q for(v=0; v if(!visited[v]){ visited[v]=TRUE; VisitFunc(v); EnQueue(Q, v); //v入队列 while(!QueueEmpty(Q)){ DeQueue(Q, u); //队头元素出队并置为 u for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w)) if(!Visited[w]){ //w为 u的尚未访问的邻接顶点 Visited[w]=TRUE; VisitFunc(w); EnQueue(Q, w); } } } }2.1.4 查找 考点 三大类查找算法及其时间复杂度。 查找，又称为检索，是实际应用中经常用到的操作，它包括静态查找表、动态查找表、哈西查找表三大类。下面我们依次复习这3类查找算法的实现以及优缺点。 1．静态查找表 顺序查找、有序查找都属于静态查找表。其中，顺序查找的平均时间是，即复杂度为O(n)。有序查找的前提是表必须是有序的，性能在平均分布的时候最优，平均时间是log(n+1)−1，即2复杂度为O(log(n))。2 顺序查找算法描述：在顺序表st中，查找元素key，若找到返回索引，否则返回0。 Int Search（Stable st, keyType key） { keyType I; st.elem[0].key=key; for(i=st.length;i>=0&&st.elem[i].key!=key;--i); return(i); } 有序查找（折半查找）算法描述如下。 Int Search（sTable st, keytype key） { Keytype low, high, mid; Low=1; High=st.length; //设置区间初值 While（low<=high） { Mid=(low+high)/2; If(stelem[mid].key==key)return(mid);//找到待查元素 Else if(st.elem[mid].key Else high=mid-1; //找不到的话，根据不同情况缩小区间 } Return 0; } 2．动态查找表 动态查找表的特点是表结构本身在查找过程中动态生成，即对给定的关键字key，若表中存在其关键字等于 key 的记录，则查找成功返回，否则插入关键字等于 key 的记录。 动态查找最常用的就是二叉树排序查找法。二叉树排序查找是通过一系列的查找和插入过程形成树。按照中根遍历法可以得到一个有序序列。 动态查找算法描述如下。 /动态查找表（二叉排序树）的链式存储结构定义 typedef struct BiTNode{ ElemType data; Struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; // 二叉排序树的建立、查找、算法的实现和分析 BiTree SearchBST(BiTree bt,KeyType key){ if (bt==NULL) return NULL;//查找失败 else { if EQ(bt->data.key,key) return bt;//查找成功 else if LT(bt->data.key,key) return(SearchBST(bt->lchild,key)); else return(SearchBST(bt->lchild,key)); } } void InsertBST(BiTree &bt,BiTree s){ // 在二叉排序树 bt中插入一个结点 s if (bt==NULL) bt=s; else if EQ(s->data.key,bt->data.key) return ();//不插入结点 else if LT(s->data.key,bt->data.key) InsertBST(bt->lchild,s);//不插入结点 else InsertBST(bt->rchild,s); } void CreateBST(Bitree &bt){ //建立一棵二叉排序树，bt指向根结点 bt=NULL; do { scanf(&x); s=(BiTree)malloc(sizeof(BiTNode));s->data.key=x;s->lchild=s->rchild=NUL}; InsertBST(bt,s);} While (x!=-1);//重复输入一系列值，直至输入的关键字等于-1结束 }//CreateBST Status DeleteBST(BiTree &bt,KeyType key){ //若 bt指向的二叉排序树中存在其关键字等于 key的数据元素，则删除它。 if(bt==NULL) return FALSE; else{ if EQ(s->data.key,bt->data.key) Delete(bt);//不插入结点 else if LT(s->data.key,bt->data.key) DeleteBST(bt->lchild,key); else DeleteBST(bt->rchild,key); } 二叉排序树的删除是一个性能瓶颈问题。在随机情况下，二叉排序树的平均查找长度是和logn等数量级的。平衡二叉树是用来平衡2二叉排序树的，当二叉排序树的左、右子树的差值的绝对值大于1时就需要平衡。平衡的二叉树是真正的logn数量级的。2 3．哈希查找表 哈希查找表是通过计算数据元素的存储地址进行查找的一种方法。 哈希查找表的操作步骤如下。（1）用给定的哈希函数构造哈希表。（2）根据选择的冲突处理方法解决地址冲突。（3）在哈希表的基础上执行哈希查找。 建立哈希表操作步骤如下。（1）取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。（2）根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。 哈希查找步骤为如下。（1）设哈希表为HST[0～M-1]，哈希函数取H（key），解决冲突的方法为R（x）；（2）对给定 k 值，计算哈希地址 Di=H（k）；若 HST 为空，则查找失败；若 HST=k，则查找成功；否则，执行step2（处理冲突）。（3）重复计算处理冲突的下一个存储地址 Dk=R（Dk-1），直到 HST[Dk]为空，或HST[Dk]=k为止。若HST[Dk]=K，则查找成功，否则查找失败。[3]2.1.5 排序 考点 各种排序算法以及它们的时间复杂度。 排序算法有很多，包括插入排序、冒泡排序、堆排序、归并排序、选择排序、计数排序、基数排序、桶排序、快速排序等。插入排序、堆排序、选择排序、归并排序、快速排序和冒泡排序都是比较排序，堆排序属于选择排序，插入排序、希尔排序属于插入排序。下面复习几种常考的排序算法。 1．冒泡排序（BubbleSort） 最简单的一个冒泡排序算法如下。 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort()2 上面冒泡排序算法的效率为：O(N) 2．选择排序（SelectSort） public void selectionSort() { int out, in, min; for(out=0; out { min = out; // minimum for(in=out+1; in if(a[in] < a[min] ) // if min greater, min = in; // we have a new min swap(out, min); // swap them } // end for(out) } // end selectionSort()
试读结束[说明：试读内容隐藏了图片]