免费智能真题库 > 历年试卷 > 软件设计师 > 2018年上半年 软件设计师 下午试卷 案例
  第4题      
  知识点：   常量   递归式   数组   常量和变量   基本思想   实现方式

 
阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。
【说明】
    某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表p，其中pi（i＝1，2，...，m）表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。
    求解此切割方案的算法基本思想如下：
    假设长钢条的长度为n英寸，最佳切割方案的最左边切割段长度为i英寸，则继续求解剩余长度为n－i 英寸钢条的最佳切割方案。考虑所有可能的i，得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下：
                  rn =max1≤ i ≤n(pi +rn-i)
对此递归式，给出自顶向下和自底向上两种实现方式。
【C代码】
/*  常量和变量说明
       n：长钢条的长度
       p[]：价格数组
*/
#define LEN 100

int Top_Down_ Cut_Rod(int p[],int n){  /*自顶向下*/
        int r=0;
        int i;
        if(n == 0){
              return 0;
        }
        for(i=1;    （1）    ;i++){
               int tmp = p[i]+Top_Down_Cut_Rod(p,n-i);
               r=(r>=tmp)?r：tmp;
        }
        return r;
}


int Bottom_Up_Cut_Rod(int p[],int n){     /*自底向上*/
        int r[LEN]={0};
        int temp=0;
        int i,j;
        for(j=1;j<=n;j++){
              temp=0;
              for(i=1;    （2）    ;i++) {
                    temp=    （3）    ;
              }
                （4）   ;
         }
         return r[n];
}
 
 
问题：4.1   （8分）
根据说明，填充C代码中的空（1）～（4）。
 
问题：4.2   （7分）
根据说明和C代码，算法采用的设计策略为（5）。
求解rn时，自顶向下方法的时间复杂度为（6）；自底向上方法的时间复杂度为（7）（用O表示）。
 
 
 

   知识点讲解    
   · 常量    · 递归式    · 数组    · 常量和变量    · 基本思想    · 实现方式
 
       常量
        与C语言不同，使用final关键字，C++语言则是const，如final float pi=3.14f、 final byte c=12。浮点常数后面要加"f"，如12.7f、 1.02f。
 
       递归式
        从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本小节主要讨论递归算法的时间复杂度分析方法。
        （1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直至得到一个求和表达式及其结果。
        （2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。
        （3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供"好"的猜测，然后用代换法证明。在递归树中，每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时，递归树的方法尤其有用。
        （4）主方法。也称为主定理，给出求解以下形式的递归式的快速方法，即
        T(n)=aT(n/b)+f(n)
        式中，a≥1和b>1是常数；f(n)是一个渐进的正函数。
 
       数组
               数组的定义及基本运算
               n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
               对数组进行的基本运算有以下两种。
               （1）给定一组下标，存取相应的数据元素。
               （2）给定一组下标，修改相应的数据元素中某个数据项的值。
               数组的顺序存储
               一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
               同样的，以列为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((j-1)m+(i-1))L
 
       常量和变量
        按照程序运行时数据的值能否改变，将程序中的数据分为常量和变量。程序中的数据对象可以具有左值和（或）右值，左值指存储单元（或地址、容器），右值是值（或内容）。变量具有左值和右值，在程序运行过程中其右值可以改变；常量只有右值，在程序运行过程中其右值不能改变。
 
       基本思想
        小波变换的基本思想是将信号展开成一族基函数的加权和，即用一族函数表示或逼近信号或函数。这一族函数是通过基本函数的平移和伸缩构成的。
        小波变换用于图像编码的基本思想就是把图像进行多分辨率分解，分解成不同空间、不同频率的子图像，然后再对子图像进行系数编码。小波变换本身并不具有压缩功能，之所以将它用于图像压缩，是因为生成的小波图像的能量主要集中于低频部分，水平、垂直和对角线上的高频部分则较少，可以将这一特性与一定的编码算法相结合，达到高效压缩图像的目的。小波变换作为一种多尺度、多分辨率的分析方法，由于小波具有很好的时频或空频局部特性，特别适合于按照人类视觉系统特性设计图像压缩编码方案，也非常有利于图像的分层传输。实验证明，图像的小波变换编码在压缩比和编码质量方面优于传统的DCT变换编码。
 
       实现方式
        IPSec可以在端系统或者安全网关中实现，也可以在现有的IP实现中集成IPSec，这种方法需要能够修改现有IP实现的源码;BITS（Bump In The Stack）实现方式是在已有的IP协议栈中实现IPSec，使之存在于IP协议和网络驱动器之间;BITW（Bump In The Wire）实现方式是在外部的加密机中实现IPSec，从而在两个路由器或两个主机之间形成安全隧道。
        IPSec的一个重要实现方式是基于VPN（Visual Private Network）的加密机制，由IPSec构成的加密IP隧道，提供了不同介质和地域网间的安全透明连接。
   题号导航      2018年上半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第4题    在手机中做本题