算法习题

算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。

以下是一些典型的算法设计与分析习题及其答案。

习题1：二分查找算法问题描述：给定一个已排序的整数数组，编写一个函数来查找一个目标值是否存在于数组中。

答案：二分查找算法的基本思想是将数组分成两半，比较中间元素与目标值的大小，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

这个过程会不断重复，直到找到目标值或搜索范围为空。

```pythondef binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return Trueelif arr[mid] < target:low = mid + 1else:high = mid - 1return False```习题2：归并排序算法问题描述：给定一个无序数组，使用归并排序算法对其进行排序。

答案：归并排序是一种分治算法，它将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。

```pythondef merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1arr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print("Sorted array is:", arr)```习题3：动态规划求解最长公共子序列问题问题描述：给定两个序列，找到它们的最长公共子序列。

算法练习题---算法概述一、选择题1、下面关于算法的描述，正确的是（）A、一个算法只能有一个输入B、算法只能用框图来表示C、一个算法的执行步骤可以是无限的D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（）A、设计算法，编写程序，提出问题，运行程序，得到答案B、分析问题，编写程序，设计算法，运行程序，得到答案C、分析问题，设计算法，编写程序，运行程序，得到答案D、设计算法，提出问题，编写程序，运行程序，得到答案3、下面说法正确的是（）A、算法+数据结构=程序B、算法就是程序C、数据结构就是程序D、算法包括数据结构4、衡量一个算法好坏的标准是（）。

A、运行速度快B、占用空间少C、时间复杂度低D、代码短5、解决一个问题通常有多种方法。

若说一个算法“有效”是指( )。

A、这个算法能在一定的时间和空间资源限制内将问题解决B、这个算法能在人的反应时间内将问题解决C、这个算法比其他已知算法都更快地将问题解决D、A和C6、算法分析中，记号O表示（），记号Ω表示（）。

A.渐进下界B.渐进上界C.非紧上界D.非紧下界7、以下关于渐进记号的性质是正确的有：（）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ⇒=ΘB.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==⇒=C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})D.f(n)O(g(n))g(n)O(f(n))=⇔=8、记号O的定义正确的是（）。

A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤f(n) ≤cg(n) }；B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤f(n) }；C. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有0 ≤f(n)<cg(n) }；D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) <f(n) }；9、记号Ω的定义正确的是（）。

平均情况:设待查找的元素在数组中的概率为P，不在数组中的概率为1-P,若出现在数组中每个位置的概率是均等的为p/nT(n)=P1D1+P2D2+...+PiDi+(1-P)Dn+1=p/2+n(1-p/2)1.叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。

答:分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 动态规划将待求解的问题分解成若干的子问题，自底向上地通过求解子问题的解得到原问题的解。

动态规划将每个子问题只求解一次并将其解保存在一个表格中,当需要再次求解此子问题时,只是简单的通过查表过的该子问题的解,避免了大量的重复计算.异同：分治法求解的问题分解后的子问题都是独立的，而使用动态规划求解的问题分解后得到的子问题往往不是相互独立的。

分治法是自顶向下用递归的方法解决问题，而动态规划则是自底向上非递归解决问题。

1.简述分治算法求解过程的三个阶段。

答:（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。

（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。

（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。

2.叙述分治法的基本思想，并分析分治法与减治法二者的区别。

答：分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解.区别：分治法是把一个大问题划分成若干个子问题，分别求解各个子问题，然后把子问题的解进行合并并得到原问题的解。

减治法同样是把一个大问题划分成若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。

算法练习题1. 斐波那契数列：1 1 2 3 5 8 13 21 …… 求第20个数；2. 今有雉兔同笼，上有三⼗五头，下有九⼗四⾜，问雉兔各⼏何？3. 求1000以内的⽔仙花数4. 求⼀个数的阶乘5. 求多个连续数的阶乘之和6. 如果今天是星期⼆，那么1000天后是星期⼏？⽤户输⼊⼀个天数，计算这个天数后是星期⼏？7. 苹果3元⼀个，鸭梨2元⼀个，桃⼦1元⼀个。

现在想⽤200元买100个⽔果，在控制台中列出所有可能性8. 求任意⼀个⼩于100000的正整数的位数，并逆序打印每⼀位数字⽐如：567，位数是3位，以此打印7 ，6 ，59. 有⼀分数序列：2/1，3/2，5/3，8/5，13/8，21/13...求出这个数列的前20项之和。

程序分析：请抓住分⼦与分母的变化规律。

10. 有⼀些苹果，每⼈分5个多1个，每⼈分6个多2个，每⼈分7个多3个，⼀共有多少个苹果11. 判断⼀个数字是不是素数12. 利⽤条件运算符的嵌套来完成此题：学习成绩>=90分的同学⽤A表⽰，60-89分之间的⽤B表⽰，60分以下的⽤C表⽰。

