算法和程序设计分析及试题附答案_08-算法和程序设计

12、在调试程序的时候，经常要设置断点，设置断点的快捷键是（）高一第二学期《算法与程序设计》学分认定试题A、F1B、F8C、F9D、F1213、算法描述可以有多种表达方法，下面哪些方法不可以描述“闰年问题”的算法（）学校：_____________ 班级：____________ 学号：____________ 姓名：____________ A、自然语言B、流程图C、伪代码D、机器语言14、以下不属于非法用户自定义标识符（常量和变量命名）的是（）一、单选题（每小题 3 分，20 小题，共60 分）A、8adB、ad8C、_a8dD、const1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于15、已知A，B，C，D 是整型变量，且都已有互不相同的值，执行语句B=0；A=C ；D=A ；D=B ；后，其值相等的用计算机解决问题的哪一个步骤？（）变量是（）A、分析问题B、设计算法C、编写程序D、调试程序A、A，DB、A，CC、C，BD、B，A2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（）16、要交换变量 A 和B 的值，应使用的语句组是( )A、编译错误B、执行错误C、逻辑错误D、任何错误计算机都能检查出来A、A=B ；B=C；C=AB、C=A ；A=B ；B=C3、下列关于算法的叙述中，错误的是（）C、A=B ；B=AD、C=A ；B=A ；B=CA、一个算法至少有一个输入和一个输出17、Visual Basic 中以单引号开头一行文字称为注释，它对程序的运行（）B、算法的每一个步骤必须确切地定义A、起一定作用 B 、有时候起作用C、一个算法在执行有穷步之后必须结束C、不起任何作用，但是必须的D、不起任何作用，但能增加程序的可阅读性D、算法中有待执行的运算和操作必须是相当基本的。

18、要使一个命令按钮显示文字“确定”，正确的设置是把该命令按钮的（）。

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

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

习题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. 以下是一道经典的算法题，请编写代码实现求最大公约数（GCD）的算法。

```pythondef gcd(a, b):if b == 0:return areturn gcd(b, a % b)# 测试print(gcd(15, 25)) # 输出 5print(gcd(54, 72)) # 输出 18```解析：这是一个使用递归实现的辗转相除法算法，也叫欧几里得算法。

当两个数 a 和 b 求最大公约数时，如果 b 等于 0，则 a 就是最大公约数；否则，将 b 作为新的 a，将 a 除以 b 的余数作为新的 b 进行递归计算。

2. 请编写代码实现一个链表的反转。

```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_linked_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev# 测试node1 = ListNode(1)node2 = ListNode(2)node3 = ListNode(3)node1.next = node2node2.next = node3reversed_head = reverse_linked_list(node1)while reversed_head:print(reversed_head.val)reversed_head = reversed_head.next```解析：这是一个经典的链表反转算法。

使用 prev、curr、next_node 三个指针来实现，其中 prev 用于保存上一个节点，curr 用于保存当前节点，next_node 用于保存下一个节点。

2009级高一算法与程序设计（选修模块）考试题满分：70分时量：60分钟笔试2010.6一、单选题（每题2分，共40分）1、0518号台风“达维”过后，要对各个单位捐款救灾情况进行分组制表，并进行积分排序，一般使用的专业电子处理软件有（）A、powerpoingB、ExcelC、WordD、Visual Basic2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（）A、设计算法，编写程序，提出问题，运行程序，得到答案B、分析问题，编写程序，设计算法，运行程序，得到答案C、分析问题，设计算法，编写程序，运行程序，得到答案D、设计算法，提出问题，编写程序，运行程序，得到答案3、交通警察到达案发现场，一般按照下列哪种思路开展工作（）①观察、分析现场②收集必要的信息③进行判断、推理④按一定的方法和步骤解决A、②①③④B、①③②④C、③①②④D、①②③④4、下面说法正确的是（）A、算法+数据结构=程序B、算法就是程序C、数据结构就是程序D、算法包括数据结构5、下列常量说明中，符合语法的是（）A、CONST color=redB、CONST const=10*5C、CONST xl：=3.9；D、CONST color=”abcd”6、VB中将两个字符串连接起来的运算符有：+和&，那么“123”+45结果是（）A、168B、12345C、”123”D、457、字符串”ABCD”和字符串”DCBA”进行比较，如果让比较的结果为真，应选用关系运算符（）A、>B、<C、=D、>=8、设a，b，c，d，e均为整型变量，且a=13，b=2，c=10，d=3，e=2，则表达式“a -b*c \ d MOD e”的值是( )A、13B、-7C、llD、09、已知A，B，C，D是简单变量，且都已有互不相同的值，执行语句B=8；A=C；D =A；D=B；后，其值相等的变量是（）A、A，DB、A，CC、C，BD、B，A10、结构化程序设计由三种基本结构组成，下面哪个不属于这三种基本结构（）A、顺序结构B、输入、输出结构C、选择结构D、循环结构11、下列结果为真的关系表达式是（）A、”A”<100B、23.5<20C、23<45 AND 72>8D、5<X<2012、以下运算符中运算优先级最高的是（）A、+B、ORC、>D、\13、整除运算时，若运算量为实数，则先取整，后相除，结果为整型或长整型。

