《《数据结构与算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课件.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本文档相关内容参见本文档相关内容参见 视频视频 10-11 10-111数据结构与算法主主讲：陈 越越 （浙江大学计算机学院）（浙江大学计算机学院）Email:2第六部分（第六部分（90分钟）分钟）l 配套教材介配套教材介绍l 主教材特点主教材特点l 辅助教材特点助教材特点l 基基础型型认证系系统PAT介介绍l 提高型提高型练习系系统ZOJ介介绍l 课程网站介程网站介绍3配套教材介配套教材介绍l主教材特点主教材特点l问题驱动：每章以：每章以问题开篇、以开篇、以实际案例案例结束，由束，由浅浅渐深，提供丰富的深，提供丰富的应用案例及解决方案。用案例及解决方案。l以更丰富的以更丰富的综合合应用案例帮
2、助用案例帮助读者增者增强对理理论的感的感性性认识，从而明白，从而明白这些数据些数据结构构为什么存在、以及什么存在、以及在什么情况下可以最好地解决什么在什么情况下可以最好地解决什么样的的问题。l提供了大量可以直接提供了大量可以直接编译运行的源代运行的源代码。不。不仅使得使得学生在学学生在学习时容易起步，可以在容易起步，可以在现成源代成源代码的基的基础上不断修改上不断修改扩充，从而解决更充，从而解决更为复复杂的的问题，而且，而且也也为IT专业人士提供了方便的人士提供了方便的经典代典代码库。4配套教材介配套教材介绍l主教材特点主教材特点l第一章：数据第一章：数据结构与算法的基本概念和两者的关构与算法
3、的基本概念和两者的关联，重点介，重点介绍了抽象数据了抽象数据类型和算法复型和算法复杂度的概念度的概念l第二章：第二章：C语言关言关键内容复内容复习l第三章：第三章：线性表以及最基本的两种性表以及最基本的两种应用：堆用：堆栈和和队列列l第四章：第四章：树，重点介，重点介绍了二叉了二叉树和搜索和搜索树，并将，并将查找、哈夫曼找、哈夫曼树和集合表示等作和集合表示等作为树形形结构的构的应用用进行了行了讨论l第五章：通第五章：通过对从海量信息中高效从海量信息中高效查找关找关键字字问题的再思考，的再思考，引出引出对散列表和散列表和经典哈希映射技典哈希映射技术的的讨论l第六章：第六章：图的各种表示方法和相关
4、算法的各种表示方法和相关算法l第七章：第七章：经典的排序算法典的排序算法l第八章：通第八章：通过对两个两个实际生活中提生活中提炼出的出的问题的求解，帮助的求解，帮助读者更深刻体会数据者更深刻体会数据结构的构的应用。用。5配套教材介配套教材介绍l主教材特点主教材特点l提供全部提供全部PPT课件（件（辅助教材助教材书后附后附赠光光盘中有，也可以向高中有，也可以向高教社直接索取，或者去教社直接索取，或者去 下下载，包括，包括书中代中代码和勘和勘误表）表）l采用本采用本书作作为教材的学校，由出版社完成教材的学校，由出版社完成资格格审查后，可后，可获得得给校校级用用户安装于局域网内的系安装于局域网内的系
5、统，内含固定的，内含固定的练习题目及数目及数据、据、标准程序。系准程序。系统允允许Admin自己增自己增删题目，并且提供目，并且提供选择题题库管理、管理、试卷生成、考卷生成、考试的功能的功能l配套网配套网络资源：提供源：提供对外公开的在外公开的在线系系统PAT（即（即Programming Ability Test系系统，http:/），有全部），有全部实验项目目（3道开放性道开放性实验项目除外）目除外）题的在的在线评判，全天候判，全天候为广大广大读者者提供免提供免费服服务l采用本采用本书作作为教材的学校，由出版社完成教材的学校，由出版社完成资格格审查后，也可免后，也可免费享受享受PAT系系统
6、定制服定制服务，即填写申，即填写申请表后，在表后，在PAT上上获得得专用用帐号，号，进行行课程程练习组织、考、考试组织。无。无须自己自己维护服服务器器6配套教材介配套教材介绍l辅助教材特点助教材特点l大量大量课程程设计题目（目（27+35+327+35+3）l建建议：每章：每章详解解2-32-3题，布置，布置1-21-2题，优秀的学生秀的学生尝试思考思考题给额外外奖励励l随随书附附赠光光盘中有中有PAT单机版，内含全部机版，内含全部实验案例案例题目及目及测试数据、数据、标准解答程序。学生可以准解答程序。学生可以尝试优化化代代码，并自行，并自行测试效果。效果。7配套教材介配套教材介绍l辅助教材特
7、点助教材特点l推荐推荐组合合l3-1 一元多一元多项式求式求导（详）3-4一元多一元多项式的乘法与加法式的乘法与加法l3-3 银行行业务队列列简单模模拟（详）+8-2 单窗口窗口“夹塞塞”版版 8-5“多多队列多窗口列多窗口”版版l4-2 树种种统计（BST）+4-4 Windows消息消息队列（堆）列（堆）4-9 笛卡儿笛卡儿树l5-1 整型关整型关键字的散列映射字的散列映射+5-2 字符串关字符串关键字的散列映射字的散列映射 5-5 QQ帐户的申的申请与登与登陆8配套教材介配套教材介绍l辅助教材特点助教材特点l推荐推荐组合合l6-1 七七桥问题+6-3 六度空六度空间+6-5 旅游旅游规划
8、划 6-8 城市城市间紧急救援急救援+6-9 社交网社交网络结点点”重要性重要性”l7-1 模模拟Excel排序排序+7-2 寻找大富翁找大富翁 7-6 奥运排行榜奥运排行榜9基基础型型认证系系统PAT介介绍l认证系系统：2011年年8月月21日日对外开放对外开放 目前已成功举办各目前已成功举办各种考试种考试21场场 题库公开题库公开102道练道练习题（往届真题）习题（往届真题）注册用户注册用户2700余余人人 提交提交12万余人次万余人次10基基础型型认证系系统PAT介介绍程序程序设计设计能力能力测试测试（Programming Ability Test，简简称称PAT），成），成绩优绩优秀
9、的学生直接免除秀的学生直接免除招聘招聘时时与考与考查查程序程序设计设计能力相关的笔能力相关的笔试环节试环节。目前合作的企目前合作的企业业已已经经达到达到47家，包括国家，包括国际际著名著名500强强企企业业甲骨文甲骨文亚亚洲研洲研发发中心、摩根士丹利中心、摩根士丹利公司（上海）、公司（上海）、Google中国、道富科技（浙中国、道富科技（浙江）公司、江）公司、华为华为公司（杭州研究院）以及国内公司（杭州研究院）以及国内著名重点著名重点IT企企业业如百度、网易研究院（杭州）、如百度、网易研究院（杭州）、阿里巴巴阿里巴巴-B2B技技术术部、部、腾讯腾讯、淘宝（中国）、淘宝（中国）软软件有限公司、件
10、有限公司、eBay中国研中国研发发中心等。中心等。Google中国：中国：PAT(A)成绩不低于成绩不低于90分者，可给予免除笔试直接进入分者，可给予免除笔试直接进入面试阶段的优惠政策。面试阶段的优惠政策。百度：百度：PAT(A)成绩不低于成绩不低于80分者，优先考虑实习岗位。分者，优先考虑实习岗位。PAT成绩优成绩优良的学生，免除招聘时与考查程序设计能力相关的笔试环节。良的学生，免除招聘时与考查程序设计能力相关的笔试环节。华为、腾讯、小米、华为、腾讯、小米、每次考每次考试后将考生全部信息（成后将考生全部信息（成绩、排名、排名、最后提交的代最后提交的代码、所在学校、所在学校/单位、位、联系方系
11、方式）以及本式）以及本场考考试的的题目描述目描述打包打包发给合作合作企企业的人力的人力资源部源部门当然是在考生同意当然是在考生同意的前提下的前提下11基基础型型认证系系统PAT介介绍l2011年年发起，由浙江大学起，由浙江大学计算机科学与技算机科学与技术学院学院统一一组织l目的目的1：培养和展示考生分析：培养和展示考生分析问题、解决、解决问题和和计算机程序算机程序设计的能力，科学的能力，科学评价价计算机程序算机程序设计人才人才l目的目的2：为企企业选拔人才提供参考拔人才提供参考标准准l难度度l甲甲级（英文）：与浙江大学（英文）：与浙江大学计算机科学与技算机科学与技术学院考研上机学院考研上机复复
12、试难度相似，最度相似，最难题属国属国际竞赛中等偏下中等偏下难度；度；分分case给分分。l乙乙级（中文）：初等（中文）：初等编程能力程能力测试。甲。甲级60分大分大约相当于乙相当于乙级的的90分以上。分以上。l已已举办5场，报名考生名考生600人，人，发放放证书442份。考生来自各地份。考生来自各地31所高校以及部分在所高校以及部分在职人人员。12基基础型型认证系系统PAT介介绍l考考试大大纲13基基础型型认证系系统PAT介介绍l考考试组织l每年每年组织3次次统一考一考试，一般安排在，一般安排在3月初（春）、月初（春）、8月底（秋）、月底（秋）、12月中（冬）月中（冬）l目前有杭州、宁波、福州
13、、西安目前有杭州、宁波、福州、西安4地考地考场l浙江大学宁波理工学院信息科学与工程学院浙江大学宁波理工学院信息科学与工程学院l浙江大学浙江大学软件学院（宁波）件学院（宁波）l福州大学数学与福州大学数学与计算机科学学院算机科学学院l西安交通大学西安交通大学l闭卷考卷考试，甲，甲级英文、乙英文、乙级中文中文题目描述，目描述，20分分钟试机，机，3小小时考考试l总分分100分，每分，每题分数的分布与分数的分布与题目目难度成正比。甲度成正比。甲级考考试的分的分数分布一般数分布一般为：20、25、25、30；乙考；乙考试的分数分布一般的分数分布一般为：15、20、20、20、25。14基基础型型认证系系
14、统PAT介介绍l考考试成成绩l每每题分分case给分；整分；整场考考试得分得分为各各题得分之和得分之和l名次根据名次根据总得分决定，相同分数得分决定，相同分数对应并列名次并列名次l考考试不不设合格合格标准，凡参加者均有成准，凡参加者均有成绩。考。考试结束后束后可可获得浙江大学得浙江大学计算机科学与技算机科学与技术学院学院统一一颁发的的证书，证书中包含考中包含考试分数和本次考分数和本次考试的排名两部分成的排名两部分成绩15基基础型型认证系系统PAT介介绍l已有已有试题分析分析lA Al4 4题：20+25+25+3020+25+25+30l难度度级别（1-51-5）一般）一般为 1.5+2.5+
15、3+3.51.5+2.5+3+3.5（或（或4 4）lB Bl5 5题：15+20+20+20+2515+20+20+20+25l难度度级别（1-51-5）一般）一般为 1+1.5+1.5+2+2.51+1.5+1.5+2+2.5l样例覆盖例覆盖50%50%以上以上测试点，点，样例等价例等价测试数据的分数占数据的分数占总分分50%50%以上以上l其它其它测试包括包括边界界测试、特殊情况、特殊情况16基基础型型认证系系统PAT介介绍l20分题目：基础编程能力分题目：基础编程能力lWorld Cup Betting(1.5)-找最大赔率值并计算收益找最大赔率值并计算收益lHave Fun with
16、 Numbers(1.5)-大数乘大数乘2，判断是否，判断是否是原数字位的重排列是原数字位的重排列lBe Unique(1.5)-输出第输出第1个唯一的数字个唯一的数字lShortest Distance(1.5)-环形公路环形公路N个出口，找任意个出口，找任意两出口间最短距离，要卡两出口间最短距离，要卡O(N)复杂度复杂度lString Subtraction(1.5)-从从S1中删除所有中删除所有S2的字符，的字符，要求要求O(n)，快速识别，快速识别S2的字符的字符17基基础型型认证系系统PAT介介绍l25分题目：简单算法应用能力分题目：简单算法应用能力lThe Best Rank(2.
17、5)-按按C语言、数学、英语、平均分语言、数学、英语、平均分成绩最好的排序成绩最好的排序lBattle Over Cities(3)-数连通集数连通集lPalindromic Number(2.5)-判断几步可以得到对称判断几步可以得到对称整数，大数加法整数，大数加法lPAT Ranking(3)-合并多个合并多个rank，有并列排名处理，有并列排名处理lLongest Symmetric String(2)-给出最长对称子串的给出最长对称子串的长度长度18基基础型型认证系系统PAT介介绍l25分题目：简单算法应用能力分题目：简单算法应用能力lCourse List for Student(3
18、)-给课程选课名单，输出每个给课程选课名单，输出每个学生的选课清单，学生的选课清单，用到用到hashlStudent List for Course(2.5)-给学生选课清单，输出每给学生选课清单，输出每门课选课名单门课选课名单lFind Coins(2.5)-从从N个整数中找个整数中找2个，和等于给定整数，个，和等于给定整数，要求要求O(N)复杂度复杂度lPop Sequence(2)-顺序入栈，判断出栈顺序是否对顺序入栈，判断出栈顺序是否对lLinked List Sorting(2.5)-链表排序，实际不用链表，直链表排序，实际不用链表，直接接qsort；但有多余结点要剔除；但有多余结点
19、要剔除19基基础型型认证系系统PAT介介绍l30分题目：算法应用能力或繁琐编程能力分题目：算法应用能力或繁琐编程能力lWaiting in Line(4)-复杂队列模拟，繁琐复杂队列模拟，繁琐lTable Tennis(4)-有有VIP队列队列的模拟，繁琐的模拟，繁琐lRecover the Smallest Number(3.5)-给给N个个整数，排列成一个最小整数整数，排列成一个最小整数，细节处理，细节处理lCounting Ones(4)-数数1N中中1出现的次数出现的次数，卡时卡时lPath of Equal Weight(4)-求树中等于求树中等于S的所的所有根到叶的路径有根到叶的路
20、径20基基础型型认证系系统PAT介介绍l15分题目：样题，基础编程能力分题目：样题，基础编程能力l害死人不偿命的害死人不偿命的(3n+1)猜想猜想(1)卡拉兹猜想卡拉兹猜想l换个格式输出整数换个格式输出整数(1)用用BBSSS1234表示表示23421基基础型型认证系系统PAT介介绍l欢迎高校加盟，建立指定考点迎高校加盟，建立指定考点22基基础型型认证系系统PAT介介绍l考点工作考点工作l招生宣招生宣传（可分享宣（可分享宣传册）册）l考生考生报名管理（收名管理（收费、确、确认考生）考生）l考考场准准备（一台（一台备用服用服务器）器）l监考和考和证书打印打印颁发等工作等工作l考点收益考点收益l（
21、考生（考生费用用-60-60）/人人l免免费获得得备用系用系统，可，可为本地学生提供本地学生提供练习平台（有平台（有adminadmin权限，可自行添加考限，可自行添加考试和和题目，但无目，但无选择题考考试）23提高型提高型练习系系统ZOJ介介绍lhttp:/l浙江大学浙江大学计算机程序算机程序设计在在线裁判系裁判系统（Zhejiang University Online JudgeZhejiang University Online Judge，简称称ZOJZOJ）l定位：国定位：国际大学生程序大学生程序设计竞赛(ACM-ICPC)(ACM-ICPC)训练题库l质量：十年来已量：十年来已积累累题目目27002700余余题，全球用，全球用户数逾数逾6 6万，万，举办（原（原创）全球公开）全球公开赛126126场，在在线提交量达提交量达320320多万人次，是全球最有影响多万人次，是全球最有影响力的程序力的程序设计竞赛类网站之一网站之一24课程网站介程网站介绍l课程网站：程网站：http:/l全套全套课程程资料：大料：大纲、日、日历、课件、件、试卷、卷、课余余资料料l无无须帐号号2526