数据结构与算法-PPT.ppt

《数据结构与算法-PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法-PPT.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本文档相关内容参见本文档相关内容参见 视频视频 10-11 10-11数据结构与算法主讲：陈主讲：陈 越越 （浙江大学计算机学院）（浙江大学计算机学院）Email:3第六部分（第六部分（90分钟）分钟）l 配套教材介绍配套教材介绍l 主教材特点主教材特点l 辅助教材特点辅助教材特点l 基础型认证系统基础型认证系统PAT介绍介绍l 提高型练习系统提高型练习系统ZOJ介绍介绍l 课程网站介绍课程网站介绍4配套教材介绍配套教材介绍l主教材特点主教材特点l问题驱动：每章以问题开篇、以实际案例结束，由问题驱动：每章以问题开篇、以实际案例结束，由浅渐深，提供丰富的应用案例及解决方案。浅渐深，提供丰富的应用

2、案例及解决方案。l以更丰富的综合应用案例帮助读者增强对理论的感以更丰富的综合应用案例帮助读者增强对理论的感性认识，从而明白这些数据结构为什么存在、以及性认识，从而明白这些数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。在什么情况下可以最好地解决什么样的问题。l提供了大量可以直接编译运行的源代码。不仅使得提供了大量可以直接编译运行的源代码。不仅使得学生在学习时容易起步，可以在现成源代码的基础学生在学习时容易起步，可以在现成源代码的基础上不断修改扩充，从而解决更为复杂的问题，而且上不断修改扩充，从而解决更为复杂的问题，而且也为也为IT专业人士提供了方便的经典代码库。专业人士提供了方

3、便的经典代码库。5配套教材介绍配套教材介绍l主教材特点主教材特点l第一章：数据结构与算法的基本概念和两者的关联，重点介绍第一章：数据结构与算法的基本概念和两者的关联，重点介绍了抽象数据类型和算法复杂度的概念了抽象数据类型和算法复杂度的概念l第二章：第二章：C语言关键内容复习语言关键内容复习l第三章：线性表以及最基本的两种应用：堆栈和队列第三章：线性表以及最基本的两种应用：堆栈和队列l第四章：树，重点介绍了二叉树和搜索树，并将查找、哈夫曼第四章：树，重点介绍了二叉树和搜索树，并将查找、哈夫曼树和集合表示等作为树形结构的应用进行了讨论树和集合表示等作为树形结构的应用进行了讨论l第五章：通过对从海量

4、信息中高效查找关键字问题的再思考，第五章：通过对从海量信息中高效查找关键字问题的再思考，引出对散列表和经典哈希映射技术的讨论引出对散列表和经典哈希映射技术的讨论l第六章：图的各种表示方法和相关算法第六章：图的各种表示方法和相关算法l第七章：经典的排序算法第七章：经典的排序算法l第八章：通过对两个实际生活中提炼出的问题的求解，帮助读第八章：通过对两个实际生活中提炼出的问题的求解，帮助读者更深刻体会数据结构的应用。者更深刻体会数据结构的应用。6配套教材介绍配套教材介绍l主教材特点主教材特点l提供全部提供全部PPT课件（辅助教材书后附赠光盘中有，也可以向高课件（辅助教材书后附赠光盘中有，也可以向高教

5、社直接索取，或者去教社直接索取，或者去 http:/ 下载，下载，包括书中代码和勘误表）包括书中代码和勘误表）l采用本书作为教材的学校，由出版社完成资格审查后，可获得采用本书作为教材的学校，由出版社完成资格审查后，可获得给校级用户安装于局域网内的系统，内含固定的练习题目及数给校级用户安装于局域网内的系统，内含固定的练习题目及数据、标准程序。系统允许据、标准程序。系统允许Admin自己增删题目，并且提供选择自己增删题目，并且提供选择题题库管理、试卷生成、考试的功能题题库管理、试卷生成、考试的功能l配套网络资源：提供对外公开的在线系统配套网络资源：提供对外公开的在线系统PAT（即（即Program

6、ming Ability Test系统，系统，http:/ 一元多项式求导（详）一元多项式求导（详）3-4一元多项式的乘法与加法一元多项式的乘法与加法l3-3 银行业务队列简单模拟（详）银行业务队列简单模拟（详）+8-2 单窗口单窗口“夹塞夹塞”版版 8-5“多队列多窗口多队列多窗口”版版l4-2 树种统计（树种统计（BST）+4-4 Windows消息队列（堆）消息队列（堆）4-9 笛卡儿树笛卡儿树l5-1 整型关键字的散列映射整型关键字的散列映射+5-2 字符串关键字的散列映射字符串关键字的散列映射 5-5 QQ帐户的申请与登陆帐户的申请与登陆9配套教材介绍配套教材介绍l辅助教材特点辅助教