计算机算法设计与分析习题及答案一．选择题1、二分搜索算法是利用 A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是 A ;A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是A 的一搜索方式;A、分支界限法B、动态规划法C、贪心法D、回溯法4. 回溯法解旅行售货员问题时的解空间树是 A ;A、子集树B、排列树C、深度优先生成树D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是B ;A、备忘录法B、动态规划法C、贪心法D、回溯法6、衡量一个算法好坏的标准是 C ;A 运行速度快B 占用空间少C 时间复杂度低D 代码短7、以下不可以使用分治法求解的是 D ;A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题8. 实现循环赛日程表利用的算法是A ;A、分治策略B、动态规划法C、贪心法D、回溯法9．下面不是分支界限法搜索方式的是D ;A、广度优先B、最小耗费优先C、最大效益优先D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是D ;A、备忘录法B、动态规划法C、贪心法D、回溯法11.备忘录方法是那种算法的变形; BA、分治法B、动态规划法C、贪心法D、回溯法12．哈夫曼编码的贪心算法所需的计算时间为B ;A、On2nB、OnlognC、O2nD、On13．分支限界法解最大团问题时,活结点表的组织形式是B ;A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是B;A、分支界限法B、动态规划法C、贪心法D、回溯法15．实现棋盘覆盖算法利用的算法是A ;A、分治法B、动态规划法C、贪心法D、回溯法16.下面是贪心算法的基本要素的是C ;A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解17.回溯法的效率不依赖于下列哪些因素 DA.满足显约束的值的个数B. 计算约束函数的时间C.计算限界函数的时间D. 确定解空间的时间18.下面哪种函数是回溯法中为避免无效搜索采取的策略BA．递归函数 B.剪枝函数 C;随机数函数 D.搜索函数19. D是贪心算法与动态规划算法的共同点;A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质20. 矩阵连乘问题的算法可由 B 设计实现;A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法21. 分支限界法解旅行售货员问题时,活结点表的组织形式是 A ;A、最小堆B、最大堆C、栈D、数组22、Strassen矩阵乘法是利用A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法23、使用分治法求解不需要满足的条件是 A ;A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解24、下面问题 B 不能使用贪心法解决;A 单源最短路径问题B N皇后问题C 最小生成树问题D 背包问题25、下列算法中不能解决0/1背包问题的是 AA 贪心法B 动态规划C 回溯法D 分支限界法26、回溯法搜索状态空间树是按照 C 的顺序;A 中序遍历B 广度优先遍历C 深度优先遍历D 层次优先遍历27．实现合并排序利用的算法是A ;A、分治策略B、动态规划法C、贪心法D、回溯法28．下列是动态规划算法基本要素的是D ;A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质29．下列算法中通常以自底向下的方式求解最优解的是 B ;A、分治法B、动态规划法C、贪心法D、回溯法30．采用广度优先策略搜索的算法是A ;A、分支界限法B、动态规划法C、贪心法D、回溯法31、合并排序算法是利用 A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法32、背包问题的贪心算法所需的计算时间为 BA、On2nB、OnlognC、O2nD、On33．实现大整数的乘法是利用的算法C ;A、贪心法B、动态规划法C、分治策略D、回溯法34．0-1背包问题的回溯算法所需的计算时间为AA、On2nB、OnlognC、O2nD、On35．采用最大效益优先搜索方式的算法是A;A、分支界限法B、动态规划法C、贪心法D、回溯法36．贪心算法与动态规划算法的主要区别是B;A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解37. 实现最大子段和利用的算法是B ;A、分治策略B、动态规划法C、贪心法D、回溯法38.优先队列式分支限界法选取扩展结点的原则是 C ;A、先进先出B、后进先出C、结点的优先级D、随机39.背包问题的贪心算法所需的计算时间为 B ;A、On2nB、OnlognC、O2nD、On40、广度优先是A 的一搜索方式;A、分支界限法B、动态规划法C、贪心法D、回溯法41. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的 B ;A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解42．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序,故算法的时间复杂度为 B ;A 、On2nB 、OnlognC 、O2nD 、On43. 以深度优先方式系统搜索问题解的算法称为 D ;A 、分支界限算法B 、概率算法C 、贪心算法D 、回溯算法44. 实现最长公共子序列利用的算法是B ;A 、分治策略B 、动态规划法C 、贪心法D 、回溯法45. Hanoi 塔问题如下图所示;现要求将塔座A 上的的所有圆盘移到塔座B 上,并仍按同样顺序叠置;移动圆盘时遵守Hanoi 塔问题的移动规则;由此设计出解Hanoi 塔问题的递归算法正确的为：B46. 动态规划算法的基本要素为 CA. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 47. 能采用贪心算法求最优解的问题,一般具有的重要性质为： AA. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用48. 回溯法在问题的解空间树中,按 D 策略,从根结点出发搜索解空间树;A.广度优先B. 活结点优先C.扩展结点优先D. 深度优先49. 分支限界法在问题的解空间树中,按 A 策略,从根结点出发搜索解空间树;A.广度优先B. 活结点优先C.扩展结点优先D. 深度优先50. 程序块 A 是回溯法中遍历排列树的算法框架程序;A.B. C. D. 51. 常见的两种分支限界法为DA. 广度优先分支限界法与深度优先分支限界法；B. 队列式FIFO 分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式FIFO 分支限界法与优先队列式分支限界法；1.算法的复杂性有 时间 复杂性和 空间 ;2、程序是 算法用某种程序设计语言的具体实现;3、算法的“确定性”指的是组成算法的每条 指令 是清晰的,无歧义的;4. 矩阵连乘问题的算法可由 动态规划 设计实现;5、算法是指解决问题的 一种方法 或 一个过程 ;6、从分治法的一般设计模式可以看出,用它设计出的程序一般是 递归算法 ;7、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征;8、以深度优先方式系统搜索问题解的算法称为 回溯法 ;9、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步; Hanoi 塔A. void hanoiint n, int A, int C, int B{ if n > 0{ hanoin-1,A,C, B;moven,a,b; hanoin-1, C, B, A; }} B. void hanoiint n, int A, int B, int C { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } }C. void hanoiint n, int C, int B, int A { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } }D. void hanoiint n, int C, int A, int B { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } } void backtrack int t{ if t>n outputx; else for int i=t;i<=n;i++ { swapxt, xi; if legalt backtrackt+1; swapxt, xi; } } void backtrack int t { if t>n outputx;elsefor int i=0;i<=1;i++ { xt=i; if legalt backtrackt+1; } }void backtrack int t { if t>n outputx; else for int i=0;i<=1;i++ { xt=i; if legalt backtrackt-1; } }voidbacktrack int t{ if t>n outputx; else for int i=t;i<=n;i++ { swapxt, xi; if legalt backtrackt+1;}}10、解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是动态规划 ,需要排序的是回溯法 ,分支限界法 ;11、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ,只使用约束条件进行裁剪的是 N皇后问题 ;12、贪心选择性质是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别;13、矩阵连乘问题的算法可由动态规划设计实现;14.贪心算法的基本要素是贪心选择性质和最优子结构性质 ;15. 动态规划算法的基本思想是将待求解问题分解成若干子问题 ,先求解子问题 ,然后从这些子问题的解得到原问题的解;16.算法是由若干条指令组成的有穷序列,且要满足输入、输出、确定性和有限性四条性质;17、大整数乘积算法是用分治法来设计的;18、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法 ;19、贪心选择性质是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别;20.快速排序算法是基于分治策略的一种排序算法;21.动态规划算法的两个基本要素是. 最优子结构性质和重叠子问题性质 ;22.回溯法是一种既带有系统性又带有跳跃性的搜索算法;23.分支限界法主要有队列式FIFO 分支限界法和优先队列式分支限界法;24.分支限界法是一种既带有系统性又带有跳跃性的搜索算法;25.回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数 ;26.任何可用计算机求解的问题所需的时间都与其规模有关;27.快速排序算法的性能取决于划分的对称性 ;28.所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到 ;29.所谓最优子结构性质是指问题的最优解包含了其子问题的最优解 ;30.回溯法是指具有限界函数的深度优先生成法 ;31.用回溯法解题的一个显着特征是在搜索过程中动态产生问题的解空间;在任何时刻,算法只保存从根结点到当前扩展结点的路径;如果解空间树中从根结点到叶结点的最长路径的长度为hn,则回溯法所需的计算空间通常为 Ohn ;32.回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架;33.用回溯法解0/1背包问题时,该问题的解空间结构为子集树结构;34.用回溯法解批处理作业调度问题时,该问题的解空间结构为排列树结构;35.旅行售货员问题的解空间树是排列树 ;三、算法填空1.背包问题的贪心算法void Knapsackint n,float M,float v,float w,float x{//重量为w1..n,价值为v1..n的 n个物品,装入容量为M的背包//用贪心算法求最优解向量x1..nint i; Sortn,v,w;for i=1;i<=n;i++ xi=0;float c=M;for i=1;i<=n;i++{if wi>c break;xi=1;c-=wi;}if i<=n xi=c/wi;}2.最大子段和: 动态规划算法int MaxSumint n, int a{int sum=0, b=0； //sum存储当前最大的bj, b存储bjfor int j=1； j<=n； j++{ if b>0 b+= aj ；else b=ai; ； //一旦某个区段和为负,则从下一个位置累和 ifb>sum sum=b;}return sum；}3.贪心算法求活动安排问题template<class Type>void GreedySelector int n, Type s, Type f, bool A{A1=true;int j=1;for int i=2;i<=n;i++if si>=fj{ Ai=true;j=i;}else Ai=false;}4.快速排序template<class Type>void QuickSort Type a, int p, int r{if p<r{int q=Partitiona,p,r;QuickSort a,p,q-1; //对左半段排序QuickSort a,q+1,r; //对右半段排序}}5. 回溯法解迷宫问题迷宫用二维数组存储,用'H'表示墙,'O'表示通道int x1,y1,success=0; //出口点void MazePathint x,int y{//递归求解:求迷宫maze从入口x,y到出口x1,y1的一条路径mazexy=''; //路径置为if x==x1&&y==y1 success=1; //到出口则成功else{if mazexy+1=='O' MazePathx,++y;//东邻方格是通路,向东尝试if success&&mazex+1y=='O' MazePath++x,y;//不成功且南邻方格是通路,向南尝试if success&&mazexy-1=='O' MazePathx,--y;//不成功且西邻方格是通路,向西尝试if success&&mazex-1y=='O' MazePath--x,y;//不成功且北邻方格是通路,向北尝试}if success mazexy=''; //死胡同置为}四、算法设计题1. 给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素x,返回其在数组中的位置,如果未找到返回-1;写出二分搜索的算法,并分析其时间复杂度;template<class Type>int BinarySearchType a, const Type& x, int n{//在a0:n中搜索x,找到x时返回其在数组中的位置,否则返回-1Int left=0; int right=n-1;While left<=right{int middle=left+right/2;if x==amiddle return middle;if x>amiddle left=middle+1;else right=middle-1;}Return -1;}时间复杂性为Ologn2. 利用分治算法写出合并排序的算法,并分析其时间复杂度void MergeSortType a, int left, int right{if left<right {//至少有2个元素int i=left+right/2; //取中点mergeSorta, left, i;mergeSorta, i+1, right;mergea, b, left, i, right; //合并到数组bcopya, b, left, right; //复制回数组a}}算法在最坏情况下的时间复杂度为Onlogn;3.N皇后回溯法bool Queen::Placeint k{ //检查xk位置是否合法for int j=1;j<k;j++if absk-j==absxj-xk||xj==xk return false;return true;}void Queen::Backtrackint t{if t>n sum++;else for int i=1;i<=n;i++{xt=i;if 约束函数 Backtrackt+1;}}4.最大团问题void Clique::Backtrackint i // 计算最大团{ if i > n { // 到达叶结点for int j = 1; j <= n; j++ bestxj = xj;bestn = cn; return;}// 检查顶点 i 与当前团的连接int OK = 1;for int j = 1; j < i; j++if xj && aij == 0 // i与j不相连{OK = 0; break;}if OK { // 进入左子树xi = 1; cn++;Backtracki+1;xi = 0; cn--; }if cn+n-i>bestn { // 进入右子树xi = 0;Backtracki+1; }}5. 顺序表存储表示如下：typedef struct{RedType rMAXSIZE+1; //顺序表int length; //顺序表长度}SqList;编写对顺序表L进行快速排序的算法;int PartitionSqList &L,int low,int high //算法10.6b{//交换顺序表L中子表L.rlow..high的记录,枢轴记录到位,并返回其所在位置, //此时在它之前后的记录均不大小于它.int pivotkey;L.r0=L.rlow; //用子表的第一个记录作枢轴记录pivotkey=L.rlow.key; //枢轴记录关键字while low<high //从表的两端交替地向中间扫描{while low<high&&L.rhigh.key>=pivotkey --high;L.rlow=L.rhigh; //将比枢轴记录小的记录移到低端while low<high&&L.rlow.key<=pivotkey ++low;L.rhigh=L.rlow; //将比枢轴记录大的记录移到高端}L.rlow=L.r0; //枢轴记录到位return low; //返回枢轴位置}void QSortSqList &L,int low,int high{//对顺序表L中的子序列L.rlow..high作快速排序int pivotloc;if low<high //长度>1{pivotloc=PartitionL,low,high; //将L.rlow..high一分为二QSortL,low,pivotloc-1; //对低子表递归排序,pivotloc是枢轴位置 QSortL,pivotloc+1,high; //对高子表递归排序}}void QuickSortSqList &L{//对顺序表L作快速排序QSortL,1,L.length; }。

算法分析与设计试卷及参考答案济南⼤学继续教育学院算法分析与设计试卷（A）学年：学期:年级：专业：学习形式：层次：（本试题满分100分，时间90分钟）⼀、单选题（每⼩题2分，共计20分。

）1. 下列情况不适合使⽤计数排序的是（）。

A 要排序的数据表的数量很⼤B 要排序的数据表中有相同的关键字C 要排序的数据表基本有序D 要排序的数据表元素各不相同2. 集合｛Ａ，Ｂ｝的幂集合为（）。

Ａ．｛Ａ｝，｛Ｂ｝Ｂ．｛Ａ｝，｛Ｂ｝，ΦC． { ｛Ａ｝，｛Ｂ｝} D {｛Ａ，Ｂ｝，｛Ａ｝，｛Ｂ｝，Φ}3．下列字符串序列不符合字典排序的是（）。

A． abc acb bca B. abc acb cbaC． bac bca abc D abc bac bca4．对于根树，出度为零的节点为（）。

Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分⽀节点5．对完全⼆叉树⾃顶向下，从左向右给节点编号，节点编号为１0的⽗节点编号为（）。

Ａ０Ｂ２Ｃ４Ｄ６6．下列程序段的算法时间的复杂度为（）。

for i ←0 to n dofor j ←0 to m do s //某种基本操作A O（n2）B O(m2)C (m+n)D O(m*n)7.三个盘⼦的汉诺塔，⾄少要执⾏移动操作的次数为 ( )。

A 1次B 3次C 6次D 7次8．与算法英⽂单词algorithm具有相同来源的单词是（）。

A logarithmB algirosC arithmosD algebra9．从排序过程是否完全在内存中显⽰，排序问题可以分为（）。

Ａ稳定排序与不稳定排序Ｂ内排序与外排序Ｃ直接排序与间接排序Ｄ主排序与辅助排序10．下列（）不是衡量算法的标准。

Ａ时间效率Ｂ空间效率Ｃ问题难度Ｄ适应能⼒⼆、简答题（每题8分，共计24分。

）1．贪婪技术的基本思想是什么？它有哪些应⽤（给出2种）？2. 拓扑排序的基本思想是什么？它可⽤于哪些实际问题中（给出2种）？3．是么是算法，算法与程序有什么区别？三、算法设计题（每题14分，共计56分。

算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。

答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。

其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。

2. 什么是动态规划算法？请给出一个动态规划算法的示例。

答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。

它的特点是具有重叠子问题和最优子结构性质。

以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。

3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。

而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。

DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。

4. 请简述贪心算法的特点及其应用场景。

答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。

然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。

《算法分析与设计》课程复习资料一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树 二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。

2.简述回溯法解题的主要步骤。

3.简述动态规划算法求解的基本要素。

4.简述回溯法的基本思想。

5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

6.简要分析分支限界法与回溯法的异同。

7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 8.贪心算法求解的问题主要具有哪些性质？简述之。

9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。

10.简述分析贪心算法与动态规划算法的异同。

三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。

2.按要求完成以下关于排序和查找的问题。

①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。

②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。

③给出上述算法的递归算法。

④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。

3.已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。

4.根据分枝限界算法基本过程,求解0-1背包问题。

已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。

湖南科技学院二○年学期期末考试信息与计算科学专业年级《算法设计与分析》试题考试类型：开卷试卷类型：C 卷考试时量：120分钟性的阶为结点的是 指1.试述回溯法的基本思想及用回溯法解题的步骤。

2.有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1给出一个最优调度方案，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少，并计算所需的最少时间。

答：最优调度方案为所需的最少时间为：_______________________3.根据优先队列式分支限界法，求下图中从v1点到v9点的单源最短路径，请画出求得最优解的解空间树。

要求中间被舍弃的结点用×标记，获得中间解的结点用单圆圈○框起（如），最优解用双圆圈◎框起。

三、算法填空（每空2分，共计10分）设R={r1,r2,...,r n}是要进行排列的n个元素，其中元素r1,r2,...,r n可能相同，试设计一个算法，列出R的所有不同排列，并给出不同排列的总数。

算法如下，填写缺失的语句。

template<typenameType>Swap(R[k],R[i]);}}}四、算法设计（共计15分）设有n个程序{1,2,3...,n}要存放在长度为L的磁带上。

