山东大学网安学院2022-2023学年【算法分析与设计】期末考试

• 算法结构

由于很快就要有软件安全考试，所以先写个草稿放这里，等我想起来了再来填坑。

据说有的题是课后题的原题，大家可以量力刷一下

老师说都是送分题，然而考试中崩溃的我并不这么认为。。。。

一、选择题（2*5）

1、求渐进复杂度问题，选出不对的

比如：f(n)=n^2/log n g(n)=n(log)2

f

(

n

)

=

Ω

(

g

(

n

)

)

f(n)=\Omega(g(n))

f(n)=Ω(g(n))

2、快排最优时间复杂度（），平均复杂度（）

3、Floyd-Warshall运用了什么思想（）

4、描述了个分而治之算法求最大最小值，让选时间复杂度的递归方程

5、回溯算法

二、简答题（15*2）

2.1 三个算法，大概就算不同数量不同子问题大小，让求T(n)，然后对三个算法复杂度排序

2.2

1 写出P、NP、NPC的定义

2 根据定义证明 P ⊆ N P P\subseteq NP P⊆NP

三、

1、主元素，只能进行A[i]=A[j]的比较，请写一个算法判断是否有主元素

2、如果有n个人需要处理业务,他们需要的处理时间是 ti​，只有一个银行柜员,请你设计一个算法,使得有限时间T内处理业务数量得到最大

3、n*m的0、1矩阵，找到最大的全1方阵

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/8e65b53b17.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