1.程序分析：(a>b)?a:b这是条件运算符的基本例⼦。

13. 求s=a+aa+aaa+aaaa+aa...a的值，其中a是⼀个数字。

例如2+22+222+2222+22222(此时共有5个数相加)，⼏个数相加由⽤户输⼊（prompt）14. ⼀球从100⽶⾼度⾃由落下，每次落地后反跳回原⾼度的⼀半；再落下，求它在第10次落地时，共经过多少⽶？第10次反弹多⾼？15. 求10000以内的完美数如果⼀个数恰好等于它的约数之和，则称该数位“完美数”。

16. 寻找丑数题⽬：我们把只包含因⼦2、3 和5 的数称作丑数（Ugly Number）。

例如6、8 都是丑数，但14 不是，因为它包含因⼦7。

习惯上我们把1 当做是第⼀个丑数。

求按从⼩到⼤的顺序的第1500 个丑数。

17. 猴⼦吃桃问题：猴⼦第⼀天摘下若⼲个桃⼦，当即吃了⼀半，还不瘾，⼜多吃了⼀个第⼆天早上⼜将剩下的桃⼦吃掉⼀半，⼜多吃了⼀个。

算法习题算法设计与分析试卷⼀、填空题（20分，每空2分）1、算法的性质包括输⼊、输出、确定性、有限性。

2、动态规划算法的基本思想就将待求问题分解成若⼲个⼦问题、先求解⼦问题，然后从这些⼦问题的解得到原问题的解。

3、设计动态规划算法的4个步骤：（1）找出最优解的性质，并刻画其结构特征。

（2）递归地定义最优值。

（3）以⾃底向上的⽅式计算出最优值。

（4）根据计算最优值得到的信息，构造最优解。

4、流⽔作业调度问题的johnson算法：（1）令N1={i|ai=bj};（2）将N1中作业依ai的ai的⾮减序排序；将N2中作业依bi的⾮增序排序。

5、对于流⽔作业⾼度问题，必存在⼀个最优调度π，使得作业π（i）和π（i+1）满⾜Johnson不等式min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}。

6、最优⼆叉搜索树即是最⼩平均查找长度的⼆叉搜索树。

⼆、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最⼤⼦段和为∑ak(2<=k<=4)=20（5分）2、由流⽔作业调度问题的最优⼦结构性质可知，T（N，0）=min{ai+T(N-{i},bi)}(1=3、最⼤⼦段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj){Int sum=0;for (int i=1;i<=n;i++)for (int j=i;j<=n;j++)int thissum=0;for(int k=i;k<=j;k++)this sum+=a[k];if(thissum>sum){sum=thissum;besti=i；bestj=j;}}return sum;}4、设计最优⼆叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w){for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]= 0;}for(int r=0;rfor(int i=1;i<=n-r;i++){int j=i+r;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]= m[i+1][j];s[i][j]=i;for(int k=i+1;k<=j;k++){int t=m[i][k-1]+m[k+1][j];if(t}m[i][j]=t; s[i][j]=k;}}5、设n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) ⽤两种⽅法求4个作业的最优调度⽅案并计算其最优值？（15分）法⼀：min(ai,bj)<=min(aj,bi)因为min(a1,b2)<=min(a2,b1)所以1→2 (先1后2)由min(a1,b3)<=min(a3,b1)得1→3 （先1后3）同理可得：最后为1→3→4→2法⼆：johnson算法思想N1＝{1，3，4} N2＝{2}N11＝{1，3，4} N12＝{2}所以N11→N12得：1→3→4→2三、简答题（30分）1、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最⼤⼦段和，则a[1:n]的最⼤⼦段和有哪三种情形？(10分)答：（1）a[1:n]的最⼤⼦段和与a[1:n/2]的最⼤⼦段和相同。

算法练习题一、基础算法1. 编写一个程序，实现一个冒泡排序算法。

2. 实现一个选择排序算法。

3. 实现一个插入排序算法。

4. 编写一个函数，计算一个整数数组中的最大值和最小值。

5. 编写一个函数，实现二分查找算法。

6. 编写一个函数，实现快速排序算法。

7. 编写一个函数，判断一个整数是否为素数。

8. 编写一个函数，实现反转一个整数数组。

9. 编写一个函数，计算两个整数数组的交集。

10. 编写一个函数，判断一个字符串是否为回文。

二、数据结构11. 实现一个单链表的基本操作，包括插入、删除、查找。

12. 实现一个双向链表的基本操作，包括插入、删除、查找。

13. 实现一个栈的基本操作，包括压栈、出栈、查看栈顶元素。

14. 实现一个队列的基本操作，包括入队、出队、查看队首元素。

