信管网备考经验

算法题一般是作为第四题出现在软件设计师下午《应用技术》科目里，主要考查对常用数据结构和算法的掌握情况，考察形式主要为C语言代码填空、采用了什么设计策略、时间，空间复杂度，算法稳定性分析、输出结果是什么等，通常考查一些中等难度的算法，在下午考试中应该算是最难的一道题，需要考生熟悉一些常用的算法和C语言的语法。

但是算法不是一朝一夕就能提高的，需要考生在平时学习与备考时就要熟悉各类常见算法，像是最短装配时间算法、B树、贪心算法、动态规划、回溯法、背包问题、最短路径、拓扑排序、堆排序等。除了熟悉算法，更重要的就是不断的做题练习。

相关推荐：软考中级软件设计师历年真题及答案免费下载

软件设计师常见算法

1、分治法：

(1)特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。

(2)经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔。

2、动态规划法(用于求最优解)

(1)特征：划分子问题(最优子结构)，并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。

(2)经典问题：斐波那契数列、矩阵乘法、背包问题、 LCS最长公共子序列。

3、回溯法

(1)特征：系统的搜索一个问题的所有解或任一解。有试探和回退的过程。

(2)经典问题：N皇后问题、迷宫、背包问题。

4、贪心法(用于求满意解)

(1)特征：局部最优，但整体不见得最优。每步有明确的，既定的策略。

(2)经典问题：背包问题(如装箱)、多机调度、找零钱问题。