算法设计与分析课程设计题目
以下题目任选一题。
一、使用C、C++、C#或JAVA 语言设计相关算法并编写一个完整
的程序，计算任意两个整数a,b 的最大公因数，其中0≤a,b≤10100。（要求：禁止网上下载大数类实现；10 分钟内输出结果）
二、使用C、C++、C#或JAVA 语言设计相关算法并编写一个简单的中国象棋模拟程序。
三、地图着色问题。对美国地图进行着色，两个共同边界的州着不同的颜色，当可以选择7、6、5、4种不同的颜色的情况下，由程序自动进行处理，给出具体的着色方案。
四、罗密欧与朱丽叶的迷宫问题。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这样一条道路。
五、宝石游戏：宝石游戏比较有趣，它在13X6 的格子里进行。游戏给出红色、蓝色、黄色、橘黄色、绿色、和柴色的宝石。当任何三个以上宝石具有相同颜色并且在一条直线（横竖斜）时，这些宝石
可以消去。游戏如图所示。现在给定当前游戏状态和一组新的石头，请编程计算当所有石头落下时游戏的状态。
提示：
输入：第一行n 表示n 组测试数据。
下面每一个测试数据包含一个13X 6 的字符表，其中B 表示蓝色，R 表示红色，O 表示橘黄色、Y 表示黄色，G 表示绿色，P 表示紫色，W 表示此处没有宝石。接下来三行，每行包含一个字符，表示新来的宝石下落的位置。
输出：
每一个测试样例，输出当所有宝石落下后游戏的状态。样例输入：
1
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
BBWWWW
BBWWWW
OOWWWW
B
B
Y
3
样例输出：
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
OOYWWW
六、若部分同学做以上五题均有难度，经指导老师同意可实现教材上任意三个经典算法。
以上题目总体要求及说明：
1、建议数据输入输出采用文件方式；
2、程序中要有注释；
3、程序中所有算法均要给出算法分析，特别是时间复杂性；
4、提交程序源代码及算法设计分析测试文档（纸质及电子版）；
5、按参考格式撰写程序算法报告及测试报告；
6、1 月13号起接受检查；
7、提交格式(程序及文档打包)：学号姓名.rar。
一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采
《计算机算法设计与分析》习题及答案 一．选择题 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.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】
一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(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. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj
《电子技术基础》课程设计题目 一、脚步声控制照明灯 要求：1.白天光线较强，照明灯不会点亮； 2.晚上又脚步声照明灯被点亮，脚步声小时后灯亮延时十秒再自动熄灭； 3.元件：功率集成电路家分立元件; 二、报警声响发生器 要求：1.能发出消防车报警，救护车报警灯的报警声; 2.输出功率≥1W 要求：1.当池中水位低于设定点时水泵自动抽水；； 3.元件：NE555时基电路加分立元件； 三、水位控制器 2.当水位到达设定点时水泵自动停止； 3.元件：NE555电路加分立元件； 4.说明：水泵工作可用灯泡亮灭进行模拟； 四、金属探测器； 要求：1.能探测木材中≥5mm深处的残留铁钉； 2.当探测到金属物时能用声或光报警； 3.元件：与非们加分立元件，探头可用带铁芯线圈自制； 五、循环灯 要求：1.有四路输出，单循环； 2.能带动6V小灯泡四只； 3.元件：J-K触发器、555时基电路、分立元件； 六、数字水位探测器 要求：1.能测出水位的高度，精度韦1/16； 2.能输出数字形式（即二进制）； 3.能以模拟电压输出； 七、直流电压升压器 要求：1.输入电压30V；输出电压45V； 2.输出电流能达到0.5A； 八、上下课铃声识别系统 要求：1.设计一个开关电路仅对学校的上课、下课铃声敏感； 2.铃声来时输出高电平； 3.能识别出上课铃声和下课铃声； 九、厕所冲水控制器 要求：1.能识别有无人进出厕所； 2.当进出人数每达6人次时，电路输出一个脉冲； 十、步进电机及启动电路 要求：1.利用数电知识设计一个步进电机驱动电路； 2.能由两根线的输入电平组合使电机能向前进、后退、保持； 十一．教室用电节能控制电路
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性__,_确定性_,_可行性_,_ （0个或多个）输入__,_ （1个或多个）_输出_。 2.算法的复杂性有__时间复杂性__和__空间复杂性__之分，衡量一个 算法好坏的标准是__时间复杂度高低___。 3.某一问题可用动态规划算法求解的显著特征是___该问题具有最优 子结构性质___。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_{A,B,C,D}_。{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含_问题的一个（最优）解_。 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题_，先求解_子问题__，然后从这些_子问题_的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为__回溯法__。 8.0-1背包问题的回溯算法所需的计算时间为__O（n2n）__,用动态规划算法所需的计算时间为_O（n）__。o(min{nc,2n}) 9.动态规划算法的两个基本要素是_最优子结构_和_重叠子问题 ___。 10.二分搜索算法是利用__动态规划法__实现的算法。
二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 1、解：（1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值； （3）以自底向上的方式计算出最优值； （4）根据计算最优值时得到的信息，构造最优解。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解 2.流水作业调度问题的johnson算法的思想。 2、解：①令N1={i|a i=b i}；②将N1中作业按a i 的非减序排序得到N1’，将N2中作业按b i的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 3、解：步骤为：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最优值为：38
算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中
for(i=0;i
电子线路课程设计题目 （模电、数电部分） 一、锯齿波发生器 二、语音放大电路 三、可编程放大器 四、数字频率计 五、可调电源 六、汽车尾灯控制电路 2011．09
一、设计一高线性度的锯齿波发生器 要求： （1）利用555定时器和结型场效应管构成的恒流源设计一高线性度的锯齿波发生器；参考电路如图所示； （2）在EWB中对该电路进行仿真； （3）焊接电路并进行调试；调试过程中思考： a、电路中两个三极管的作用是什么？其工作状态是怎么样的？ b、R3阻值的大小会对锯齿波的线性度产生什么影响？ c、输出锯齿波的幅值范围多大？ d、调节电路中的可调电阻对波形有什么影响？ e、LM324的作用是什么？ （4）参考电路图中采用的是结型场效应管设计的，若采用N沟道增强型VMOS管和555定时器来设计一高线性度的锯齿波发生器，该如何设计？ LM324 图2 高线性度锯齿波发生器的设计
二、语音放大电路的设计 通常语音信号非常微弱，需要经过放大、滤波、功率放大后驱动扬声器。 要求： （1） 采用集成运算放大器LM324和集成功放LM386N-4设计一个语音放大电路；假设 语音信号的为一正弦波信号，峰峰值为5mV ，频率范围为100Hz~1KHz ，电路总体原理图如下所示； 具体设计方案可以参照以下电路： 图4 语音放大电路 （2） 仔细分析以上电路，弄清电路构成，指出前置放大器的增益为多少dB?通带滤波器 的增益为多少dB? （3） 参照以上电路，焊接电路并进行调试。 a 、 将输入信号的峰峰值固定在5mV ，分别在频率为100Hz 和1KHz 的条件下测试前
一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）
内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T
电子技术与电子工艺课程设计题目 一、脚步声控制照明灯 要求：1.白天光线较强，照明灯不会点亮； 2.晚上又脚步声照明灯被点亮，脚步声小时后灯亮延时十秒再自动熄灭； 3.元件：功率集成电路家分立元件; 二、题目：简易数字计时电路 设计并组装一简易的数字计时装置。能显示“小时”（0～23时）、“分”（0～59分）和“秒”（0～59秒）。小时、分、秒的十位的零均不予以显示 按实验任务要求设计电路，其方框图见图，选择器件，画出安装图。 三、灯循环控制电路 要求：1.有四路输出，单循环； 2.能带动6V小灯泡四只； 3.元件：J-K触发器、555时基电路、分立元件； 四、上下课铃声识别系统 要求：1.设计一个开关电路仅对学校的上课、下课铃声敏感； 2.铃声来时输出高电平； 3.能识别出上课铃声和下课铃声；
五．教室用电节能控制电路 要求设计制作一个控制电路，当天黑时有声音一楼灯亮，有人上楼梯时2 楼灯亮,当人数少于一定时只有2楼灯亮，否则3楼开始亮，以此类推。 六、商店迎宾机器人电路: （一）、设计基本要求： 1、能判断顾客进门与出门，在有顾客进门时“欢迎光临”，出门时“谢谢光临” 2、能实时统计来访人数及当前店内人数，并用数码管显示出来 3、电路设计要求有抗干扰的措施 4、统计误差不超一人 5、电路设计不能用MCU，只能应用普通中小规模集成电路芯片。成本控制在20元内 （二）、原理框图 七、多种波形发生器 1、设计要求 用中小规模集成芯片设计制作产生方波、三角波和正弦波等多种波形信号输出的波形发生器，具体要求如下： 1）、输出波形工作频率范围为0.02H Z~20KH Z，且连续可调；
填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进
精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include
湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14
电子技术课程设计 一、课程设计目的： 1．电子技术课程设计是机电专业学生一个重要实践环节，主要让学生通过自己设计并制作一个实用电子产品，巩固加深并运用在“模拟电子技术”课程中所学的理论知识； 2．经过查资料、选方案、设计电路、撰写设计报告、答辩等，加强在电子技术方面解决实际问题的能力，基本掌握常用模拟电子线路的一般设计方法、设计步骤和设计工具，提高模拟电子线路的设计、制作、调试和测试能力； 3．课程设计是为理论联系实际，培养学生动手能力，提高和培养创新能力，通过熟悉并学会选用电子元器件，为后续课程的学习、毕业设计、毕业后从事生产和科研工作打下基础。 二、课程设计收获： 1.学习电路的基本设计方法；加深对课堂知识的理解和应用。 2.完成指定的设计任务，理论联系实际，实现书本知识到工程实践的过渡； 3.学会设计报告的撰写方法。 三、课程设计教学方式： 以学生独立设计为主，教师指导为辅。 四、课程设计一般方法 1. 淡化分立电路设计，强调集成电路的应用 一个实用的电子系统通常是由多个单元电路组成的，在进行电子系统设计时，既要考虑总体电路的设计，同时还要考虑各个单元电路的选择、设计以及它们之间的相互连接。由于各种通用、专用的模拟、数字集成电路的出现，所以实现一个电子系统时，根据电子系统框图，多数情况下只有少量的电子电路的参数计算，更多的是系统框图中各部分电子电路要正确采用集成电路芯片来实现。
2. 电子系统内容步骤： 总体方案框图---单元电路设计与参数计算---电子元件选择---单元电路之间连接---电路搭接调试---电路修改---绘制总体电路---撰写设计报告(课程设计说明书) （1）总体方案框图： 反映设计电路要求，按一定信息流向，由单元电路组成的合理框图。 比如一个函数发生器电路的框图： （2）单元电路设计与参数计算---电子元件选择： ●基本模拟单元电路有：稳压电源电路，信号放大电路，信号产生电路，信号处理电 路（电压比较器，积分电路，微分电路，滤波电路等），集成功放电路等。 ●基本数字单元电路有：脉冲波形产生与整形电路（包括振荡器，单稳态触发器，施 密特触发器），编码器，译码器，数据选择器，数据比较器，计数器，寄存器，存储器等。
计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O （1），在最坏情况下，搜索的时间复杂性为O（logn）。4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程： n2O(1) T(n)2T(n/2)O(n)n2解得此递归方可得T(n)= O（）。 nlogn5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer阶段6．所花的时间是 T(n/2) ，算法的时间复杂度是 O( log n) 。7．Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是 2O(n) 。8．背包问题可用贪心法，回溯法等策略求解。39．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n) ，子2问题空间大小是 O(n) 。10．图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是nm ，解空间树中每个内结点的孩子数是 m 。11．单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。 13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。 14、直接或间接地调用自身的算法称为（递归算法）。 15、记号在算法复杂性的表示法中表示（渐进确界或紧致界）。 16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。 17、动态规划算法适用于解（具有
1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。
一、课程设计说明书应包括以下内容: 1、中文摘要; 2、绪论(内容介绍; 3、工作原理(理论分析; 4、整体方案设计,画出系统结构图(系统框图; 5、具体实施,包括:主电路的设计、参数计算、元器件选择、控制电路设计、 驱动电路设计等; 6、仿真模型的搭建,给出不同条件下的结果并进行分析; 7、设计说明书10~15页,要求手写,仿真或实验结果图可打印然后粘到说明书中; 8、A3图纸一张(硬件电路图,Protel、CAD等软件。 9、仿真软件为Matlab/Simulink; 10、做仿真的要给出所有仿真模型,并说明搭建过程及原理,给出仿真结果,进行分析并得出结论。 二、上交材料 1、设计说明书,1张A3图纸; 2、截止日期:2017-07-14(周五,具体时间与相应老师联系; 3、负责老师:电气14-3,李一丹老师,153******** 电气14-4,王玉萍老师,136******** 电气14-10,郑爽老师,188********
电气14-11,李雯老师,159******** 电气14-12,吕雄飞老师,139******** 注意:3~4人一组,每组不得超过4人。不许雷同。 1.升压斩波电路的设计(除常规要求外,应实现仿真设计指标:直流输入电压24V; 输出电压54V; 输出电流5A; 工作频率100KHz; 最大输出纹波电压0.2V。 2.降压斩波电路的设计(除常规要求外,应实现仿真设计指标:直流输入电压36V; 输出电压12V; 输出电流3A; 工作频率100KHz; 最大输出纹波电压0.05V。 3.DC/AC变换器的设计(除常规要求外,应实现仿真设计指标:输入电压:12V直流电压; 输出交流220V; 单相;
复习 一、简答题（每小题5分，选答2题，共10分） 1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。 4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。 二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52 算法Mystery(n) //输入：非负整数n S=0 for i ← 1 to n do S ← S + i*i Return S a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 2. 考虑下面的递归算法。P52 算法Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ← A[0]; maxval ← A[0] for i ←1 to n-1 do if A[i] < minval minval ← A[i] if A[i] > maxval maxval ← A[i] return maxval – minval a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 3. 考虑下面的递归算法P59 算法Q(n) //输入：正整数 if n=1 return 1 else return Q(n-1) + 2*n -1 a. 建立该函数值的递推关系并求解，以确定该算法计算的是什么； b. 建立该算法所做的乘法运算次数的递推关系并求解； c. 建立该算法所做的加减运算次数的递推关系并求解。 三、算法设计题（每小题10分，共20分） 1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人
电子技术课程设计题 1 音频小信号功率放大电路设计 设计并制作音频小信号功率放大电路。具体要求如下： （１）放大倍数A V≥1000； （２）通频带100Hz~10KHz； （３）放大电路的输入电阻R I≥1MΩ; （４）在负载电阻为8Ω的情况下，输出功率≥2W； （５）功率放大电路效率大于50%； （６）输出信号无明显失真。 说明：设计方案和器件根据题目要求自行选择，但要求在通用器件范围内。不能选用集成音频功放。 测试条件：技术指标在输入正弦波信号峰值Vp=10mV的条件进行测试（输入电阻通过设计方案预以保证），设计报告中应有含有详细的测试数据说明设计结果。 参考元器件：NE5532、TL082或TL084，3DG6/3DG21，3AX83/3BX83，1N4148/1N4001，TIP41/42中功率管或2N3055大功率管等。 主要测试设备：直流电源，信号源，示波器和8Ω功率电阻。 2 数控直流电源的设计 设计一线性输出电压可调的直流电源。电源有电压增（UP）和电压减（DOWN）两个键，按UP时电压步进增加，按DOWN时电压步进减小。具体要求如下：（１）输出电压5~12V，步进为1V； （２）输出电压误差最大±0.1V； （３）输出电流不小于1A； 测试条件：分别测试输出为5V、6V、7V、。。。、12V的输出电压。输出电流通过设计预以保证。 发挥部分：用LED或数码管显示电压设定值； 参考元器件：74LS192,74HC138,三极管S8050/S8550，LM317，CD4511等。 3 数控直流稳压电源设计 设计一个数控直流稳压电源。具体要求如下： （1）输出电压：0~9.9V步进可调，调整步距0.1V； （2）输出电压值用LED数码管显示； （3）电压调整：由“+”、“-”两键分别控制输出电压的步进增减； 提示：（1）用可逆计数器和D/A实现电压预置和电压步进控制； （2）用线性电源实现可控电源； 发挥部分：输出电压可在0~9.9V范围任意预置。 参考元器件：74HC190，DAC0832，三极管S8050/8550，3DD15等。 4 DDS信号源的设计(A) 设计一个简单的DDS正弦波信号发生器，有频率增（UP）和频率减（DOWN）两个键，按UP时频率步进增加，按DOWN时频率频率步进减小。具体要求如下：（１）输出信号的频率范围为10Hz~1000Hz，步进为10Hz。 （２）要求输出信号无明显失真。