算法试卷

算法设计与分析课程试题一

一、选择题

1．选出不是算法所必须具备的特征（）。

A有穷性B确切性C高效性D可行性

2．下列（）不是衡量算法的标准。

A 时间效率

B 空间效率

C 问题的难度

D 适应能力

3．与递推关系x(n)=2x(n-1)+1,x(1)=1等价的通项公式为（）。

A x(n)=2n

B x(n)=2n-1

C x(n)=2n+1

D x(n)=n!

4．二维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（）。

A 1个

B 2个

C 6个

D 8个

5．下列是动态规划算法基本要素的是（）。

A 最优子结构B构造最优解 C 贪心选择因子D界限函数

6．（）算法应用到广度优先遍历策略。

A 分支界限法

B 动态规划法C分治法D回溯法

7．Prim算法求最小生成树采用的是（）算法思想。

A 贪心算法

B 动态规划法

C 回溯法

D 蛮力法11．三个盘子的汉诺塔，至8．对于凸集下列说法正确的是（）。

A 凸集中的所有点都属于凸包；

B 凸集中任意两点的连线都在凸中；

C 凸集中任意两点的连线都不在凸集中；D一个点集如果不是凸集，则点集中任意两点的连线都不在凸集中少9．对多段图问题描述不正确的是：；

Ａ、多段图是一个无向图Ｂ、可用向前处理法；

Ｃ、可用向后处理法；Ｄ、可用分治法解决。

10．以下对回溯法描述正确的是：；

Ａ、解必须表示成一个2n-元组（x1，x1，x2，x2，﹒﹒﹒，x n，x n）;

Ｂ、回溯法的解必须满足一组综合的约束条件，称为解函数；

Ｃ、满足显示约束的所有元组不能确定一个可能的解空间,

Ｄ、隐式约束描述了元组中元素x i必须彼此相关的情况。

二、填空

1．算法区别于程序：。

2．递推公式x(n)=x(n-1)+n,x(0)=0，x(n)= 。

3．．按分治策略求解棋盘覆盖问题时，对于如图1所示的23×23的特殊棋盘，共需要____个L型骨牌；并在棋盘上填写L型骨牌的覆盖情况。

+ + - + - +

+

+ - - - - + - + + + -

- + + - - + -

- - +

图1 棋盘覆盖 图2 符号三角形

4．对下述五个文件用贪心方法进行最优归并：文件x 1，x 2，x 3，x 4和x 5分别有18，

24，

8，6和

28个记录；则文件移动的最少次数为：

。 5

．常见的智能算法有 、 、 、

。 三、简答题：

1．简述算法的复杂性分析主要是分析算法的什么耗费情况以及算法的时间复杂度用什么计量？

2．简述贪心算法、动态规划和分治算法的基本思想。 3．对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或

或

，并简述理由。

(1)

(2)

(3)

4．试用贪心算法求解下列问题：将正整数n 分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。

三、应用题

1．试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。

2．用动态规划算法求下面网络的最短路：

3已知元素a ，b ，…，h 依次有概率0.1，0.2，0.05，0.1，0.3，0.05，0.15，0.05，其余情况的概率为0，请建立其最优二叉搜索树。（10分） 4考虑下面的用最少硬币个数找出n 分钱的问题。

1）当时用2角5分、一角、5分和1分四种硬币面值时，设计一个贪心算法找出n 分钱，并证明算法能够产生一个最优解。

2）假设可使用的硬币面值是c0，c1，…，ck，其中，c是一个正整数且c>1，k≥1。证明在这种情况下贪心算法总能产生最优解。给出一个贪心算法不能产生最优解的硬币面值组合。

算法设计与分析课程试题二

一、选择题

1．选出不是算法所必须具备的特征（）。

A输入输出性B确定性C可行性D高效性

2．下列函数关系随着输入量增大增加量最快的是（）。

A nlogn B3n3 C3n+2 D n!

3．下列程序段的算法时间复杂度是（）

