，湘潭大学2024年下学期2010级。
算法设计与分析》课程考试试卷。
a卷）适用年级专业2010级网络工程。
考试方式闭卷考试时间 120 分钟。
学院专业班级。
学号姓名。一、填空题（每空1分，共15分）
1、算法是由若干条指令组成的序列，且满足输入和输出这四条性质。
2、一个算法的时空性能是指该算法的复杂性和（ ）复杂性，前者是算法包含的计算量，后者是算法需要的存储量。
3、函数3n3+10n的渐进表达式为函数logn3的渐进表达式为。
4、贪心法得到的解一定/不一定）是最优解，用回溯法得到的解一定/不一定）是最优解。
5、通常能用动态规划法求解的问题应具备和的性质。
6、快速排序和归并排序策略上是相同的，都是用的算法。
7、计算机产生的随机数都是有周期的，所以被称为（ ）随机数。
8、计算模型ram、rasp以及tm在计算能力上是（ ）的，在计算速度上是（ ）的。
二、判断题（每小题2分，共10分）
三、计算题（共20分）
注意：要求写出计算过程）
1、 对于下面的各组函数，确定，并简述理由。 （每小题5分，共10分）
2、假设某算法在输入规模为n时的计算时间为。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？
（5分）
3、分析下列程序段所代表的算法的时间复杂性：（5分）
四、问答题（每题5分，共10分）
1、什么是概率算法？试说说舍伍德、拉斯维加斯、蒙特卡罗算法各自的特点。
2、什么是np问题？什么是np完全问题？二者有何关系？
五、求解题（每题10分，共30分）
注意：要求给出求解过程）
1、设多级图g＝(v,e),v＝,v1=,v2=，v3=，v4=，v5=。其耗费如右表所示。请用动态规划法。
求从顶点1到顶点10的最小耗费路径。
2、采用快速排序对序列e,x,a,m,p,l,f按照字母顺序排序，请写出每趟排序后的结果（10分）
3、有无向图如下所示，请用prim算法求出它的最小生成树，要求写出求解过程。
六、算法设计题（15分）
注意：请用自然语言描述你的思路，再写伪**。）
1、 子集和问题：子集和问题的一个实例为。其中， 是一个正整数的集合，c是一个正整数。子集和问题判定是否存在s的一个子集s1，使得。
试设计一个解子集和问题的回溯法，要求说明所采用的算法思想（4分），并给出伪**（8分），分析所给出的算法的时间复杂度（3分）。
算法初步练习卷
算法初步试卷一。一 选择题 本题共10小题，每小题4分，共40分，在每小题给出的四个选项中，只有一项是符合题目要求的 1.下列语言中，哪一个是输入语句。2.右边程序的输出结果为。a 3，4b 7，7 c 7，8d 7，11 3 算法。s1 m a s2 若bs3 若cs4 若ds5 输出m，则输出m...
算法初步组卷
2015年03月16日zng的高中数学组卷。一 选择题 共17小题 三 解答题 共5小题 2015年03月16日zng的高中数学组卷。一 选择题 共17小题 1 下面程序运行的结果是 2 计算机执行如图的程序段后，输出的结果是 3 下列给出的输入语句 输出语句和赋值语句。1 输出语句input a ...
《算法与数据结构》A卷
2011 2012学年第一学期期末考试试题 a 卷。课程名称 算法与数据结构 任课教师签名 出题教师签名 2011计算机合作联盟命题组审题教师签名 考试方式 闭 卷适用专业 10计科1 2 考试时间 110 分钟。注 判断题和选择题的答案写在答题纸上 1.与数据元素本身的形式 内容 相对位置 个数无...