软考-常见算法题

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

相关概念

算法是由基本运算及规定的运算顺序所构成的完整的解题步骤。

算法应该具有以下五个重要的特征:

1、有穷性(Finiteness): 指算法必须能在执行有限个步骤之后终止;

2、确定性(Definiteness) :算法的每一条指令必须有确切的含义;

3、输入(Input):一个算法有0个或多个输入;

4、输出(Output) :一个算法有1个或多个输出;

5、可行性(Effectiveness) :算法的每个步骤都能有效执行并能得到确定的结果 (也称有效性)。

算法类型

软考中常见算法类型:分治法、回溯法、贪心法、动态规划法。

一、分治法

将一个问题拆分为若干个小规模的子问题,通常用递归的思想求解子问题,子问题相互独立但与原问题相同,再将子问题的解合并得到原问题的解。(自下向上)

经典例题:

(2018年下)在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。

软考-常见算法题

该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( 62 );对应的时间复杂度为( 63 )。

假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( 64 )个消防栓。以下关于该求解算法的叙述中,正确的是( 65 )。

(62)A.分治        B.动态规划        C.贪心        D.回溯

(63)A.O(lgn)        B.O(n)        C.O(n²lgn)        D.O(n²)  

(64)A.4        B.5        C.6       D. 7

(65)A.肯定可以求得问题的一个最优解

        B.可以求得问题的所有最优解

        C.对有些实例,可能得不到最优解

        D.只能得到近似最优解

【解析】题本中算法基本思路为去掉已被覆盖的房子,可以将问题的规模逐步缩小,形成规模较小的子问题,而这些问题的求解与原问题的求解过程相同,因此属于分治法的算法思想。由于本题的算法过程,是以此与各个房子进行判断,当所有房子都被比较后,问题结束。因此时间复杂度与房子个数有关,为。

题目坐标序列为(10,20,30,35,60,80,160,210,260,300):

第一轮放置:在x=10的右侧20m处安装一个消火栓,覆盖半径为20m,覆盖范围为10-x-50,也即可以覆盖10,20,30,35这4栋房子;

第二轮放置:去掉前面覆盖的房子,在第5栋房子x=60右侧20m处安装一个防火栓,覆盖范围为60-x-100,可以覆盖60,80这2栋房子;

第三轮放置:去掉前面覆盖的房子,在第7栋房子x=160右侧20m处安装一个防火栓,覆盖范围为160-x-200,可以覆盖160这1栋房子;

第四轮放置同上,覆盖第8栋210这1栋房子;

第五轮放置:去掉前面覆盖的房子,在第9栋房子x=260右侧20m处安装一个防火栓,覆盖范围为260-x-300,可以覆盖260,300这2栋房子。

房子覆盖完毕,因此需安装5个消火栓。

最后一空,A选项得到一个最优解是动态规划的特点,B选项得到所有最优解是回溯法的特点,排除A、B选项,对比C、D选项,C的说法更合理。

【答案】62.A        63.B        64.B        65.C

二、动态规划法

划分子问题为最优的子策略,并把子问题的解使用数组存储,利用查表查出子问题结果构造最终问题结果。与分治法不同的是子问题不独立,相同子问题可能会被求解多次。(自底向上/自下而上)

经典例题:

(2019年上)已知矩阵和相乘的时间复杂度为O(m*n*p)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵相乘的计算顺序具有最优子结构,即的最优计算顺序包含其子问题​​​​​​​和软考-常见算法题的最优计算顺序。

可以列出其递归式为:

软考-常见算法题

其中,的维度为, m[i,j]表示软考-常见算法题最优计算顺序的相乘次数。

先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策

略为( 62 )。算法的时间复杂度为( 63 ),空间复杂度为( 64 )。

给定一个实例,()=(20,15,4,10,20,25),最优计算顺序为( 65 )。

(62)A.分治法        B.动态规划法        C.贪心法        D.回溯法

(63)A.O(n²)        B. O(n²lgn)        C.O(n³)        D. O(2n)        

(64)A.O(n²)        B. O(n²lgn)        C.O(n³)        D. O(2n)

(65)A.(((A1*A2)*A3)*A4)*A5        B. A1*(A2*(A3*(A4*A5)))

        C.((A1*A2)*A3)* (A4*A5)        D. (A1*A2) *( (A3*A4)*A5)

【解析】

(1)本题提到“ 已知确定n个矩阵相乘的计算顺序具有最优子结构,即的最优计算顺序包含其子问题​​​​​​​和软考-常见算法题的最优计算顺序”,即规模为n的问题的解与较小规模为k的问 题的解有关,具有最优子结构,并且提到“m[i,j]表示软考-常见算法题最优计算顺序的相乘次数”即,用中间数组m[i,j]存放中间子结果,所以本题描述的算法策略是动态规划法,特点是具有最优子结构,并且会利用中间表记录中间结果,最后利用查表得到最优解。