for (i=1;i<=n;i++)

for (j=1;i<=m;m++)

for (j=1;i<=k;k++)

S;

A O(kn2)

B O(km2)

C O(m+n+k)

D O(mnk)

4．N个盘子的汉诺塔，至少要执行移动操作次数为（）。

A N次

B N2次

C logN次

D 2N-1次

5．以下描述是有关算法设计的基本步骤：

①问题的陈述②算法分析③模型的拟制④算法的实现

⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起

其中正确的顺序是（）。

A、①②③④⑤⑥

B、①③⑤②④⑥

C、②④①③⑤⑥

D、⑥①③⑤②④

6．一个四城市的旅行售货员问题，其解空间的深度为（）。

A 3

B 4

C 5

D 6

7．下列是动态规划算法基本要素的是（）。

A 最优子结构B构造最优解 C 贪心选择因子D界限函数

8．Floyd算法属于（）。

A 贪心算法B概率算法C回溯法D分支限界法

9．（）算法应用到广度优先遍历策略。

A 分支界限法

B 动态规划法C分治法D回溯法

10．下列算法不是智能算法（）。

A 粒子群

B 枚举法C模拟退火D分支限界

二、填空

1．4n2,logn,3n,20n,2,n2/3,n!按渐近阶从低到高顺序排序：、、、。

2．一个具有n个圆盘的Hanoi塔，至少移动___________次圆盘才能达到目标状态。3．对于问题状态S，由根到S的那条路径确定了这个解空间中的一个元组，那么状态S称为。

4．Strassen矩阵乘法可以利用__________算法实现.

5．二分检索平均情况下不成功检索的时间复杂度为：________ 。

6．有设备更新问题如下所示，

五年内收益最大的设备更新策略的最大收益为__________。

7. 概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到________________（完全不同/基本近似）的效果——求解时间甚至是所得的结果。概率算

法大致可以分为四类：数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法。其中________________算法用于求解问题的准确解——但此解未必正确如素数测试问题，而________________算法不会得到不正确的解，但该算法可能找不到问题的解如整数因子分解问题；________________算法则常用于求解数值问题的近似解；________________算法主要体现在设法消除算法最坏情形下的复杂性余特殊实例之间的关联性，如引入随机方法的快速排序算法。

三、应用题。

1．对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或或

，并简述理由。

(1)

(2)

(3)

2．请分别说明分治策略、动态规划、贪心选择策略、回溯法和分支限界法在实际应用中的适用条件。

3．试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。

4．求生成树和最小耗费生成树：

5．试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：

，对于给定的两个整数和，要求用最少的变换和变换次数将变为。

算法设计与分析课程试题三

一、选择题

1、以下描述正确的是：；

Ａ、Ｏ（logn）<Ｏ（n1/2）<Ｏ（n2）<Ｏ（10n）；

Ｂ、Ｏ（n2 /logn）<Ｏ（n（logn）2）<Ｏ（n2）<Ｏ（10n）；

Ｃ、算法可分为多项式时间算法和指数时间算法；

Ｄ、如果｜f(n)｜≡c｜g(n)｜，则记为f(n)＝Ｏ(g(n))。

2．若f(n)=2n3+3n，g(n)=100n2+2n+100，则f=O(g)为（B ）。

A 真

B 假

C 无法确定D均不是

3．Fibonacci数列第5项为（）。

A 3

B 5

C 8

D 13

4．设作业数量Ｎ＝４，作业长度分别为（Ｌ1，Ｌ2，Ｌ３，Ｌ4）＝（３，９，５，７）。那么将他们放在磁带（Ｌ﹥４０）上时，则最佳的放置顺序为：；

Ａ、１，２，４，３；Ｂ、１，３，４，２；

Ｃ、２，４，３，１；Ｄ、４，２，１，３。

5．下列问题一般不采用分治法的是：；

Ａ、检索；Ｂ、选择；

Ｃ、极值；Ｄ、15－迷。

