第一讲 数据结构与算法实习简介

《第一讲 数据结构与算法实习简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法实习
概论北京大学信息科学技术学院

主讲：张铭、郝丹
mzhang[at]net.pku.edu.cnhaod[at]sei.pku.cnhttp://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/2011.8张铭赵海燕王腾蛟宋国杰，《数据结构与算法实验教程》（国家十一五规划教材），高教社2011年1月
助教!卞俊杰[00848192－1000012714]bianjunjie@cis.pku.edu.cn!刘鸿博[1000012715-1000012831]liuhongbo@pku.edu

2、.cn!宋子琴[1000012835-1000017665]songziqin@pku.edu.cnWeb信息处理!人工智能!队列、图、字符、广义表、集合、搜图形图像!矩阵散列、排序、索树及各种有向图!队列、栈、图、矩阵、索引、检索!空间索引树、检索!数据库概论!操作系统!编译原理!线性表、多链表、队列、存储管理表、字符串、栈、散排序及B+索引树
排序及目录树
列表及语法树!算法分析与设计
数据结构与算法实习
数据结构与算法!程序设计实习
概率统计集合论与图论
计算概论!北京大学信息学院©版权所有，转载或翻印必究Page3数据结构与算法体系图
前沿应

3、用：后缀树、XMLDOM树、搜索引擎…...
抽象数据类型ADT
算法分析时空折衷
逻辑
运算
存储
理论
线性（表、栈、排序：插入、分治顺序、链接、队列、串）
、快速、堆、基数
散列、索引


抽树(二叉树、森检索:二分、散列
内存、外存
林)

象

图（有向、无外排序索引：BST、B+
向、DAG）

B+树，倒排
设计
外排序，广义表，稀疏矩阵，字符树，扩展研究:
Patricia树，AVL，红黑树，伸展树……课程目的
配合“数据结构与算法”主课，提高实际动手能力和程序设计的质量
!基本数据结构
!线性表(向量、串、栈和队列)、二叉树、树、

4、图等
!ADT、STL
!综合应用程序
!排序、检索、文件、索引等技术
!程序设计实践和技巧
数据结构的逻辑组织
!逻辑结构描述数据元素之间的关系!123456!线性结构!1
!线性表（表，栈，队列，串等）!2
3
!非线性结构!4
5
6
!树（二叉树，Hu"man树，二叉搜索树等）!!图（有向图，无向图等）!1
2
6
3
5
4
核心内容
!基本算法
!枚举法、贪心法
!递归、回溯、搜索与分支限界
!分治法、动态规划
!问题建模
!数学建模、软件模型补充内容
!C++编程技术补充
!标准模板库STL的基本概念
!C++流处理
!程序设计实践和技

5、巧
!风格、设计和实现
!界面、排错
!测试、性能和可扩展性
进度安排（可调顺序）
!1.第一周数据结构与算法实习简介
!2.第二周算法（一）：穷举法、贪心法
!3.第三周程序设计实践（一）：风格、设计和实现
!4.第四周算法（二）：回溯法、搜索问题
!5.第五周国庆放假
!6.第六周习题课
!7.第七周算法（三）：分治法
!8.第八周程序设计实践（二）：项目设计案例
!9.第九周算法（四）：数据结构与算法技巧!10.第十周特邀校友讲座
!11.第十一周算法（五）：动态规划
!12.第十二周程序设计实践（三）：界面、排错、测试 
!13.第十三周习题

6、课
!14.第十四周图的应用、算法优化
!15.第十五周问题建模专题讨论
!16.第十六周习题课，大实习设计和项目展示
成绩评定办法
!平时：5%!开卷随堂测试、课堂表现和交流!ACM作业：15%
!北大ACM结果、源程序、实习报告!综合上机题：30%!源程序、实习报告!POJ机考：30%!源程序!期末考试20%
考勤
!可以申请自学，必须写出书面申请
"提交时间：9月15日课上"自学的同学可以不来听课
"同样交作业、上机题、考试
!不要迟到早退、旷课
"有事提前请假
"实习班考勤措施
"课堂讨论
"随堂小测试
作业要求
!实习课3道大综合实习，5道

7、ACM!“诚实代码”
!要调试，要测试!POJ题目要有帐号“11DS学号”
!大实习题需要测试用例
!都要提交上机报告
诚信
!端正学习态度、调动学习兴趣
"提倡讨论，但严禁抄袭
"可以讨论思路
"但要亲自动手实现
"发现抄袭，严肃查处
"抄袭者和被抄袭者本次作业或上机题计双倍倒扣分，即得-20分
"以后的作业题会得到重点检查
"严重的期评将给予不及格处理
团队合作能力
!专业能力
!技术过硬,质量高
!沟通能力
!表达能力,沟通技巧
!全局观
!不要成为团队的Bottleneck!敬业精神
!追求卓越，积极主动
!个人信誉
!做一个可以信赖的人
上

8、机题编程风格
!诚实代码保证
!内部文档要求
!过程代码要求
!面向对象的代码要求
按时提交作业，严禁抄袭