算法设计与分析——选择题

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


1:给定程序时间复杂度的递推公式:T(1)=1,T(N)=2T(N/2)+N。则对该程序时间复杂度最接近的描述是:

A.O(logN)     B.O(N)     C.O(NlogN)     D.O(N2)


2:程序P1和P2时间复杂度的递推公式:

P1: T(1)=1, T(N)=T(N/2)+1;

P2: T(1)=1, T(N)=2T(N/2)+1;

则下列关于两程序时间复杂度的结论中最准确的是:

A.均为O(logN)

B.P1是O(logN),P2是O(N)

C.均为O(N)

D.P1是O(logN),P2是O(NlogN)


3:下面代码段的时间复杂度是()。

for ( i=0; i<n; i++ )
    for ( j=0; j<m; j++ )
        a[i][j]=0; 

A.O(1)     B.O(mn)     C.O(m2)      D.O(n2)


4:下面代码段的时间复杂度是()。
i=1;
while( i<=n )
    i=i*3;

A.O(n)     B.O(n2)     ;C.O(1)     D.O(log3n)


5:下面代码段的时间复杂度是()。
x=n; //n>1
y=0;
while( x≥(y+1)*(y+1) )
    y++;

A.O(1)     B.O(n1/2)     C.O(n)     D.O(log2n)


6:下面算法的时间复杂度为 ▁▁▁▁▁。

int foo(int n)
{
    int i, s = 0;
    for (i = 1; i * i <= n; ++i)
    {
        s += i;
    }
    return s;
}

A.O(n2)     B.O(n)     C.O(sqrt(n) )     D.O(log2n)


7:求整数n(n>=0)的阶乘的算法如下,其时间复杂度为( )。
long fact(long n)
{
if (n<=1) return 1return n*fact(n-1)}

A.O(log2n)     B.O(n2 )     C.O(n)     D.O(nlog2n)


8:算法P1和P2时间复杂度的递推方程分别为:

P1:T(n) = T(n/2) + 1, T(1)=1

P2:T(n) = 2T(n/2) + 1, T(1)=1

则下列关于P1和P2两个算法时间复杂度的结论中正确的是( )。

A.均为O(logn)

B.均为O(n)

C.P1为O(logn),P2为O(n)

D.P1为O(logn),P2为O(nlogn)


9:T(n)表示当输入规模为n时的算法效率,以下算法中效率最优的是( )。

A.T(n)=T(n-1)+1,T(1)=1

B.T(n)=2n

C.T(n)=T(n/2)+1,T(1)=1

D.T(n)=3nlog2n


10:下列函数中,哪个函数具有最慢的增长速度:

A.N1.5

B.NlogN2

C.N2logN

D.N(logN)2



11:用分治法解决一个规模为N的问题。若每步将问题分成规模均为N/3的8个子问题,且治而得到解的步骤耗时O(N2logN),则整个算法的时间复杂度为__。

A.O(N2logN)

B.O(N2log2N)

C.O(N3logN)

D.O(Nlog8/log3)


12:用分治法解决一个规模为N的问题。下列哪种方法是最慢的?

A.每步将问题分成规模均为N/3的2个子问题,且治的步骤耗时O(N)

B.每步将问题分成规模均为N/3的2个子问题,且治的步骤耗时O(NlogN)

C.每步将问题分成规模均为N/2的3个子问题,且治的步骤耗时O(N)

D.每步将问题分成规模均为N/3的3个子问题,且治的步骤耗时O(NlogN)


13:用分治法解决一个规模为N的问题。若每步将问题分成规模均为N/5的4个子问题,且治而得到解的步骤耗时O(logN),则整个算法的时间复杂度为__。

A.O(Nlog4/log5)

B.O(N)

C.O(logN)

D.O(log2N)


14:用分治法解决一个输入规模为 N 的问题时,如果每步都将问题划分为 9 个规模为 N/3 的子问题,并且用 O(N2logN) 的时间治之,则下列哪项最接近总的时间复杂度?

A.O(N2log2N)

B.O(N2logN)

C.O(N2)

D.O(N3logN)

15:下列多少种排序算法用了分治法?
堆排序
插入排序
归并排序
快速排序
选择排序
希尔排序

A.2

B.3

C.4

D.5

16:分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题,分别解决子问题,最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题( )。

A.问题规模相同,问题性质相同

B.问题规模相同,问题性质不同