6．一维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（）。

A 1个

B 2个

C 6个

D 8个

7．下列问题中具有多项式解法的是（）。

A背包问题B生成排列序列问题 C n个元素的排序问题 D 集合的幂集问题

8．排列问题属于（）。

A 可解问题B不可解问题 C P问题 D NP问题

9．对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。

A、回溯法

B、分支限界法

C、回溯法和分支限界法

D、回溯法求解子集树问题

10．12个金币中有一枚是假币，至少需要称量的次数是（）。

A 0

B 1

C 3

D 4

二、填空

1．算法的五个重要特性是：________、_________、_________、_________、_________。2．用贪心方法求解背包问题的约束条件是：_____________________________。

3．设有n个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成。如果n=2k，循环赛最少需要进行________天；如果n=2k+1，循环赛最少需要进行_____________天。其中，k为正整数。

4．用分支限界法求解0-1背包问题时，对于每个物品j有重量w j和价值v j，考虑当前物品i，已装入背包中物品的重量和价值分别为cw、cv，剩余物品的价值上界为urv，剩余容量为c，目前已有的最优价值为bestp，则当左儿子满足约束条件____________属于可行结点时，就将它加入活结点队列中；当右儿子满足上界条件_____________时才将它加入活结点队列中。

5．快速排序法的基本思想是重新排列关键字，把一个文件分成两个文件，使得第一个文件中所有元素均小于第二个文件中的元素；然后再对两个子文件进行同样的处理。其算法如下：

算法（快速排序是一种递归算法）：

Qsort(L,k,m)//L待排序序列，k、m是分类文件之首、末关键字(1,n)

Begin

if k < m then

begin

Split(L,k,m,i)//将L分组

Qsort(L,k,i-1)

Qsort(L,i+1,m)

end

end

Split(L,k,m,i) //将序列L进行分组

Begin

i=k,j=m,x=L(k)

while __________ do

begin

while __________ do j=j-1

if j<>i then L(i)=L(j),i=i+1

while (L(i)j) do i=i+1

if i<>j then L(j)=L(i),j=j-1

end

__________

End

7．已知作业队列及其所需要运行的时间为t1=2，t2= 5，t3= 8，t4= 1，t5= 5，t6= 1），在三台处理器上运行，按贪心法调度总运行时间为__________，最佳运行时间为__________。

吉普车总装油量为500L，耗油量为1L/里，要自行设置燃料库穿越1000里的沙漠，使用倒推法首先应共设置__________个站点，第一个距离起点__________里，存放__________L油，总耗油量达到最少，即__________L。

三、解答题

1．证明：O(f)+O(g)=O(f+g)

2．求下列函数的渐近表达式：

3n2+10n; 21+1/n;

3．分别用快速分类法、归并分类法把元素序列（3，1，4，1，5，9，6，5，3，5，8，9，7）分类，并分析每种情况下的比较次数。

四、编程与求解

1、（编程）。做一个“二分”检索程序，它将原集合分成１／４和３／４大小的两个集合，并求出这种算法时间复杂度。

2、（求解）用动态规划的方法求解下述背包问题：效益Ｐ＝（11，21，31，33，43），重量Ｗ＝（1，11，21，23，33），背包可承重量Ｍ＝45，Ｎ＝5。

3、在下列数据上模拟快速排序过程。

（4，5，6，7，8，4）

4、有以下7个作业，他们的效益值和期限分别为（p1，p2，p3，p4，p5，p6，p7）＝（3，5，20，18，1，6，30）和（d1，d2，d3，d4，d5，d6，d7）＝（1，3，4，3，2，1，2），利用贪心算法求解改作业排序问题的最优解。（写清楚关键步骤）

5、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：

(1) 删除一个字符。

(2) 插入一个字符。

(3) 将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。

6、试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：

。对于给定的两个整数和，要求用最少的变换和变换次数将变为。

2013华科计算机学院硕士学位研究生复试细则

