一、Please answer T or F for each of the following statements to indicate whether the
statement is true or false
1. An algorithm is an instance, or concrete representation, for a computer program
in some programming language. ( F )
2. The following problem is a Decision Problem: What is the value of a best
possible solution? ( F )
3. The dynamic programming method can not solve a problem in polynomial time.
( F)
4. Assume that there is a polynomial reduction from problem A to problem B. If
we can prove that A is NP-hard, then we know that B is NP-hard. ( F )
5. If one can give a polynomial-time algorithm for a problem in NP, then all the
problems NP can be solved in polynomial time. ( F )
6. In an undirected graph, the minimum cut between any two vertices a and b is
unique. ( F)
7. Linear programming can be solved in polynomial time, but integer linear
programming can not be solved in polynomial time. ( T )
8. We can solve the maximum independent set problem in a graph with at most
100 vertices in polynomial time. ( T ) 结论
9. If an algorithm solves a problem of size n by dividing it into two subproblems of
size n/2, recursively solving each subproblems, and then combine the solutions in linear time. Then the algorithm runs in O(n log n) time. ( T )
10. Neural Computation, Fuzzy Computation and Evolution Computing are the
three research fields of Computational Intelligence. ( T )
二、Given the following seven functions f1(n) = n5+ 10n4, f2(n) = n2+ 3n
, f3(n) =
f4(n) = log n + (2log n)3, f5(n) = 2n+n!+ 5e n, f6(n) = 3log(2n) + 5log n, f7(n) = 2n log n+log n n. Please answer the questions:
第 1 页共5 页
(a) Give the tight asymptotic growth rate (asymptotic expression with θ) to each
of them; (7分)
(b) Arrange them in ascending order of asymptotic growth rate。(3分) 参考答案和评分标准：
a)
(1) n5 + 10n4 = θ (n5) （1分，非最简表达式或写成O或Ω不符合题意，不给分）
(2) n2 +3n = θ (3n) （1分，标准同上）
(3) 210000
= θ (n0.75) （1分，标准同上）
(4) log n + (2log n)3 =θ ( (log n)3) （1分，标准同上）
(5) 2n+n!+ 5e n =θ (n!) （1分，标准同上）
(6) 3log2n + 5log n =θ (n) （1分，标准同上）
(7) 2n log n+log n n. =θ (n n) （1分，标准同上）
b)
f4 f3 f6 f1 f2 f5 f7 (3分，每个错误位置扣0.5分，扣完为止）
三、Please answer the following questions:
(a)。
四、In the interval scheduling problem, we are given n jobs each of which has a
starting time s and a finishing time f, and the goal is to find a maximum set of mutually compatible jobs (two jobs are compatible if they don’t overlap). Please answer the following questions:
(a) Design a greedy algorithm for the interval scheduling problem and prove the
correctness of it.
(b) Assume that we are given 8 jobs with starting time and finishing time (s, t)
being (0,2), (1,3), (8,9), (3,7), (7,8), (2,4）,(6,9), (4,5). Use your algorithm to find
a solution to this instance.
参考答案及评分标准：
a）
将所有工作（jobs）按其完成时间的先后进行排序；
第 2 页共5 页
第 3 页 共 5 页
在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。
证明用反证法，假设贪心算法不是最优导出矛盾，课件中有证明。证明思路大体正确即可给全分。
b)
答案是 (0,2),(2,4),(4,5),(7,8),(8,9).
五、Find a minimum s-t cut in the following directed graph (the number beside the
edge is the capacity of the edge). You are required to give the computation steps and show the cut and its size. （9分） v5v4v3v1v2T 1045556106333234
参考答案： 18.
S
v5v4
v3v1v2
(9,10)
(4,4)(5,5)(4,5)
(6,6)(9,10)
(6,6)(3,3)(0,3)(3,3)(0,2)(0,3)(2,4)分）
给出第一个和增广路径（2分）
后面任意两个增广路径（1分一个）
最后答案18和这个cut （3分，任给一个cut即可，最后结果18错误
则不给分）
六、Prove that if we can check if a graph has a clique of size k in polynomial time
then we can also find a clique of size k in polynomial time (a clique of a graph is
a complete subgraph ).
参考答案及评分标准：
设检查算法为B，我们构造一个找到解的算法A，该算法多项式次调用B。
（1分）
算法A的步骤和思想：依次从图中删除一个点，再调用算法B来检查是否还存在大小为k的clique，如果存在则直接从图中删除这个点（2分）；
如果不存在，则将这个点放入解集，同时将图中所有不和这个点相邻的点全删除，再删除这个点本身，在剩余的图中再检查是否存在大小为k-1的clique。（3分）
以上思想正确给全分，其它正确解法也给全分。
七、We know that finding a longest path in a graph is NP-hard. Please show that
finding a longest path that passing through a given vertex is also NP-hard. (6分) 参考答案及评分标准：
将最长路径问题归约到通过某个点的最长路径问题。思想如下：
对于每个最长路径问题G，我们对图G中每个点得到一个通过这个点的最长路径问题，总共得到n（n为G中点的个数）个问题，如果后一个问题存在多项式算法，则前一个问题也存在。
以上思想正确给全分，否则最多给3分。
八、In a supermarket, there are n different types of goods for sale. Each type of goods
第 4 页共5 页
第 5 页 共 5 页 has a price of 0i w > dollars and a value of 0i v >. Now you are asked to buy some goods such that: for each type of goods, at most 2 pieces are bought, the total value of the goods is at least V and the total money used is minium. Use a dynamic programming algorithm to solve the above problem.
(a) Please define your subproblem; (b) Give the recurrence relation based on your subproblems;
(c) Solve the following instance showed in Table 1 by using the bottom-up method, where V=10. You are required to give the computation steps (the table used to store the solutions to the subporblems).
Table 1
参考答案及评分标准：
（a ）定义OPT （i ，v ）为只能选择前i 种物品且价值达到v 的最小花销；
（b ） 建立递归关系式：
{}0if v 0(,)no solution if i 0 and v>0
min (1,),(1,),2(1,2)otherwise i i i i OPT i v OPT i v w OPT i v v w OPT i v v ≤??==??-+--+--?
其中第一条边界条件1分，第二条1分，第三条递归关系式3分。 （c ）画出存储的表格，用自底而上的方法求解
算出最后正确答案
本题若忽略了每种物品有两个，则总分的基数分为10分，然后根据各步骤是否正确再参照以上标准进行评分。若直接当成背包问题来说，基数分为5分。
中央广播电视大学律师实务试题答案及评分标准 一、填空（在下列空格内填入正确内容，每空1分，共15分） 1．律师法所称的律师，是指取得律师___执业证书___，为社会提供___法律服务__的执业人员。 2．律师执业不受_____地域_____限制。 3．合伙制律师事务所，__合伙人__对该律师事务所的债务承担___无限责任___和___连带责任__。 4．律师应当保守在执业中知悉的__国家秘密__和当事人的__商业秘密_，不得泄露当事人的_隐私_。 5．冒充律师从事法律服务的，由__公安机关_责令停止非法执业，没收违法所得，可以并处__五千_元以下罚款、___十五__日以下拘留。 6．在侦查阶段，犯罪嫌疑人聘请律师的，可以_自己__聘请，也可以由其__亲属__代为聘请。除涉及__国家秘密__的案件，律师会见在押的犯罪嫌疑人，不需要经侦查机关批准。 二、判断正误（判断下列各题内容是否正确，正确的在题后括号内打√，错误的打×，每小题2分，共10分） 1．只要取得律师资格，公民就可以以律师身份执业。（×） 2．律师既可以在一个律师事务所执业，也可以根据自身情况，在两个以上律师事务所执业。（×） 3．律师应聘担任法律顾问，与聘方的法律关系，是一种契约关系。（√） 4．曾担任法官、检察官的律师，从人民法院、人民检察院离任后两年内，不得担任诉讼代理人或者辩护人。（√） 5．《中华人民共和国律师法》自1997年10月1日起施行。（×） 三、名词解释（每个5分，共25分） 1．法律顾问 是指法人、非法人组织和自然人，为进行正当经营，提高管理水平，增加社会和经济效益，维护合法利益，而聘任的以其知识和技能提供服务的律师所进行的专业活动。 2．律师见证 是律师应当事人请求，以律师及其工作机构的名义，就本人眼见或亲自审查的法律行为利法律事件，出具文书，证明其真实性、合法性的业务活动。 3．辩护权 就是刑事诉讼中的被告人，依据事实和法律，针对指控、起诉进行辩解、辩驳，以维护他的诉讼权利和合法利益的一项权利。 4．法律咨询 是指专业咨询部门，就国家机关、企业事业单位、社会团体、人民群众提出的有关法律事务的询问，作出解释或说明，提出建议和提供解决方案的一种业务活动。 5．代书 就是律师以委托人的名义，根据事实，依照法律，反映委托人的合法意志，代替委托人书写法律行为文书的创造性的业务活动。 四、简答题（每小题8分，共24分） 1．申请领取律师执业证书，应当提交哪些文件？（1）申请书；（2）律师资格证明；（3）申请人所在律师事务所出具的实习鉴定材料。（2分）（4）申请人身份证件的复印件。（2分）2．律师代理有什么特征？（1）须以被代理人的名义实施法律行为。（2分）（2）在受托的权限范围内独立地进行活动。（2分）（3）实施的法律行为，应能产生民事权利和义务，即具有法律的意义。（2分）（4）进行代理活动所产生的法律后果，应由被代理人承担。3．什么是辩护律师的工作原则？ （1）辩护应以事实为根据，以法律为准绳。（3分）（2）不得轻易拒绝为被告人辩护，而应积极地去维护被告人的诉讼权利和其他合法权益。3）在同检察、审判机关分工的基础上，同他们相互制约。（2分） 五、论述题（14分） 什么是律师制度？它包含哪几方面的内容？ 律师制度是指依照法律，规定律师向社会提供法律服务进行业务活动的原则和任务，方式和内容，权利和义务，以及律师机构的组织原则和管理体制，以利于维护当事人的合法权益，加强法制与发扬民主，而实行的一项法律制度。（4分）它包含以下儿方面内容：1．是一项法律制度，把它等同于司法制度的观点是不科学的。（2．5分）2．以国家法律的确认为其存在的前提，是依法律规定而建立起来的一项法律制度。（2.5分）3．主要是规范律师进行
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D
6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G
《计算机算法设计与分析》习题及答案 一．选择题 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 ）。
枝江英杰学校2014—2015学年度第一学期期中考试 二年级语文试卷 (时间：60分钟满分：100分命题人：孟媛媛) 一、我会看拼音，写词语。（8分） yóu qímín zúɡào sù hù xiānɡ jiào shì tán qín bō lànɡɡuà qiān 二、我会在正确的读音下面打“√”。（5分） 1、孩子如果已经长大，就得（děi d?）告别妈妈。 2、我兴（xìnɡ xīnɡ）奋地走在回家的路上。 3、我们大家都（dū dōu）爬上了天都（dū dōu）峰。 4、大雁在天空排成一行（hánɡ xínɡ）人字。 三、我会比一比，再组词。（8分） 抬（）壮（）杨（）极（） 治（）状（）扬（）吸（） 四、我能把下面的词语补充完整。（6分） （）( )古迹无（）无( ）（）（）可亲徒（）无（）（）苗（）长（）长（）短五、我会查字典（6分）
六、我会照样子，写词语。（10分） 1、例：许许多多 又．细又．长 一．本正经 2、近义词： 例：中心—（中央）格外—著名— 3、例：拍皮球雪人桌子 七、我会选词填空。（4分） 四周四处 1、广场（），灯火辉煌，美极了。 2、他（）张望，找不到妈妈。 急及 1、走路去上学已经来不（）了，丹丹只好请爸爸开车送她上学。 2、飞机快要起飞了，小方还在路上塞车，他很着（）。 八、我会照样子，写句子（8分） 1、例：叶子上的虫还用治？叶子上的虫不用治。 今天怎么可能下雨? ______ __________________。 2、例：李晓庆是我们班的劳动委员。我们班的劳动委员是李晓庆。 我的家乡是美丽的宜昌。_____________ ______________。 3、例：北京真美啊！我要把它画下来。 真__________！我________________ ____________。 4、例：我们飞快地在田野里奔跑。小猴子地爬上葡萄
习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)
m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1） 不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若 ，则包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干 个连通的情形来证明。设 , 对于中的路 若与邻接，则构成一个闭路。若是一条路，由于，因 此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。 证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通；
算法实现题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
Us R[ + R ： 〃 R. R? + （&3 + = O.3A （4 分） 八=—1.2A （&〃&+叫）+ /?3 （4 分）解：11 =1 .9/8（r A 《电工学》试卷二 答案及评分标准 一、 选择题（30分/每小题2分） BBCCB ABACC BBCBC 二、 （12 分） 解：（1）电压源久单独作用时 （2）电流源单独作用时 根据叠加原理，有】 = r + r = -o.9A （4分） 三、 （12分） 解：三要素 %1 初始值 w c （0+） = w c （0_） = （/s =18V （2 分） %1 稳态值 以（8）= _/ /? =—6V （2分） %1 时间常数 ￡ = RC = （R[ + /?2）C = 10% （2 分） 根据三要素法，有 f w c （/） = u c （00）+ [u c （0+） - u c （oo ）]e r =-6 + 24e -l （w, V （2 分） z c （r ） = c 虫哈2 = -1.2e~ 1000/ A （4 分） 四、 （12分） h =―-— = 1.36/-75.7° A I = I\ + l2 =0.86/36.9° A （3分）
P = U/cos （-36.9°） = 146W （3 （4 分） 心M B =3?垣* 1 + 〃 e = （//sin （-36.9°） = -121var （3分） S = 67 = 190V A （3分） 五、（10分） R 解： “A=（l ----- 间 （4 分） & "o =（1 + ：）"A = （1 + ：）（1 + （43）） *3 0 *2 （1六、（ 14 （1 CE ，CE = Uy —/（?&—，E 煌
语文试题答案及评分标准 卷一（选择题，共50分） 一、（本大题10个小题，每小题2分，共20分） 二、（本大题6个小题，每小题3分，共18分） 三、（本大题4小个小题，每小题3分，共12分） 卷二（非选择题，共70分） 四、（本大题5个小题，共15分） 21．（5分） 想要研究自然现象与人类社会的关系，通晓古往今来变化的规律，成为一家之言。 22．（3分） （1）天生我材必有用 （2）我们共享雾霭、流岚、虹霓。 （3）胜似闲庭信步。 （4）以先国家之急而后私仇也。 （5）相逢何必曾相识。 【评分标准】如果答题超过三句，选择正确答案给分。答对一句得1分，答对三句即得满分，答题错误不倒扣分。句中有错别字或漏字、添字，该句不得分。 23．（4分） 五、（本大题5个小题，每小题3分，共15分） 24．（3分） （1）树比人活的长久，但并不以此傲人；（2）树绝对不伤人；（3）树比人坚忍；（4）树
会帮助人。 【评分标准】每点1分，答出三点即可 25、（3分） 这句话运用了象征（托物言志、比喻）的手法，表面上说的是树，实际上说的是人（1分）。“不曾”说明人往往是很坚强的，能够战胜各种不幸和灾难（1分），“却”字使句 意发生了转折，指出人们常常会被名利和赞扬所压垮（1分） 26、（3分） 虔诚、尊敬——嫉妒——自卑、伤感——自信、自强（每一点1分） 27、（3分） 文章的主旨（2分）：我们不管身处何种环境，地位如何卑微，都没有理由也不应该自惭 形秽，而应像小草那样坦然、快乐地生活。 草的特征（1分）：不因卑微而羞愧、安然的怡然挺立。 28、（3分） 感悟如下均可：自卑人人都有，但要勇于面对；人们虽然会在各个方面存在差异，但不 能自惭形秽，要豁达自信；人应该坦然快乐地生活，你就能走出自卑的泥潭，收获属于 自己的成功。 【评分标准】（只要谈到其中的某一点，意思相近即可得2分，能结合实际生活谈2分）六、作文（45分） 29．【评分标准】 说明：①不写题目扣2分； ②不足700字，每少50字扣2分； ③错别字每2个扣1分，重复的不计，最多扣3分； ④卷面不整洁，字迹潦草，不能进入一类卷。 范文 1、学会转身，是生活的智慧 转身是一种生活方式，让达成目标的人们重新审视生活；转身是一种生活态度，是摒弃名利后的一种本质的回归；转身也是一种选择，是对光鲜外表下深藏的隐患的警醒。二战时期纳粹法西斯在欧洲大肆残杀犹太人，匈牙利处于腥风血雨之中。 当时那里有一位意大利籍商人叫佩拉斯卡，在纷乱的战世中，却选择留在匈牙利解救
图论及其应用答案电子科 大 Newly compiled on November 23, 2020
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两 个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通， 而在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从 u 与到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。
模拟电子技术试卷2答案及评分标准 一、判断题(每题1分，共10分) 1.因为N型半导体的多子是自由电子，所以它带负电。（错） 2.在N型半导体中如果掺入足够量的三价元素，可将其改型为P型半导体。（对） 3.放大电路的输出功率是由有源元件提供的。（错） 4.由于放大的对象是变化量，所以当输入信号为直流信号时，任何放大电路的输出都毫无变化；（错） 5.差分放大电路中的发射极公共电阻对共模信号和差模信号都存在影响，因此，这种电路是靠牺牲差 模电压放大倍数来换取对共模信号的抑制作用的。（错） 6.若放大电路的负载不固定，为使其电压放大倍数稳定，可以引入电压负反馈，也可以引入电流负反 馈。（错） 7.电子电压表不可以用来测量三极管放大电路的静态工作电压。（对） 8.功率放大电路的效率是指输出功率与输入功率之比。（错） 9.迟滞比较器的抗干扰能力比过零比较器强。（对） 10.在RC桥式正弦波振荡电路中，若RC串并联选频网络中的电阻均为R，电容均为C，则振荡频率 fo=1/RC。（错） 二、填空题（每空1分，共20分） 1.硅二极管的门槛电压约为0.5v ，导通压降约为0.7v 。 2.要使三极管处于放大状态，发射结必须正偏，集电结必须反偏。 3.根据结构的不同，晶体三极管可分为NPN 和PNP两种类型。 4.理想运算放大器的开环放大倍数A od为_无穷大，输入阻抗R id为无穷大，输出阻抗R od为零_，共模 抑制比为K CMR为无穷大，频带宽度BW为无穷大。 5.功率放大器的基本要求是：1）应有尽量大的输出功率；2）效率要高；3）非线性失真要小； 4）放大管要采取散热等保护措施。
道路勘测设计期末考试试卷(A) 答案及评分标准（样板） 一、名词解释（3分×5＝15分） 1.设计速度：在气候条件好、行车密度小、汽车运行只受道路本身条件影响时,一般司机能保持安全而舒适地行驶的最大速度。 2.动力因数：某型汽车在海平面高程，在滿载情况下，单位车座克服道路阻力和惯性阻力的性能。 评分标准： 答出下划线部分即可得分，每题3分 二、填空题（15分，每空0.5分） 1.方格网式、环形放射式、自由式、混合式。 2. 具有足够的驱动力来克服各种行驶阻力（或R T ≥） 和 驱动力小于或等于轮胎于路面之间的附着力（或k G T ?≤）。 路面平整坚实； 路面粗糙不滑。 3．停车视距；超车视距 评分标准： 每空的分数为0.5分。 三、判断并说明理由（15分, 判断0.5分，说明理由1.0分） 1.错误；应改为：公路等级的确定与远景交通量、使用任务及其性质有关。 2.错误：应改为：横向力系数可以衡量不同重量汽车的在弯道的稳定程度。 3.错误：应改为：按二者最大值计算确定 4.错误：应改为：?=??
的缓和曲线，则超高过渡可仅在缓和曲线的一个区段进行。 答出基本要点得5分；答得不完整酌情扣分。 2．答案及评分标准 要点： 限制最大合成坡度可以防止急弯陡坡组合，引起横向滑移危机行车安全；限制最小的合成坡度主要以防止道路排水不畅，影响行车安全 答出每一要点给2.5分。答得不完整酌情扣分。 五、叙述题与作图题（15分） 1．答案及评分标准 要点： 纸上定线的方法步骤及作用： （1）定导向线。 ①分析地形，找出各种可能的走法。 ②求平距a，并定匀坡线。作用一是放通了路线，证明方案是成立的，二是放坡可发现中间控制点，为下步工作提供依据。 ③确定中间控制点，分段调整纵坡，定导向线。目的是大概定出具有理想坡度的折线，利用了有利地形，避开了不利地形，可作为试定平面线形的参考。 （2）修正导向线。 ①试定平面线形，点绘纵断面图，设计理想纵坡 ②定修正导向线。目的：用纵断面修改平面，避免纵向大填大挖 ③定二次导向线。目的：用横断面最佳位置修正平面，避免横向填挖过大。 （3）具体定线。 在二次修正导向线基础取反复试线，采取直线型定线方法或曲线型定线方法，定出平面线形。 评分标准： 本题共10分。纸上定线的方法步骤6分；作用要点4分，每一要点给1分。 2．答案及评分标准
精品文档习题胡明-版)-王红梅-算法设计与分析(第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
工业机器人技术 试卷B 卷 答案及评分标准 出卷教师： 适应班级： 考试方式： 本试卷考试分数占学生总评成绩的70 % 题号 一 二 三 四 五 总分 核分人 得分 复查总分 总复查人 （本题36分）一、简答(每小题6分，共36分) 1．简述工业机器人的主要应用场合。 1) 恶劣工作环境及危险工作，如：压铸车间及核工业等领域的作业环境。(2分) 2) 特殊作业场合和极限作业，如：火山探险、深海探密和空间探索等领域。(2分) 3) 自动化生产领域，如：焊接机器人、材料搬运机器人、检测机器人、装配机器人、喷漆和喷涂 机器人。(2分) 2．说明工业机器人的基本组成部分。 工业机器人由三大部分六个子系统组成。 三大部分是机械部分、传感部分和控制部分。 六个子系统是驱动系统(1分)、机械结构系统(1分)、感受系统(1分)、机器人－环境交互系统(1分)、人机交互系统(1分)和控制系统。(1分) 3．简述工业机器人关节制动器的作用。 许多机器人的机械臂都需要在各关节处安装制动器, 其作用是: 在机器人停止工作时, 保持机 械臂的位置不变; 在电源发生故障时, 保护机械臂和它周围的物体不发生碰撞。(6分) 4．机器人的新型驱动方式有哪些？新型驱动方式有什么优点？ 磁致伸缩驱动、压电晶体驱动器、形状记忆金属、静电驱动器(4分)。新型驱动方式可以实现驱动元件的简单化和微型化，更适宜于机器人的使用。(2分) 5．试述运用D-H 方法建立机器人运动学方程时，如何建立连杆坐标系？ 建立连杆坐标系的规则如下: ① 连杆n 坐标系的坐标原点位于n +1关节轴线上,是关节n +1的关节轴线与n 和n +1关节轴 线公垂线的交点。(2分) ② Z 轴与n +1关节轴线重合。(2分) ③ X 轴与公垂线重合;从n 指向n +1关节。(1分) ④ Y 轴按右手螺旋法则确定。(1分) 6．工业机器人控制系统的特点有哪些？ (1) 机器人的控制与机构运动学及动力学密切相关。(2分) (2) 是一个多变量控制系统，要求系统具有一定的智能性。(1分) (3) 是一个复杂的计算机控制系统。(1分) (4) 描述机器人状态和运动的数学模型是一个非线性模型,各变量之间还存在耦合。(1分) (5) 机器人的动作往往可以通过不同的方式和路径来完成, 因此存在一个“最优”的问题。(1 分) 得分 评卷人 学院名称 专业班级： 姓名： 学号： 密 封 线 内 不 要 答 题 ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ 密 ┃┃┃┃┃┃┃┃┃┃┃ 封 ┃┃┃┃┃┃┃┃┃┃┃ 线 ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020
习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。
道路勘测设计期末考试试卷（A） 答案及评分标准（样板） 一、名词解释（3分X 5= 15分） 1?设计速度：在气候条件好、行车密度小、汽车运行只受道路本身条件影响时，一般司机能保持安全而舒适地行驶的最大速度。 2.动力因数：某型汽车在海平面高程，在滿载情况下，单位车座克服道路阻力和惯性阻 力的性能。 评分标准： 答出下划线部分即可得分，每题3分 二、填空题（15分，每空0.5分） 1. 方格网式、环形放射式、自由式、混合式。 2. 具有足够的驱动力来克服各种行驶阻力（或T _ R）和驱动力小于或等于轮胎于 路面之间的附着力（或T兰呱）。路面平整坚实：路面粗糙不滑。 3 ?停车视距；超车视距 评分标准： 每空的分数为0.5分。 三、判断并说明理由（15分，判断0.5分，说明理由1.0分） 1.错误；应改为：公路等级的确定与远景交通量、使用任务及其性质有关。 2?错误：应改为：横向力系数可以衡量不同重量汽车的在弯道的稳定程度。 3?错误：应改为：按二者最大值计算确定 4?错误：应改为：：「：：2是取一：二2应为600M 评分标准： 每一题1.5分，判断错误不得分，判断正确但没有改正或改正不正确得0.5分。 四、简答题（4X 5=20分） 1.答案及评分标准
基本要点： 般情况下超高缓和段长度与缓和曲线相同，如果为了线形协调而在平面上布置了较长的缓和曲线，则超高过渡可仅在缓和曲线的一个区段进行。 答出基本要点得 5 分；答得不完整酌情扣分。 2．答案及评分标准 要点： 限制最大合成坡度可以防止急弯陡坡组合，引起横向滑移危机行车安全；限制最小的合 成坡度主要以防止道路排水不畅，影响行车安全 答出每一要点给 2.5 分。答得不完整酌情扣分。 五、叙述题与作图题（15 分） 1．答案及评分标准 要点： 纸上定线的方法步骤及作用： （1）定导向线。 ①分析地形，找出各种可能的走法。 ②求平距a，并定匀坡线。作用一是放通了路线，证明方案是成立的，二是放坡可发现 中间控制点，为下步工作提供依据。 ③确定中间控制点，分段调整纵坡，定导向线。目的是大概定出具有理想坡度的折线， 利用了有利地形，避开了不利地形，可作为试定平面线形的参考。 （2）修正导向线。 ①试定平面线形，点绘纵断面图，设计理想纵坡 ②定修正导向线。目的：用纵断面修改平面，避免纵向大填大挖 ③定二次导向线。目的：用横断面最佳位置修正平面，避免横向填挖过大。 （3）具体定线。 在二次修正导向线基础取反复试线，采取直线型定线方法或曲线型定线方法，定出平面 线形。 评分标准： 本题共10 分。纸上定线的方法步骤 6 分；作用要点4 分，每一要点给 1 分。 2．答案及评分标准
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：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. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人
2017英语试题参考答案及评分标准 第I 卷（选择题, 共65 分） 一～三题 (一) 一～三题答案： 1-5 BCABA 6-10 CACBB 11-15 CCBBA 16-20 BAABC 21 -25 DCBBA 26-30 BDBCC 31-35 CDBAC 36-40 ADCCD 41-45 ABCDD 46-50 AACBB 51-55 DBAAC (二) 评分说明： 1、1-35题，每小题1分; 2、36-55题，每小题1.5分； 3、与答案不符, 不得分。 第II 卷（非选择题, 共55分） 四、听力填表 (一) 答案： 56. next Saturday 57. the school hall 58. sports shoes 59. bring 60. sick （二）评分说明: 1、本题共5分，每小题1分； 2、与所给答案不符，只要语法、意义、拼写（含大小写）正确，符合逻辑及英语表达习惯也可得分； 3、第56、57、58小题，若只写出答案的中心词，如：Saturday、hall(school hall)、shoes 得0.5分。next Saturday中，Saturday首字母小写得0.5分。 五、动词填空 (一) 答案: 61. felt 62. were riding 63. is not /isn’t 64. to see 65. am, looking 66. are told 67. have discovered 68. trying 69. will go/am going 70. can travel (二) 评分说明： 1、本题共10分，每空1分; 2、未用所给动词者，不得分； 3、与所给答案不同，只要语法正确,也可得分。 4、第70小题若答案是will travel，得0.5分。 六、综合填空 (一)答案: 71. best72. whatever/what 73. tired 74. even 75. After 76. also/always77. food 78. health 79. love/like 80. space (二) 评分说明： 1、本题共10分，每空1分; 2、与所给答案不符，只要语法、意义、拼写正确，符合逻辑及英语表达习惯也可得分；
第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn)
证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1]
相关主题
文本预览