7、材特点l推荐组合推荐组合l6-1 七桥问题七桥问题+6-3 六度空间六度空间+6-5 旅游规划旅游规划 6-8 城市间紧急救援城市间紧急救援+6-9 社交网络结点社交网络结点”重要性重要性”l7-1 模拟模拟Excel排序排序+7-2 寻找大富翁寻找大富翁 7-6 奥运排行榜奥运排行榜10基础型认证系统基础型认证系统PAT介绍介绍l认证系统：认证系统：http:/ 目前已成功举办各目前已成功举办各种考试种考试21场场 题库公开题库公开102道练道练习题（往届真题）习题（往届真题）注册用户注册用户2700余余人人 提交提交12万余人次万余人次11基础型认证系统基础型认证系统PAT介绍介绍程序设计

8、能力测试（程序设计能力测试（Programming Ability Test，简称，简称PAT），成绩优秀的学生直接免除），成绩优秀的学生直接免除招聘时与考查程序设计能力相关的笔试环节。招聘时与考查程序设计能力相关的笔试环节。目前合作的企业已经达到目前合作的企业已经达到47家，包括国际著名家，包括国际著名500强企业甲骨文亚洲研发中心、摩根士丹利强企业甲骨文亚洲研发中心、摩根士丹利公司（上海）、公司（上海）、Google中国、道富科技（浙中国、道富科技（浙江）公司、华为公司（杭州研究院）以及国内江）公司、华为公司（杭州研究院）以及国内著名重点著名重点IT企业如百度、网易研究院（杭州）、企业如百

9、度、网易研究院（杭州）、阿里巴巴阿里巴巴-B2B技术部、腾讯、淘宝（中国）软技术部、腾讯、淘宝（中国）软件有限公司、件有限公司、eBay中国研发中心等。中国研发中心等。Google中国：中国：PAT(A)成绩不低于成绩不低于90分者，可给予免除笔试直接进入分者，可给予免除笔试直接进入面试阶段的优惠政策。面试阶段的优惠政策。百度：百度：PAT(A)成绩不低于成绩不低于80分者，优先考虑实习岗位。分者，优先考虑实习岗位。PAT成绩优成绩优良的学生，免除招聘时与考查程序设计能力相关的笔试环节。良的学生，免除招聘时与考查程序设计能力相关的笔试环节。华为、腾讯、小米、华为、腾讯、小米、每次考试后将考生全

10、部信息（成绩、排名、每次考试后将考生全部信息（成绩、排名、最后提交的代码、所在学校最后提交的代码、所在学校/单位、联系方单位、联系方式）以及本场考试的题目描述打包发给合作式）以及本场考试的题目描述打包发给合作企业的人力资源部门企业的人力资源部门 当然是在考生同当然是在考生同意的前提下意的前提下12基础型认证系统基础型认证系统PAT介绍介绍l2011年发起，由浙江大学计算机科学与技术学院统一组年发起，由浙江大学计算机科学与技术学院统一组织织l目的目的1：培养和展示考生分析问题、解决问题和计算机程序设计：培养和展示考生分析问题、解决问题和计算机程序设计的能力，科学评价计算机程序设计人才的能力，科学

11、评价计算机程序设计人才l目的目的2：为企业选拔人才提供参考标准：为企业选拔人才提供参考标准l难度难度l甲级（英文）：与浙江大学计算机科学与技术学院考研上机甲级（英文）：与浙江大学计算机科学与技术学院考研上机复试难度相似，最难题属国际竞赛中等偏下难度；分复试难度相似，最难题属国际竞赛中等偏下难度；分case给给分。分。l乙级（中文）：初等编程能力测试。甲级乙级（中文）：初等编程能力测试。甲级60分大约相当于乙分大约相当于乙级的级的90分以上。分以上。l已举办已举办5场，报名考生场，报名考生600人，发放证书人，发放证书442份。考生来自各地份。考生来自各地31所高校以及部分在职人员。所高校以及部

12、分在职人员。13基础型认证系统基础型认证系统PAT介绍介绍l考试大纲考试大纲14基础型认证系统基础型认证系统PAT介绍介绍l考试组织考试组织l每年组织每年组织3次统一考试，一般安排在次统一考试，一般安排在3月初（春）、月初（春）、8月底（秋）、月底（秋）、12月中（冬）月中（冬）l目前有杭州、宁波、福州、西安目前有杭州、宁波、福州、西安4地考场地考场l浙江大学宁波理工学院信息科学与工程学院浙江大学宁波理工学院信息科学与工程学院l浙江大学软件学院（宁波）浙江大学软件学院（宁波）l福州大学数学与计算机科学学院福州大学数学与计算机科学学院l西安交通大学西安交通大学l闭卷考试，甲级英文、乙级中文题目描

13、述，闭卷考试，甲级英文、乙级中文题目描述，20分钟试机，分钟试机，3小时小时考试考试l总分总分100分，每题分数的分布与题目难度成正比。甲级考试的分分，每题分数的分布与题目难度成正比。甲级考试的分数分布一般为：数分布一般为：20、25、25、30；乙考试的分数分布一般为：；乙考试的分数分布一般为：15、20、20、20、25。15基础型认证系统基础型认证系统PAT介绍介绍l考试成绩考试成绩l每题分每题分case给分；整场考试得分为各题得分之和给分；整场考试得分为各题得分之和l名次根据总得分决定，相同分数对应并列名次名次根据总得分决定，相同分数对应并列名次l考试不设合格标准，凡参加者均有成绩。考