程序i存放在磁带上的长度是Li，1≤i≤n。

程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序，在保证存储最多程序的前提下还要求磁带的利用率达到最大。

（1）给出求解存储最多程序的算法，并证明算法的正确性；（2）给出求解使磁带的利用率达到最大的方案的算法思路。

五、算法设计（共计15分）通过键盘输入一个高精度的正整数n （n 的有效位数≤240），去掉其中任意s 个数字后，剩下的数字按原左右次序将组成一个新的正整数。

对给定的n 和s ，寻找一种方案，使得剩下的数字组成的新最小。

算法分析与设计作业及参考答案作业题目1、请分析冒泡排序算法的时间复杂度和空间复杂度，并举例说明其在实际中的应用场景。

2、设计一个算法，用于在一个未排序的整数数组中找到第二大的元素，并分析其时间复杂度。

3、比较贪心算法和动态规划算法的异同，并分别举例说明它们在解决问题中的应用。

参考答案1、冒泡排序算法时间复杂度：冒泡排序的基本思想是通过相邻元素的比较和交换，将最大的元素逐步“浮”到数组的末尾。

在最坏情况下，数组完全逆序，需要进行 n 1 轮比较和交换，每一轮比较 n i 次（i 表示当前轮数），所以总的比较次数为 n(n 1) ／ 2，时间复杂度为 O(n^2)。