(2)题干给出“已知矩阵A 和B 相乘的时间复杂度为O(mnp)”,即矩阵乘法的实现过程,可以简单理解为3层嵌套循环,所以时间复杂度为O(n^3)。

(3)本题在计算过程中,需要临时存储空间存放中间结果m[][],二维数组占据空间为n*n,即空间复杂度为 O(n^2)。

(4)可以按照选项直接计算出相应乘法次数进行判断。

给定一个实例,()=(20,15,4,10,20,25), 表示A1 (20×15),A2(15×4),A3(4×10),A4(10×20), A5(20×25)。

选项A:(((A1 ×A2 ) ×A3 ) ×A4 ) ×A5,根据括号计算顺序,先计算A1×A2= (20×4),乘法次数为20×15×4=1200; 然后计算A12×A3=A123(20×10),乘法次数为20×4×10=800;接着计算A123×A4=A1234(20×20),乘法次数为 20×10×20=4000;最后计算A1234×A5 =A12345 (20×25),乘法次数为20×20×25=10000。 A选项乘法次数为1200+800+4000+10000=16000次;

选项B:A1 ×(A2 ×(A3 ×(A4 ×A5 ))) ,根据括号计算顺序,先计算A4 ×A5 =A45 (10×25),乘法次数为10×20×25=5000;然 后计算A3 ×A45 =A345 (4×25),乘法次数为4×10×25=1000;接着计算A2 ×A345 =A2345 (15×25),乘法次数为 15×4×25=1500;最后计算A1 ×A2345 =A12345 (20×25),乘法次数为20×15×25=7500。 B选项乘法次数为5000+1000+1500+7500=15000次;

选项C:((A1 ×A2 )×A3 )× (A4 ×A5 ) ,根据括号计算顺序,先计算A1×A2 =A12(20×4),乘法次数为20×15×4=1200;然后计算A12 ×A3 =A123 (20×10),乘法次数为20×4×10=800;接着计算A4 ×A5 =A45 (10×25),乘法次数为 10×20×25=5000;最后计算A123 ×A45 =A12345 (20×25),乘法次数为20×10×25=5000。 C选项乘法次数为1200+800+5000+5000=12000次;

选项D:(A1 ×A2 ) ×( (A3 ×A4 )×A5 ) ,根据括号计算顺序,先计算A1 ×A2 =A12 (20×4),乘法次数为20×15×4=1200; 然后计算A3 ×A4 =A34 (4×20),乘法次数为4×10×20=800;接着计算A34 ×A5=A345 (4×25),乘法次数为 4×20×25=2000;最后计算A12 ×A345 =A12345 (20×25),乘法次数为20×4×25=2000。 D选项乘法次数为1200+800+2000+2000=6000次; D选项为最优计算顺序

三、贪心法

不考虑整体,只在当前做出最优的选择,求得局部最优解。(自顶向下)

经典例题:

(2012年上)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij。为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的运输目的地1,然后选择离运输目的地1最近的运输目的地2,…,每次在需访问的运输目的地中选择离当前运输目的地最近的运输目的地,最后回到中央仓库。刚该算法采用了__(63)__算法设计策略,其时间复杂度为__(64)__。

(63)A.分治         B.动态规划          C.贪心         D.回溯

(64)A.O(n²)        B. O(n)        C.O(nlgn)        D. O(1)

【解析】

由于每次选择下一个要访问的城市时都是基于与当前最近的城市来进行,是一种贪心的选择策略,因此采用的是贪心策略。而货车从中央仓库出发,第一个要到达的目的地是在n个目的地中选择一个,第二个要到达的目的地是在n-1个目的地中选择一个,...,第n个要到达的目的地是在1个目的地中选择一个,因此时间复杂度为n+(n-1)+…+l= n*(n-l)/2=O(n²)

四、回溯法

搜索问题的所有解或任一解,在搜索过程中发现不满足求解条件则回溯,尝试别的路径。

适用于深度优先探索。

经典例题:

(2019年上)n皇后问题描述为:在一个nXn的棋盘上摆放n个皇后,要求任意两个皇后不能冲突, 即任意两个皇后不在同一行、同一列或者同一斜线上。

算法的基本思想如下:

