“数据结构与算法”作业
  • 务必标明姓名和学号。算法请尽可能写得清晰规整，加上必要注释
  • 作业应按时独立完成，在要求的截止日期前交。超过日期一周之内，成绩递减1/2，其余类推
  • 请将独立的程序文件上载教学网给辅导老师，其他作业可用DOC或PDF格式的文件，同样上载。
  • 各同学所指定的辅导老师见下面和 “课程通知”
  • 由于今后作业的程序可能更大，需要良好的模块组织，原通知的程序文件名统一形式取消。但请为作业的程序文件选择合适的名字，每次作业的文件打包（可用 zip/rar/7z 压缩文件格式），打包文件采用统一取名形式“DS-学号-作业序号.xxx”（xxx 可以是 zip/rar/7z），以便辅导老师确认交作业的同学。
  • 为保证作业文件得到正确处理，程序文件开头一律用 Python 注释形式提供下面信息： 
    # 姓名
# 学号
# 完成作业所用时间（估计）
# DS 序号
    其中的“姓名”，“学号”和“完成作业所用时间”和“序号”填入具体信息。

关于大作业分组方式的调整方案

  • 根据一些同学的要求，综合考虑各种情况，有关大作业分组方式做如下调整。
  • 一个大作业组由两位同学组成，自由结组，确定后在整个学期内不能改变。
  • 尽可能在同一个辅导老师的范围内结组，也允许跨辅导老师安排结组。
  • 每组由一位同学负责联系，在下周（10.16）前每个组给自己的辅导老师发一个邮件报到。跨辅导老师的组先选一个辅导老师报到，有可能根据情况调整负责的辅导老师。
  • 大作业的工作以小组为单位进行，完成后按时上交。成绩为两人的成绩。
2014年春季辅导教师：
胡婷婷负责学号 10601-10640 的同学；从第5次作业开始学号 10641-10689 的同学
陈　晨负责学号 10641-10689 的同学；从第5次作业开始学号 10692-10728 的同学
刘海洋负责学号 10692-10728 的同学；从第5次作业开始 10729 以上学号及其他同学
张　可负责学号 10729 以上及其他同学；从第5次作业开始学号 10601-10640 的同学
序号 布置日期 提交日期 作业内容
9 12.22 12.28 本次作业主要是为了帮助同学复习字典与集合一章的概念和算法。
  1. 假设一个散列表有 13 个元素，用取模 13 作为散列函数，采用开地址法和线性探查技术解决冲突。请画出这一散列表在顺序地插入数据 [38, 15, 29, 88, 67, 44, 75, 52, 64] 之后的状态。
  2. 请根据最佳二叉排序树的构造算法，基于下面数据建立与之对应的最佳二叉排序树：树关键码集合是 [a, b, c, d, e]，内部结点的权集合是 [6, 14, 1, 7, 4]，外部结点的权集合为 [5, 7, 10, 3, 4, 8]。请画出所构造的二叉排序树，计算其 ASL（平均检索长度）。
  3. 将关键码 [7, 42, 57, 33] 顺序插入下面的平衡二叉排序树（AVL 树），请先给原树中的结点标明平衡因子，然后画出各关键码插入并调整后的情况，并请说明每次调整使用的是哪种调整（或无需调整）。
8 12.11 15.1.2 第三个分组项目。这次要求做一个更接近实际应用的项目，请从两个题目中任选一个，具体要求见项目说明文件：
  1. 图书索引处理。这里有一个文件，是一部著名计算机专著的一部分索引，作为本项目的参考数据文件。
  2. 视频信息的收集和管理，这是一个牵涉到互联网信息收集和处理的项目。
7 12.04 12.11 作业内容
  1. 请分别按照 Prim 和 Kruskal 算法做出下面网络的最小生成树：
  2. 请根据 Dijkstra 算法分别做出下面带权有向图从 V0 和 V8 出发到其他所有顶点的最短路径：
  3. 请求出下面 AOE 网中以 V0 为始点 V9 为终点的关键路径：
6 11.20 12.05 第二个分组项目，两个题目任选一个，要求见项目说明文件：
  1. 电梯模拟系统
  2. 五子棋游戏程序
5 11.13 11.20 作业内容： 前两个题写电子文档或纸面作业，第3题写程序。

1，根据二叉树的几种结构形态，严格证明扩充二叉树的外部路径长度和内部路径长度的关系式 E = I + 2*n。

2，请总结出在二叉树的 list 表示中空表的个数与树中分支结点与叶结点数目的关系公式，并严格证明这一关系公式。