15. 实现一个二叉树的基本操作，包括插入、删除、查找。

16. 实现一个二叉搜索树的基本操作，包括插入、删除、查找。

17. 实现一个哈希表的基本操作，包括插入、删除、查找。

三、搜索与图论18. 编写一个程序，实现深度优先搜索（DFS）算法。

19. 编写一个程序，实现广度优先搜索（BFS）算法。

20. 编写一个程序，求解迷宫问题。

21. 编写一个程序，计算一个有向图的拓扑排序。

22. 编写一个程序，计算一个无向图的欧拉回路。

23. 编写一个程序，计算一个加权无向图的最小树（Prim算法）。

24. 编写一个程序，计算一个加权有向图的最短路径（Dijkstra算法）。

25. 编写一个程序，计算一个加权有向图的所有顶点对的最短路径（Floyd算法）。

四、动态规划26. 编写一个程序，实现背包问题。

27. 编写一个程序，计算最长公共子序列（LCS）。

28. 编写一个程序，计算最长递增子序列（LIS）。

29. 编写一个程序，实现编辑距离（Levenshtein距离）。

30. 编写一个程序，实现硬币找零问题。

31. 编写一个程序，实现矩阵链乘问题。

算法复杂度习题一、选择题1.个算法应该是（）。

A.程序B.问题求解步骤的描述C.要满足五个基本特性D. A和C 2.某算法的时间复杂度为O(n2)，表明该算法的（）。

A.问题规模是n2 B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比3.以下算法的时间复杂度为（）。

void fun(int n) { int i=l;while(i<=n) i=i*2; }A. O(n)B. O(n2)C. O(nlog2n)D. O(log2n)4.【2021年计算机联考真题】设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

x=2;while(xA. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 5.【2021年计算机联考真题】求整数n (n>=0)阶乘的算法如下，其时间复杂度是（）。

intfact(int n){ if (n<=l) return 1; return n*fact(n-1); } A. O(log2n) B.O(n) C. O(nlog2n) D. O(n2) 6.有以下算法，其时间复杂度为（）。

voidfun (int n){ int i=0; while(i*i*i<=n) i++; } A. O(n) B.O(nlogn) C. D. 7.程序段 for(i=n-l;i>l;i--) for(j=1;jA[j+l]) A[j]与 A[j+1]对换; 其中n为正整数，则最后一行的语句频度在最坏情况下是（）。

A.O(n) B. O(nlogn) C. O(n3) D. O(n2) 8.以下算法中加下划线语句的执行次数为（）。

int m=0, i, j; for(i=l;i<=n;i++) for(j=1;j<=2*i;j++)m++; A. n(n+1) B. n C. n+1 D. n2 9.下面说法错误的是（）。

一、选择题1、衡量一个算法好坏的标准是（ ）。

（A ）运行速度快 （B ）占用空间少 （C ）时间复杂度低 （D ）代码短2、函数n n 1032 的渐进表达式是（ ）。

（A ）O(23n ) （B ）O(3) （C ）O(n 10) （D ）O(2n )3、以下不可以使用分治法求解的是（ ）。

（A ）棋盘覆盖问题 （B ）选择问题 （C ）归并排序 （D ） 0/1背包问题4、二分搜索算法是利用（ ）实现的算法。

（A ）分治策略 （B ）动态规划法 （C ）贪心法 （D ）回溯法5、二分搜索算法的时间复杂性为（ ）。

（A ）O(2n ) （B ）O(n ) （C ）O(n log ) （D ）O(n n log )6、快速排序算法的时间复杂性为（ ）。

（A ）O(2n ) （B ）O(n ) （C ）O(n log ) （D ）O(n n log )7、实现大整数的乘法是利用（ ）的算法。

（A ）分治策略 （B ）动态规划法 （C ）贪心法 （D ）回溯法8、矩阵连乘问题的算法可由（ ）设计实现。

（A ）分支界限算法 （B ）动态规划算法 （C ）贪心算法 （D ）回溯算法9、实现循环赛日程表利用的算法是（ ）。

（A ）分治策略 （B ）动态规划法 （C ）贪心法（D ）回溯法10、下列是动态规划算法基本要素的是（ ）。

（A ）定义最优解 （B ）构造最优解 （C ）算出最优解 （D ）子问题重叠性质11、最长公共子序列算法利用的算法是（ ）。

（A ）分治法 （B ）动态规划法 （C ）贪心法 （D ）回溯法12、下列算法中通常以自底向上的方式求解最优解的是（ ）。

（A ）备忘录法 （B ）动态规划法 （C ）贪心法 （D ）回溯法13、以下不可以使用分治法求解的是（ ）。

（A ）棋盘覆盖问题 （B ）选择问题 （C ）归并排序 （D ）0/1背包问题14、下列算法中不能解决0/1背包问题的是（ ）（A ）贪心法 （B ）动态规划 （C ）回溯法 （D ）分支限界法15、算法是由若干条指令组成的有穷序列，而且满足以下性质（ ）（A ）输入：有0个或多个输入 （B ）输出：至少有一个输出（C ）确定性：指令清晰，无歧义 （D ）有限性：指令执行次数有限，而且执行时间有限A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)16、函数32n +10nlog n 的渐进表达式是( ).A. 2nB. 32nC. nlog nD. 10nlog n17、能采用贪心算法求最优解的问题，一般具有的重要性质为：（ ）（A ）最优子结构性质与贪心选择性质 （B ）重叠子问题性质与贪心选择性质（C ）最优子结构性质与重叠子问题性质 （D ）预排序与递归调用18、回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

