算法导论答题笔记_0x0

第1章 练习与思考题

练习1.1

1.1-1（开放问题）
原题：
给出生活中一个需要排序的例子或者现实生活中需要计算凸壳的一个例子。
回答：
考试成绩需要排序得到排名；
计算光线反射的时候需要计算凸壳。

1.1-2（开放问题）
原题：
除速度外，在真实环境中还可能使用哪些其他有关效率的量度？
回答：
个人见解有功率，汽车的百公里加速时间。还有计算机的空间消耗，资源占用。

1.1-3（开放问题）
原题：
选择一种你以前已知的数据结构，并讨论其优势和局限。
回答：
链表。链表的优势可以概括为“动态”二字，包括长度（大小）随意扩增，数据的增加、删除、插入十分方便。
缺点是查找比较麻烦，不支持随机存取。

1.1-4（开放问题）
原题：
前面给出的最短路径与旅行商问题有哪些相似之处？又有哪些不同？
回答：
最短路径求两点间最短路。旅行商问题是遍历所有点，并回到起点的最短路。
两者共同点是都是最优化问题，求最短路。
不同是旅行商问题要求遍历所有点，整个路径是一个经过所有点的回路。
注意旅行商问题的起点终点并不重要，环上任意一点都可以作为起、终点。

ps：完整问答会稍后整理并在gayhub上更新。