关于做好2013年计算机学院硕士学位研究生复试、录取工作的通知根据教育部《2013年招收攻读硕士学位研究生管理规定》和《2013年招收攻读硕士学位研究生管理规定实施细则》、《教育部关于加强硕士研究生招生复试工作的指导意见》（教学【2006】4号），学校《关于做好2013年硕士研究生复试、录取工作的通知》，现将我院硕士学位研究生复试、录取工作通知如下。 一、复试、录取工作原则 1、坚持德智体全面衡量、保证质量、科学选拔、择优录取、宁缺勿滥的原则。 2、严格按照初试成绩确定参加复试考生名单并实行差额复试。 3、根据初、复试总成绩决定正式录取名单并公示。 4、坚持公正、公平、公开，各工作环节保证做到有章可循。 二、复试、录取工作组织领导 1、我院成立招生复试工作领导小组，具体领导、组织学院的复试、录取工作。 2、成立复试小组，在学校招生工作领导小组和学院招生复试工作领导小组指导下开展复试工作。 3、成立监察小组，检查我院在招生录取工作中对国家招生政策、法律、制度和纪律的贯彻执行情况，依法对参与招生工作人员履行职责情况进行监督。 三、硕士生入学考试考生参加复试分数线基本要求 1、学术型学位：总分基本要求320分，政治理论50分，英语一50分，数学一80分，计算机学科专业基础综合80分。 2、专业学位：总分基本要求320分，政治50分，英语二50分，数学二80分，计算机学科专业基础综合80分。 3、强军计划：总分基本要求245分，政治40分，英语40分，数学40分，计算机学科专业基础综合40分。 4、少数民族高层次骨干计划：按国家规定执行。 四、复试、录取工作具体办法及时间安排 1、我院复试时间是3月14日至18日。 2、参加复试考生名单见研究生院招生信息网，实行差额复试。我院不再以邮寄等其它方式发复试通知单。 3、我院将按照专业进行复试。参加复试的考生须填报志愿（见附件）、并于3 月12日前发送到指定的邮箱。 4、3月14日，考生凭身份证、准考证，毕业证书原件（非应届生）或学生证（应届生），直接到计算机学院研究生科（南一楼西侧438室）报到。报到时，每位考生需交复试费100元并领取银行记账凭证。考生的资格审查在复试报到时进行，凡未进行资格审查或资格审查未通过的考生一律不予录取。

大学计算机专业课程介绍

大学计算机专业课程介绍 课程名称：面向对象程序设计课程编码：1015501 适用专业：计算机科学与技术 课程内容：本课程主要介绍面向对象程序设计原理和方法，内容有：1.面向对象程序设计概述，数据的抽象和封装，继承性，多态性；2.C＋＋源程序的构成，C＋＋在非面向对象方面的一些新的扩展；3.类和对象；4.派生类与继承；5.多态性等。 教材：《C++面向对象程序设计教程》陈维兴林小茶编著清华大学出版社 课程名称：软件工程课程编码：1020602 适用专业：计算机科学与技术 课程内容：本课程主要介绍软件工程原理，内容有：1.软件危机与软件工程；2.可行性研究；3.需求分析；4.总体设计；5.详细设计；6.编码；7.软件测试；8.维护；9.面向对象方法学引论；10.面向对象分析；11.面向对象设计；12.面向对象的实现等 教材：《软件工程导论》（第三版）张海藩编清华大学出版社 参考书：《实用软件工程》郑人杰等清华大学出版社 课程名称：离散数学课程编码：1014601 适用专业：计算机科学与技术 课程内容：本课程主要介绍离散数学原理，内容有：1.集合论:集合、关系、映射；2.图的基本概念、图的遍历、平面图、有向图；3.代数系统：代数结构，概念、性质、运算，半群、独异点、群与子群，陪集与拉格朗日定理，同态与同构、环；4.数理逻辑：命题逻辑、谓词逻辑等。 教材：《离散数学》第一版郭希娟主编吉林科技出版社 参考书：《离散数学》赵树春辽宁教育出版社 课程名称：计算机组成原理课程编码：1014801 适用专业：计算机科学与技术 课程内容：本课程主要介绍计算机组成原理，内容有：1.计算机系统概论；2.数据化信息编码与数据表示；3.计算机的逻辑部件；4.运算器；5.指令系统；6.中央处理器部件（CPU）；7.存储系统；8.辅助存储器；9.输入输出设备；10.输入输出系统；11.计算机系统等。 教材：《计算机组成与结构》（第二版）王爱英主编清华大学出版社 参考书：《计算机组成原理》（第二版）白中英科学技术出版社 课程名称：高级语言及程序设计课程编码：1020501 适用专业：计算机科学与技术 课程内容：本课程主要介绍数据库常用开发工具，内容有：1.C语言概述；2.数据类型、运算符与表达式；3.最简单的C程序设计；4.逻辑运算和判断选取控制；5.循环控制；6.数组；7.函数；8.编译预处理；9.指针；10.结构体与共