人工智能核心算法复习题含答案一、单选题（共40题，每题1分，共40分）1、假设我们有一个使用ReLU激活函数(ReLU activation function)的神经网络，假如我们把ReLU激活替换为线性激活，那么这个神经网络能够模拟出同或函数(XNOR function)吗A、可以B、不能C、不好说D、不一定正确答案：B2、EM算法是（）A、半监督B、都不是C、有监督D、无监督正确答案：D3、让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是(___)？A、监督学习B、倍监督学习C、无监督学习D、半监督学习正确答案：D4、YOLOv3在coco数据集上聚类了（）个矛框？A、9B、nanC、80D、3正确答案：A5、在一个神经网络中，知道每一个神经元的权重和偏差是最重要的一步。

如果知道了神经元准确的权重和偏差，便可以近似任何函数，但怎么获知每个神经的权重和偏移呢？A、以上都不正确的B、搜索每个可能的权重和偏差组合，直到得到最佳值C、随机赋值，听天由命D、赋予一个初始值，然后检查跟最佳值的差值，不断迭代调整权重正确答案：D6、执行完语句X_train, X_test, y_train, y_test = train_test_split( ... iris.data, iris.target, test_size=0.4, random_state=0),训练集占比多少?A、50%B、70%C、60%D、40%正确答案：C7、如果一个模型在测试集上偏差很大，方差很小，则说明该模型?A、过拟合B、刚好拟合C、可能过拟合可能欠拟合D、欠拟合正确答案：C8、下列哪个神经网络结构会发生权重共享A、卷积神经网络B、循环神经网络C、全连接神经网络D、卷积和循环神经网络正确答案：D9、混沌度(Perplexity)是一种常见的应用在使用深度学习处理NLP问题过程中的评估技术，关于混沌度，哪种说法是正确的？A、混沌度越高越好B、混沌度对于结果的影响不一定C、混沌度没什么影响D、混沌度越低越好正确答案：D10、关于递归函数基例的说明，以下选项中错误的是A、递归函数的基例不再进行递归B、每个递归函数都只能有一个基例C、递归函数的基例决定递归的深度D、递归函数必须有基例正确答案：B11、通过以下哪些指标我们可以在层次聚类中寻找两个集群之间的差异？（）A、以上都行B、均链接C、单链接D、全链接正确答案：A12、考虑以下问题：假设我们有一个5层的神经网络，这个神经网络在使用一个4GB显存显卡时需要花费3个小时来完成训练。

数据结构与算法练习题库（含答案）一、单选题（共80题，每题1分，共80分）1、对一棵二叉树的结点从 1 开始顺序编号。

要求每个结点的编号大于其左子树所有结点的编号、但小于右子树中所有结点的编号。

可采用▁▁▁▁▁ 实现编号。

A、中序遍历B、先序遍历C、层次遍历D、后序遍历正确答案：A2、设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？A、5B、4C、2D、0正确答案：C3、两个有相同键值的元素具有不同的散列地址A、一定不会B、一定会C、可能会D、有万分之一的可能会正确答案：C4、将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。

散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。

问：当第一次发现有冲突时，散列表的装填因子大约是多少？A、0.73B、0.27C、0.64D、0.45正确答案：D5、对N个记录进行归并排序，归并趟数的数量级是：A、O(NlogN)B、O(logN)C、O(N)D、O(N2)正确答案：B6、下列说法不正确的是：A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、图的深度遍历不适用于有向图C、遍历的基本算法有两种：深度遍历和广度遍历D、图的深度遍历是一个递归过程正确答案：B7、二叉树的中序遍历也可以循环地完成。

给定循环中堆栈的操作序列如下（其中push为入栈，pop为出栈）： push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()A、6是根结点B、2是4的父结点C、2和6是兄弟结点D、以上全不对正确答案：C8、设最小堆（小根堆）的层序遍历结果为{1, 3, 2, 5, 4, 7, 6}。