《数据结构与算法》PPT课件.pptVIP

本文档相关内容参见视频10-11,数据结构与算法,主讲：陈越（浙江大学计算机学院）Email:chenyue,3,第六部分（90分钟）,配套教材介绍主教材特点辅助教材特点基础型认证系统PAT介绍提高型练习系统ZOJ介绍课程网站介绍,4,配套教材介绍,主教材特点问题驱动：每章以问题开篇、以实际案例结束，由浅渐深，提供丰富的应用案例及解决方案。以更丰富的综合应用案例帮助读者增强对理论的感性认识，从而明白这些数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。提供了大量可以直接编译运行的源代码。不仅使得学生在学习时容易起步，可以在现成源代码的基础上不断修改扩充，从而解决更为复杂的问题，而且也为IT专业人士提供了方便的经典代码库。,5,配套教材介绍,主教材特点第一章：数据结构与算法的基本概念和两者的关联，重点介绍了抽象数据类型和算法复杂度的概念第二章：C语言关键内容复习第三章：线性表以及最基本的两种应用：堆栈和队列第四章：树，重点介绍了二叉树和搜索树，并将查找、哈夫曼树和集合表示等作为树形结构的应用进行了讨论第五章：通过对从海量信息中高效查找关键字问题的再思考，引出对散列表和经典哈希映射技术的讨论第六章：图的各种表示方法和相关算法第七章：经典的排序算法第八章：通过对两个实际生活中提炼出的问题的求解，帮助读者更深刻体会数据结构的应用。,6,配套教材介绍,主教材特点提供全部PPT课件（辅助教材书后附赠光盘中有，也可以向高教社直接索取，或者去下载，包括书中代码和勘误表）采用本书作为教材的学校，由出版社完成资格审查后，可获得给校级用户安装于局域网内的系统，内含固定的练习题目及数据、标准程序。系统允许Admin自己增删题目，并且提供选择题题库管理、试卷生成、考试的功能配套网络资源：提供对外公开的在线系统PAT（即ProgrammingAbilityTest系统，,7,配套教材介绍,辅助教材特点大量课程设计题目（27+35+3）建议：每章详解2-3题，布置1-2题，优秀的学生尝试思考题给额外奖励随书附赠光盘中有PAT单机版，内含全部实验案例题目及测试数据、标准解答程序。学生可以尝试优化代码，并自行测试效果。,8,配套教材介绍,辅助教材特点推荐组合3-1一元多项式求导（详）3-4一元多项式的乘法与加法3-3银行业务队列简单模拟（详）+8-2单窗口“夹塞”版8-5“多队列多窗口”版4-2树种统计（BST）+4-4Windows消息队列（堆）4-9笛卡儿树5-1整型关键字的散列映射+5-2字符串关键字的散列映射5-5QQ帐户的申请与登陆,9,配套教材介绍,辅助教材特点推荐组合6-1七桥问题+6-3六度空间+6-5旅游规划6-8城市间紧急救援+6-9社交网络结点”重要性”7-1模拟Excel排序+7-2寻找大富翁7-6奥运排行榜,10,基础型认证系统PAT介绍,认证系统：,2011年8月21日对外开放目前已成功举办各种考试21场题库公开102道练习题（往届真题）注册用户2700余人提交12万余人次,11,基础型认证系统PAT介绍,程序设计能力测试（ProgrammingAbilityTest，简称PAT），成绩优秀的学生直接免除招聘时与考查程序设计能力相关的笔试环节。目前合作的企业已经达到47家，包括国际著名500强企业甲骨文亚洲研发中心、摩根士丹利公司（上海）、Google中国、道富科技（浙江）公司、华为公司（杭州研究院）以及国内著名重点IT企业如百度、网易研究院（杭州）、阿里巴巴-B2B技术部、腾讯、淘宝（中国）软件有限公司、eBay中国研发中心等。,Google中国：PAT(A)成绩不低于90分者，可给予免除笔试直接进入面试阶段的优惠政策。百度：PAT(A)成绩不低于80分者，优先考虑实习岗位。PAT成绩优良的学生，免除招聘时与考查程序设计能力相关的笔试环节。华为、腾讯、小米、,每次考试后将考生全部信息（成绩、排名、最后提交的代码、所在学校/单位、联系方式）以及本场考试的题目描述打包发给合作企业的人力资源部门当然是在考生同意的前提下,12,基础型认证系统PAT介绍,2011年发起，由浙江大学计算机科学与技术学院统一组织目的1：培养和展示考生分析问题、解决问题和计算机程序设计的能力，科学评价计算机程序设计人才目的2：为企业选拔人才提供参考标准难度甲级（英文）：与浙江大学计算机科学与技术学院考研上机复试难度相似，最难题属国际竞赛中等偏下难度；分case给分。乙级（中文）：初等编程能力测试。甲级60分大约相当于乙级的90分以上。已举办5场，报名考生600人，发放证书442份。考生来自各地31所高校以及部分在职人员。,13,基础型认证系统PAT介绍,考试大纲,14,基础型认证系统PAT介绍,考试组织每年组织3次统一考试，一般安排在3月初（春）、8月底（秋）、12月中（冬）目前有杭州、宁波、福州、西安4地考场浙江大学宁波理工学院信息科学与工程学院浙江大学软件学院（宁波）福州大学数学与计算机科学学院西安交通大学闭卷考试，甲级英文、乙级中文题目描述，20分钟试机，3小时考试总分100分，每题分数的分布与题目难度成正比。甲级考试的分数分布一般为：20、25、25、30；乙考试的分数分布一般为：15、20、20、20、25。,15,基础型认证系统PAT介绍,考试成绩每题分case给分；整场考试得分为各题得分之和名次根据总得分决定，相同分数对应并列名次考试不设合格标准，凡参加者均有成绩。考试结束后可获得浙江大学计算机科学与技术学院统一颁发的证书，证书中包含考试分数和本次考试的排名两部分成绩,16,基础型认证系统PAT介绍,已有试题分析A4题：20+25+25+30难度级别（1-5）一般为1.5+2.5+3+3.5（或4）B5题：15+20+20+20+25难度级别（1-5）一般为1+1.5+1.5+2+2.5样例覆盖50%以上测试点，样例等价测试数据的分数占总分50%以上其它测试包括边界测试、特殊情况,17,基础型认证系统PAT介绍,20分题目：基础编程能力WorldCupBetting(1.5)-找最大赔率值并计算收益HaveFunwithNumbers(1.5)-大数乘2，判断是否是原数字位的重排列BeUnique(1.5)-输出第1个唯一的数字ShortestDistance(1.5)-环形公路N个出口，找任意两出口间最短距离，要卡O(N)复杂度StringSubtraction(1.5)-从S1中删除所有S2的字符，要求O(n)，快速识别S2的字符,18,基础型认证系统PAT介绍,25分题目：简单算法应用能力TheBestRank(2.5)-按C语言、数学、英语、平均分成绩最好的排序BattleOverCities(3)-数连通集PalindromicNumber(2.5)-判断几步可以得到对称整数，大数加法PATRanking(3)-合并多个rank，有并列排名处理LongestSymmetricString(2)-给出最长对称子串的长度,19,基础型认证系统PAT介绍,25分题目：简单算法应用能力CourseListforStudent(3)-给课程选课名单，输出每个学生的选课清单，用到hashStudentListforCourse(2.5)-给学生选课清单，输出每门课选课名单FindCoins(2.5)-从N个整数中找2个，和等于给定整数，要求O(N)复杂度PopSequence(2)-顺序入栈，判断出栈顺序是否对LinkedListSorting(2.5)-链表排序，实际不用链表，直接qsort；但有多余结点要剔除,20,基础型认证系统PAT介绍,30分题目：算法应用能力或繁琐编程能力WaitinginLine(4)-复杂队列模拟，繁琐TableTennis(4)-有VIP队列的模拟，繁琐RecovertheSmallestNumber(3.5)-给N个整数，排列成一个最小整数，细节处理CountingOnes(4)-数1N中1出现的次数，卡时PathofEqualWeight(4)-求树中等于S的所有根到叶的路径,21,基础型认证系统PAT介绍,15分题目：样题，基础编程能力害死人不偿命的(3n+1)猜想(1)卡拉兹猜想换个格式输出整数(1)用BBSSS1234表示234,22,基础型认证系统PAT介绍,欢迎高校加盟，建立指定考点,2