算法导论 第三版 第21章 答案 英

Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1

算法设计与分析(简略版)

中国地质大学研究生课程论文封面 课程名称算法设计与分析 教师姓名 XXXXXX 研究生姓名侉哥 研究生学号 1201666666 研究生专业 XXXXXXXXXXXXX 所在院系计算机学院 类别: A.博士 B.硕士√ C.进修生 日期: 2016.1.12

《算法设计与分析》课程报告 本学期，我选修了XXX教授的《算法分析与算法设计》这门课程。课堂上，戴老师条理清晰、深入浅出地为我们讲解了算法复杂度、分支算法、贪心算法、动态规划算法、基本检索与周游方法、回溯算法和分支-限界法等知识内容。此外，还为我们介绍了NP-难度和NP-完全的问题。 第一章导引与基本数据结构 老师首先引入编程实现两矩阵相乘和编程实现求证平行四边形两个例子，举例说明现阶段计算机算法可以解决的问题（计算问题）和不可以解决（几何证明）的问题。 接着老师指出算法是指计算的方法，而计算是基于规则的变换，物理角度可以理解为是基于规则的物理状态的变换，也可以理解为是基于规则的信息的变换。接着老师讲解了算法的三个重要特性：无二义性、能解性、有限性。当然算法的特性还包括输入和输出。 之后老师讲解了算法设计与分析的含义，讲了计算模型的假设和两个重要的量：问题的规模和频率计数。也就是空间复杂度和时间复杂度的分析方法，根据时间复杂度，算法一般可以分为多项式时间复杂度（P算法）和指数时间复杂度（NP算法）。 多项式时间内可以执行完成的算法是P算法，例如时间复杂度为： O(1)

算法导论第二章答案

第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort(T[] Input) where T:IComparable { T key; int i; for (int j = 1; j < Input.Length; j++) { key = Input[j]; i = j - 1; for (; i >= 0 && Input[i].CompareTo(key)>0;i-- ) Input[i + 1] = Input[i]; Input[i+1]=key; } } 揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j] 这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1. 如果按照大部分计算机编程语言的思路，修改为： INSERTION-SORT(A) 1 for j ← 1 to length[A] 2 do key ←A[j] 3 i ←j-1

算法导论 第三版 第六章 答案 英

Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1

信息安全专业课程书籍推荐

