软件工程专升本2025年算法设计试卷（含答案）

软件工程专升本2025年算法设计试卷（含答案）考试时间：______分钟总分：______分姓名：______一、简述算法的基本特性。请至少列举并解释其中四项。二、已知数组`A=[5,2,9,1,5,6]`，请分别写出使用选择排序和快速排序对数组`A`进行升序排序的过程。无需写出完整的伪代码或代码，只需描述关键步骤或划出数组变化状态即可。三、解释什么是算法的时空复杂度？为什么在评价一个算法时需要考虑它的时空复杂度？四、给定一个无向图`G=(V,E)`，其中`V`是顶点集合，`E`是边集合。请简要说明深度优先搜索（DFS）和广度优先搜索（BFS）的基本思想，并分别描述它们在图`G`中用于查找顶点`u`和顶点`v`之间是否存在路径时的主要区别。五、什么是动态规划算法？请说明动态规划算法适用于解决哪些类型的问题，并给出一个不属于此类问题的例子，简要说明理由。六、请设计一个算法，用于找出一个无向连通图中所有长度为2的简单路径（即路径中不含重复顶点，且路径经过的边不重复）。要求描述算法的基本思想，无需写出伪代码。七、假设你正在设计一个算法来判断一个给定的自然数`n`是否是一个素数。请描述一个效率较高的算法思路，并简要分析其时间复杂度。八、编写一个算法，输入为一个非空字符串`s`，输出该字符串中所有不同字符的出现次数。例如，输入`"hello"`，输出应表明`'h':1,'e':1,'l':2,'o':1`。请使用C/C++或Java语言实现该算法的核心部分（即包含主要逻辑的代码片段即可，无需完整程序框架）。试卷答案一、算法的基本特性包括：1.有穷性：算法必须在执行有限步骤后终止。2.确定性：算法每一步的操作都有确切的定义，没有歧义。3.可行性：算法的每一步都可以被精确地执行。4.输入：算法有零个或多个输入。5.输出：算法有一个或多个输出。二、选择排序过程：初始数组:`[5,2,9,1,5,6]`第一轮：找到最小值1，与第一个元素5交换->`[1,2,9,5,5,6]`第二轮：在剩余部分`[2,9,5,5,6]`中找到最小值2->`[1,2,9,5,5,6]`(已就位)第三轮：在剩余部分`[9,5,5,6]`中找到最小值5，与第一个元素9交换->`[1,2,5,9,5,6]`第四轮：在剩余部分`[5,9,5,6]`中找到最小值5，与第一个元素5交换->`[1,2,5,5,9,6]`(已就位)第五轮：在剩余部分`[9,5,6]`中找到最小值5，与第一个元素9交换->`[1,2,5,5,5,6]`(已就位)第六轮：剩余部分`[9,6]`，找到最小值6，与9交换->`[1,2,5,5,5,6]`(已就位)最终排序结果:`[1,2,5,5,6,9]`快速排序过程：初始数组:`[5,2,9,1,5,6]`选择枢轴（如第一个元素）`5`，进行分区：数组分区后（以第一个`5`为枢轴）：`[2,1,5,5,6,9]`（实际分区过程可能因枢轴选择和划分方法不同而略有差异，此处示意划分结果，`5`左边元素均小于等于`5`，右边均大于等于`5`）对子数组`[2,1]`和`[6,9]`递归快速排序。对`[2,1]`，选择枢轴`2`，分区后为`[1,2]`。对`[6,9]`，选择枢轴`6`，分区后为`[6,9]`。合并结果（忽略枢轴已就位）：`[1,2,5,5,6,9]`。三、算法的时空复杂度是用来衡量算法效率的度量。*时间复杂度描述算法执行时间随输入规模增长的变化趋势。通常使用大O表示法（BigOnotation）。*空间复杂度描述算法执行过程中临时占用的存储空间随输入规模增长的变化趋势，也常用大O表示法。评价算法时需要考虑时空复杂度，因为：1.资源限制：计算机资源（CPU时间、内存）是有限的。高时间复杂度的算法在处理大数据时可能无法在合理时间内完成；高空间复杂度的算法可能因内存不足而失败。2.效率比较：不同的算法解决同一问题，其时空复杂度可能不同。选择时空复杂度更优的算法可以提高效率。3.适用性：对于内存受限的环境（如嵌入式系统），空间复杂度尤为重要；对于对响应时间要求高的应用，时间复杂度更为关键。四、基本思想：*DFS：从起始顶点出发，尽可能深地探索一条路径，直到无法继续深入时回溯，然后探索另一条路径。使用栈（递归或显式栈）实现。*BFS：从起始顶点出发，先访问所有相邻顶点，然后再访问这些相邻顶点的相邻顶点，依此类推。使用队列实现。查找路径的主要区别：1.发现路径的顺序：对于无向图，DFS倾向于先深挖一条路径，可能先发现距离起点较远的顶点；BFS则按距离起点的远近顺序逐层访问顶点，最先发现距离最近的顶点（如果存在路径）。2.实现方式：DFS依赖栈，BFS依赖队列。3.路径长度：BFS找到的从起点到终点的路径（如果存在）guaranteed是最短的（边数最少）。五、动态规划（DP）算法：*定义：一种通过将原问题分解为相对简单的子问题来解决复杂问题的方法。它存储已解决子问题的结果（通常使用数组或表格），避免重复计算。*适用问题类型：主要适用于具有以下两个特性的问题：1.最优子结构：整体问题的最优解包含其子问题的最优解。2.重叠子问题：在问题的求解过程中，许多相同的子问题会被重复计算多次。*不属于此类问题的例子：纯粹的顺序查找问题。因为顺序查找不分解问题，也不存储子问题结果以避免重复计算，其子问题之间没有最优子结构关联。六、算法基本思想：1.初始化一个空集合`Paths`用于存储最终结果。2.遍历图中的每一个顶点`u`。3.对于顶点`u`，找到所有与其相邻的顶点`v`（即边`(u,v)`在`E`中）。4.对于每一个相邻顶点`v`，再次找到所有与`v`相邻且不同于`u`的顶点`w`（即边`(v,w)`在`E`中，且`w!=u`）。5.对于每一对顶点`(u,v)`和`(v,w)`，如果边`(u,v)`和`(v,w)`都存在于`E`中，则将路径`[u,v,w]`添加到集合`Paths`中。6.继续步骤3-5，直到图中的所有顶点都被处理完毕。7.返回集合`Paths`作为输出。七、效率较高的算法思路（朴素算法优化）：1.如果`n<=1`，则`n`不是素数（约定0和1既不是素数也不是合数）。2.如果`n==2`，则`n`是素数。3.如果`n`是偶数且`n>2`，则`n`不是素数。4.对于所有奇数`i`，从`i=3`开始，直到`i*i>n`：*检查`n`是否能被`i`整除（即`n%i==0`）。*如果能整除，则`n`不是素数，直接返回`false`。5.如果以上所有检查都没有发现`n`能被任何数整除，则`n`是素数，返回`true`。时间复杂度分析：该算法主要时间消耗在步骤4的循环中。循环次数约为`n/2-2+n/4-2+...+sqrt(n)`。可以证明，这个循环的大致次数是`O(sqrt(n))`。每次循环内的取模操作是`O(1)`。因此，总时间复杂度为`O(sqrt(n))`。这比简单地对所有小于`n`的数进行检查（`O(n)`）要高效得多。八、```javaimportjava.util.HashMap;importjava.util.Map;publicclassCharFrequency{publicstaticvoidmain(String[]args){Strings="hello";Map<Character,Integer>frequencyMap=newHashMap<>();for(charc:s.toCharArray()){//如果字符c已存在于map中，则获取其当前计数并加1//如果字符c不存在，则使用默认值0，然后加1frequencyMap.put(c,frequencyMap.getOrDefault(c,0)+1);}//构建输出字符串StringBuilderresult=newStringBuilder();for(Map.Entry<Character,Integer>entry:frequencyMap.entrySet()){result.append('\'').append(entry.getKey()).append("':").append(entry.getValue()).append(",");}