将第i个皇后摆放在第i行,i从1开始,每个皇后都从第1列开始尝试。尝试时判断 在该列摆放皇后是否与前面的皇后有冲突,如果没有冲突,则在该列摆放皇后,并考虑摆 放下一个皇后;如果有冲突,则考虑下一列。如果该行没有合适的位置,回溯到上一个皇后考虑在原来位置的下一个位置上继续尝试摆放皇后,……,直到找到所有合理摆放方案。

【C代码】
下面是算法的C语言实现。

(1)常量和变量说明
n: 皇后数,棋盘规模为n×n
queen[]: 皇后的摆放位置数组, queen[i]表示第i个皇后的位置, 1≤queen[i]≤n
(2)C程序   (附带注释便于理解)

#include <stdio.h>
#define n 4
int queen[n+1];

void Show(){ /* 输出所有皇后摆放方案 */
    int i;
    printf("(");
    for(i=1;i<=n;i++){
        printf(" %d",queen[i]);
    }
    printf(")\n");
}

int Place(int j)
{ /* 检查当前列能否放置皇后,不能放返回0,能放返回1 */
    int i;
    for(i=1;i<j;i++)
    { /* 检查与已摆放的皇后是否在同一列或者同一斜线上 */
        if( (1) ) ‖ abs(queen[i]-queen[j]) == (j-i)) 
        {
        return 0;
        }
    }
    return (2) ;
}

void Nqueen(int j){
    int i;
    for(i=1;i<=n;i++){
        queen[j] = i;
        if( (3) ){
            if(j == n) 
            { /* 如果所有皇后都摆放好,则输出当前摆放方案 */
                Show();
            } 
            else 
            { /* 否则继续摆放下一个皇后 */
                (4) ;
            }
        }
    }
}

int main(){
    Nqueen (1);
    return 0;
}

(1)常量和变量说明
n: 皇后数,棋盘规模为n×n
queen[]: 皇后的摆放位置数组, queen[i]表示第i个皇后的位置, 1≤queen[i]≤n
(2)C程序

【问题1】(8分)

根据题干说明,填充C代码中的空(1)〜(4)。

【问题2】(3分)

根据题干说明和C代码,算法采用的设计策略为 (5)

【问题3】(4分)

当n=4时,有 (6) 种摆放方式,分别为 (7) 。

【解题思路】

n皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击,如图所示。

软考-常见算法题

 问题的要求在于把n个皇后放在一个nXn的棋盘上,不能同行,不能同列,也不能位于同一条对角线上。很容易看出n=2和n=3问题无解。所以假设n=4,4皇后问题,即4个皇后必须分别占据一行,如图

软考-常见算法题

从空棋盘开始,把皇后1放在第一行可能的位置上,即(1,1)。皇后2不能放在第一列和第二列,所以放在第一个可能的位置(2,3),第二行第三列的格子。但往下证明是死胡同,因为皇后3会没有位置可放。所以,该算法进行回流,把皇后2放在可能的位置(2,4)。皇后3放在(3,2),但皇后4没有位置可放,证明探索失败,把算法回流到底,皇后1移动至(1,2),接着皇后2到(2,4),皇后3到(3,1),皇后4到(4,3),出来了4皇后问题的第一个可行解。 下图为此次可行解的探索树。

软考-常见算法题

回到【问题1】,从题本要求中的判断位置冲突和程序中return 0 可知if中后半句为判断当前摆放皇后是否和已摆放皇后在同一对角线,则可推断出(1)为判断是否为同列,即queen[i]==queen[j]。容易得出(2)为返回1。(4)的提示根据if-else得出,如果全部摆放完成则执行show()输出结果,否则填写递归函数继续摆放Nqueen(j+1)。最后推空(3),程序中未出现过Place()的调用,所以此空应有Place(j)的调用,同时可以注意到(4)中有逐个摆放皇后的思想也即j+1,所以if判断中j不能超过皇后数n,(3)为Place(j)&&j<n。

【问题2】皇后问题整体思想体现的是回溯法的思想:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

【问题3】当n=4时,也就是4皇后问题,有2种摆放方式,分别为2413、3142(可以从皇后1不能放在(1,1)、(1,4)的思想上推论)

(补充:假设为8皇后问题,有92种解)


五四青年,当以最饱满的精神状态去迎接新时代的考卷。奋斗,是青春最靓丽的景色!

只争朝夕,不负韶华!文章来源地址https://www.toymoban.com/news/detail-471151.html

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

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

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