14、试结束后考试不设合格标准，凡参加者均有成绩。考试结束后可获得浙江大学计算机科学与技术学院统一颁发的证可获得浙江大学计算机科学与技术学院统一颁发的证书，证书中包含考试分数和本次考试的排名两部分成书，证书中包含考试分数和本次考试的排名两部分成绩绩16基础型认证系统基础型认证系统PAT介绍介绍l已有试题分析已有试题分析lA Al4 4题：题：20+25+25+3020+25+25+30l难度级别（难度级别（1-51-5）一般为）一般为 1.5+2.5+3+3.51.5+2.5+3+3.5（或（或4 4）lB Bl5 5题：题：15+20+20+20+2515+20+20+20+25l难度级别（难度级

15、别（1-51-5）一般为）一般为 1+1.5+1.5+2+2.51+1.5+1.5+2+2.5l样例覆盖样例覆盖50%50%以上测试点，样例等价测试数据的分数占总以上测试点，样例等价测试数据的分数占总分分50%50%以上以上l其它测试包括边界测试、特殊情况其它测试包括边界测试、特殊情况17基础型认证系统基础型认证系统PAT介绍介绍l20分题目：基础编程能力分题目：基础编程能力lWorld Cup Betting(1.5)-找最大赔率值并计算收益找最大赔率值并计算收益lHave Fun with Numbers(1.5)-大数乘大数乘2，判断是否，判断是否是原数字位的重排列是原数字位的重排列lB

16、e Unique(1.5)-输出第输出第1个唯一的数字个唯一的数字lShortest Distance(1.5)-环形公路环形公路N个出口，找任意个出口，找任意两出口间最短距离，要卡两出口间最短距离，要卡O(N)复杂度复杂度lString Subtraction(1.5)-从从S1中删除所有中删除所有S2的字符，的字符，要求要求O(n)，快速识别，快速识别S2的字符的字符18基础型认证系统基础型认证系统PAT介绍介绍l25分题目：简单算法应用能力分题目：简单算法应用能力lThe Best Rank(2.5)-按按C语言、数学、英语、平均分语言、数学、英语、平均分成绩最好的排序成绩最好的排序lB

17、attle Over Cities(3)-数连通集数连通集lPalindromic Number(2.5)-判断几步可以得到对称判断几步可以得到对称整数，大数加法整数，大数加法lPAT Ranking(3)-合并多个合并多个rank，有并列排名处理，有并列排名处理lLongest Symmetric String(2)-给出最长对称子串的给出最长对称子串的长度长度19基础型认证系统基础型认证系统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；但有多余结点要剔除；但有多余结点要剔除20基础型认证系统基础型认证系统PAT介绍介绍l30分题目：算法应用能力或繁

19、琐编程能力分题目：算法应用能力或繁琐编程能力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的所的所有根到叶的路径有根到叶的路径21基础型认证系统基础型认证系统PAT介绍介绍l15分题目：样题，基

20、础编程能力分题目：样题，基础编程能力l害死人不偿命的害死人不偿命的(3n+1)猜想猜想(1)卡拉兹猜想卡拉兹猜想l换个格式输出整数换个格式输出整数(1)用用BBSSS1234表示表示23422基础型认证系统基础型认证系统PAT介绍介绍l欢迎高校加盟，建立指定考点欢迎高校加盟，建立指定考点23基础型认证系统基础型认证系统PAT介绍介绍l考点工作考点工作l招生宣传（可分享宣传册）招生宣传（可分享宣传册）l考生报名管理（收费、确认考生）考生报名管理（收费、确认考生）l考场准备（一台备用服务器）考场准备（一台备用服务器）l监考和证书打印颁发等工作监考和证书打印颁发等工作l考点收益考点收益l（考生费用（

21、考生费用-60-60）/人人l免费获得备用系统，可为本地学生提供练习平台（有免费获得备用系统，可为本地学生提供练习平台（有adminadmin权限，可自行添加考试和题目，但无选择题考试）权限，可自行添加考试和题目，但无选择题考试）24提高型练习系统提高型练习系统ZOJ介绍介绍lhttp:/ University Online JudgeZhejiang University Online Judge，简称，简称ZOJZOJ）l定位：国际大学生程序设计竞赛定位：国际大学生程序设计竞赛(ACM-ICPC)(ACM-ICPC)训练题库训练题库l质量：十年来已积累题目质量：十年来已积累题目27002700余题，全球用余题，全球用户数逾户数逾6 6万，举办（原创）全球公开赛万，举办（原创）全球公开赛126126场，场，在线提交量达在线提交量达320320多万人次，是全球最有影响多万人次，是全球最有影响力的程序设计竞赛类网站之一力的程序设计竞赛类网站之一25课程网站介绍课程网站介绍l课程网站：课程网站：http:/