[转载]武大信息安全专业课程简介(四) (2011-07-10 01:16:12)转载原文 标签：转载 原文地址：武大信息安全专业课程简介(四)作者：柏拉图的思念 武大信息安全专业课程简介(四) 2006-12-27 13:57 模式识别 Pattern Recognition 7、课程简介 本课程是信息安全专业的专业选修课。模式识别是一门理论与应用并重的技术科学，与人工智能关系密切，其目的是用机器完成人类智能中通过视觉、听觉、触觉等感官去识别外界环境的工作。本课程主要介绍了模式识别的主要几种方法，基于统计学的决策论方法，基于句法分析的结构方法和集成方法,及相关应用。 9、指定教材 《模式识别》，杨光正等，中国科学科技大学出版社，2003。 10、参考书目 《模式识别原理、方法及应用》，J．P．Marques de sa，清华大学出版社，2002。 《模式识别》，边肇祺，清华大学出版社，2000。 算法设计与分析 The Design and Analysis of Algorithms 7、课程简介 本课程是计算机科学与技术专业的专业必修课，信息安全专业的专业选修课。本课程旨在培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，为学生进一步学习奠定良好的基础。 10、指定教材 《计算机算法基础》（第二版），余祥宣、崔国华、邹海明，华中理工大学出版社 11、参考书目 《Fundamentals of Computer Algorithms》,E,Horowitz and S.Sahni, Computer Science Press,1978 《The Design and Analysis of Computer Algorithms》A. V. Aho, J. E. Hopcrort, and J.D.Ullman,Addison-Wesley Publishing Company,1978 《Introduction To Algorithms》(Second Edition),T H Cormen 、C. E. Leiserson 、R.. L. Rivest and C. Stein, The MIT Press,2001 编译原理 The Principles of Compiler 7、课程简介 本课程是计算机科学与技术专业的专业基础必修课，信息安全专业的专业选修课。开设本课程的目的是使学生了解并掌握编译过程中所涉及的基本理论和方法，具备分析和实现编译程序的基本能力。 10、指定教材 《编译原理》，何炎祥、李晓燕、王汉飞编著，华中科技大学出版社，2000。 11、参考书目 《程序设计语言编译原理》（第三版），陈火旺、刘春林等，国防工业出版社，2000。 《计算机编译原理》，张幸儿，科学出版社，1999。 《编译原理》，吕映芝等，清华大学出版社，1998。

算法导论 第三版 第七章 答案 英

Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1

智能交通专业

智能交通专业 辅修专业（学位）培养方案 专业主任（签字）： 学院/系（盖章）：交通科学与工程学院 2019年4月

本科就读于非交通运输大类专业的学生，在修满第一学年主修专业规定的全部课程学分后，可在第一学年末或第二学年初符合学校辅修条件，按照全校统一时间安排申请修读本辅修专业（学位）。 一、培养目标 具有系统的工程实践经历，能够从事智能交通的设计开发、工程应用、运行管理等方面工作，能够推动智能交通领域的发展和进步拔尖创新人才。 （1）熟悉智能交通的国内外现状和发展趋势；（2）具备系统思维和智能交通思维能力，能够综合运用交通工程、大数据挖掘、人工智能等专业知识、技能和方法，独立解决与辅修专业相关的智能交通问题；（3）具有跨学科能力、团队合作能力和有效的交流能力。 二、培养要求 1. 掌握并能够运用智能交通专业所需的相关基本理论和基础知识，了解本专业领域的前沿发展现状和趋势； 2. 掌握文献检索及运用现代信息技术获取相关信息的基本方法； 3. 掌握科学的思维方法，具有综合运用所学理论、知识和技术设计智能交通系统的能力； 4. 具有对智能交通工程问题进行系统表达、建立模型、分析求解、论证优化的能力； 5. 具有进行智能交通系统开发和设计、技术改造与创新设计的基本能力； 6. 具有一定的国际视野和跨文化交流、竞争与合作的初步能力； 7. 具备终身教育的意识，具有继续学习和适应社会和科技发展的能力。 三、主干学科 交通运输工程 四、辅修课程 （1）“大学计算机—计算思维导论”及计算机语言相关课程，在辅修之前需获得相应学分（该学分不含在辅修学分要求内）。在修读“人工智能”、“机器学习”课程前，学生需先完成“概率论与数理统计”、“线性代数”、“微积分”课程的学习并获得学分。 （2）辅修期间完成以下课程的学习，共25学分。 专业基础课程与平台课程，共11学分：交通工程学（2.0学分），人工智能（2.0学分），Python 语言（2.0学分），计算机算法基础（3.0学分），机器学习（2.0学分）。 专业核心课程，共8学分：数字图像处理（2.0学分），智能交通控制（2.0学分），交通系统建模与仿真（2.0学分），交通大数据应用（2.0学分）。 专业选修课程，共6学分。其中，以下课程任选2门，4学分：交通地理信息系统（2.0学分），自动驾驶与车联网（2.0学分），公路基础设施智能管理技术（2.0学分），桥梁结构智能检测（2.0学分）。以下课程任1门，2学分：基础设施智能建设概论（2.0学分），BIM三维实景建模（2.0

