算法设计与分析 期末考试试卷

这篇具有很好参考价值的文章主要介绍了算法设计与分析 期末考试试卷。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.渐进表示法中f(n)= O(g(n))意味着f(n)的数量级 [ 不大于 ] g(n)的数量级【填“小于”、“大于”、“不小于”或“不大于”】,平时各种教材中见到的O(n2)表达的意思是算法的复杂度
[ 等于 ] n2数量级【填“小于”、“等于”或“大于”】。
2.算法的正确性通常采用 【 理论证明 】 或测试的方法。
3.如果某算法的时间复杂度为θ(2n),机器的运算速度按109次/秒估算,则n= 【30 】时,机器运算时间为1秒钟【注:210≈1000】,如果n增大3,则运算时间会变为 【 8】 秒。
4.分治算法一般采用 【 二分法 】 。【填“二分法”、“三分法”或“n分法”】
5.用f(n,m)表示两个长度分别为n,m的字符串X、Y的最长公共子序列的长度,补充完整的递推式。
0 【 n== 0||m==0 】
f(n,m)={ f(n-1,m-1)+1 Xn=Ym
【Max(f(n-1,m),f(n,m-1) 】 Xn != Ym
6.对于运算量很大的问题,用随机方法其结果通常 【 】误差【填“有”或“没有”】

算法设计与分析 期末考试试卷
算法设计与分析 期末考试试卷

函数渐进性的O, Ω ,Θ的表示
算法设计与分析 期末考试试卷

算法设计与分析 期末考试试卷

1.如果算法设计与分析 期末考试试卷
,则有( B)。 A.
算法设计与分析 期末考试试卷

B.
算法设计与分析 期末考试试卷

C.
算法设计与分析 期末考试试卷

D.以上都不对

时间复杂度知识点梳理

2.按数量级排序,正确的是( B )。
A.n1/2 < (logn)2
B.n1/2 > (logn)2
C.logn> n
D.logn >n1/2

算法设计与分析 期末考试试卷
https://blog.csdn.net/qq_40811682/article/details/100052294

3.对数组元素a[from]~a[to]进行快速排序时,假设一趟相遇过程将元素a[from]移到数组单元a[pos],则初始元素a[from]在该区间是第(C)小元素。
A.to-from+1 B.from-pos+1 C. pos-from+1 D. to–pos+1

快速排序

4.对解空间树进行深度优先搜索的是( A )。
A.回溯算法 B.分支限界算法 C.分治算法
D.动态规划算法

5.硬币找零问题即是对于面值系统为a1,a2,…,ak(其中a1=1)且个数不限的k种硬币,找零S元钱,求最少硬币个数,关于这个问题的描述正确的是(D )。
A.对于任意面值系统贪心算法均可得到最优解
B.面值系统必须递减排序,动态规划算法才能得到最优解
C.贪心算法的时间复杂度是θ(kS)
D.动态规划算法的时间复杂度是θ(k
S)

6.鬼牌除外的一副扑克牌,共有13种扑克牌,每种牌4张,不考虑花色,从中任取k张牌有多少种可能结果?该问题最适合的算法是( C )。
A.回溯算法
B.概率算法
C.动态规划算法
D.分治算法

7.如果一个问题采用贪心算法、动态规划算法、回溯算法、分支限界算法都可以得到最优解,对四种算法进行比较,你认为最有可能的是( B )。
A.动态规划算法效率最高
B.贪心算法效率最高
C.回溯算法效率最高
D.分支限界算法效率最高

8.下面关于回溯算法与分支限界算法的描述,正确的是( A )。
A.前者不创建解空间树,后者创建解空间树
B.后者不创建解空间树,前者创建解空间树
C.两者均创建解空间树
D.两者均不创建解空间树

9.下面关于图论中弗洛伊德算法的描述,错误的是(C )。
A.能求图中任意两点的最小距离 B.算法可以用二维数组存放结果
C.算法适合有向图,不能用于无向图 D.图中边的权值必须是非负数

10.关于P类和NP类问题,下列说法正确的是( A )。
A.P类是容易处理的
B.NP类问题是不能处理的
C.P类=NP类
D.P类≠NP类
算法设计与分析 期末考试试卷

算法设计与分析 期末考试试卷
三.算法分析题。(本大题4小题,每小题5分,共20分)

1.分析下面程序段的时间复杂度。

   int i,j,s;
	for(i=1;i<=n;i++)
		for(s=0,j=1;s<=n;j++)
       		 s=s+j;

O(N^1.5)

2.分析下面程序段的时间复杂度。

  int x=n, i=1;
   while(x>0)
	{  x= x-i; 
	   i=i*2;
	}

Log(n+1)=O(logn)

3.请描述下面递归函数运行时可能发生的问题。

void f(int n)
{  int  a[1000];
     if(n>0)  f(n-1);
}
  int main() { int n=10000;  f(n);  return 0; }

栈内存不够,强制停止递归函数因为栈溢出而被操作系统强制结束

4.如果机器速度按109次/秒估算,那么下面程序所用时间大约是多少秒?

void f(int n)
{ 
 if(n<0)  return ;
     else  for(i=1;i<5;i++)  f(n-1);
}
  int main() { int n=20;  f(n);  return 0; }
【注:可以按2101000来估算。】

420=240=1000^4,
10004/109=10^3

斐波那契数的时间复杂度斐波那契数的时间复杂度、空间复杂度详解算法设计与分析 期末考试试卷

四.解答题。(本大题3小题,每小题8分,共24分)

1.如果系统rand( )函数产生的随机数范围在[0,32767],请写出表达式产生[a,b]范围随机整数【其中a,b均为整数,且b-a<32767】,请写出表达式产生[0,1]范围且小数点后含有3位的随机小数。

rand()%(b-a+1)+a
Rand()*1001/1000
算法设计与分析 期末考试试卷

2.假设打印时间分别为6,3,8,1,4分钟的5个人同时排队等待一台打印机服务,一个人的等待时间=排在他前面的人的打印时间之和+自己的打印时间,为了求出使得所有人的等待时间总和最小的打印顺序,请给出一种贪心策略,并计算出所有人的等待时间之和。

贪心策略是时间短的先打印,等待时间之和15+34+43+62+8*1=49

3.分析下面算法程序的输出结果。

 int  n=3,X[100];
   int xianjie(int k, int i)
   {  if(k==1 && i<=2) return 0;
      if(k==2 && i<=1) return 0;
      return 1;
   }
void  f(int k)
   {  if(k-1==n) { cout<<endl;  for(int i=1;i<=n;i++) cout<<X[i]<<” ”; }
      else  for(int i=1;i<=n;i++)
           if(xianjie(k,i))
           { X[k]=i;  f(k+1);}
   }
   int  main( ){ f(1);  return 0;}

算法设计与分析 期末考试试卷

五.算法设计题。(本大题2小题,第1小题12分,第2小题14分,共26分)

1.如图m*n方格矩阵a[m][n]中摆放着价值不等的宝贝(价值可正可负),从左上角a[0][0]出发到达右下角a[m-1][n-1],可以向右或向下走到相邻格子,并捡起当前格子的宝贝(无论价值的正负),每个格子只能走一遍,求能捡到宝贝价值之和的最大值。算法设计与分析 期末考试试卷

(1)按动态规划算法的解题过程,写出递推关系式。(6分)
(2)根据递推关系式,写出递归型的动态规划函数。(6分)

算法设计与分析 期末考试试卷

算法设计与分析 期末考试试卷

2.n个正整数元素的集合a[],求元素之和为S的所有子集【注:集合元素依次为a[0],a[1],… a[n-1],要求有剪枝函数】。

#include<iostream>
using namespace std;
int  a[100]= {8,9,7,5,3,2,1} , n=7, S=15;//初始化数据

算法设计与分析 期末考试试卷文章来源地址https://www.toymoban.com/news/detail-477951.html

int X[100];
int sumS=0,leftS=35;
int xianzhi(int k,int i){
	if(i==1&&sumS+a[k]>S) return 0;
	if(i==0&&sumS+leftS-a[k]<S) return 0;
	return 1;
}
void f(int k){
	if(k-1==n){
		if(sumS==S){
			cout<<endl<<"{";
			for(int i=0;i<=6;i++){
				if(X[i]==1) 	cout<<a[i]<<", ";
			}
			cout<<"}";
		}
	}
	else for(int i=0;i<=1;i++){
			if(xianzhi(k,i)){
				X[k]=i;
				if(i==1){sumS+=a[k];leftS-=a[k];}
				f(k+1);
				if(i==1){sumS-=a[k];leftS+=a[k];}
			}
	}
}

int main(){
	f(0);
	return 0;
}

到了这里,关于算法设计与分析 期末考试试卷的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【软件工程】软件工程期末考试试卷

    瀑布模型把软件生命周期划分为八个阶段 :问题的定义、可行性研究、软件需求分析、系统总体设计、详细设计、编码、测试和运行、维护。八个阶段又可归纳为三个大的阶段: 计划阶段、开发阶段和( C) 。   A、详细计划 B、可行性分析  C 、 运行阶段  D、 测试与排错

    2024年02月09日
    浏览(50)
  • 51单片机期末考试试卷及答案

    一、  填空题 1、设X=5AH ,Y=36H,则 X 与 Y“或”运算为 7EH ,X 与 Y 的“异或”运算 为 6CH 。 2、若机器的字长为 8 位,X=17 ,Y=35,则X+Y= 110100 ,X-Y= 11101110 (要求结果写出二进制形式)。 3、单片机复位后,堆栈指针 SP 的值是 07h 。 4、若采用6MHz 的晶体振荡器,则 MCS-51单片

    2024年02月10日
    浏览(42)
  • 桂电 数电实验 期末考试 试卷+解析(74LS192 + 74LS153 + 74LS139 + 74LS00 / 74LS20)

    目录 考试注意事项 A卷    74LS192 + 74LS00 B卷  74LS153 + 74LS00 / 74LS20 + 74LS139  C卷   74LS153 + 74LS00 / 74LS20 + 74LS139 课程感悟 1.考试前请检查实验箱号和仪器号与座位号是否一样,不一样请请示老师更换; 2.请自行检查导线、芯片、仪器的好坏,如有问题,请及时找教师更换;否则由

    2024年02月03日
    浏览(42)
  • 【算法设计与分析】期末复习

    1.1算法与程序 算法:是解决问题的 一种方法或一个过程 ,是由若干条 指令 组成的有穷序列。 算法性质 : 1.输入:有零个或多个 2.输出:至少一个 3.确定性:组成算法的每条指令清晰无歧义 4.有限性:算法中每条指令的执行次数和执行时间是有限的 5.算法与程序的区别:程

    2024年02月04日
    浏览(41)
  • 算法设计与分析-期末复习经典例题

    算法设计应满足的目标:正确性,可使用,可读,健壮,高效率,低存储 算法的5个重要特征:有限、确定、可行、输入、输出 通常用 函数的返回值 表示算法能否正确执行,如果某个形参需要将执行结果回传给实参,需要将该形参设计为 引用型参数 算法分析是分析算法 占

    2024年02月03日
    浏览(49)
  • 算法设计与分析期末复习题

    1.应用Johnson法则的流水作业调度采用的算法是(D) A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上,并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正

    2024年02月09日
    浏览(36)
  • 算法时空复杂度分析:大O表示法

    算法题写完以后,面试官经常会追问一下你这个算法的时空复杂度是多少?(好像作为一名算法工程师,我日常码代码的过程中,并没有太注意这个,惭愧~但是找做后端开发的男票求证了一下,他们日常工作确实会去考虑这种问题)那么无论是为了应付面试,还是为了未来

    2024年03月22日
    浏览(36)
  • 计算机算法设计与分析期末复习

    以下是我的部分算法笔记,希望可以给复习的小伙伴们参考一下: 题目: 一切合法的输入数据都能得出满足要求的结果,包括典型的、苛刻的输入数据也能够得出满足要求的结果。这个含义对应算法的(正确性) 算法要对异常情况进行适当的处理,就是算法的(健壮性)

    2024年02月13日
    浏览(39)
  • 算法设计与分析 期末复习 北邮BUPT

    以下内容以“算法设计与分析-2022”王晓茹老师的ppt为大纲 问题、要求 也均为老师课堂上的口述要求和ppt上的要求 渐进上界、渐进下界 证明 O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x { f ( n ) , g ( n ) } ) O(f(n))+O(g(n)) = O(max{f(n),g(n)}) O ( f ( n )) + O ( g ( n )) = O ( ma x { f ( n ) , g ( n )}) (最后一

    2024年01月16日
    浏览(51)
  • 【期末复习】计算机算法设计与分析

    小编相信大家都很急切,要如何短时间学会算法通过考试呢?下面就让楼主带大家一起了解吧。 算法期末考试,其实就是算法期末考试了。那么小编为什么会算法期末考试,相信大家都很好奇是怎么回事。大家可能会感到很惊讶,小编怎么会算法期末考试呢?但事实就是这样

    2024年02月03日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包