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

本文档相关内容参见 视频 10-11,数据结构与算法,主讲：陈 越（浙江大学计算机学院）Email:,3,第六部分（90分钟）,配套教材介绍 主教材特点 辅助教材特点 基础型认证系统PAT介绍 提高型练习系统ZOJ介绍 课程网站介绍,4,配套教材介绍,主教材特点问题驱动：每章以问题开篇、以实际案例结束，由浅渐深，提供丰富的应用案例及解决方案。以更丰富的综合应用案例帮助读者增强对理论的感性认识，从而明白这些数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。提供了大量可以直接编译运行的源代码。不仅使得学生在学习时容易起步，可以在现成源代码的基础上不断修改扩充，从而解决更为复杂的问题，而且也为IT专业人士提供了方便的经典代码库。,5,配套教材介绍,主教材特点第一章：数据结构与算法的基本概念和两者的关联，重点介绍了抽象数据类型和算法复杂度的概念第二章：C语言关键内容复习第三章：线性表以及最基本的两种应用：堆栈和队列第四章：树，重点介绍了二叉树和搜索树，并将查找、哈夫曼树和集合表示等作为树形结构的应用进行了讨论第五章：通过对从海量信息中高效查找关键字问题的再思考，引出对散列表和经典哈希映射技术的讨论第六章：图的各种表示方法和相关算法第七章：经典的排序算法第八章：通过对两个实际生活中提炼出的问题的求解，帮助读者更深刻体会数据结构的应用。,6,配套教材介绍,主教材特点提供全部PPT课件（辅助教材书后附赠光盘中有，也可以向高教社直接索取，或者去 下载，包括书中代码和勘误表）采用本书作为教材的学校，由出版社完成资格审查后，可获得给校级用户安装于局域网内的系统，内含固定的练习题目及数据、标准程序。系统允许Admin自己增删题目，并且提供选择题题库管理、试卷生成、考试的功能配套网络资源：提供对外公开的在线系统PAT（即Programming Ability Test系统，http:/），有全部实验项目（3道开放性实验项目除外）题的在线评判，全天候为广大读者提供免费服务采用本书作为教材的学校，由出版社完成资格审查后，也可免费享受PAT系统定制服务，即填写申请表后，在PAT上获得专用帐号，进行课程练习组织、考试组织。无须自己维护服务器,7,配套教材介绍,辅助教材特点大量课程设计题目（27+35+3）建议：每章详解2-3题，布置1-2题，优秀的学生尝试思考题给额外奖励随书附赠光盘中有PAT单机版，内含全部实验案例题目及测试数据、标准解答程序。学生可以尝试优化代码，并自行测试效果。,8,配套教材介绍,辅助教材特点推荐组合3-1 一元多项式求导（详）3-4一元多项式的乘法与加法3-3 银行业务队列简单模拟（详）+8-2 单窗口“夹塞”版 8-5“多队列多窗口”版4-2 树种统计（BST）+4-4 Windows消息队列（堆）4-9 笛卡儿树5-1 整型关键字的散列映射+5-2 字符串关键字的散列映射 5-5 QQ帐户的申请与登陆,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介绍,程序设计能力测试（Programming Ability Test，简称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分题目：基础编程能力World Cup Betting(1.5)-找最大赔率值并计算收益Have Fun with Numbers(1.5)-大数乘2，判断是否是原数字位的重排列Be Unique(1.5)-输出第1个唯一的数字Shortest Distance(1.5)-环形公路N个出口，找任意两出口间最短距离，要卡O(N)复杂度String Subtraction(1.5)-从S1中删除所有S2的字符，要求O(n)，快速识别S2的字符,18,基础型认证系统PAT介绍,25分题目：简单算法应用能力The Best Rank(2.5)-按C语言、数学、英语、平均分成绩最好的排序Battle Over Cities(3)-数连通集Palindromic Number(2.5)-判断几步可以得到对称整数，大数加法PAT Ranking(3)-合并多个rank，有并列排名处理Longest Symmetric String(2)-给出最长对称子串的长度,19,基础型认证系统PAT介绍,25分题目：简单算法应用能力Course List for Student(3)-给课程选课名单，输出每个学生的选课清单，用到hashStudent List for Course(2.5)-给学生选课清单，输出每门课选课名单Find Coins(2.5)-从N个整数中找2个，和等于给定整数，要求O(N)复杂度Pop Sequence(2)-顺序入栈，判断出栈顺序是否对Linked List Sorting(2.5)-链表排序，实际不用链表，直接qsort；但有多余结点要剔除,20,基础型认证系统PAT介绍,30分题目：算法应用能力或繁琐编程能力Waiting in Line(4)-复杂队列模拟，繁琐Table Tennis(4)-有VIP队列的模拟，繁琐Recover the Smallest Number(3.5)-给N个整数，排列成一个最小整数，细节处理Counting Ones(4)-数1N中1出现的次数，卡时Path of Equal Weight(4)-求树中等于S的所有根到叶的路径,21,基础型认证系统PAT介绍,15分题目：样题，基础编程能力害死人不偿命的(3n+1)猜想(1)卡拉兹猜想换个格式输出整数(1)用BBSSS1234表示234,22,基础型认证系统PAT介绍,欢迎高校加盟，建立指定考点,23,基础型认证系统PAT介绍,考点工作招生宣传（可分享宣传册）考生报名管理（收费、确认考生）考场准备（一台备用服务器）监考和证书打印颁发等工作考点收益（考生费用-60）/人免费获得备用系统，可为本地学生提供练习平台（有admin权限，可自行添加考试和题目，但无选择题考试）,24,提高型练习系统ZOJ介绍,http:/浙江大学计算机程序设计在线裁判系统（Zhejiang University Online Judge，简称ZOJ）定位：国际大学生程序设计竞赛(ACM-ICPC)训练题库质量：十年来已积累题目2700余题，全球用户数逾6万，举办（原创）全球公开赛126场，在线提交量达320多万人次，是全球最有影响力的程序设计竞赛类网站之一,25,课程网站介绍,课程网站：http:/全套课程资料：大纲、日历、课件、试卷、课余资料无须帐号,26,欢迎交流、指教谢谢！,