算法设计与分析章节练习(2020.02.09)

问答题
设计算法，在数组r[n]中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。
答案：
问答题
一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，0=d1n≤s，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。
答案：贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加...
问答题
请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。
答案：
问答题
数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径。算法如下，空白处应填？
答案：
1.c<=r
2.t[r][c]+=t[r+1][c]
3.t[r][c]+=t[r+1][c+1]
判断题
好的算法在很大程度上取决于问题中数据所采用的数据结构。
答案：错误
问答题
证明等式gcd（m，n）=gcd（n，m mod n）对每一对正整数m，n都成立.
答案：
问答题
用回溯法解布线问题时，求最优解的主要程序段如下：如果布线区域划分为n×m的方格阵列，扩展每个结点需O（1）的时间，L为最短布线路径的长度，则算法共耗时（O（mn）），构造相应的最短距离需要（O（L））时间。
答案：
单项选择题
回溯法搜索状态空间树是按照（）的顺序。
A.中序遍历
B.广度优先遍历
C.深度优先遍历
D.层次优先遍历
问答题
分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。
答案：
多项选择题
以下字符串中，是回文字符串的是（）。
A.abcba
B.12321
C.1221
D.abcdef