算法导论 第三版 第二章 答案 英

Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i]

第二单元参考书目

第二单元参考书目 考试科目 考试覆盖内容及参考书 代数学基础N. Jacobson, Basic Algebra I, II. Basic Algrbra I 中的Galois理论；Basic Algebra II中的第一章（范畴理论）、第三章（模论）、第四章（环论）、第七章（交换代数） 微分几何《微分几何讲义》（第二版），陈省身、陈维桓著，1983年，1版，北京大学出版社。《黎曼几何初步》，伍鸿熙著，北京大学出版社。 实分析与复分析庄圻泰，张南岳《复变函数》，北京大学出版社，1984年。周民强《实变函数》，北京大学出版社，有新版。 泛函分析（甲）《泛函分析讲义》（上、下册），张恭庆、林源渠著，北京大学出版社。John B.Conway: A Course in Functional Analysis, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985. 分析与代数复旦大学数学系陈传璋等编《数学分析》高等教育出版社，2000年版。北京大学数学系几何与代数教研室代数小组编《高等代数》(修订版)高等教育出版社，1988年版。 高等概率论《测度论基础》，严加安，科学出版社。 数理统计《高等数理统计》，峁诗松，王静龙，濮晓龙，高等教育出版社，1998 偏微分方程（甲）《二阶椭圆型方程与椭圆型方程组》第一部分（陈亚浙、吴兰成著，科学出版社出版。《数学物理方程》，复旦大学数学系主编，高等教育出版社。 近世代数《代数》（英文版），（美）I. Martin Isaacs（威斯康星大学麦迪逊分校）著，机械工业出版社。 运筹学基础 运筹学导论(初级篇第8版)，作者：(美)塔哈；译者：薛毅、刘德刚、朱建明、侯思祥；校注：:韩继业； 出版：人民邮电出版社，2008年 计算机科学基础《离散数学》，左孝凌著，上海科技文献出版社。《计算机算法基础》，邹海明、余祥宣著，华中科技大学出版社。《形式语言与自动机理论》，John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman，清华大学出版社。 决策分析《决策分析》陈珽著，科学出版社，1991年。 经济学

算法导论 第三版 第24章 答案 英

Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1

Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v)

《计算机算法基础》第三版,课后习题答案

