算法设计与分析问答题每日一练(2019.11.11)

问答题
请画出用回溯法解释皇后问题的解空间树和搜索空间树。
答案：
解空间树：

用回溯法的搜索空间树：
问答题
假设在文本“ababcabccabccacbab”中查找模式“abccac”，写出分别采用BF算法和KMP算法的串匹配过
答案：
问答题
请写出prim算法的基本思想。
答案：思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。
处理过程：首先加入最小代价的一条边到T，...
问答题
磁带最优存储问题：设有n=5个程序，要存放在长为L的磁带上。程序i存放在磁带上的读取概率为x=（0.71，0.46，0.9，0.73，0.35），长度p=（872，452，265，120，85），编写程序确定这n个程序的存储次序，使得平均读取时间最小。
答案：
问答题
Alan Turing是怎样对人类计算过程进行概括的？
答案：Turing根据这个过程构造出了一个计算模型，称之为Turing机。
这个计算模型有一条带子（带子相当于一张纸...