软件设计师算法基础及常见算法考点
编程小助手
2024-04-18 14:21
软件设计师算法基础及常见算法考点有哪些?为了方便考生及时有效的备考,编程学习网小编为大家精心整理了软考中级软件设计师算法基础及常见算法考试知识点,供大家参考和学习。如想获取更多计算机软件水平考试的模拟题及备考资料,请关注编程学习网网站的更新。
【考法分析】
1、本知识点的考查形式主要有:根据题干的情景描述,判断所使用的算法策略;判断算法相关描述是否正确;下午题也会考查根据题干说明和代码,判断算法策略。
【要点分析】
1、算法的特性:
(1)有穷性:执行有穷步之后结束。
(2)确定性:算法中每一条指令都必须有确切的含义,不能含糊不清。
(3)输入(>=0)
(3)输出(>=1)
(4)有效性(可行性):算法的每个步骤都能有效执行并能得到确定的结果。例如a=0,b/a就无效。
2、分治法
(1)特征:把一个问题拆分成多个小规模的相同子问题,一般可用递归解决。
(2)经典问题:斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔。
3、动态规划法(用于求最优解)
(1)特征:划分子问题(最优子结构),并把子问题结果使用数组存储,利用查询子问题结果构造最终问题结果。
(2)经典问题:斐波那契数列、矩阵乘法、背包问题、 LCS最长公共子序列。
4、回溯法
(1)特征:系统的搜索一个问题的所有解或任一解。有试探和回退的过程。
(2)经典问题:N皇后问题、迷宫、背包问题。
5、贪心法(用于求满意解)
(1)特征:局部最优,但整体不见得最优。每步有明确的,既定的策略。
(2)经典问题:背包问题(如装箱)、多机调度、找零钱问题。
【备考点拨】
1、掌握算法的特性、概念;
2、掌握常见算法的特点、适用场景,并能够加以区分。
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341