4.2在下列情况下求解递归关系式 T(n)= () 2(/2)() g n T n f n ? ? + ?否则 足够小 n 当①n=2k g(n)= O(1)和f(n)= O(n)； ②n=2k g(n)= O(1)和f(n)= O(1)。 解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) =…… =2k T(1)+2k-1f(2)+2k-2f(22)+…+20f(2k) =2k g(n)+ 2k-1f(2)+2k-2f(22)+…+20f(2k) ①当g(n)= O(1)和f(n)= O(n)时， 不妨设g(n)=a，f(n)=bn，a，b为正常数。则 T(n)=T(2k)= 2k a+ 2k-1*2b+2k-2*22b+…+20*2k b =2k a+kb2k =an+bnlog2n= O(nlog2n) ②当g(n)= O(1)和f(n)= O(1)时， 不妨设g(n)=c，f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+…+20d=c2k+d(2k-1) =(c+d)n-d= O(n) 4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j) integer mid if low≤high then mid←??2/) (high low+ if x=A(mid) then j←mid; endif if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

《算法导论2版》课后答案_加强版2

1 算法导论第三次习题课 2008.12.17

2 19.1-1 如果x 是根节点：degree[sibling[x]] > sibling[x] 如果x 不是根节点：degree[sibling[x]] = sibling[x] –119.1-3 略

3 19.2-2 过程略( union 操作) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2-6 算法思想：找到堆中最小值min ，用min-1代替-∞. [遍历堆中树的根节点]

4 15.1-1 15.1-2 略P195 或P329 15.1-4 f i [j]值只依赖f i [j-1]的值，从而可以从2n 压缩为2个。再加上f*、l*、l i [j]。 Print-station(l, I, j ) //i 为线路，j 为station if j>1 then Print-station(l, l i [j], j-1 ) print “line”I, “station”j;

5 15.2-1 略（见课本） 15.2-2 15.2-4 略 MATRIX-CHAIN-MULTIPLY(A, s, i, j) if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j), j) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1,j) return MATRIX-MULTIPLY(x, y) else return A i

6 15.3-1 （归纳法）递归调用 枚举15.3-2 没有效果，没有重叠子问题 15.3-4 略 (3)n Ο3/2(4/) n n Θ

187武汉光电国家实验室-华中科技大学2014硕士研究生复试细则

武汉光电国家实验室2014年硕士研究生考研复 试分数线及复试办法 根据学校有关规定，结合我们实验室的具体情况，特制定此复试工作细则，本细则适用我实验室学术型和专业型所有专业。 一、复试工作领导小组及复试小组 在实验室党总支和行政监查全程监控下，成立武汉光电国家实验室研究生招生工作领导小组和研究生复试工作小组，保证招生工作的公开、公平性，增强透明度，加强对考生全面素质的考核，坚持德智体全面发展，确保生源质量。 二、复试人员的培训（略） 三、招收学科及招生计划 2014年实验室招收科学学位72名：包括光学工程、电子科学与技术、计算机科学与技术、生物医学工程、生物医学光子学；招收专业学位9名：包括计算机专业、光学工程、信息与通信工程、生物医学工程专业的硕士生； 四、复试分数线和上线名单 复试分数线见“华中科技大学研究生招生信息网”；总上线人96名，复试名单查询“华中科技大学研究生招生信息网” 五、复试工作安排 （一）报到：到武汉光电国家实验室研究生工作组（光电国家实验室D202）报到时，每位考生需交复试费100元。 （二）具体安排如下 3月13日（星期四） 上午08:30—11:30，下午14:30—17：30复试学生报到。

3月14日（星期五） 上午宣读政策和心理健康测试（具体时间和地点报到时公布或见实验室网站通知） 下午14:00所有统考考生到校医院进行体检（准备1寸照片一张，体检费为35元,请学生自备零钱。体检不要求空腹。请考生在体检表中注明光电国家实验室学院字样（光电国家实验室代码为 187）。（本校免推生的体检时间为3月15号上午，体检卡请在3月13号来D202领取；外地免推生没有体检的，可以在当地医院体检之后，将体检报告单邮寄到D202） 报考计算机专业的考生3月14号晚上笔试，其他专业3月15号上午笔试 3月15日（星期六）： 全天复试（笔试+面试），复试地点东九，详细地址报到时通知 3月18日（星期二）：上午10：00公示复试后的加权平均成绩，学生与导师进行双向选择。 六、复试主要内容 （一）英语听说测试（占复试总成绩的20%） 按照华中科技大学硕士研究生复试英语听说测试实施办法执行。 （二）专业笔试（占复试总成绩的40%） 1.报考计算机专业的研究生： ●时间：计算机专业的与计算机学院相关专业共同组织复试：3月14号晚上笔 试，3月15日上午上机，3月15日下午英语听说测试，3月15号晚上综合面试（具体时间报到时通知）。 ●地点：东九（具体地点报到时通知）