部分习题与思考的答案与提示
第二章 习题与思考
1. 编程调用栈操作函数压入1000000个随机整数，再全部弹出来，打印花费的总时间。
提示：可以使用clock()函数获取当前时间，在压入数据前调用一次clock()，压入完数据后再调用一次clock()，两次时间差便是实际花费的总时间。
2. 编程将100万个随机整数插入到SortTable中，再调用快速排序函数排序，打印出排序花费的时间。
提示：参考第1题的提示。
3. 编程将1～1000000的整数一次插入排序表里，调用二分查找函数将1～10000000这100万个数依次查找一遍，打印出花费的时间。
提示：参考第1题的提示。
4. 编码实现动态环形队列DeQue的弹出尾部节点函数DeQue_PopTail()和插入头部函数DeQue_InsertHead()函数。
提示：参考DeQue_PopHead()和DeQue_InsertTail()的实现。
第三章 习题与思考
1． 在整块内存链表的实现中，考虑一下如果当自由空间的节点用完时，再插入数据，申请一块大一倍的内存，将原来内存中数据直接拷贝过去，将多出的一半自由空间加入到自由空间链表中，此时再插入数据，试问这种实现方式存在什么问题？
提示：申请大一倍的内存后，内存的起始地址和原来内存的起始地址不一样，导致拷贝完后，链表的链接指向的还是原来那块内存中的内容。
2． 编码实现一个整块内存中的链表插入算法，要求实现任意个数节点的插入。
提示：参考第1题。
第四章 习题与思考
1． 编码将100万个随机整数插入到哈希表中，再将这100万个整数全部查找一遍，看需要花费多长时间？
提示：可以使用rand()函数来生成随机数，调用rand()函数前需要先调用srand()函数初始化随机数发生器。
第五章 习题思考：
1． 证明AVL树中从根节点到任一树梢节点的路径上不存在连续三个树梢节点。
证明：使用反证法，假设存在三个连续的树梢节点，那么这三个连续树梢节点最上面的那个节点的左右子树高度差将大于等于2，与AVL树的条件矛盾。
2． 证明红黑树中从根节点到任一树梢节点的路径上不存在连续三个树梢节点。
证明：使用反证法，假设存在连续三个树梢节点，那么由红黑树的条件知道从根节点到任一树梢节点路径中的黑色节点数量相等，而从根节点到第2个树梢节点的路径必然要经过第1个树梢节点，根节点到第3个树梢节点的路径必然经过第2个树梢节点，因此知道三个树梢节点的第2个和第3个节点必为红色，但这又与红黑树中没有连续两个红色节点的条件矛盾，因此得证。
3． 使用非递归算法编码实现二叉树的前序遍历函数。
答案：见光盘源代码
4． 编码实现二叉树的宽度遍历函数。
提示：参考树的宽度遍历算法
5． 使用红黑树替代哈希表去实现前面讲过的WebServer Cache文件管理功能。
6． 比较一下哈希表、AVL树、红黑树在各种操作效率方面的区别。
7． 估算一下对一个5000单词的文件进行分词大约需 要多少次词典查询？
假设平均每句有10个单词，那么有500句，每句大约耗费10×9/2=45次词典查询，因此总共需要大约500×45＝22500次词典查询。
8． 一个企业想建一个内部搜索引擎，假设总共有十万个关键词，十万个网页文件，估算一下搜索关键词词典大约要占多少内存空间?
答：假设平均每个网页有500个不重复的单词，那么在关键词词典中，每个网页出现的平均次数为500次；
所有网页在关键词词典中出现总次数为：500×10万次。
每个关键词所对应的网页文件平均个数为：500×10万/10万＝500个。
如果给网页文件名编号的话，编号需要消耗4字节，那么一个关键词对应的网页文件列表就需要消耗：4字节×500＝2000字节。
10万个关键词的词典总共需要消耗：10万×2000字节＝200M字节。
假设每个网页文件名需要消耗32字节空间，那么
网页文件名和编号表消耗的空间为：10万×（32＋4）＝3.6M字节
总共需要消耗203.6M字节的空间
9． 考虑一下如何在搜索引擎的关键词词典中搜索包含某个关键词但不包含另外一个关键词的结果。
答：先按书中5.6.3中介绍的方法求出同时包含两个关键词的交集，再将包含第1个关键词的集合中减去交集便得到了所需的结果。
10． 编码实现一个简易的搜索引擎功能。要求对给定目录下的网页文件输出关键词词典，对给定的关键词要求能输出包含这个关键词的所有文件。
提示：搜索给定目录下的网页文件可以使用操作系统提供的文件搜索函数。
第六章 习题与思考
1． 编码使用哈希AVL树去替代哈希表实现前面哈希表那章中的WebServer CACHE文件管理。
2． 编码调用哈希红黑树去实现一个英文词典的管理功能。
3． 将哈希红黑树、哈希AVL树和前面几章讲过的各种数据结构作一个插入、删除、查找、有序性、时间效率、空间效率等方面的综合比较。
第七章 习题与思考
1． 画出宽度优先搜索算法的流程图。
2． 编程实现无环有向图的分层算法。
3． 编程实现哈密顿圈算法。
第八章 习题与思考
1． 实现多个任务可以同时遍历操作的多任务链表。
2． 将前面第4章中的WebServer CACHE文件管理改写成支持多任务的。
3． 编码：创建多个任务，一些任务不停地向消息队列中发送数据，一些任务不停地从消息队列接收数据，然后还有一个任务不停地遍历消息队列里的数据。
4． 将本章的消息队列代码改写成当队列满时，发送操作会阻塞在那里。
提示：增加一个计数信号量，当计数为0时表示消息队列满，在发送操作中要先判断计数是否为0，为0则需要等待；在接收操作中则需要将计数加1。
5． 编码实现一个支持多任务操作的哈希AVL树。
第九章 习题与思考：
1． 将9.3.2节中的Efree(void *p, size_t size) 函数的第2个参数去掉的话，如何修改代码来实现它。
提示：需要在内存的头部或尾部保存内存的size信息。
2．如何将本章讲的内存泄漏检查和内存越界检查结合起来一起使用？
提示：在内存泄漏检查的基础上对分配的内存尾部多分配4字节存放内存校验字节，在进行内存泄漏检查时顺便检查一下内存校验字节是否遭到破坏。
3．如果原来已经写好了一个软件，如何在不修改原来代码的基础上将其中的内存管理算法替换成本章所讲的动态等尺寸内存分配算法？
提示：可以使用本书第2章讲过的HOOK方法。
本文来源：https://www.2haoxitong.net/k/doc/e82bbdef0975f46527d3e1c7.html
文档为doc格式