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

问答题
如果所要搜索的模式包含一些英语中较少见的字符，我们应该如何修改该蛮力算法来利用这个信息？
答案：每次都从这些少见字符开始比较，如果匹配，则向左边和右边进行其它字符的比较.
单项选择题
数据结构与算法中，直接插入排序的稳定性和希尔排序的稳定性是（）
A.一样的
B.不一样
C.可能一样也可能不一样
D.不确定
问答题
同时找n个元素中最大与次大元素的好的算法，并说明你给出算法是好的理由。
答案：
单项选择题
下列流程图中是选择结构的是（）。
A.①③
B.①②④
C.②③④
D.②④
问答题
对于以下的矩阵乘法，计算其最小的运算次数及结合方式。M=M1×M2×M3×M4[10×20][20×10][10×30][30×50]
答案：
问答题
在一个6×6的棋盘上，共放置12颗棋子，每个格子最多只能放一个棋子，要求每一行，每一列以及两条主对角线上恰好都是两颗棋子。请用回溯法输出所有可能的布局。在不考虑对称的情况下，共有多少种布局？
答案：
问答题
考虑下面的货币兑付问题：在面值为（v1，v2，…，vn）的n种货币中，需要支付y值的货币，应如何支付才能使货币支付的张数最少，即满足，且使最小（xi是非负整数）。设计动态规划算法求解货币兑付问题，并分析时间性能和空间性能。
答案：
问答题
已知n-1个元素已按min-堆的结构形式存放在A（1），A（n-1）。现要将另一存放在A（n）的元素和A（1：n-1）中元素一起构成一个具有n个元素的min-堆。对此写一个计算时间为O（logn）的算法。
答案：
判断题
数据结构与算法里，函数的返回值必须由return语句返回。
答案：正确
单项选择题
请选下列VB程序运行时（如图所示），在文本框Text1中输入20，在文本框Text2中输入13，单击命令按钮command1后，文本框Text3中显示的内容是（）
A.”33”
B.33
C.”2013”
D.2013