在最好情况下，数组已经有序，只需要进行一轮比较，时间复杂度为 O(n)。

平均情况下，时间复杂度也为 O(n^2)。

空间复杂度：冒泡排序只在原数组上进行操作，不需要额外的存储空间，空间复杂度为 O(1)。

应用场景：冒泡排序算法简单易懂，对于规模较小的数组，或者对算法的简单性要求较高而对性能要求不是特别苛刻的场景，如对少量数据进行简单排序时，可以使用冒泡排序。

例如，在一个小型的学生成绩管理系统中，需要对一个班级的少量学生成绩进行排序展示，冒泡排序就可以满足需求。

2、找到第二大元素的算法以下是一种使用遍历的方法来找到未排序整数数组中第二大元素的算法：｀｀｀pythondef find_second_largest(arr)：largest ＝ arr0second_largest ＝ float(＇inf'）for num in arr:if num ＞ largest:second_largest ＝ largestlargest ＝ numelif num ＞ second_largest and num!＝ largest:second_largest ＝ numreturn second_largest｀｀｀时间复杂度分析：这个算法需要遍历数组一次，所以时间复杂度为O(n)。

算法设计与分析考试题目及答案Revised at 16:25 am on June 10, 2021I hope tomorrow will definitely be better算法分析与设计期末复习题一、 选择题1.应用Johnson 法则的流水作业调度采用的算法是DA. 贪心算法B. 分支限界法C.分治法D. 动态规划算法塔问题如下图所示;现要求将塔座A 上的的所有圆盘移到塔座B 上,并仍按同样顺序叠置;移动圆盘时遵守Hanoi 塔问题的移动规则;由此设计出解Hanoi 塔问题的递归算法正确的为：B3. 动态规划算法的基本要素为C A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用4. 算法分析中,记号O 表示B , 记号Ω表示A , 记号Θ表示D ; A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界5. 以下关于渐进记号的性质是正确的有：A 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. Ofn+Ogn = Omin{fn,gn} D. f (n)O(g(n))g(n)O(f (n))=⇔=Hanoi 塔A. void hanoiint n, int A, int C, int B { if n > 0 {hanoin-1,A,C, B; moven,a,b;hanoin-1, C, B, A; } B. void hanoiint n, int A, int B, int C { if n > 0 {hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; }C. void hanoiint n, int C, int B, int A { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; }D. void hanoiint n, int C, int A, int B { if n > 0 {hanoin-1, A, C, B; moven,a,b;hanoin-1, C, B, A; }6.能采用贪心算法求最优解的问题,一般具有的重要性质为：AA. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中,按D策略,从根结点出发搜索解空间树;广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中,按A策略,从根结点出发搜索解空间树;A．广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块A是回溯法中遍历排列树的算法框架程序;A.B.C.D.10.xk的个数;11. 常见的两种分支限界法为DA. 广度优先分支限界法与深度优先分支限界法；B. 队列式FIFO分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式FIFO分支限界法与优先队列式分支限界法；12. k带图灵机的空间复杂性Sn是指BA.k带图灵机处理所有长度为n的输入时,在某条带上所使用过的最大方格数;B.k带图灵机处理所有长度为n的输入时,在k条带上所使用过的方格数的总和;C.k带图灵机处理所有长度为n的输入时,在k条带上所使用过的平均方格数;D.k带图灵机处理所有长度为n的输入时,在某条带上所使用过的最小方格数;13. N P类语言在图灵机下的定义为DA.NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}；B.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；C.NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}；D.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；14. 记号O的定义正确的是A;A.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ fn ≤cgn }；B.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ cgn ≤fn }；>0使得对所有n≥n0C.Ogn = { fn | 对于任何正常数c>0,存在正数和n有：0 ≤fn<cgn }；>0使得对所有n≥n0D.Ogn = { fn | 对于任何正常数c>0,存在正数和n有：0 ≤cgn < fn }；15. 记号Ω的定义正确的是B;A.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ fn ≤cgn }；B.Ogn = { fn | 存在正常数c和n0使得对所有n≥n0有：0≤ cgn ≤fn }；>0使得对所有n≥n0有：C.gn = { fn | 对于任何正常数c>0,存在正数和n0 ≤fn<cgn }；D.gn = { fn | 对于任何正常数c>0,存在正数和n0 >0使得对所有n≥n0有：0 ≤cgn < fn }；二、 填空题1. 下面程序段的所需要的计算时间为 2O(n ) ;2.3.4. 5.6. 用回溯法解题的一个显着特征是在搜索过程中动态产生问题的解空间;在任何时刻,算法只保存从根结点到当前扩展结点的路径;如果解空间树 中从根结点到叶结点的最长路径的长度为hn,则回溯法所需的计算空间通常为Ohn ;7. 回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架;8. 用回溯法解0/1背包问题时,该问题的解空间结构为子集树结构; 9.用回溯法解批处理作业调度问题时,该问题的解空间结构为排列树结构; 10.用回溯法解0/1背包问题时,计算结点的上界的函数如下所示,请在空格中填入合适的内容：11. n m12. 用回溯法解图的m着色问题时,使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性,则需耗时渐进时间上限Omn;13.;设分分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用fn个单位时间;用Tn表示该分治法解规模为|P|=n的问题所需的计算时间,则有：(1)1 ()(/)()1O nT nkT n m f n n=⎧=⎨+>⎩通过迭代法求得Tn的显式表达式为：log1log()(/)nmk j jmjT n n k f n m-==+∑试证明Tn的显式表达式的正确性;2. 举反例证明0/1背包问题若使用的算法是按照p i/w i的非递减次序考虑选择的物品,即只要正在被考虑的物品装得进就装入背包,则此方法不一定能得到最优解此题说明0/1背包问题与背包问题的不同;证明：举例如：p={7,4,4},w={3,2,2},c=4时,由于7/3最大,若按题目要求的方法,只能取第一个,收益是7;而此实例的最大的收益应该是8,取第2,3 个;3. 求证：Ofn+Ogn = Omax{fn,gn} ;证明：对于任意f1n∈ Ofn ,存在正常数c1和自然数n1,使得对所有n≥n1,有f1n≤ c1fn ;类似地,对于任意g1n ∈ Ogn ,存在正常数c2和自然数n2,使得对所有n≥n2,有g1n ≤c2gn ;令c3=max{c1, c2}, n3 =max{n1, n2},hn= max{fn,gn} ;则对所有的 n ≥ n3,有f1n +g1n ≤ c1fn + c2gn≤c3fn + c3gn= c3fn + gn≤ c32 max{fn,gn} = 2c3hn = Omax{fn,gn} .4. 求证最优装载问题具有贪心选择性质;最优装载问题：有一批集装箱要装上一艘载重量为c 的轮船;其中集装箱i 的重量为Wi;最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船; 设集装箱已依其重量从小到大排序,x 1,x 2,…,x n 是最优装载问题的一个最优解;又设1min{|1}i i nk i x ≤≤== ;如果给定的最优装载问题有解,则有1k n ≤≤;证明： 四、 解答题1. 机器调度问题;问题描述：现在有n 件任务和无限多台的机器,任务可以在机器上得到处理;每件任务的开始时间为s i ,完成时间为f i ,s i <f i ;s i ,f i 为处理任务i 的时间范围;两个任务i,j 重叠指两个任务的时间范围区间有重叠,而并非指i,j 的起点或终点重合;例如：区间1,4与区间2,4重叠,而与4,7不重叠;一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器;因此,在可行的分配中每台机器在任何时刻最多只处理一个任务;最优分配是指使用的机器最少的可行分配方案;问题实例：若任务占用的时间范围是{1,4,2,5,4,5,2,6,4,7},则按时完成所有任务最少需要几台机器提示：使用贪心算法画出工作在对应的机器上的分配情况;2. 已知非齐次递归方程：f (n)bf (n 1)g(n)f (0)c =-+⎧⎨=⎩ ,其中,b 、c 是常数,gn 是n 的某一个函数;则fn 的非递归表达式为：nnn i i 1f (n)cb b g(i)-==+∑;现有Hanoi 塔问题的递归方程为：h(n)2h(n 1)1h(1)1=-+⎧⎨=⎩ ,求hn 的非递归表达式;解：利用给出的关系式,此时有：b=2, c=1, gn=1, 从n 递推到1,有： 3. 单源最短路径的求解;问题的描述：给定带权有向图如下图所示G =V,E,其中每条边的权是非负实数;另外,还给定V 中的一个顶点,称为源;现在要计算从源到所有其它各顶点的最短路长度;这里路的长度是指路上各边权之和;这个问题通常称为单源最短路径问题;解法：现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径;请将此过程填入下表中;4. 请写出用回溯法解装载问题的函数; 装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i 的重量为wi,且121ni i w c c =≤+∑;装载问题要求确定是否有一个合理的装载方案可将这n 个集装箱装上这2艘轮船;如果有,找出一种装载方案;解：void backtrack int i{用分支限界法解装载问题时,对算法进行了一些改进,下面的程序段给出了改进部分；试说明斜线部分完成什么功能,以及这样做的原因,即采用这样的方式,算法在执行上有什么不同;初始时将;也就是说,重量仅在搜索进入左子树是增加,因此,可以在算法每一次进入左子树时更新bestw 的值;43 2 110030maxint10 - {1} 初始 dist5 dist4 dist3 dist2 u S 迭代7. 最长公共子序列问题：给定2个序列X={x 1,x2,…,xm }和Y={y 1,y2,…,yn },找出X 和Y 的最长公共子序列;由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系;用cij 记录序列Xi 和Yj 的最长公共子序列的长度;其中, Xi={x1,x2,…,xi}；Y j={y1,y2,…,yj};当i=0或j=0时,空序列是Xi 和Yj 的最长公共子序列;故此时Cij=0;其它情况下,由最优子结构性质可建立递归关系如下：00,0[][][1][1]1,0;max{[][1],[1][]},0;i j i ji j c i j c i j i j x y c i j c i j i j x y ⎧==⎪=--+>=⎨⎪-->≠⎩在程序中,bij 记录Cij 的值是由哪一个子问题的解得到的;8.1.2.3.4.5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________;6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解;7.以深度优先方式系统搜索问题解的算法称为_____________;背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________;9.动态规划算法的两个基本要素是___________和___________;10.二分搜索算法是利用_______________实现的算法;二、综合题50分1.写出设计动态规划算法的主要步骤;2.流水作业调度问题的johnson算法的思想;3.若n=4,在机器M1和M2上加工作业i所需的时间分别为ai 和bi,且a 1,a2,a3,a4=4,5,12,10,b1,b2,b3,b4=8,2,15,9求4个作业的最优调度方案,并计算最优值;4.使用回溯法解0/1背包问题：n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间从根出发,左1右0,并画出其解空间树,计算其最优值及最优解;5.设S=｛X1,X2,···,Xn｝是严格递增的有序集,利用二叉树的结点来存储S中的元素,在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,1在二叉搜索树的内结点中找到X=Xi ,其概率为bi;2在二叉搜索树的叶结点中确定X∈Xi ,Xi+1,其概率为ai;在表示S的二叉搜索树T中,设存储元素Xi的结点深度为C i ；叶结点Xi,Xi+1的结点深度为di,则二叉搜索树T的平均路长p为多少假设二叉搜索树Tij=｛Xi ,Xi+1,···,Xj｝最优值为mij,Wij= ai-1+bi+···+bj+aj,则mij1<=i<=j<=n递归关系表达式为什么6.描述0-1背包问题;三、简答题30分1.流水作业调度中,已知有n个作业,机器M1和M2上加工作业i所需的时间分别为ai 和bi,请写出流水作业调度问题的johnson法则中对ai和bi的排序算法;函数名可写为sorts,n2.最优二叉搜索树问题的动态规划算法设函数名binarysearchtree答案：一、填空1．确定性有穷性可行性 0个或多个输入一个或多个输出2.时间复杂性空间复杂性时间复杂度高低3. 该问题具有最优子结构性质4.{BABCD}或{CABCD}或{CADCD｝5.一个最优解6.子问题子问题子问题7.回溯法8. on2n omin{nc,2n}9.最优子结构重叠子问题10.动态规划法二、综合题1.①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造最优解；2. ①令N1={i|ai<bi},N2={i|ai>=bi}；②将N1中作业按ai的非减序排序得到N1’,将N2中作业按bi的非增序排序得到N2’；③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度;3.步骤为：N1={1,3},N2={2,4}；N 1’={1,3}, N2’={4,2}；最优值为：384.解空间为{0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1, 1,1,0,1,1,1}; 解空间树为：该问题的最优值为：16 最优解为：1,1,0 5.二叉树T 的平均路长P=∑=+ni 1Ci)(1*bi +∑=nj 0dj *aj{mij=0 i>j6.已知一个背包的容量为C,有n 件物品,物品i 的重量为W i ,价值为V i ,求应如何选择装入背包中的物品,使得装入背包中物品的总价值最大; 三、简答题 1.void sortflowjope s,int n {int i,k,j,l;fori=1;i<=n-1;i++ag=0 k++; ifk>n break;ag==0ifsk.a>sj.a k=j; swapsi.index,sk.index; swapsi.tag,sk.tag;} }l=i;<sj.b k=j;swapsi.index,sk.index; ag,sk.tag; }mij=Wij+min{mik+mk+1j} 1<=i<=j<=n,mii-1=0}2.void binarysearchtreeint a,int b,int n,int m,int s,int w{int i,j,k,t,l;fori=1;i<=n+1;i++{wii-1=ai-1;mii-1=0;}forl=0;l<=n-1;l++Init-single-sourceG,s2. S=Φ3. Q=VGQ<> Φdo u=minQS=S∪{u}for each vertex 3do 4四、算法理解题本题10分根据优先队列式分支限界法,求下图中从v1点到v9点的单源最短路径,请画出求得最优解的解空间树;要求中间被舍弃的结点用×标记,获得中间解的结点用单圆圈○框起,最优解用双圆圈◎框起;五、算法理解题本题5分设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成;1如果n=2k,循环赛最少需要进行几天；2当n=23=8时,请画出循环赛日程表;六、算法设计题本题15分分别用贪心算法、动态规划法、回溯法设计0-1背包问题;要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间;七、算法设计题本题10分通过键盘输入一个高精度的正整数nn的有效位数≤240,去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数;编程对给定的n 和s,寻找一种方案,使得剩下的数字组成的新数最小;样例输入178543S=4样例输出13一、填空题本题15分,每小题1分1．规则一系列运算2. 随机存取机RAMRandom Access Machine；随机存取存储程序机RASPRandom Access Stored Program Machine；图灵机Turing Machine3. 算法效率4. 时间、空间、时间复杂度、空间复杂度5．2n6．最好局部最优选择7. 贪心选择最优子结构二、简答题本题25分,每小题5分1、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同；对这k个子问题分别求解;如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解;2、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的;3、某个问题的最优解包含着其子问题的最优解;这种性质称为最优子结构性质;4、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索,解为叶子结点;搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到上层父结点,继续下一步深度优先搜索过程;在回溯法中,并不是先构造出整棵状态空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造;5、PPolynomial问题：也即是多项式复杂程度的问题;NP就是Non-deterministicPolynomial的问题,也即是多项式复杂程度的非确定性问题;NPCNP Complete问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难的问题,这种问题就是NPC问题;三、算法填空本题20分,每小题5分1、n后问题回溯算法1 Mj&&Li+j&&Ri-j+N2 Mj=Li+j=Ri-j+N=1;3 tryi+1,M,L,R,A4 Aij=05 Mj=Li+j=Ri-j+N=0 2、数塔问题; 1c<=r2trc+=tr+1c 3trc+=tr+1c+1 3、Hanoi 算法 1movea,c2Hanoin-1, a, c , b 3Movea,c 4、1pv=NIL 2pv=u3 v ∈adju 4Relaxu,v,w四、算法理解题本题10分五、18天2分；2当n=23=8时,循环赛日程表3分;六、算法设计题本题15分 1贪心算法 Onlogn ➢ 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包;若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包;依此策略一直地进行下去,直到背包装满为止; ➢ 具体算法可描述如下：void Knapsackint n,float M,float v,float w,float x {Sortn,v,w; int i;for i=1;i<=n;i++ xi=0; float c=M;for i=1;i<=n;i++ {if wi>c break; xi=1; c-=wi; }if i<=n xi=c/wi; }2动态规划法 Oncmi,j 是背包容量为j,可选择物品为i,i+1,…,n 时0-1背包问题的最优值;由0-1背包问题的最优子结构性质,可以建立计算mi,j 的递归式如下;void KnapSackint v,int w,int c,int n,int m11 {int jMax=minwn-1,c;for j=0;j<=jMax;j++ /mn,j=0 0=<j<wn/ mnj=0;1 2 3 4 5 6 7 82 1 43 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 4 6 5 8 7 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1for j=wn;j<=c;j++ /mn,j=vn j>=wn/mnj=vn;for i=n-1;i>1;i--{ int jMax=minwi-1,c;for j=0;j<=jMax;j++ /mi,j=mi+1,j 0=<j<wi/mij=mi+1j;for j=wi;j<=c;j++/mn,j=vn j>=wn/mij=maxmi+1j,mi+1j-wi+vi;}m1c=m2c;ifc>=w1m1c=maxm1c,m2c-w1+v1;}3回溯法 O2ncw:当前重量 cp:当前价值 bestp：当前最优值voidbacktrack int i//回溯法 i初值1{ifi>n //到达叶结点{ bestp=cp; return; }ifcw+wi<=c //搜索左子树{cw+=wi;cp+=pi;backtracki+1;cw-=wi;cp-=pi;}ifBoundi+1>bestp//搜索右子树backtracki+1;}七、算法设计题本题10分为了尽可能地逼近目标,我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符;然后回到串首,按上述规则再删除下一个数字;重复以上过程s次,剩下的数字串便是问题的解了;具体算法如下：输入s, n;while s > 0{ i=1; //从串首开始找while i < lengthn && ni<ni+1{i++;}deleten,i,1; //删除字符串n的第i个字符s--;}while lengthn>1&& n1=‘0’deleten,1,1; //删去串首可能产生的无用零输出n;。

高中信息技术《算法与程序设计VB （选修）》知识要点相关知识点（一）算法1.定义相关题解：1算法：就是解决问题的方法和步骤。

算法是程序设计的“灵魂”，算法+数据结构＝程序。

单选题1、下列关于算法说法不正确的是( A )A 、算法独立于任何具体的语言，BASIC 算法只能用BASIC 语言来实现B 、解决问题的过程就是实现算法的过程C 、算法是程序设计的“灵魂”D 、其它三项都正确2．算法的描述方法：1算法的描述：可分多种表达方法，一般用自然语言、流程图和伪代码进行描述。

2自然语言描述法：指用人们日常生活中使用的语言（本国语言），用自然语言描述符合我们的习惯，且容易理解。

3流程图描述：也称程序框图，它是算法的一种图形化表示方法。

且描述算法形象、直观，更易理解。

4伪代码描述法：是介于自然语言和计算机程序语言之间的一种算法描述。

是专业软件开发人员常用方法。

相关题解：单选题1、图形符号" "在算法流程图描述中表示( B ).A 处理或运算的功能B 输入输出操作C D 算法的开始或结束2、图形符号在算法流程图描述中表示( A ).A B 输入输出操作C 用来判断条件是否满足需求D 算法的开始或结束3、以下哪个是算法的描述方法?( A )A 流程图描述法B 枚举法C 顺序法D 列表法4、以下哪个是算法的描述方法?( D )A 顺序法B 列表法C 集合法D 自然语言描述法（二）程序设计基础（1）常用高级编程语言：BASIC、VB、Pascal、C、C++、Java1面向对象的程序设计语言：其中的对象主要是系统设计好的对象，包括窗体等、控件等2控件：是指工具箱中的工具在窗体中画出的、能实现一定功能的部件，如文本框，命令按钮等。

对象属性＝属性值对象中属性可以在设计界面时通过属性窗中设置，也可以在运行时通过程序代码设置,方法如下例：给文本框“Txt123”的“Text”属性赋值为字符串“20”，代码如下Txt123.text =”20”变量＝对象.属性如果要获取对象的状态或特性，这时就要读取对象的属性值，方法如下例：读取文本框“txt123”的“Text”属性的代码如下a = txt123.text2方法［对象］.方法［参数名表］例：form.print ”欢迎使用”该语句使用print方法在form1窗体中显示字符串“欢迎使用”3事件及事件驱动事件是对象对外部操作的响应，如在程序执行时，单击命令按钮会产生一个Click事件。

《算法设计与分析》试卷1一、多项选择题（每空2分, 共20分）:1.以下关于算法设计问题的叙述中正确的是__________。

A.计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关B.利用计算机无法解决非数值问题C.计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中, 主要进行的是判断、比较, 而不是算术运算D、算法设计与分析主要研究对象是非数值问题, 当然也包含某些数值问题2.算法的特征包括_________。

A.有穷性B、确定性C.输入和输出D.能行性或可行性3、以下描述是有关算法设计的基本步骤:①问题的陈述②算法分析③模型的拟制④算法的实现⑤算法的详细设计⑥文档的编制, 应与其它环节交织在一起其中正确的顺序是__________。

A.①②③④⑤⑥B.①③⑤②④⑥C.②④①③⑤⑥D.⑥①③⑤②④4.以下说法正确的是__________。

A.数学归纳法可以证明算法终止性B.良序原则是证明算法的正确性的有力工具C. x = 小于或等于x的最大整数（x的低限）D. x = 小于或等于x的最大整数（x的高限）5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C上所用的次数, 则递归方程为__________, 其初始条件为__________, 将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数, 则有递归方程为__________, 其中F1=F2=__________。

A.Fn=Fn-1+Fn-2 B、h（n）= 2h（n-1）+1C.1 D、h（1）= 1E、h（n）=2n-1F、06.在一个有向连通图中（如下图所示）, 找出点A到点B的一条最短路为____ ______。

A.最短路: 1→3→5→8→10, 耗费: 20B、最短路：1→4→6→9→10, 耗费：16C.最短路: 1→4→6→9, 耗费: 12D.最短路: 4→6→9→10, 耗费: 13二、填空（每空2分, 共20分）:1.快速排序法的基本思想是重新排列关键字, 把一个文件分成两个文件, 使得第一个文件中所有元素均小于第二个文件中的元素；然后再对两个子文件进行同样的处理。

高一第二学期《算法与程序设计》学分认定试题学校：_____________ 班级：____________ 学号：____________ 姓名：____________一、单选题（每小题3分，20小题，共60分）1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（）A、分析问题B、设计算法C、编写程序D、调试程序2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（）A、编译错误B、执行错误C、逻辑错误D、任何错误计算机都能检查出来3、下列关于算法的叙述中，错误的是（）A、一个算法至少有一个输入和一个输出B、算法的每一个步骤必须确切地定义C、一个算法在执行有穷步之后必须结束D、算法中有待执行的运算和操作必须是相当基本的。

4、流程图中表示判断的是（）。

Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（）A、顺序结构B、选择结构C、层次结构D、循环结构6、能够被计算机直接识别的语言是（）A、伪代码B、高级语言C、机器语言D、汇编语言7、在VB语言中，下列数据中合法的长整型常量是（）A、08AB、2380836EC、88.12345D、1.2345E68、求Mid(“ABCDEFG”,3,2)的结果是（）A、“ABC”B、“CD”C、“ABCDEF”D、“BCD”9、表达式 A+B+C<D AND A>=3 OR NOT C<0 OR D>0当A=3,B=4,C=-5,D=6时的运算结果是（）A、0B、1C、TRUED、FALSE10、在循环语句 For x=1 to 100 step 2……Next x 中，x能达到的最大值是（）A、100B、99C、98D、9711、在下列选项中，不属于VB的对象的是（）A、窗体的背景颜色B、命令按钮C、文本框D、标签12、在调试程序的时候，经常要设置断点，设置断点的快捷键是（）A、F1B、F8C、F9D、F1213、算法描述可以有多种表达方法，下面哪些方法不可以描述“闰年问题”的算法（）A、自然语言B、流程图C、伪代码D、机器语言14、以下不属于非法用户自定义标识符（常量和变量命名）的是（）A、8adB、ad8C、_a8dD、const15、已知A，B，C，D是整型变量，且都已有互不相同的值，执行语句B=0；A=C；D=A；D=B；后，其值相等的变量是（）A、A，DB、A，CC、C，BD、B，A16、要交换变量A和B的值，应使用的语句组是( )A、A=B；B=C；C=AB、C=A；A=B；B=CC、A=B；B=AD、C=A；B=A；B=C17、Visual Basic中以单引号开头一行文字称为注释，它对程序的运行（）A、起一定作用B、有时候起作用C、不起任何作用，但是必须的D、不起任何作用，但能增加程序的可阅读性18、要使一个命令按钮显示文字“确定”，正确的设置是把该命令按钮的（）。

算法设计与分析复习题目及答案一、算法的基本概念1、什么是算法？算法是指解决特定问题的一系列明确步骤，它具有确定性、可行性、有穷性、输入和输出等特性。

例如，计算两个数的最大公约数的欧几里得算法，就是通过反复用较小数去除较大数，然后将余数作为新的较小数，直到余数为 0，此时的除数就是最大公约数。

2、算法的复杂度包括哪些？它们的含义是什么？算法的复杂度主要包括时间复杂度和空间复杂度。

时间复杂度是指算法执行所需要的时间量，通常用大 O 记号来表示。

例如，一个算法的时间复杂度为 O(n)，表示其执行时间与输入规模 n成正比。

空间复杂度则是算法在运行过程中所需要的额外存储空间的大小。

比如说，一个算法需要创建一个大小为 n 的数组来存储数据，那么其空间复杂度就是 O(n)。

二、分治法1、分治法的基本思想是什么？分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题结构相同。

然后分别求解这些子问题，最后将子问题的解合并得到原问题的解。

2、请举例说明分治法的应用。

例如归并排序算法。

将一个未排序的数组分成两半，对每一半分别进行排序，然后将排好序的两部分合并起来。

其时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

三、动态规划1、动态规划的基本步骤有哪些？动态规划的基本步骤包括：（1）定义问题的状态。

（2）找出状态转移方程。

（3）确定初始状态。

（4）计算最终的解。

2、解释最长公共子序列问题，并给出其动态规划解法。

最长公共子序列问题是指找出两个序列的最长公共子序列的长度。

假设我们有两个序列 X 和 Y，用 dpij 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。

状态转移方程为：如果 Xi 1 ＝＝ Yj 1，则 dpij ＝ dpi 1j 1 ＋ 1否则 dpij ＝ max(dpi 1j, dpij 1)四、贪心算法1、贪心算法的特点是什么？贪心算法在每一步都做出当前看起来最优的选择，希望通过这种局部最优选择达到全局最优解。

算法与程序设计试题(共8页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--算法与程序设计期中考试试题一、选择题：每题2分，30题，共60分（）1．以下问题中最适合用计算机编程处理的是＿＿D＿＿。

A．制定本学期的学习计划B．计算正方形的周长C．创作一首歌曲D．求1000以内的所有素数（）2．用计算机解决问题的步骤一般为D。

(p3)①编写程序②设计算法③分析问题④调试程序A．①②③④B．③④①②C．②③①④D．③②①④（）3．下面说法正确的是A。

(P5)A．算法+数据结构=程序B．算法就是程序C．数据结构就是程序D．算法包括数据结构（）4．以下D是算法具有的特征。

(P5)①有穷性②确定性③可行性④输入⑤输出A．①②③B．②③④C．③④⑤D．①②③④⑤（）5．常用的算法描述方法有D。

A．用自然语言描述算法B．用流程图描述算法C．用伪代码描述算法D．以上都是（）6．流程图中表示判断框的是B。

(P8)A．矩形框B．菱形框C．圆形框D．椭圆形框（）7．程序设计语言的发展阶段不包括A。

(P11)A．自然语言B．机器语言C．汇编语言D．高级语言（）8．要使命令按钮显示文字“确定”，正确的设置是把该命令按钮的C。

(P18)A．Font属性设置为“确定”B．ForeColor属性设置为“确定”C．Caption属性设置为“确定”D．BorderStyle属性设置为“确定”（）10．下面的属性中，用于设定控件高度的是化程B序设。

(P18) A．FontB．HeightC．CaptionD．Width（）11．窗体的BackColor属性用于设置窗体的＿＿D＿＿。

(p18)A．宽度B．前景色C．高度D．背景色12．在VB中，若要将变量N定义为单精度型数据，则下列表示方法中正确的是B化。

(P21)A．Dim N as StringB．Dim N as SingleC．Dim N as IntegerD．Dim N as Long（）14．在程序设计的过程中，错误的声明一个变量会导致程序不能正常编译。