CS32132 Data Structures and Algorithms - Autumn 2021

这个文档列出了哈尔滨工业大学计算学部2021年秋数据结构与算法课程历次作业的要求，以及根据个人理解所构造的输入输出格式样例。本项目同时包含了这些数据的生成器，仅供参考。

项目持续更新中，如有缺漏、建议，欢迎私信、 PR 、提 issue ！

Github 项目源址 private

索引

普通作业

• 绪论

  • 字符串排序
  • 求最大元素位置
  • 比赛图

• 线性表

  • 链表块转置
  • 求链表对称差
  • 共享栈
  • 链表字符串
  • 广义表

• 树和二叉树

  • 完全二叉树
  • 最近公共祖先
  • 二叉堆
  • 多路平衡归并排序（胜者树与败者树）
  • 森林的后序遍历

• 图及算法

  • 农夫过河

• 查找

  • 二分查找
  • 二叉搜索树

大作业

• 【线性表】家电仓库

实验

• 实验一【线性表】
  • 分时系统模拟
  • 模拟飞机起降系统的设计
  • 多项式乘除法
  • 算术表达式求值
  • 食堂售饭问题
• 实验二
  • 遍历二叉树
  • 哈夫曼树
• 实验三
  • 图的遍历
  • 工程安排

加分作业

• 【加分作业】字符串匹配算法报告

详细内容

绪论

字符串排序

定义字符集是大写字符和数字的集合，设其顺序为： A，B，C，... ，Z，0，1，2，... ，9 ，现给出若干字符串，给出其字典序排列。

定义字典序：

• 对于 a 和 b 两个字符串，若前 i-1 位相同，第 i 位不同，则第 i 位按顺序靠前者字典序更小。

• 若 a 是 b 的前缀，且长度比 b 小，则 a 的字典序比 b 小。

• 输入格式

第一行两个整数 n 和 len 。

接下来 n 行，每行一个长度不超过 len 的字符串，包含 [A-Z0-9] ，即大写字母和数字 。

• 输出格式

n 行排好序的字符串。

• 样例输入

8 5
PAB
5C
PABC
CXY
CRSI
7
B899
B9

• 样例输出

B899
B9
CRSI
CXY
PAB
PABC
5C
7

最大元素位置

有一个包括 100 个元素的数组，每个元素的值都是 实数，写出一种算法求其最大元素的位置。

• 输入格式

一行， 100 个实数，以空格分隔，下标范围 1-100。

• 输出格式

一个整数，表示最大元素的位置

• 样例输入

3.14 2.718 1428.57 114.514 1926.0817 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 9.00 10.00 11.00 12.00 13.00 14.00 15.00 16.00 17.00 18.00 19.00 20.00 21.00 22.00 23.00 24.00 25.00 26.00 27.00 28.00 29.00 30.00 31.00 32.00 33.00 34.00 35.00 36.00 37.00 38.00 39.00 40.00 41.00 42.00 43.00 44.00 45.00 46.00 47.00 48.00 49.00 50.00 51.00 52.00 53.00 54.00 55.00 56.00 57.00 58.00 59.00 60.00 61.00 62.00 63.00 64.00 65.00 66.00 67.00 68.00 69.00 70.00 71.00 72.00 73.00 74.00 75.00 76.00 77.00 78.00 79.00 80.00 81.00 82.00 83.00 84.00 85.00 86.00 87.00 88.00 89.00 90.00 91.00 92.00 93.00 94.00 95.00

• 样例输出

5

比赛图

在有 n 个选手 P1 , P2 , P3 , … , Pn 参加的单循环赛中，每对 选手之间非胜即负。现要求求出一个选手序列： P1' , P2' , P3', … , Pn' , 其满足 Pi' 胜 Pi+1' （ i = 1, … , n-1 ）。

提示：本题即给出一个比赛图（完全有向图），求其任一哈密顿路。

• 输入格式

  第一行一个整数 n ，表示队伍数目

  接下来 n*(n-1)/2 行，每行两个数 a_i, b_i ，表示 a_i 队打败了 b_i 队

• 输出格式

  一个序列 p_1, p_2, ... p_n ，满足 p_i 胜过 p_{i+1}

• 样例输入

  4
  1 2
  1 3
  4 1
  3 2
  4 2
  3 4

• 样例输出

  1 3 4 2

线性表

链表块转置

给出长度为 n 的链表，给出一个整数 k ， 将链表每个长度为 k 的连续区间进行翻转，末尾不足 k 个元素的区间不翻转。

注：作为练习，你需要使用单向链表。

• 输入格式

  第一行两个整数 n ， k ，意义如题。

  第二行 n 个整数，依次表示链表每个节点的值。

• 输出格式

  依次输出翻转后链表的节点值。

• 样例输入

  10 3
  1 2 3 4 5 6 7 8 9 10

• 样例输出

  3 2 1 6 5 4 9 8 7 10

链表对称差

给出两个链表 A ，B ，求其元素对称差，即生成一个新链表，里面每个元素恰好只属于 A，B 其中一者。

注：作为练习，你需要使用链表进行存储。