C.问题规模不同,问题性质相同

D.问题规模不同,问题性质不同

17:在寻找 n 个元素中第 k 小元素问题中,如快速排序算法思想,运用分治算法对 n 个元素进行划分,如何选择划分基准?下面( ) 答案解释最合理。

A.随机选择一个元素作为划分基准

B.取子序列的第一个元素作为划分基准

C.用中位数的中位数方法寻找划分基准

D.以上皆可行。但不同方法,算法复杂度上界可能不同

18:对于下列二分查找算法,以下正确的是( )。

A.

int binarySearch(int a[], int n, int x)
{
 int low=0, high=n-1;
 while(low<=high)
 {

      int mid=(low+high)/2;
      if(x==a[mid])

          return mid;
      if(x>a[mid])

          low=mid;
      else

          high=mid;
 }
 return1;
}

B.

int binarySearch(int a[], int n, int x)
{
 int low=0, high=n-1;
 while(low+1!=high)
 {

      int mid=(low+high)/2;
      if(x>=a[mid])

          low=mid;
      else

          high=mid;
 }
 if(x==a[low])

     return low;
 else

     return1;
}

C.

int binarySearch (int a[], int n, int x)
{
 int low=0, high=n-1;
 while(low     {

      int mid=(low+high)/2;

      if(x <a[mid]) 
                
          high=mid;
      else

          low=mid;
 }
 if(x==a[low])

     return low;
 else

     return1;
}

D.

int binarySearch(int a[], int n, int x)
{
 if(n > 0 && x >= a[0])
 {

      int low = 0, high = n-1;
      while(low < high)
      {

           int mid=(low+high+1)/2;
           if(x < a[mid])
               high=mid-1;
           else

               low=mid;
      }
      if(x==a[low])

          return low;
 }
 return1;
}

19:实现大整数的乘法是利用的( )算法。

A.贪心法

B.分治策略

C.回溯法

D.动态规划法


20:在寻找n个元素中第k小元素的问题中,如采用快速排序算法思想,运用分治法对n个元素进行划分,如何选择划分基准?下面____答案最合理。

A.随机选择一个元素作为划分基准

B.取子序列的第一个元素作为划分基准

C.用中位数的方法寻找划分基准

D.以上皆可行,但不同方法的算法复杂度上界可能不同


21:关于回溯法以下叙述中不正确的是( )

A.回溯法有“通用解题法”之称,它可以系统地搜索一个问题的所有解或任意解

B.回溯法是一种既带系统性又带跳跃性的搜索算法

C.回溯法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

D.回溯算法在生成解空间的任一结点时先判断该结点是否可能包含问题的解,如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向祖先结点回溯


22:回溯法在问题的解空间树中,按( )策略,从根结点出发搜索解空间树。

A.广度优先

B.活结点优先

C.扩展结点优先

D.深度优先


23:回溯法的效率不依赖于下列哪些因素

A.满足显约束的值的个数

B.计算约束函数的时间

C.计算限界函数的时间

D.确定解空间的时间


24:下面哪种函数是回溯法中为避免无效搜索采取的策略

A.递归函数

B.剪枝函数

C.随机数函数

D.搜索函数


25:下列程序块哪个是回溯法中遍历排列树的算法框架程序。

A.
void backtrack (int t)
{
if (t>n) output(x);

 else
    
  for (int i=t;i<=n;i++) {
    swap(x[t], x[i]);
    if (legal(t)) backtrack(t+1);
    swap(x[t], x[i]);
  }
        
}

B.

void backtrack (int t)

{
if (t>n) output(x);

else
  for (int i=0;i<=1;i++) {
    x[t]=i;
    if (legal(t)) backtrack(t+1);
  }
}

C.

void backtrack (int t)

{
if (t>n) output(x);

else
  for (int i=0;i<=1;i++) {
    x[t]=i;
    if (legal(t)) backtrack(t-1);
  }
}

D.文章来源地址https://www.toymoban.com/news/detail-728680.html

void backtrack (int t)
{
if (t>n) output(x);

else
  for (int i=t;i<=n;i++) {
    swap(x[t], x[i]);
    if (legal(t)) backtrack(t+1);
  }
}

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

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

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

相关文章

  • day45—选择题

    A 205 B 205.140 C 68 D 205.140.36 思路:A类地址网络号是0 ~ 127,B类地址网络号是128.0 ~ 191.255,C类是192.0.0 ~ 223.255.255,因此这是一个C类网络,24位网络号 A 服务端收到客户端的SYN包后等待2 ml时间后就会进入SYN_SENT状态 B 服务端收到客户端的ACK包后会进入SYN_RCVD状态 C 当客户端处于ESTA

    2024年02月04日
    浏览(36)
  • 云计算选择题(二)

    云计算知识点-CSDN博客 云计算选择题及答案-CSDN博客 云计算试题及答案-CSDN博客 云计算简答题-CSDN博客 云计算简答题(二)-CSDN博客 云计算单选题及答案-CSDN博客 云计算多选题及答案-CSDN博客 云计算选择题(二)-CSDN博客  与SaaS不同的,这种“云”计算形式把开发环境或者

    2024年04月22日
    浏览(32)
  • day31—选择题

    A 1 B 9 C 10 D 11 思路:CPU中只能处理一个,一共有12个进程,那么处在就绪队列中的最多就是11个 A 线程同步的方法包括使用临界区,互斥量,信号量等 B 两个线程同时对简单类型全局变量进行写操作也需要互斥 C 实现可重入函数时,对自动变量也要用互斥量加以保护 D 可重入函

    2023年04月20日
    浏览(79)
  • day26—选择题

    A 形式参数可被字段修饰符修饰 B 形式参数不可以是对象 C 形式参数为方法被调用时真正被传递的参数 D 形式参数可被视为local variable 思路:字段修饰符指的是public等,形式参数是不可以被public等修饰的;形式参数可以是对象;实参为方法被调用时真正被传递的参数;local v

    2023年04月14日
    浏览(41)
  • day29—选择题

    A toString(),equals() B clone(),equals() C hashCode(),equals() D getClass(),clone() 思路:先调用对象的HashCode方法将对象映射为数组下标,再通过equals方法判断元素内容是否相同;toString是打印元素内容,clone是拷贝;getclass是获取对象的类对象 A 编译运行通过,输出结果是88 B 编译时错误,co

    2023年04月17日
    浏览(47)
  • day24—选择题

    A O(N * M * logN) B O(N*M) C O(N) D O(M) 建立一个长度为N的最大/最小堆:将这N条链表的第一个元素拿出来建立最大/小堆,时间复杂度为O(N);依次从最小堆中取出堆顶元素,此时堆顶就是当前集合的最小值,将链表的其他元素放入堆中,调整堆的时间复杂度(O(logN)),总共还需要入堆的

    2023年04月18日
    浏览(56)
  • kafka基础选择题

    1.下面哪个命令行参数可以用来删除Kafka中的Topic? 解析 本题考查命令行操作 A:list用于查看当前服务器中的所有 topic,A错误 B:create用于创建一个新的topic,B错误 C:delete 用于删除 topic,C正确 D:describe 用于查看某个 Topic 的详情,D错误 2.在Kafka中,()是ISR 队列中最小的

    2024年02月13日
    浏览(42)
  • c++选择题笔记

    c++的三大特性:封装,多态,继承 局部变量能否和全局变量重名?可以,局部变量会屏蔽全局变量。在使用全局变量时需要使用 \\\":: \\\"。 拷贝构造函数:参数为同类型的对象的常量引用的构造函数 函数指针:int (*f)(int,int) = max;  静态成员函数 没有this指针。 静态成员不能是虚

    2024年02月12日
    浏览(38)
  • PHP选择题复习

    1. 如何使用 PHP 输出 “hello world”? A.  \\\"Hello World\\\"; B.  echo \\\"Hello World\\\"; C.  Document.Write(\\\"Hello World\\\"); 答案: B 2. 下面代码执行结果是? ?php FUNCTION TEST() {     ECHO \\\"HELLO WORLD!n\\\"; } test(); ? A. HELLO WORLD! B. 没有任何输出 C. 编译错误,代码无法运行 D. hello world! 答案:A 解析:用户定

    2024年02月02日
    浏览(56)
  • day32—选择题

    A 减少磁盘 I/O 次数 B 减少平均寻道时间 C 提高磁盘数据可靠性 D 实现设备无关性 思路:CPU执行速度要快于磁盘io速度,为了提高效率,对于经常访问的磁盘数据,可以使用磁盘缓存来提高io速度;可以减少的是平均寻道次数,而不是时间;数据的可靠性不是由缓冲区决定的;

    2023年04月21日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包