江苏大学 程序设计与算法/算法设计与分析/数据结构与算法/程序设计与数据结构 期末/考研复试复习

简介: 江苏大学 程序设计与算法/算法设计与分析/数据结构与算法/程序设计与数据结构 期末/考研复试复习

考试范围

1.问答题

2.根据代码写时间复杂度

3.0-1背包问题的分支限界法/回溯法计算实例

4.正确性证明(lcs,不相交区间)

5.动态规划填表(lcs,背包,矩阵)

6.算法设计实践题

一、问答题

 1.什么是最坏情况时间复杂性?什么是平均情况时间复杂性?

最坏情况的时间复杂性是规模为n的所有输入中,基本运算执行次数为最多的时间复杂性。平均时间复杂性是规模为n的所有输入的算法时间复杂性的平均值(假设每种输入情况等概率出现)。

 2.什么是递归算法?什么是递归函数?

 递归:若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的。

 递归算法:直接或间接地调用自身的算法。

 递归函数:用函数自身给出定义的函数。

  3.递归函数的二要素是什么?

 边界条件、递归方程。

  4.分治法的设计思想是什么?

 将要求解的较大规模的问题分割成若干个更小规模的子问题。

 对这若干子问题分别求解。如果子问题的规模仍然不够小,则再划分为若干个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。

 5.什么叫问题的最优子结构性质?

 最优子结构性质:问题的最优解包含着其子问题的最优解。

 6.动态规划基本步骤是什么?

 分解。将原问题可以分解为若干个规模较小的相同问题。

 递归地定义最优值。(相当于分治法中的合并操作)

 以自底向上的方式计算出最优值。

 根据计算最优值时得到的信息,构造最优解。

 7.动态规划算法的基本要素是什么?举例说明一些可以用动态规划算法解决的问题。

 动态规划算法的基本要素是:最优子结构:问题的最优解包含子问题  的最优解、重叠子问题:每次产生的子问题不是新问题,被反复计算多次。

 矩阵连乘、最长公共子序列、0-1背包问题

 8.说明分治法与动态规划法的相同点和不同之处?

 与分治法类似,动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。动态规划法与分治法的一个重要的不同点在于,用分治法分解后得到的子问题通常都是相互独立的,而用动态规划法分解后得到的子问题很多都是重复的。因此,对重复出现的子问题,只是在第一次遇到时才进行计算,然后把计算所得的结果保存起来;当再次遇到该子问题时,就直接引用已保存的结果,而不再重新求解。

 9.贪心算法的两个重要要素是什么?举例说明一些可以用贪心算法解决的问题。

 两个重要要素:贪心选择性质:所求的问题的整体最优解可以通过一系列局部最优的选择达到、最优子结构性质:问题最优解包含子问题最优解。

 活动安排问题、最优装载问题、单源最短路径问题

 10.什么叫贪心选择性质?

 所求问题的整体最优解可以通过一系列的局部最优选择来得到,即贪心选择来达到。

 11.贪心算法与动态规划算法的的相同点和不同之处?

 相同点:都具有最优子结构性质,都用来求解最优化问题。

 不同点:贪心算法具有贪心选择性质,局部最优解能得到整体最优解。动态规划具有重叠子问题性质。

  12.背包问题与0-1背包问题有何区别?

 0-1背包问题物品有两种选择,要么放进去要么不放进去,而背包问题可以放部分,重量的选择可以是非整数

 13.回溯法与分支限界法之间的相同点是什么?不同之处在哪些方面?

 回溯法和分支限界法都需要隐式地构造解空间树并对其进行搜索。回溯法以深度优先的顺序进行搜索,避免不必要的搜索。分支限界法则以广度优先或最小耗费(最大效益优先)的方式搜索解空间树。

  14.分支限界法基本思想是什么?

 分支限界法以广度优先或以最小耗费(最大效益)优先的方式搜索解空间树。扩展子结点时,一次性生成它的所有孩子结点,舍弃不可能导致可行解或最优解的子结点,其余节点进入队列。

 15.常用的剪枝函数有哪两类?

 约束函数剪枝和限界函数剪枝。

  16.约束函数的功能是什么?

 在扩展节点处剪去不满足约束的子树,保留可行解点。

 17.限界函数的功能是什么?

 剪去可行但得不到最优解的子树。

  18.常见的两种分支限界法是什么?

 (1)队列式(FIFO)分支限界法

按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。

  (2)优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

  19.什么是P问题和NP问题?

 如果一个问题可以找到一个能在多项式时间里解决它的算法,那么这个问题就属于P问题。

 NP问题不是非P类问题,是多项式复杂程度的非确定性问题。 是指可以在多项式的时间里验证一个解的问题。

 20.回溯法中剪枝函数有哪几类?各有何用途?

 约束函数:用约束函数在扩展结点处剪去不满足约束的子树,保留可行节点;

 限界函数:用限界函数剪去得不到最优解的子树。

 21.什么是NP完全问题?

  NP完全问题又叫NPC问题。同时满足下面两个条件的问题就是NPC问题。

 第一条,它是一个NP问题;

 第二条,所有的NP问题都可以约化到它。

  22.子集树和排列树。

 都是回溯法的状态空间树。

 子集树:从n个元素组成的集合S中找出S满足某种性质的子集时,相应的解空间树。

 排列树:当所给问题是确定n个元素满足某种性质的排列时,相应解空间树为排列数。

二、时间复杂度计算

1.动态规划、贪心:

最内层循环次数。

image.png


5.递归

image.png


三、证明:

活动安排问题

image.png


最长公共子序列问题


image.png

四、动态规划填表:

最长公共子序列:

从左至右、从上往下更新。

0-1背包:

从左至右、从下往上更新。w为重量/体积,v为价值。

image.png


矩阵连乘:

image.png

五、实践题

1.棋盘覆盖

算法设计与分析/数据结构与算法实验1:棋盘覆盖问题

2.循环赛安排

算法设计与分析/数据结构与算法实验2:循环赛安排问题

3.矩阵连乘

算法设计与分析/数据结构与算法实验3:矩阵连乘问题

4.添加括号数目问题

算法设计与分析/数据结构与算法实验4:添加括号数目问题

5.找新数

算法设计与分析/数据结构与算法实验5:找新数最小的删除方案

6.0-1背包问题(回溯法)

算法设计与分析/数据结构与算法实验6:0-1背包问题(回溯法)

7.0-1背包问题(分支限界法)

算法设计与分析/数据结构与算法实验7:0-1背包问题(分支限界法)


目录
相关文章
|
21天前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
45 4
|
16天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
49 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
19天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
18 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
4天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
12天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
28 4
|
19天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
13 0
数据结构与算法学习十四:常用排序算法总结和对比
|
19天前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
26 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
23天前
|
机器学习/深度学习 存储 算法
【数据结构与算法基础】——算法复杂度
【数据结构与算法基础】——算法复杂度
|
10天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
20 0
|
16天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
22 0