3，请在表达式的 list 表示基础上完成下面工作：

  • 定义函数 variables(exp)，它求出在表达式 exp 出现的所有变量的集合；
  • 扩充本次课程中的示例函数 evel_exp，增加一个参数 values，对应实参应是一个字典，以可能在表达式里出现变量为关键码给出变量的值。新的 eval_exp 在求值中遇到变量时检查该字典，用字典提供的对应值取代这个变量。
  • 设 exp 是可以包含变量的代数表达式（其中只有加和乘运算），请定义函数 derive(exp, var)，它给出 exp 对变量 var 的导函数表达式。
请在上交程序文件里写一些使用你定义的函数的实例。
4 10.30 11.13 作业内容：

1，请试写出描述下面集合的正则表达式（注意写出匹配集合尽可能小的表达式）：

  • 数学学院 13 级所有本科生的学号集合。
  • 北京大学图书馆中数学书籍的馆藏目录索书号的集合。
写一个程序文件，其中代码使用了你的正则表达式，通过一些例子说明它们能正确工作。对每个表达式，在这个文件里用一段注释说明它所匹配的字符串集合。

2，实现一个中缀表达式求值函数。课堂讨论的某些代码可能有帮助，请实现一个独立的函数。另外写一个 demo 函数展示你的函数的功能，说明它能正确工作。

（11月6日新增作业）下面是几个书面作业题，目的在于帮助理解课堂讨论的一些内容（可以用电子文档或纸面形式交作业）：

3, 把下面中缀表达式翻译为与之等价的前缀形式：

  • (a + b) * (c - d)
  • 2 * (a + b) / c / d
4, 把下面后缀表达式翻译为与之等价的中缀形式：
  • a b c / f d - * 3 r / + -
  • 2 a + b / c d - e f - * /
5, 设有一系列元素 a, b, c, d，可以从左到右顺序取用
  • 如果有一个栈 st，可以做的操作是 (1) 取一个元素并压栈；(2) 从栈里弹出一个元素并输出。请列出能得到的所有输出序列。
3 10.21 11.6 第一个分组项目，有关描述见项目说明文件。
2 10.09 10.16 作业内容：

请检查自己上学期的编程作业，从中找出 3 个使用了 list 的函数定义。应用有关算法分析的技术，以及课程中有关 list 的实现和性质情况的介绍，考察这几个函数的复杂性。请注意，所考察的函数应是能处理任意大小的表的函数，以表长度为问题规模 n 完成要求的分析工作。三个函数应该有一定的差异性。

作业用一个文档文件（例如 word 文件）的形式上交。拷贝你原来的程序（把格式整理好），然后写出你的分析和结论。

1 9.25 10.9 作业内容：

1，扩充参考程序所给的有理数类，加入下面功能：

  • 减法、乘法和除法的运算符的定义；
  • 判断相等和小于关系的运算符的定义（用运算符 == 和 <）；
  • 转换到整数（取整）和浮点数的方法。
运算符的特殊函数名请查看语言手册 3.3.7 节（Emulating numeric types）。

2，定义一个表示时间的类 Time，它提供下面操作：

  • Time(hours, minutes, seconds) 创建一个时间对象；
  • t.hours()，t.minutes()，t.seconds() 分别返回时间 t 的小时、分钟和秒钟；
  • 为 Time 对象定义加法和减法操作（用运算符 + 和 -）；
  • 定义时间对象的等于和小于关系运算（用运算符 == 和 <）。
注意：Time 类的对象可以采用不同的表示。例如，你可以给每个对象定义三个“域” hours，minutes 和 seconds，基于这种表示实现所有操作。也可以用一个域 seconds，构造对象时从参数计算出该时间表示的从一天的 0 hour 0 minute 0 second 起算的秒值，基于这种秒值实现所有操作。请从易实现的角度权衡，选择你认为合适的设计。

这种情况也表现出 “抽象数据类型” 的抽象性，其内部实现与使用之间有良好的隔离，换一种实现方式（或改变一些操作的实现技术）完全可以不影响使用它的代码。

注意：在定义了一个类后，应写一段使用它的演示代码，产生一些输出。代码和输出应能清晰表现你完成的工作，以便辅导老师检查。演示代码是作业的必要部分。

自我练习（考察完成同样工作的不同程序的时间代价的增长趋势）：利用 time 包的 time 函数（上学期已介绍），考察课堂幻灯片给出的生成整数表的几种方法。写一些代码，用不同大小的的参数运行各 test_i 函数，输出其运行时间。分析总结各函数相对于参数的耗时增长趋势，比较不同方法。
本页及相关页面（除另声明者外）由裘宗燕创建维护，可自由用于各种学习活动。其他使用需得到作者许可。