基本信息

编辑推荐
204道试题全部从ACM国际大学生程序设计竞赛和其他程序设计竞赛中精选而出,并给出详尽试题解析。
由浅入深、循序渐进地引入基本能力、线性表、树、图的编程实验,同时注重从思维方式上历练读者的编程能力。
相关推荐:
《挑战程序设计竞赛(第2版)》
《算法设计编程实验:大学程序设计课程与竞赛训练教材》
《ACM国际大学生程序设计竞赛:算法与实现》
内容简介
计算机书籍
《数据结构编程实验:大学程序设计课程与竞赛训练教材》以知识体系结构和思维方式两个方面作为主线,分成四大篇14章介绍了基本能力的编程实验(基础)、线性数据结构的编程实验(线性表)、层次类非线性表的编程实验(树)以及群聚类非线性表的编程实验(图),并将“排序”和“搜索”的内容融合到相关章节中。每章节由实验范例和题库两个部分组成,试题全部选自ACM国际大学生程序设计竞赛和其他程序设计竞赛,共204题,并给出了试题来源和在线测试地址。每个实验范例不仅有详尽的知识要点阐述和试题解析,而且列出了写有详细注释的参考程序;而题库中的所有试题无论难易,都有清晰的提示。本书还附带了存储所有试题的英文原版描述和大部分试题的测试数据等资料的光盘。
《数据结构编程实验:大学程序设计课程与竞赛训练教材》的实验范例部分可以作为程序设计语言和数据结构的实验教材,供大学教学使用;题库部分则可以作为计算机专业学生的研修资料和程序设计竞赛的培训教材。
作译者
王建德,著名的信息学奥林匹克竞赛金牌教练,国务院特殊津贴专家,中学特级教师。他所辅导的学生在国际奥林匹克信息学竞赛(IOI)中获7金、3银、2铜的优异成绩,先后出版了24本关于程序设计和算法的学术专著,其中《实用算法的分析与程序设计》广受好评,长期以来是国内各类程序设计竞赛的必备教程。
目录
前言
第一篇 基本能力的编程实验
第1章 简单计算的编程实验 2
1.1 改进程序书写风格的实验范例 2
1.2 正确处理多组测试数据的实验范例 4
1.3 提高实数精度的实验范例 7
1.4 使用二分法提高计算时效的实验范例 8
1.5 相关题库 13
第2章 简单模拟的编程实验 23
2.1 直叙式模拟的实验范例 23
2.2 筛选法模拟的实验范例 26
2.3 构造法模拟的实验范例 28
2.4 相关题库 30
第3章 简单递归的编程实验 36
3.1 计算递归函数的实验范例 36
3.2 用递归算法求问题解的实验范例 37
3.3 求解递归数据的实验范例 40
3.4 相关题库 42
本篇小结 46
前言
1)在课程中需要增加思维方式和解题策略的引导,引导学生思考各类数据结构的本质特征是什么;面对当前问题为什么要采用这样的数据结构而不宜采用那样的数据结构;当有多个数据结构可用时,怎样权衡时间复杂度、空间复杂度、编程复杂度和思维复杂度四个因素,寻找最合时宜的数据结构,将“知识导向”与“智慧导向”真正结合起来。
2)在课程中需要引入案例教学,通过模拟或者重现现实生活中的一些场景,让学生置身问题情境之中,通过思考、讨论和上机编程来进行学习。传统教学将数据结构“束之高阁”,在理论教学和笔试上兜来兜去,可能会使学生浑然不知数据结构在现实生活中究竟派什么用处,懵懵懂懂,最终失去了学习的意义。“纸上得来终觉浅,绝知此事要躬行”。案例教学则是一种以问题和动手编程驱动学习的方式:将知识置于问题情境和实践过程之中,变枯燥乏味为生动活泼。学生拿到试题后,先进行审题,然后温习或查阅各种他认为必要的数据结构知识,这无形中激发了他们的求知欲望,加深了他们对知识真谛的理解。捕捉到相关的理论知识后,学生还要经过缜密思考和动手编程,使之变为解决问题的程序方案。这个“认识-实践-再认识-再实践”的过程,应视为知识理解上的一种提高,知识学习与应用能力间的一种转变和升华。
基于上述想法,我们近年来开设了“数据结构实验”课程,并将ACM国际大学生程序设计竞赛和其他程序设计竞赛中的典型试题分门别类,精选了其中204道试题,翻译后作为学习数据结构知识的实验案例。这些试题不仅为相关知识创设了丰富有趣的问题背景,而且在相关网站上都有试题的在线测试。学生不仅可以带着问题学习数据结构,而且所编程序的正确性和效率也可以通过相关网站上的测试系统得到实时检验,达到“学以致用”的目的。
本书试题的在线测试地址主要有:
在线评测系统简称网址
北京大学在线评测系统POJhttp://poj.org/
浙江大学在线评测系统ZOJhttp://acm.zju.edu.cn/onlinejudge/
UVA在线评测系统UVAhttp://uva.onlinejudge.org/ http://livearchive.onlinejudge.org/
Ural在线评测系统Uralhttp://acm.timus.ru/
SGU在线评测系统SGUhttp://acm.sgu.ru/
本书按照数据结构的知识结构和循序渐进的原则,共分四大篇(基本能力的编程实验、线性数据结构的编程实验、层次类非线性表的编程实验、群聚类非线性表的编程实验)14个章节。每个章节为相关数据结构知识提供了大量的实验范例,并且建立了相关的试题库,其中实验范例68道,题库试题136道。每个实验范例不仅有知识要点阐述和详尽的试题解析,还列出了写有详细注释的参考程序;题库中的所有试题无论难易,都有清晰的提示。教师既可以将实验范例作为开设数据结构实验课程的教材,也可以从相关题库中挑选数据结构实验课程的作业、考题或指导ACM集训活动的培训资料。每道题都注明了试题来源和在线测试网址,考虑到网站更新给读者学习带来不便的可能情况,本书还附带了存储所有试题的英文原版描述和大部分试题的测试数据等资料的光盘。我们之所以这样做,就是力图构建一个尽可能丰富、实用和长效的数据结构实验课程资源库。
需要说明的是,本书是在复旦大学ACM集训队长期活动的基础上积累而成的。阿拉法特·居来提、姚哲云、张昊等同学精心编写了所有程序,每道程序都通过了严格的测试验证,其中一些程序经多次修改,精益求精。这些同学为本书的出版付出了辛勤的劳动,作出了不可或缺的贡献。在此,向他们表示由衷的感激。另外,衷心感谢复旦大学计算机学院2006、2007、2008级同学在使用本书讲义过程中提出的宝贵意见和建议。由于时间和水平所限,书中肯定夹杂了不少缺点和错误,表述不当和笔误更是在所难免,热忱欢迎学术界同仁和读者赐正。如果你在阅读中发现了问题,请通过书信或电子邮件告诉我们,以便及时整理成勘误表放在本书的专门网站上,供广大读者查询更正。我们更期望读者对本书提出建设性意见,以便再版时改进。我们的联系方式是:
通信地址:上海市邯郸路220号复旦大学计算机科学技术学院 吴永辉
邮编:200433
E-mail:yhwu@fudan.edu.cn