第二章递归与分治策略20秋人大测试辅导参考

欧阳老师

第二章递归与分治策略
1.[问答题]给定如下二分搜索算法，请分析算法的复杂性。<br>  int BinarySearch(Type a[], const Type& x, int l, int r){<br>       while (r ＞= l){ <br>          int m = (l+r)/2;<br>          if (x == a[m]) return m;<br>          if (x ＜ a[m]) r = m—1; else l = m+1;<br>       }<br>      return —1;<br>  } <br>   <br>
人大作业无忧答案网整理

    正确答案:——整个算法在最坏情况下的计算时间复杂性为O(logn)。<br>——
2.[问答题]什么是直接递归和间接递归？消除递归一般要用到什么数据结构？<br>

    正确答案:——在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。<br>——    ap5u.com 答 案q q 1647861640
3.[单选题]Strassen矩阵乘法是利用（    ）实现的算法。
    A.分治策略
    B.动态规划法
    C.贪心法
    D.回溯法
    正确答案:——A——
4.[单选题]实现棋盘覆盖算法利用的算法是（    ）。
    A.分治法
    B.动态规划法
    C.贪心法
    D.回溯法
    正确答案:————
5.[问答题]简述分治法所能解决的问题一般应具有的特征。<br>

    正确答案:————
6.[判断题]快速排序是基于分治法设计的算法。
    A.错误
    B.正确
    正确答案:————
转载注明 无忧答案网