相关文章

  • ZYNQ相关的常见概念

    ZYNQ :是赛灵思公司(Xilinx)推出的新一代全可编程片上系统(APSoC),它将处理器的软件可编程性与FPGA的硬件可编程性进行完美整合。 PS :(Processing System),ZYNQ可以大概分为ARM和FPGA两部分,PS就是ARM的SOC部分,是整块板子的处理系统。 PL :(Progarmmable Logic),意为可编程逻辑

    2024年02月04日
    浏览(35)
  • 移动技术相关基本概念

    一种能够保障企业信息网络安全的高级网络设备,主要作用是隔离内外网,阻隔外界攻击,保护企业网络不遭受黑客攻击、木马病毒入侵、信息泄露等安全威胁。 同时还能对企业内部的流量进行监视,保护企业敏感数据不被内部人员窃取、泄露。 根据不同的分类标准,网络

    2024年02月13日
    浏览(43)
  • 图论相关基本概念

    从逻辑结构上讲,图是一种典型的 非线性结构 。 图(Graph) 是由 顶点的有穷非空集合和顶点之间边的集合 组成的,通常表示为 G(V , E) ,其中, G表示—个图,V是图G中顶点的集合,E是图G中边的集合。其中: 顶点集合V={x|x属于某个数据对象集}是有穷非空集合 E={(x,y)|

    2024年02月01日
    浏览(39)
  • 计算机网络-物理层基本概念(接口特性 相关概念)

    求极限传输速率:奈氏准则,香农定理(背景环境不一样) 编码:数据变成数字信号 调制:数字信号变成模拟信号 信道不同传输 数据形式不同 数据交换方式:核心(打电话是电路交换) 导向传输介质:看得见的 非导向传输介质:看不见的 传输介质并不属于物理层,它们

    2024年01月24日
    浏览(51)
  • HTTP基本概念-HTTP 常见字段有哪些?

    资料来源 : 小林coding 小林官方网站  : 小林coding (xiaolincoding.com) Host 字段 客户端发送请求时,用来指定服务器的域名 Host:www.A.com 有了 Host 字段,就可以将请求发往「同一台」服务器上的不同网站。 Content-Length 字段 服务器在返回数据时,会有 Content-Length 字段,表明本次回应

    2024年02月21日
    浏览(33)
  • 4.10.1、IP 多播技术的相关基本概念

    多播(Multicast,也称为组播)是一种实现 “一对多” 通信的技术,与传统单播“一对一”通信相比,多播可以极大地节省网络资源。 在因特网上进行的多播,称为 IP 多播。 如下所示:若采用单播方式,则视频服务器需要发送 60 个该视频节目 这些视频节目通过各路由器的转

    2024年02月09日
    浏览(35)
  • 机器学习的第一节基本概念的相关学习

    目录 1.1 决策树的概念 1.2 KNN的概念 1.2.1KNN的基本原理 1.2.2 流程: 1.2.3 优缺点 1.3 深度学习 1.4 梯度下降 损失函数 1.5 特征与特征选择 特征选择的目的 1.6 python中dot函数总结 一维数组的点积: 二维数组(矩阵)的乘法: 多维数组的乘法: 1.7  suffler   打乱 1.8 特征和标签 1

    2024年02月10日
    浏览(49)
  • 什么是机器学习?监督学习的定义、概率论的基本概念以及模型选择、过拟合与欠拟合的问题。常见的监督学习算法,包括朴素贝叶斯(Naive Bayes)、决策树(Decision Tree)支持向量机随机森林

    作者:禅与计算机程序设计艺术 什么是机器学习?从定义、发展历程及目前的状态来看,机器学习由3个主要分支组成:监督学习(Supervised Learning),无监督学习(Unsupervised Learning)和强化学习(Reinforcement Learning)。这三类学习都可以使计算机系统根据输入数据自动分析和改

    2024年02月09日
    浏览(53)
  • Shell编程 管道和重定向 | 基本概念及其相关应用

    在Linux中,管道和重定向是非常有用的工具,用于处理命令的输入和输出。它们允许你将多个命令组合在一起,将命令的输出发送到文件或从文件中读取输入。以下是有关Linux管道和重定向的详细介绍,并附带了丰富的示例: 管道符号 | 用于将一个命令的输出传递给另一个命

    2024年01月18日
    浏览(42)
  • 【音视频原理】图像相关概念 ② ( 帧率 | 常见帧率标准 | 码率 | 码率单位 )

    帧率 Frame Rate , 帧 指的是 是 画面帧 , 帧率 是 画面帧 的 速率 ; 帧率 的 单位是 FPS , Frames Per Second , 是 每秒钟 的 画面帧 个数 ; 帧率 是 动画 / 电影 / 游戏 的 每秒钟 的 画面数 , 用于 测量 视频 的 信息数量 ; 帧率 越高 , 视频 信息数量越多 ; 帧率 与 流畅度 相关 , 帧率越高

    2024年01月20日
    浏览(95)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包