一个递归算法的递归公式如下: [图] 请分析该算法的时...
一个递归算法的递归公式如下:请分析该算法的时间复杂度。
一个递归算法的递归公式如下:请分析该算法的时间复杂度。
第1题
图1给出了一个算法流程图,该算法流程图的功能是( )。请同时在答题纸上编写出该流程图对应的程序。
A、求a,b,c三数的最大数
B、将a,b,c按从小到大排列
C、求a,b,c三数的最小数
D、将a,b,c按从大到小排列
第2题
图1给出了一个算法流程图,该算法流程图的功能是( )。请完成填空后在答题纸上写出该流程图对应的C语言程序.
A、求a,b,c三数的最大数
B、求a,b,c三数的最小数
C、将a,b,c按从小到大排列
D、将a,b,c按从大到小排列
第3题
补全下面用Raptor给出求解斐波那契数的递归算法。
A、fab(b,a-1)
B、fab(a-1,b)
C、fab(a-1,b-1)
D、fab(b-1 ,a-1)
第4题
算法5-6:迪杰斯特拉最短路径算法【图】 Description 在带权有向图G中,给定一个源点v,求从v到G中的其余各顶点的最短路径问题,叫做单源点的最短路径问题。 在常用的单源点最短路径算法中,迪杰斯特拉算法是最为常用的一种,是一种按照路径长度递增的次序产生最短路径的算法。 在本题中,读入一个有向图的带权邻接矩阵(即数组表示),建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。 Input 输入的第一行包含2个正整数n和s,表示图中共有n个顶点,且源点为s。其中n不超过50,s小于n。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数,如果大于0,则表示第i个顶点有指向第j个顶点的有向边,且权值为对应的整数值;如果这个整数为0,则表示没有i指向j的有向边。当i和j相等的时候,保证对应的整数为0。 Output 只有一行,共有n-1个整数,表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径,输出-1。 请注意行尾输出换行。 Sample Input4 1 0 3 0 1 0 0 4 0 2 0 0 0 0 0 1 0Sample Output6 4 7
第5题
已知,,其中均为自然数,新函数h可递归的构造如下:h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x),请按递归式进行计算下列式子,不正确的是_____。
A、h(4,x) = 12x
B、h(1,x) = x
C、h(2,x) = 2x
D、h(3,x) = 6x
第6题
已知f(x)=x,, 其中均为自然数,新函数h可递归的构造如下:h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x),其中S(n)为后继函数,请按递归式进行计算下列式子,正确的是_____。
A、h(4,x) = 5x+6
B、h(1,x) = x
C、h(2,x) = 2x
D、h(3,x) = 3x+1
E、上述都不正确
第7题
算法5-5:有向无环图的拓扑排序【图】 Description 由某个集合上的一个偏序得到该集合上的一个全序,这个操作被称为拓扑排序。偏序和全序的定义分别如下: 若集合X上的关系R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。 设R是集合X上的偏序,如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序关系。 由偏序定义得到拓扑有序的操作便是拓扑排序。 拓扑排序的流程如下: 1. 在有向图中选一个没有前驱的顶点并且输出之; 2. 从图中删除该顶点和所有以它为尾的弧。 重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。 采用邻接表存储有向图,并通过栈来暂存所有入度为零的顶点,描述拓扑排序的算法 在本题中,读入一个有向图的邻接矩阵(即数组表示),建立有向图并按照以上描述中的算法判断此图是否有回路,如果没有回路则输出拓扑有序的顶点序列。 Input 输入的第一行包含一个正整数n,表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1,对于第i行的第j个整数,如果为1,则表示第i个顶点有指向第j个顶点的有向边,0表示没有i指向j的有向边。当i和j相等的时候,保证对应的整数为0。 Output 如果读入的有向图含有回路,请输出“ERROR”,不包括引号。 如果读入的有向图不含有回路,请按照题目描述中的算法依次输出图的拓扑有序序列,每个整数后输出一个空格。 请注意行尾输出换行。 Sample Input4 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0Sample Output3 0 1 2 HINT 在本题中,需要严格的按照题目描述中的算法进行拓扑排序,并在排序的过程中将顶点依次储存下来,直到最终能够判定有向图中不包含回路之后,才能够进行输出。 另外,为了避免重复检测入度为零的顶点,可以通过一个栈结构维护当前处理过程中入度为零的顶点。
第9题
如果一个算法的时间频度T(n)=+4n+5,则其时间复杂度为_________。
A、O()
B、O(+4n+5)
C、O(+4n)
D、O(1)
第10题
一个图有7个顶点,编号为0~6,其邻接矩阵如下:回答以下问题: (1)画出该有向图。 (2)求顶点0的入度和出度。 (3)求顶点2的度。
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!