• 输入格式

  第一行两个整数 n，m，表示 A，`B 两个链表的长度。

  第二行 n 个整数，依次表示链表 A 的每个节点元素值。

  第三行 m 个整数，依次表示链表 B 的每个节点元素值。

• 输出格式

  一行，若干整数，依次表示 A 与 B 的对称差所生成链表中的元素值。

• 样例输入

  20 20
  47 24 20 41 34 44 7 7 30 26 25 8 28 35 28 1 15 25 6 37 
  38 35 1 10 4 29 38 26 12 40 20 7 48 8 19 36 38 11 1 27 

• 样例输出

  47 24 41 34 44 30 25 28 15 6 37 38 10 4 29 12 40 48 19 36 11 27

【大作业】家电仓库

你需要编写一个程序，用来维护商场家电的库存。具体来说：

1. 每种家电的信息都需要存储在链表节点里；
2. 当出现进货、出货等操作时，意味着维护链表的增、删、改、查操作；
3. 每日营业结束时链表信息需存入文件，次日开始营业时从文件里读取数据，程序继续运行。

更详细的要求如下：

• 每个链表的节点字段包括：家电名称、品牌、单价和数量；
• 这是一个有序链表，以商品单价作为排序依据；
• 一种商品的进货与出货意味着商品的数量字段增加或减少；
• 支持通过商品名称查询该商品的品牌、单价和数量信息；
• 链表数据文件的结构需要通过精心设计，以期实现每日开始营业时链表结构与前一日结束营业前等价。

为了规范地模拟上述需求，可选择模拟命令行操作，此处提供的输入样例仅模拟程序运行时增、删、改、查的命令，以及前一日的营业数据文件，输入 exit 表示营业结束，程序将保存文件后退出；输出样例则提供了一种可能的命令行UI设计，仅供参考。

注：作为练习，你需要使用链表进行存储。

• 输入格式

  • 对于输入文件：

    第一行一个整数 n ，表示商品数目。

    接下来每行有 <name> <brand> <price> <amount> 总共 4 个数据，分别表示商品的名称、品牌、数量、单价，name、brand为字符串，price 为正实数，amount 为非负整数。

  • 对于输入命令：

    若干行，当出现 admin@system ~时可以输入，以 exit 结束。

    每行为以下几种命令中的一种：

    • put <name> <amount> ：表示名为 name 的商品增加 amount 个库存，如果 name 商品不存在，则为这种商品新建一个节点，并提示其输入商品的品牌、单价信息，格式为 <brand> <price>。
    • get <name> <amount> ：表示名为 name 的商品减少 amount 个库存，若商品不存在或库存不足，则报错，错误信息示例见样例。
    • query <name> ：表示需要调出名为 name 的商品的所有信息，若商品不存在则报错。
    • query --all ：表示需要调出所有商品信息。

    name，brand 等字段均为不带空格、缩进、换行、回车等字符的字符串。

• 输出格式

  对于每条命令：

  • 若操作成功，则给出形如 操作成功 的回应，或干错不回应，毕竟在Linux中 没有回应就是最好的回应；

  • 若失败则输出错误信息，形如 库存不足；

  • 查询指令将输出商品信息，格式形如：

    name: Cleaner-V8-Fluffy-Extra
    brand: Dyson
    price: 2399.00
    amount: 996

  • 程序启动时表示开始营业，可输出 文件加载成功 等信息。

  • 输入 exit 表示营业结束，文件写入完成后可出输出 文件已保存 等信息。

  • 对于无效命令应报错。

• 样例输入

  • 前一日营业的数据文件：

    3
    Cleaner-V8-Fluffy-Extra     Dyson  2399.00  996
    Fridge-BCD-481WGHTDD9D9U1   Haier  4399.00  758
    Television-XR-55X91J        Sony   5499.00  576

  • 输入命令：

    query --all
    put Television-XR-55X91J 100
    get Fridge-BCD-481WGHTDD9D9U1 50
    get Television-XR-55X91J 30
    get Television-XR-55X91J 2000
    put Cooker-Hood-JCD7+HT8BE.S 200
    Fotile 3899.00
    got Television-XR-55X91J 2000
    get Television-XR-55X91J 2000
    get Table-Lamp-1S 50
    exit

• 样例输出

  • 控制台输出记录：

    程序启动...
    正在读取数据...
    数据读取完成！
    开始营业。
    
    root@system ~ query --all
    库存列表：
    name: Cleaner-V8-Fluffy-Extra
    brand: Dyson
    price: 2399.00
    amount: 996
    
    name: Television-XR-55X91J
    brand: Sony
    price: 5499.00
    amount: 576
    
    name: Fridge-BCD-481WGHTDD9D9U1
    brand: Haier
    price: 4399.00
    amount: 758
    
    admin@system ~ put Television-XR-55X91J 100
    【库存更新】Television-XR-55X91J 的库存修改为 676
    
    admin@system ~ get Fridge-BCD-481WGHTDD9D9U1 50
    【库存更新】Fridge-BCD-481WGHTDD9D9U1 的库存修改为 708
    
    admin@system ~ get Television-XR-55X91J 30
    【库存更新】Television-XR-55X91J 的库存修改为 646
    
    admin@system ~ got Television-XR-55X91J 2000
    【错误】未知命令：got
    
    admin@system ~ get Television-XR-55X91J 2000
    【错误】库存不足！
    
    admin@system ~ put Cooker-Hood-JCD7+HT8BE.S 200
    【添加商品】请输入 Cooker-Hood-JCD7+HT8BE.S 的品牌名称和单价：
    Fotile 3899.00
    商品添加完成！
    
    admin@system ~ get Table-Lamp-1S 50
    【错误】商品 Table-Lamp-1S 不存在！
    
    admin@system ~ exit
    
    正在保存数据...
    数据保存完成！
    结束营业。

  • 保存的库存数据：

    4
    Cleaner-V8-Fluffy-Extra     Dyson   2399.00   996
    Cooker-Hood-JCD7+HT8BE.S    Fotile  3899.00   200
    Fridge-BCD-481WGHTDD9D9U1   Haier   4399.00   758
    Television-XR-55X91J        Sony    5499.00   576

共享栈

实现一种数据结构，要求能同时维护多个栈，包括 push，pop操作，所有栈共用同一片存储池。

作为练习，请使用静态链表实现。

• 输入格式

  第一行三个数，n, m, k，表示共享栈的个数，存储池大小，以及指令条数。

  接下来 k 每行一条命令，有三种命令：

  1 x y 表示向 x 号栈压入元素 y ，的范围为 [0, n - 1]

  2 x 表示输出 x 号栈的栈顶元素。

  3 x 表示弹出 x 号栈的栈顶元素，空栈不做任何操作。

• 输出格式

  对于每个 2 操作，输出结果，空栈栈顶返回0。

  全部操作结束后输出 n 行，表示 [0, n - 1] 号栈每个栈从栈顶到栈底的所有元素。

• 样例输入

  8 39 39
  3 5
  3 0
  3 0
  1 7 105
  1 2 40
  2 2
  3 5
  3 5
  1 2 98
  1 1 91
  1 3 47
  1 6 106
  3 0
  3 6
  2 1
  2 5
  1 4 113
  3 3
  2 0
  1 5 20
  1 3 120
  2 1
  1 0 114
  1 6 42
  1 7 54
  2 3
  2 5
  1 7 5
  1 3 101
  1 2 100
  2 6
  1 4 7
  1 5 122
  1 0 48
  2 6
  1 2 77
  1 5 122
  1 7 121
  1 0 112

• 样例输出

  40
  91
  0
  0
  91
  120
  20
  42
  42
  112 48 114 
  91 
  77 100 98 40 
  101 120 
  7 113 
  122 122 20 
  42 
  121 5 54 105 

链表字符串

用链表实现字符串的存储、查找和切片。具体来说你可以实现如下接口：

class String
{
public:
    //若s为对象本身的子串，则返回子串的起始下标；否则返回-1。
    virtual int getIndex(const String &s);
    
    //返回处于区间 [a, b] 内的子串
    virtual String subString(int a, int b);
};

• 输入格式

  第一行一个字符串 s ，表示要操作的字符串

  第二行一个整数，表示操作个数

  接下来 n 行，每行有以下操作的一种：

  1 t 如果 t 是 s 的子串，则输出开始位置在 s 中的索引，若 s 的长度为 length，则索引范围为 [0, length - 1]；否则输出 -1

  2 a b 输出 s 中处于 [a, b] 区间的子串，越界部分不输出

• 输出格式

  n 行，对于每种操作，输出其结果。

• 样例输入

  YmBYpuUnvhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmdBAN
  26
  2 3 31
  1 iGPSCCU
  2 3 4
  2 29 45
  1 vhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmdBAN
  1 liGPSCCUTcFqSXlm
  1 qSXlmdB
  2 5 44
  1 GPSCC
  1 nvhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmdBANabc
  1 uUnvhaNrNluLeJzqxvwHrQJyBliGP
  2 2 8
  1 BYpuUnvhaNrNluLeJzqxvwHrQJyBliGPSC
  1 haNrNluLeJzqxv
  1 TcFqSXlm
  1 vhaNrNluLeJzqx
  2 31 32
  2 20 23
  2 45 47
  1 rQJyBliGPS
  2 12 46
  1 liGPSCCUTcFq
  1 UnvhaNrNluLe
  2 34 34
  2 37 49
  1 abcPSCCUTcFqSXl

• 样例输出

  YpuUnvhaNrNluLeJzqxvwHrQJyBli
  31
  Yp
  BliGPSCCUTcFqSXlm
  8
  30
  41
  uUnvhaNrNluLeJzqxvwHrQJyBliGPSCCUTcFqSXl
  32
  -1
  5
  BYpuUnv
  2
  9
  38
  8
  iG
  qxvw
  mdB
  25
  rNluLeJzqxvwHrQJyBliGPSCCUTcFqSXlmd
  30
  6
  S
  UTcFqSXlmdBAN
  -1

【加分作业】字符串匹配算法报告

写一篇论文，描述下列各类算法的思想，并实现其中 2-3 个算法。

• 朴素算法
• KMP 算法
• 有限自动机算法
• Boyer-Moore 算法
• Simon 算法
• Colussi 算法
• Galil-Giancarlo 算法
• Apostolico-Crochemore 算法
• Horspool 算法
• Shift-Or 算法
• Sunday 算法

广义表

实现广义表数据结构，要求支持从字符串中解析并构造广义表，以及广义表的深度拷贝。

具体来说，你需要通过输入的数据构造出一个广义表变量 a，再创建另一个广义表变量 b，把 a 的存储结构复制给 b，最后输出能够描述 b 的字符串。

注：要实现满足如下输入输出格式的程序很容易，事实上把输入的字符串直接输出就可以，但作为练习，请根据要求实现一个广义表。

• 输入格式

  一个字符串，描述了一个非递归，无共享节点的广义表。

• 输出格式

  一个字符串，表示 b。

• 样例输入

  (1, 2, 3, 4, 5, 6, 7, (9, (11, 12, 13, 14, 15, (17, (20, ), 19),),  )     )

• 样例输出

  (1, 2, 3, 4, 5, 6, 7, (9, (11, 12, 13, 14, 15, (17, (20), 19))))

实验一

这是线性表部分的实验，从以下五个题目中选择一个完成即可。

分时系统模拟

把CPU同时分给多个用户使用的方法，称为分时方法。设有三个用户 Wang，Li和 Yao，同时开始与计算机对话，具体情况如表下所示。

用户 Wang 在时间 0 进入系统经后，CPU 分配给它四个时间周期，运行得出结果后，又输入新内容，此时 CPU 又分配给它 8 个时间周期。最后 CPU 又分配给它3个时间周期，运行得出结果后，用户 Wang 的任务全部完成。 Li 和 Yao 的执行情况类似，只是根据用户起动的相对时间排成一个队列。

当Wang完成了所请求的第一次的CPU时间周期后，到输入新内容再一次请求CPU时间这一时间的间隔，称为用户延迟周期（假设这里为5个时间周期）。一个适当的调度原则将CPU分配给Li，当Li完成后，同样再把CPU分配给Yao，这种原则叫"先进先出"。

这种调度原则可归纳为以下三点：

1. 当一用户请求CPU时间，它就进入请求使用CPU的队列。
2. 在此队列首部的用户是当前CPU的使用者，并在整个CPU时间周期内继续在队首。
3. 当一用户完成了它的现行请求CPU是间周期后，出队，并在下一个请求之前不再入队。

编写算法，实现该调度策略。

模拟飞机起降系统的设计

对于繁忙的机场来说，合理安排飞机的起降非常重要。你需要编写一个程序，维护飞机的起飞或降落动作、机场内外飞机的的数量及等待时间，和跑道的空闲时间。

具体来说，这座机场有以下特征：

• 飞机场只有一条跑道。
• 为了保证安全，我们规定时间间隔 t 内只能起降一架飞机，即时间被划分为 [0, t, 2t, 3t, ...] 的， t 为整数且 >=1，每个 [k*t, (k+1)*t] 被称为一个单位时间。

模拟开始时：

• 每一个时刻都可能有至多一架飞机请求起飞或降落，或没有飞机请求。
• 当某一时刻飞机请求起降，而下一个单位时间跑道空闲，则飞机可在下一个单位时间起飞；若不空闲，则飞机进入等待队列。
• 等待队列是有序的，降落的飞机总是排在起飞的飞机前面；对于同是起飞或降落的飞机，请求时间早的飞机总是排在请求时间晚的飞机前面。
• 机场地面和附近空域的容量都有限，所以等待队列的总容量是有限的。若某时刻等待队列已满，则这一时刻任何起降请求都会被拒绝。

多项式乘除法

给任意两个合法的一元多项式，分别输出其相乘和相除的结果。

下图所列的就是一元多项式的一般形式：

算术表达式求值

给出任何一个合法的算术表达式，输出其后缀表达式，并求值。

例如 1 + 2 * (3 + 4) / 5 就是一个算术表达式，其后缀表达式为，1 2 3 4 + * 5 / +，值为 3.8

食堂售饭问题

假设某食堂有四个窗口对外售饭，从上午 11:00 开始到下午 13:00 结束。

由于某窗口在某个时间只能接待一个同学，因此在学生多的时候需要在窗口前排队，刚来的同学如果发现有空闲窗口即可上前买饭，反之若均有同学则要排到人数最少的窗口的后面。

现要设计一个算法模拟这种业务并计算一天中午饭同学在食堂的平均时间。

树与二叉树

完全二叉树

给定一棵二叉树，判断其是否为完全二叉树。

• 输入格式

  第一行一个整数 n，表示二叉树的节点个数。

  接下来 n 行，每行两个整数 i，p_i，表示第 i 号节点的父节点编号为 p_i。

  若 p_i = -1，则 i 是根节点。

  输入保证是一棵二叉树。

• 输出格式

  如果是完全二叉树，则输出YES，否则输出NO。

• 样例输入 1

  10
  1 -1
  2 1
  3 1
  4 2
  5 2
  6 3
  7 3
  8 4
  9 4
  10 5

• 样例输出 1

  YES

• 样例解释：

  如图，是一个完全二叉树。

  

• 样例输入 2

  10
  1 -1
  2 1
  3 1
  4 2
  5 2
  6 3
  7 5
  8 4
  9 4
  10 5

• 样例输出 2

  NO

• 样例解释：

  如图，不是一个完全二叉树。

  

最近公共祖先

给定一棵二叉树，查询其任意两个节点的最近共祖先。

• 输入格式

  第一行两个整数 n，m，表示二叉树的节点个数、询问次数。

  接下来 n 行，每行两个整数 i，p_i，表示第 i 号节点的父节点编号为 p_i。

  若 p_i = -1，则 i 是根节点。

  最后 m 行，每行两个整数 x，y，表示查询编号为 x，y 节点的最近公共祖先（LCA）。

• 输出格式

  对于每个查询，输出其 LCA 的编号。

• 样例输入

  10 5
  1 -1
  2 1
  3 1
  4 2
  5 2
  6 3
  7 3
  8 4
  9 4
  10 5
  4 3
  8 10
  3 6
  9 9
  10 7

• 样例输出

  1
  2
  3
  9
  1

• 样例解释：

  如图，是一个二叉树。

  

  • 4 3 的LCA是 1
  • 8 10 的LCA是 2
  • 3 6 的LCA是 3
  • 9 9 的LCA是 9
  • 10 7 的LCA是 1

二叉堆

设计一个程序模仿操作系统的进程管理问题，进程服务按优先级高的先服务，同优先级的先到先服务的管理原则。

注：尽管你可以直接用快速排序完成本题，但作为练习，请使用堆排序。

• 输入格式

  本题要求从文件输入，设文件 task.dat 中存放了仿真进程服务请求。

  输入若干行，每行两个整数，分别表示进程号和优先级。

• 输出格式

  一行，优先级从高到低依次输出进程编号，对于优先级相同的，编号小的排在前面。

• 样例输入

  1 30
  2 20
  3 40
  4 20
  5 0

• 样例输出

  3 1 2 4 5

多路平衡归并排序（胜者树与败者树）

给出若干已经排好序的数组（或称顺串），分别使用胜者树和败者树对其进行排序。

• 输入格式

  第一行一个整数 n，表示排好序的数组数。

  接下来 n 行，每行若干整数，是一个有序序列。

• 输出格式

  两行，分别表示使用胜者树和败者树进行归并排序的结果。

  这两个序列应当是一致的。

  注：尽管你可以使用快速排序、将序列输出两次、直接完成本题，但作为练习，请使用胜者树和败者树。

• 样例输入

  8
  10 15 16
  9 20 38
  20 20 30
  6 15 25
  8 15 20
  9 11 16
  90 100 110
  17 18 20

• 样例输出

  6 8 9 9 10 11 15 15 15 16 16 17 18 20 20 20 20 20 25 30 38 90 100 110
  6 8 9 9 10 11 15 15 15 16 16 17 18 20 20 20 20 20 25 30 38 90 100 110

森林的后序遍历

森林可以使用带度数的后序遍历进行存储。

给出一个森林的后续遍历，以及每个节点的节点个数，通过此来构造森林，并输出其先序遍历。

• 输入格式

  第一行一个整数 n，表示森林的节点个数。

  第二行 n 个整数，每个整数都代表森林的一个节点编号，这是森林的后序遍历。

  第三行 n 个整数，其 i 个整数表示第二行的后序遍历中第 i 个整数对应节点的子节点数。

• 输出格式

  两行，第一行 n 个整数表示森林的先序遍历，第二行 n 个整数表示森林的中序遍历。

  森林子树的出现顺序在先序遍历、后序遍历中保持一致。

• 样例输入

  10
  2 5 6 3 4 1 10 8 9 7
  0 0 0 2 0 3 0 1 0 2

• 样例输出

  1 2 3 5 6 4 7 8 10 9

• 样例解释

  如图，即为所求森林。

  

  其先序遍历为 1 2 3 5 6 4 7 8 10 9

实验二

遍历二叉树

已知一个二叉树的先序遍历、中序遍历，建立二叉树，并分别用输出该二叉树的先序遍历、中序遍历、后序遍历。

注：作为练习，本题的遍历算法不允许使用递归。

• 输入格式

  第一行一个整数 n，表示二叉树的节点个数。

  第二行是 n 个整数的序列，表示二叉树的先序遍历。

  第三行是 n 个整数的序列，表示二叉树的中序遍历。

  n >= 8

• 输出格式

  三行序列，分别表示二叉树的先序遍历、中序遍历、后序遍历。

• 样例输入

  10
  1 2 4 8 9 5 10 3 6 7
  8 4 9 2 5 10 1 6 3 7

• 样例输出

  1 2 4 8 9 5 10 3 6 7
  8 4 9 2 5 10 1 6 3 7
  8 9 4 10 5 2 6 7 3 1

• 样例解释

  如图，即为所求二叉树。

  

哈夫曼树

给出一篇英文文章，构造哈夫曼树，并对其进行编码、译码。

以下输入输出格式仅供参考。

• 输入格式

  从 article.txt 中输入一篇英文文章，可能包含 ascii 码表的所有字符。

• 输出格式

  输出至以下 3 个文件。

  • huffman-encode-list.txt：包含文章字符出现频率，以及编码结果。
  • binary.txt：整篇文章的编码结果。
  • decode-result.txt：由编码重新解析回文章的结果。

• 样例输入

  article.txt

  What is Lorem Ipsum?
  Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book. It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged. It was popularised in the 1960s with the release of Letraset sheets containing Lorem Ipsum passages, and more recently with desktop publishing software like Aldus PageMaker including versions of Lorem Ipsum.
  
  Where does it come from?
  Contrary to popular belief, Lorem Ipsum is not simply random text. It has roots in a piece of classical Latin literature from 45 BC, making it over 2000 years old. Richard McClintock, a Latin professor at Hampden-Sydney College in Virginia, looked up one of the more obscure Latin words, consectetur, from a Lorem Ipsum passage, and going through the cites of the word in classical literature, discovered the undoubtable source. Lorem Ipsum comes from sections 1.10.32 and 1.10.33 of "de Finibus Bonorum et Malorum" (The Extremes of Good and Evil) by Cicero, written in 45 BC. This book is a treatise on the theory of ethics, very popular during the Renaissance. The first line of Lorem Ipsum, "Lorem ipsum dolor sit amet..", comes from a line in section 1.10.32.
  The standard chunk of Lorem Ipsum used since the 1500s is reproduced below for those interested. Sections 1.10.32 and 1.10.33 from "de Finibus Bonorum et Malorum" by Cicero are also reproduced in their exact original form, accompanied by English versions from the 1914 translation by H. Rackham.
  
  Why do we use it?
  It is a long established fact that a reader will be distracted by the readable content of a page when looking at its layout. The point of using Lorem Ipsum is that it has a more-or-less normal distribution of letters, as opposed to using 'Content here, content here', making it look like readable English. Many desktop publishing packages and web page editors now use Lorem Ipsum as their default model text, and a search for 'lorem ipsum' will uncover many web sites still in their infancy. Various versions have evolved over the years, sometimes by accident, sometimes on purpose (injected humour and the like).
  
  Where can I get some?
  There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don't look even slightly believable. If you are going to use a passage of Lorem Ipsum, you need to be sure there isn't anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary, making this the first true generator on the Internet. It uses a dictionary of over 200 Latin words, combined with a handful of model sentence structures, to generate Lorem Ipsum which looks reasonable. The generated Lorem Ipsum is therefore always free from repetition, injected humour, or non-characteristic words etc.

• 样例输出

  huffman-encode-list.txt

  ascii code:   0, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010000
  ascii code:   1, frequency: 0.0000000, huffman code: 1001000011100101000000100100
  ascii code:   2, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010001
  ascii code:   3, frequency: 0.0000000, huffman code: 10010000111001010001
  ascii code:   4, frequency: 0.0000000, huffman code: 100100001110010100000010011
  ascii code:   5, frequency: 0.0000000, huffman code: 1001000011100101000000100101000011
  ascii code:   6, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010011
  ascii code:   7, frequency: 0.0000000, huffman code: 1001000011100010101
  ascii code:   8, frequency: 0.0000000, huffman code: 10010000111000000010
  ascii code:   9, frequency: 0.0000000, huffman code: 10010000111000000011101
  ascii code:  10, frequency: 0.0038697, huffman code: 10010101
  ascii code:  11, frequency: 0.0000000, huffman code: 10010000111001010000001001010001
  ascii code:  12, frequency: 0.0000000, huffman code: 100100001110010100000010010111101
  ascii code:  13, frequency: 0.0038697, huffman code: 11011011
  ascii code:  14, frequency: 0.0000000, huffman code: 100100001110010100000010010111111010010
  ascii code:  15, frequency: 0.0000000, huffman code: 1001000011100001
  ascii code:  16, frequency: 0.0000000, huffman code: 10010000111000001
  ascii code:  17, frequency: 0.0000000, huffman code: 100100001110010101
  ascii code:  18, frequency: 0.0000000, huffman code: 10010000111000000100
  ascii code:  19, frequency: 0.0000000, huffman code: 1001000011100000001111
  ascii code:  20, frequency: 0.0000000, huffman code: 10010000111000000011010
  ascii code:  21, frequency: 0.0000000, huffman code: 10010000111001010000001000
  ascii code:  22, frequency: 0.0000000, huffman code: 10010000111000000011100001
  ascii code:  23, frequency: 0.0000000, huffman code: 1001000011100101000000100101001
  ascii code:  24, frequency: 0.0000000, huffman code: 1001000011100101000000100101110
  ascii code:  25, frequency: 0.0000000, huffman code: 100100001110010100000010010100000
  ascii code:  26, frequency: 0.0000000, huffman code: 100100001110010100000010010111100
  ascii code:  27, frequency: 0.0000000, huffman code: 10010000111001010000001001011111011
  ascii code:  28, frequency: 0.0000000, huffman code: 10010000111001010000001001011111111
  ascii code:  29, frequency: 0.0000000, huffman code: 100100001110010100000010010111110101
  ascii code:  30, frequency: 0.0000000, huffman code: 10010000111001010000001001011111100010
  ascii code:  31, frequency: 0.0000000, huffman code: 100100001110011
  ascii code:  32, frequency: 0.1618833, huffman code: 101
  ascii code:  33, frequency: 0.0000000, huffman code: 1001000011100100
  ascii code:  34, frequency: 0.0019349, huffman code: 110110100
  ascii code:  35, frequency: 0.0000000, huffman code: 10010000111001011
  ascii code:  36, frequency: 0.0000000, huffman code: 10010000111000101001
  ascii code:  37, frequency: 0.0000000, huffman code: 1001000011100000000
  ascii code:  38, frequency: 0.0000000, huffman code: 10010000111000000101
  ascii code:  39, frequency: 0.0022573, huffman code: 100100000
  ascii code:  40, frequency: 0.0006450, huffman code: 10011110110
  ascii code:  41, frequency: 0.0006450, huffman code: 10010000110
  ascii code:  42, frequency: 0.0000000, huffman code: 10010000111000000011011
  ascii code:  43, frequency: 0.0000000, huffman code: 1001000011100000001110001
  ascii code:  44, frequency: 0.0103193, huffman code: 1001110
  ascii code:  45, frequency: 0.0012899, huffman code: 011100110
  ascii code:  46, frequency: 0.0109642, huffman code: 1000101
  ascii code:  47, frequency: 0.0000000, huffman code: 1001000011100101000000100101010
  ascii code:  48, frequency: 0.0048371, huffman code: 10010001
  ascii code:  49, frequency: 0.0048371, huffman code: 10010011
  ascii code:  50, frequency: 0.0016124, huffman code: 011100100
  ascii code:  51, frequency: 0.0022573, huffman code: 100100101
  ascii code:  52, frequency: 0.0009674, huffman code: 1101101010
  ascii code:  53, frequency: 0.0012899, huffman code: 1001000010
  ascii code:  54, frequency: 0.0003225, huffman code: 1001000011101
  ascii code:  55, frequency: 0.0000000, huffman code: 10010000111001010000001001010000101
  ascii code:  56, frequency: 0.0000000, huffman code: 10010000111001010000001001010000100
  ascii code:  57, frequency: 0.0006450, huffman code: 11011010111
  ascii code:  58, frequency: 0.0000000, huffman code: 10010000111001010000001001011111110
  ascii code:  59, frequency: 0.0000000, huffman code: 100100001110010100000010010111111001
  ascii code:  60, frequency: 0.0000000, huffman code: 100100001110010100000010010111110100
  ascii code:  61, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101011
  ascii code:  62, frequency: 0.0000000, huffman code: 10010000111001010000001001011111100011
  ascii code:  63, frequency: 0.0012899, huffman code: 1001010011
  ascii code:  64, frequency: 0.0000000, huffman code: 10010000111000100
  ascii code:  65, frequency: 0.0006450, huffman code: 0111001111
  ascii code:  66, frequency: 0.0012899, huffman code: 1001111100
  ascii code:  67, frequency: 0.0025798, huffman code: 100111111
  ascii code:  68, frequency: 0.0000000, huffman code: 100100001110001011
  ascii code:  69, frequency: 0.0012899, huffman code: 1001111101
  ascii code:  70, frequency: 0.0006450, huffman code: 0111001110
  ascii code:  71, frequency: 0.0003225, huffman code: 11011010110
  ascii code:  72, frequency: 0.0006450, huffman code: 10011110010
  ascii code:  73, frequency: 0.0083844, huffman code: 1001011
  ascii code:  74, frequency: 0.0000000, huffman code: 10010000111000101000
  ascii code:  75, frequency: 0.0000000, huffman code: 1001000011100000011
  ascii code:  76, frequency: 0.0074170, huffman code: 1101100
  ascii code:  77, frequency: 0.0016124, huffman code: 011100101
  ascii code:  78, frequency: 0.0000000, huffman code: 1001000011100101001
  ascii code:  79, frequency: 0.0000000, huffman code: 100100001110010100001
  ascii code:  80, frequency: 0.0003225, huffman code: 100100001111
  ascii code:  81, frequency: 0.0000000, huffman code: 1001000011100000001100
  ascii code:  82, frequency: 0.0009674, huffman code: 1001010010
  ascii code:  83, frequency: 0.0006450, huffman code: 10011110111
  ascii code:  84, frequency: 0.0022573, huffman code: 100101000
  ascii code:  85, frequency: 0.0000000, huffman code: 1001000011100101000001
  ascii code:  86, frequency: 0.0006450, huffman code: 10011110011
  ascii code:  87, frequency: 0.0012899, huffman code: 1001111000
  ascii code:  88, frequency: 0.0000000, huffman code: 100100001110000000111001
  ascii code:  89, frequency: 0.0000000, huffman code: 100100001110010100000000
  ascii code:  90, frequency: 0.0000000, huffman code: 100100001110010100000011
  ascii code:  91, frequency: 0.0000000, huffman code: 1001000011100101000000011
  ascii code:  92, frequency: 0.0000000, huffman code: 1001000011100101000000101
  ascii code:  93, frequency: 0.0000000, huffman code: 10010000111000000011100000
  ascii code:  94, frequency: 0.0000000, huffman code: 1001000011100101000000010
  ascii code:  95, frequency: 0.0000000, huffman code: 100100001110010100000010010110
  ascii code:  96, frequency: 0.0000000, huffman code: 1001000011100101000000100101011
  ascii code:  97, frequency: 0.0512738, huffman code: 10000
  ascii code:  98, frequency: 0.0116092, huffman code: 1000100
  ascii code:  99, frequency: 0.0219284, huffman code: 100011
  ascii code: 100, frequency: 0.0280555, huffman code: 11010
  ascii code: 101, frequency: 0.0980329, huffman code: 000
  ascii code: 102, frequency: 0.0158014, huffman code: 111001
  ascii code: 103, frequency: 0.0141890, huffman code: 110111
  ascii code: 104, frequency: 0.0270880, huffman code: 01100
  ascii code: 105, frequency: 0.0528862, huffman code: 0011
  ascii code: 106, frequency: 0.0012899, huffman code: 1001111010
  ascii code: 107, frequency: 0.0077394, huffman code: 1110000
  ascii code: 108, frequency: 0.0270880, huffman code: 01101
  ascii code: 109, frequency: 0.0309578, huffman code: 11101
  ascii code: 110, frequency: 0.0519187, huffman code: 0010
  ascii code: 111, frequency: 0.0635279, huffman code: 1111
  ascii code: 112, frequency: 0.0196711, huffman code: 100110
  ascii code: 113, frequency: 0.0000000, huffman code: 1001000011100101000000100101111100
  ascii code: 114, frequency: 0.0541761, huffman code: 0100
  ascii code: 115, frequency: 0.0567559, huffman code: 0101
  ascii code: 116, frequency: 0.0619155, huffman code: 1100
  ascii code: 117, frequency: 0.0267656, huffman code: 01111
  ascii code: 118, frequency: 0.0070945, huffman code: 0111000
  ascii code: 119, frequency: 0.0077394, huffman code: 1110001
  ascii code: 120, frequency: 0.0022573, huffman code: 100100100
  ascii code: 121, frequency: 0.0135440, huffman code: 011101
  ascii code: 122, frequency: 0.0000000, huffman code: 1001000011100101000000100101111110110
  ascii code: 123, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101010
  ascii code: 124, frequency: 0.0000000, huffman code: 1001000011100101000000100101111110000
  ascii code: 125, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101110
  ascii code: 126, frequency: 0.0000000, huffman code: 10010000111001010000001001011111101111
  ascii code: 127, frequency: 0.0000000, huffman code: 1001000011100011
  

  binary.txt（为防止页面炸掉，已转换为十六进制表示，末尾不足补零）

  9E 19 0C A6 B7 67 A0 ED 97 32 BF B2 9E DC AE CF 
  41 DB 2E 65 7F 69 AD 53 EC CD 76 E9 FD EB B7 04 
  93 2F F3 71 82 CC 86 58 65 BD 81 6A E3 B3 05 19 
  86 5B D3 2D 3D 71 1D 8B 76 7A 0E D9 73 2B FB 59 
  05 B1 00 2B 8C 14 CB 4F 5C 47 64 0B 57 20 5A 82 
  6A E9 FD EB B7 04 93 28 70 12 A9 94 62 E3 05 93 
  90 A4 64 56 75 E2 C0 56 05 5E 5C 0B F8 95 99 0C 
  B0 25 CF FE 16 17 78 35 A1 DB FC DC 76 61 60 5A 
  AB 1A 43 B1 1A 35 4F 2E 7D EC 38 0B 0B 8E CC 2A 
  CC 23 3E 82 B1 3F F8 45 B2 F2 B2 0B 55 E8 E0 DC 
  0D 52 FC BE 4D 76 F2 6E 05 8C 16 3D 0C 2C EB 11 
  F9 60 D5 FB 8C 15 A2 13 53 2C FA 1A 23 C4 F2 38 
  EE 3B 30 51 98 65 BC EA 83 B0 32 32 DE 85 50 58 
  70 6B 5D AF 28 D9 02 DC 6A 2D 97 97 8C 16 CD F3 
  3D B0 43 51 AA 65 71 82 C9 ED 79 0E C8 AD E2 78 
  CB 8C 15 03 44 14 5F E6 EC 18 90 51 95 58 06 2D 
  8F CB 20 64 65 BD D9 E8 3B 65 CC AF ED 9A 0A B0 
  DC 2C EB 02 D5 EF A0 A8 23 05 8D 76 F1 3C 65 D0 
  5E 19 F3 59 9F 11 A6 AC 32 DE AF F3 9C 60 82 B4 
  F8 0A E7 B7 4F 5B 21 F0 DC 39 61 C0 25 32 8D AF 
  D1 96 F5 C0 45 3F 25 BF CD D9 E8 3B 65 CC AF EC 
  5D B9 5D B9 59 E1 81 05 D7 85 A7 96 3F E8 BC A7 
  F6 53 DB 95 9F F9 62 41 1D B9 F6 6F 99 ED 82 58 
  81 A6 39 9D 76 7A 0E D9 73 2B FB 4D 69 7E 55 3E 
  CC D7 6A 40 B5 FD B8 24 99 16 CB CA C8 2D 4F FC 
  5A 65 61 66 31 18 BF CD 8D B0 55 38 E0 DB B2 18 
  65 5A 78 12 18 F4 17 94 FE DD AA 42 B3 E4 FE 75 
  EC 38 19 6F 4F 2F B8 09 5C 92 32 32 35 D1 04 5B 
  ED D4 5B 29 1C 6C 82 6A B9 63 9F B4 CB 3E 3E 13 
  AC 2E C8 61 95 99 3F 90 AB E9 61 96 79 43 B3 68 
  13 9A 7B BB A2 0E D9 FF B5 A3 71 4C AC F3 34 DC 
  C8 E1 3A B7 FF 80 D5 7C D7 C8 5F E6 E3 05 EF A0 
  BF 11 63 7A 0B B2 18 65 78 FA 69 67 58 FC 94 47 
  83 1E 93 AF 29 FD B0 BB 3D 07 6C B9 95 FD B3 41 
  56 1B 89 D6 05 AB BF 99 6F 71 89 EF DD 97 18 2C 
  67 81 6F F3 71 82 F1 F4 D5 32 B1 B6 0A A7 1C 1B 
  5A 78 12 18 F4 13 AE 8D 63 F7 01 06 AE 30 57 96 
  BD F1 32 11 1A 2A FB D2 31 16 EC F4 1D B2 E6 57 
  F6 C7 FD 0B 79 4F ED 51 1E 1F 92 D9 38 B2 72 31 
  64 AE 4B 02 D5 93 8B 27 23 16 4B 25 BF CD DA 68 
  57 38 C8 E2 3D 6C F9 E5 E8 FE D1 95 CB 06 FA 3F 
  BB 4B 3D A5 0C 16 7D 92 62 0E 85 BF CD DA DF FA 
  B0 2D 59 F5 C1 B6 43 58 8E D9 F9 C6 13 E7 5E 28 
  79 80 A9 95 DA A4 2B 3E 4F E2 D9 43 0D 6C 4F FE 
  14 D6 C2 E2 08 61 A8 BE 57 18 2E 30 7A 3B 7F 9A 
  31 87 1A CE AE 02 3B 66 F9 9E D8 25 D3 D0 CB 7B 
  8C 16 52 05 03 55 81 46 22 D9 43 05 E4 D1 72 B4 
  C8 5F E6 EC F4 1D B2 E6 57 F6 75 DA 6C F4 1D A7 
  32 BF B7 5E DF 4A A7 96 1D 19 16 2E D2 75 8F FA 
  16 F2 9F DB 0A D3 21 4C AA 88 F0 FC AC 9C 59 39 
  18 B2 57 24 5D B9 59 43 05 5C 81 6A 09 AB 1B 1E 
  5C 2F F3 76 7A 0E D9 73 2B FB 5E A3 55 4C A3 17 
  18 2C 9C 85 23 22 B4 D6 A0 99 3F 4F 8C 6A C4 0D 
  FE 37 9F 4B 8C F5 14 CB 02 05 C1 A8 B6 7B 88 F0 
  FC 96 C9 C5 93 91 8B 25 72 58 16 AC 9C 59 39 18 
  B2 59 2D E5 3F B7 69 A1 5C E3 23 88 F5 B3 E7 97 
  A3 FB 46 57 2C 1B E8 FE ED 2C 47 6C FC E3 09 F6 
  08 2C 1A BF 50 4C 9F A7 C6 35 4C AE 30 1A 51 24 
  84 79 7D 0F 73 28 36 F3 E9 D9 D6 11 C7 FD 9A 04 
  63 56 23 B6 7D 2D DA 6A CA E0 22 9F 92 DE 53 FB 
  71 82 C9 ED 79 3D AA E2 40 95 B0 C3 F2 B1 1D B3 
  CA 2D 94 A1 1F 06 43 B1 76 E5 76 E5 67 86 3B 75 
  F7 88 AF 51 4F 25 3D B9 59 79 4D 6C 2B 7C B7 A1 
  72 11 1A 6A C1 AB CC 23 CB 8C 86 58 54 10 D0 4B 
  C4 DA DB 10 5D 1A E2 42 3C 1A B1 1D B8 C1 50 43 
  50 88 D1 63 F2 C0 59 7F 9B 0B 34 37 17 8B 01 56 
  FF F0 32 DE C3 29 E2 D6 C1 DF 7E 45 B2 86 0B 37 
  99 65 FE 6B D4 CB 7B B3 D0 76 CB 99 5F DA 6B 71 
  90 CA 79 59 05 B0 BD F4 0E 6F 47 33 42 AD 2F 4E 
  C1 B7 46 B8 87 11 F8 7E 57 F9 AD 19 81 16 75 82 
  DF 9A 6F 51 AB 9F 5E A6 5B D9 04 FF CB 01 65 60 
  41 3A C7 E5 80 B2 B0 20 90 4E BD 87 03 2D E9 E5 
  6F FF 0A D3 E0 2A 08 6A 11 1A 2C FA 5B B4 D5 91 
  6B 96 04 ED D0 5E 19 F3 59 9F 11 A6 AC 32 DE CD 
  08 F8 43 70 B6 05 AB C4 44 B3 43 71 46 8F 3D 16 
  97 F1 AF 51 76 7A 0E D9 73 2B FB 60 B7 18 0D 2E 
  87 30 7B 72 F7 F4 1B 70 49 32 75 81 6A C2 A8 82 
  46 CB CF A5 90 37 D0 76 9C CA FE C8 2F 13 6B 6B 
  CA 3F 70 12 F6 04 ED E2 22 55 3C 0B 57 0D AD A6 
  57 18 0D 29 97 30 28 DD 8B 67 9C 10 FD EB 5C 04 
  53 F2 5A C8 38 14 38 F6 B8 1A BE E0 25 C6 0A E8 
  82 2C EA BF D1 87 D0 B6 23 B6 11 C6 7A 05 93 AA 
  FF 46 1F 42 DF 2B 33 D2 6F 51 67 B1 94 F4 23 C1 
  AA C7 F7 DE 96 05 AB 8C 15 A7 C0 48 68 BB 72 BB 
  72 B3 C3 02 0B 1C 0A CB BB 8C AB FD 12 9E DC AC 
  A1 81 05 82 0B D8 13 B5 C4 10 E1 87 E4 B7 F9 B3 
  41 56 1B 85 BF CD D9 E8 3B 65 CC AF ED 83 88 1B 
  61 11 A2 75 88 FC B8 C1 7B 09 EB D0 F1 DA C8 38 
  15 5F CF 21 06 AC 1B 81 21 87 E5 4C AA FF 45 E7 
  D3 B3 AC 47 69 94 F4 23 C1 AA C7 F7 DE 93 AF A5 
  48 16 BF A6 A3 57 8F A6 96 F1 61 C6 CB AF 29 06 
  56 FF F0 A1 C0 2A AD 3D D9 8D 76 C4 0D 30 E2 11 
  1A 22 D9 7C D7 7D F6 08 2E FE 65 BD CF AF 51 61 
  66 82 AC 37 17 F9 BB 3D 07 6C B9 95 FD 9D 5D F7 
  D2 03 57 3E C4 15 5E 82 E3 02 0A 6A 52 0C B0 27 
  71 86 5B D1 D8 90 44 82 A9 96 F5 87 AD 02 A6 57 
  18 2F 4F 5A 68 BF CD C1 24 C8 B5 CF 6B 6E 30 5D 
  9E 83 B6 5C CA FE DD C1 04 86 7A 2D F2 B8 C1 65 
  96 04 21 97 01 6A E7 D4 13 08 65 99 06 87 26 43 
  56 36 3C B8 2D 82 D2 11 85 58 23 B3 AF 61 C0 CB 
  7B 8C 35 B8 C1 79 34 5C B8 8F 17 70 41 21 9E 97 
  CA E3 05 96 58 10 86 45 B2 F2 BD 42 D8 5D 1C 78 
  7E 50 47 6F F3 7D C0 4A E4 91 91 BB 21 86 57 8F 
  A6 96 75 8F FB 10 C8 6A F1 3C 65 85 64 0B 5C BD 
  B7 F9 BD FD 06 D5 05 80 A3 15 71 1F 1E 3D 02 CE 
  B9 F7 70 41 21 82 EC F4 1D B2 E6 57 F6 F1 61 C6 
  CA DF FE 0B 50 41 7C A1 11 A2 2D 94 30 5D C1 04 
  86 0D 5D 9E 83 B6 5C CA FE D3 5B 8C 08 39 F4 16 
  0D E3 07 56 F2 80 5E 53 FB 50 4C 30 F0 FC A7 53 
  29 E8 47 83 55 8F EF BD 27 5F 4A 5E 4E 68 D9 04 
  84 78 10 D7 0E 3B C7 D3 4B 46 47 17 6E 54  

  decode-result.txt

  What is Lorem Ipsum?
  Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book. It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged. It was popularised in the 1960s with the release of Letraset sheets containing Lorem Ipsum passages, and more recently with desktop publishing software like Aldus PageMaker including versions of Lorem Ipsum.
  
  Where does it come from?
  Contrary to popular belief, Lorem Ipsum is not simply random text. It has roots in a piece of classical Latin literature from 45 BC, making it over 2000 years old. Richard McClintock, a Latin professor at Hampden-Sydney College in Virginia, looked up one of the more obscure Latin words, consectetur, from a Lorem Ipsum passage, and going through the cites of the word in classical literature, discovered the undoubtable source. Lorem Ipsum comes from sections 1.10.32 and 1.10.33 of "de Finibus Bonorum et Malorum" (The Extremes of Good and Evil) by Cicero, written in 45 BC. This book is a treatise on the theory of ethics, very popular during the Renaissance. The first line of Lorem Ipsum, "Lorem ipsum dolor sit amet..", comes from a line in section 1.10.32.
  The standard chunk of Lorem Ipsum used since the 1500s is reproduced below for those interested. Sections 1.10.32 and 1.10.33 from "de Finibus Bonorum et Malorum" by Cicero are also reproduced in their exact original form, accompanied by English versions from the 1914 translation by H. Rackham.
  
  Why do we use it?
  It is a long established fact that a reader will be distracted by the readable content of a page when looking at its layout. The point of using Lorem Ipsum is that it has a more-or-less normal distribution of letters, as opposed to using 'Content here, content here', making it look like readable English. Many desktop publishing packages and web page editors now use Lorem Ipsum as their default model text, and a search for 'lorem ipsum' will uncover many web sites still in their infancy. Various versions have evolved over the years, sometimes by accident, sometimes on purpose (injected humour and the like).
  
  Where can I get some?
  There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don't look even slightly believable. If you are going to use a passage of Lorem Ipsum, you need to be sure there isn't anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary, making this the first true generator on the Internet. It uses a dictionary of over 200 Latin words, combined with a handful of model sentence structures, to generate Lorem Ipsum which looks reasonable. The generated Lorem Ipsum is therefore always free from repetition, injected humour, or non-characteristic words etc.
  

图及算法

农夫过河

农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小、除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷菜吃，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和自己过河。

• 输入格式

  无

• 输出格式

  若干行，表示每次农夫从哪将运输或不运输什么东西，形如以下描述都是合法的。

  • 农夫运输羊到对岸
  • 农夫从对岸运输狼回来
  • 农夫到对岸，不运输任何东西

• 样例输入

  #N/A

• 样例输出

  #无可奉告

实验三

图的遍历

给出一个图，指定开始节点，求其任意DFS序（深度优先搜索序）、BFS序（广度优先搜索序）。

• 输入格式

第一行两个整数 n，m，s，表示点数、边数和开始节点。

接下来 m 行，每行两个整数 u，v，表示从 u 至 v 有一条边。

输入保证开始节点能够到达所有节点。

• 输出格式

第一行 n 个整数，表示图的任意DFS序。

第二行 m 个整数，表示图的任意BFS序。

• 样例输入

  8 14 6
  6 2
  6 4
  6 5
  1 4
  1 5
  2 3
  2 4
  4 5
  7 1
  5 7
  7 3
  8 5
  6 8
  1 3

• 样例输出

  6 8 5 7 1 3 4 2
  6 8 5 4 2 7 3 1

• 样例解释

  如图：

  

  显然可得从 6 开始的 DFS 序和 BFS 序。

工程安排

一项工程由多道工序组成，按照施工过程的要求，这些工序之间，客观上有一个必须遵守的先后关系。对那些紧接在已知工序前的工序叫紧前工序，把已知工序后边紧接的工序叫后项工序，只有已知工序的所有紧前工序都完成，已知工序才能开始施工。例如某项工程的工序表如下：

给出若干工序及其先后关系、完成所需时间，求完成所有工序所需最短时间。

• 输入格式

  第一行两个整数 n，m，表示工艺数，关系数。

  第二行 n 个整数，第 i 个整数表示第 i 号工序所需时间。

  接下来 m 行，每行两个整数 u，v，表示 u 是 v 的紧前工序。

• 输出格式

  第一行若干个整数，表示最长关键路径。

  第二行一个整数，表示完成所有工序所需的最少时间。

• 样例输入

  10 11
  6 2 3 5 3 2 3 4 2 2
  1 3
  1 4 
  1 5
  2 8
  3 6
  4 7
  5 8
  8 9
  6 10
  7 10
  9 10

• 样例输出

  1 5 8 9 10
  17

• 样例解释

  如图：

  

  工艺线路 1 -> 5 -> 8 -> 9 -> 10 所耗费的时间最长，为 6 + 3 + 4 + 2 + 2 = 17 。

查找

二分查找

给出一个有序整数序列，每次询问一个数，求这个数在序列中的索引范围 [a, b) （上界和下界）。

为了使问题一般化，我们对上下界做出如下定义：

对于一个序列（数组） a 和一个数 v ：

• 下界：最小的 i ，使得 a[i] >= v 。
• 上界：最小的 i ，使得 a[i] > v 。

注；作为练习，请使用二分查找，保证每次询问在O(log(n))时间复杂度内处理完成，否则会超时。

• 输入格式

第一行两个整数 n，m，表示序列长度和询问个数（n <= 1e5，m <= 1e5）。

第二行 n 个整数，表示这个序列。

接下来 m 行，每行一个整数，表示询问其上下界。

序列索引范围 [1, ..., n]

• 输出格式

m 行，每行两个整数 a，b，表示每个询问的结果，即输出其上下界，表示区间 [a, b) 内有此数。

• 样例输入

  10 5
  1 2 2 2 4 5 5 7 9 10
  2
  7
  5
  4
  8

• 样例输出

  2 5
  8 9
  6 8
  5 6
  9 9

• 样例解释

二叉搜索树

跳表、AVL树与红黑树

阅读跳表、AVL树与红黑树相关原理介绍，完成以下任务：

• 理解跳表、AVL树与红黑树原理。
• 实现跳表、AVL树或红黑树之一【选做】