计科计算机18算法设计与分析A卷 

扬州大学试题纸

(2019－2020学年第2学期)

____________信息工程学院（人工智能学院）

计科18，计算机18班（年）级题目得分阅卷人

…………………………………课程算法设计与分析(A)卷四

五

六

总分

名一二三

__________________姓注意：学生无需上传本试题纸，须在答题纸上答题，在试题纸上答题无效。

得分

一、请用渐进符号定义证明5????4??????2但??2??Θ??5????4??。（10分）得分

二、试给出递归方程??????3??得分

??4号___________________学_______________班…………………………….级…………………………..线??????的解，并证明之。（10分）

三、数组A[1…n]存放了n个不同的整数。已知存在p，1

得分

四、有一公司需购买n个软件的许可证，但根据法规，每个月只能获得一种许可证。每份许可证售价100元，但价格随时间推移而指数增长。第j种许可证在k个月后够买时的价

………………………………………………….??

（15装格是100?????。请问该公司以什么顺序购买这n个许可证花费最小，并证明你的结论。

________________系分）

得分

五、设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出

一种分法，使得这K+1个部分的乘积能够为最大。（例如：有一个数字串：312，当N=3，K=1时会有以下两种分法：3×12=36、31×2=62，这时，符合题目要求的结果是：31×2=62。）

(1)证明该问题满足最优子结构性质。（6分）(2)写出动态规划求解该问题的递归式。（5分）

(3)计算数字串为12345，K=2的解，写出详细的计算过程。（10分）(4)分析算法的复杂度。（4分）

院学第1页

得分

六、对下列有向无环图从顶点??1开始执行深度优先搜索，在搜索过程中当顶点有多个未访问邻居时优先访问编号小的顶点。

（1）给出DFS算法的详细步骤；（14分）（2）分析DFS算法的时间复杂性；（7分）（3）给出图中顶点深度优先搜索顺序。（4分）

2页

第