算法导论1.1 Exercises 答案
1.1-1
B站上一系列的视频所需要根据播放时长、播放量等等一些参数进行排序。
百度地图等等寻找最优路径的系统。一般寻找物理路径长度最短或者是到达时间最少的路径。
1.1-2
内存空间。如果是涉及到需要通信的算法，那么还需要考虑通信量，通信开销等等。如果涉及浮点数运算，那么还要考虑精度。
1.1-3
以链表和顺序表进行对比。链表相比顺序表的优点是，删除操作和插入操作都可以达到\(O(1)\)的时间复杂度，但是链表的缺点是它不支持随机访问，必须一个个元素进行遍历。
1.1-4
最短路径问题和TSP问题的相似之处在于它们的最终目标都是求出一条最优的路径用于解决问题。不同之处在于，最短路径有明确的起点和终点，TSP问题没有；最短路径问题所求路径并非必须经过图上所有点，而TSP问题所求路径必须经过图上所有点。
1.1-5
其实这个问题似乎仅仅取决于问题的严谨程度。
以字符串匹配为例，如果是字符串的数量非常小，那么直接通过字符串本身匹配就能得到精准的结果；如果数量字符串的数量非常大，那么就考虑使用哈希值进行更高效的匹配。虽然由于哈希冲突，可能导致原本不匹配的两个字符串匹配上了，但是这个概率很微小，这种方法近似于最优的精准匹配。
1.1-6
Hangman猜词游戏：
一开始时，玩家A掌握一个单词\(s\)，并留下和单词长度对应数量的空白和下划线。
玩家B负责猜测这个单词是否含有某一个字母\(c\)，如果猜测正确，那么A将在所有对应的位置上填上字母\(c\)。否则使用一次猜测错误的机会。B最多有\(7\)次猜测错误的机会。
目标是玩家B是否能猜测出整个单词，这个问题的目的是帮助B猜出这个单词。