部分习题与思考的答案与提示

《部分习题与思考的答案与提示》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、部分习题与思考的答案与提示第二章习题与思考1.编程调用栈操作函数压入1000000个随机整数，再全部弹出来，打印花费的总时间。提示：可以使用clock()函数获取当前时间，在压入数据前调用一次clock()，压入完数据后再调用一次clock()，两次时间差便是实际花费的总时间。2.编程将100万个随机整数插入到SortTable中，再调用快速排序函数排序，打印出排序花费的时间。提示：参考第1题的提示。3.编程将1～1000000的整数一次插入排序表里，调用二分查找函数将1～10000000这100万个数依次

2、查找一遍，打印出花费的时间。提示：参考第1题的提示。4.编码实现动态环形队列DeQue的弹出尾部节点函数DeQue_PopTail()和插入头部函数DeQue_InsertHead()函数。提示：参考DeQue_PopHead()和DeQue_InsertTail()的实现。第三章习题与思考1．在整块内存链表的实现中，考虑一下如果当自由空间的节点用完时，再插入数据，申请一块大一倍的内存，将原来内存中数据直接拷贝过去，将多出的一半自由空间加入到自由空间链表中，此时再插入数据，试问这种实现方式存在什么问题？提示

3、：申请大一倍的内存后，内存的起始地址和原来内存的起始地址不一样，导致拷贝完后，链表的链接指向的还是原来那块内存中的内容。2．编码实现一个整块内存中的链表插入算法，要求实现任意个数节点的插入。提示：参考第1题。第四章习题与思考1．编码将100万个随机整数插入到哈希表中，再将这100万个整数全部查找一遍，看需要花费多长时间？提示：可以使用rand()函数来生成随机数，调用rand()函数前需要先调用srand()函数初始化随机数发生器。第五章习题思考：1．证明AVL树中从根节点到任一树梢节点的路径上不存在连续三

4、个树梢节点。证明：使用反证法，假设存在三个连续的树梢节点，那么这三个连续树梢节点最上面的那个节点的左右子树高度差将大于等于2，与AVL树的条件矛盾。2．证明红黑树中从根节点到任一树梢节点的路径上不存在连续三个树梢节点。证明：使用反证法，假设存在连续三个树梢节点，那么由红黑树的条件知道从根节点到任一树梢节点路径中的黑色节点数量相等，而从根节点到第2个树梢节点的路径必然要经过第1个树梢节点，根节点到第3个树梢节点的路径必然经过第2个树梢节点，因此知道三个树梢节点的第2个和第3个节点必为红色，但这又与红黑树中没有

5、连续两个红色节点的条件矛盾，因此得证。3．使用非递归算法编码实现二叉树的前序遍历函数。答案：见光盘源代码4．编码实现二叉树的宽度遍历函数。提示：参考树的宽度遍历算法5．使用红黑树替代哈希表去实现前面讲过的WebServerCache文件管理功能。6．比较一下哈希表、AVL树、红黑树在各种操作效率方面的区别。7．估算一下对一个5000单词的文件进行分词大约需要多少次词典查询？假设平均每句有10个单词，那么有500句，每句大约耗费10×9/2=45次词典查询，因此总共需要大约500×45＝22500次词典查询。

6、8．一个企业想建一个内部搜索引擎，假设总共有十万个关键词，十万个网页文件，估算一下搜索关键词词典大约要占多少内存空间?答：假设平均每个网页有500个不重复的单词，那么在关键词词典中，每个网页出现的平均次数为500次；所有网页在关键词词典中出现总次数为：500×10万次。每个关键词所对应的网页文件平均个数为：500×10万/10万＝500个。如果给网页文件名编号的话，编号需要消耗4字节，那么一个关键词对应的网页文件列表就需要消耗：4字节×500＝2000字节。10万个关键词的词典总共需要消耗：10万×2000

7、字节＝200M字节。假设每个网页文件名需要消耗32字节空间，那么网页文件名和编号表消耗的空间为：10万×（32＋4）＝3.6M字节总共需要消耗203.6M字节的空间9．考虑一下如何在搜索引擎的关键词词典中搜索包含某个关键词但不包含另外一个关键词的结果。答：先按书中5.6.3中介绍的方法求出同时包含两个关键词的交集，再将包含第1个关键词的集合中减去交集便得到了所需的结果。1．编码实现一个简易的搜索引擎功能。要求对给定目录下的网页文件输出关键词词典，对给定的关键词要求能输出包含这个关键词的所有文件。提示：搜索给

8、定目录下的网页文件可以使用操作系统提供的文件搜索函数。第六章习题与思考1．编码使用哈希AVL树去替代哈希表实现前面哈希表那章中的WebServerCACHE文件管理。2．编码调用哈希红黑树去实现一个英文词典的管理功能。3．将哈希红黑树、哈希AVL树和前面几章讲过的各种数据结构作一个插入、删除、查找、有序性、时间效率、空间效率等方面的综合比较。第七章习题与思考1．画出宽度优先搜索算法的流程图。2．编程实现无环有向图