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

单项选择题
小明用10元钱正好买了20分和50分的邮票共35张，求这两种邮票名买了多少张？（）
A.20分的邮票25张，50分的邮票10张
B.20分的邮票30张，50分的邮票5张
C.20分的邮票28张，50分的邮票7张
D.20分的邮票10张，50分的邮票25张
单项选择题
数据结构与算法里，一趟（）最后要返回中轴所在的位置，然后将小的移动到它的左边，将大的移动到它的右边。
A.快速排序
B.直接插入排序
C.冒泡排序
D.都不对
问答题
对于标识符集（a1，a2，a3，a4）=（end，goto，print，stop），已知已知P（1：4）=（1，4，2，1）和Q（0：4）=（4，2，4，1，1）。使用动态规划方法构造一棵最佳二叉排序树（计算出C、W、R阵的结果）。
答案：
判断题
数据结构与算法里，直接插入排序必须需要使用return语句才能实现。
答案：错误
判断题
continue是可以用于switch语句中
答案：错误
问答题
什么是多项式时间近似方案（PTAS）？什么是完全多项式时间近似方案（FPTAS，FPAS）？
答案：多项式时间近似方案（PTAS，Polynomial Time Approximation ...
多项选择题
数据结构与算法中，排序可以分为四大类，主要包含有（）。
A.插入排序
B.交换排序
C.选择排序
D.归并排序
问答题
分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。
答案：（1）贪心算法O（nlog（n））
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多...
单项选择题
在Windows中，可以提供WWW服务的软件是（）。
A.IIS
B.ISA
C.ISP
D.ASP
单项选择题
下面问题（）不能使用贪心法解决。
A.单源最短路径问题
B.N皇后问题
C.最小花费生成树问题
D.背包问题