算法设计与分析试卷(A卷)
⼀、选择题（选择1-4个正确的答案, 每题2分，共20分）
（1）计算机算法的正确描述是：
机械工程学报英文B．算法是⼀个有穷规则的集合，其中之规则规定了⼀个解决某⼀特定类型的问题
的运算序列。
C．算法是⼀个对任⼀有效输⼊能够停机的图灵机。
D．⼀个算法，它是满⾜5 个特性的程序，这5个特性是：有限性、确定性、能⾏性、有0个或多个输⼊且有1个或多个输出。
A．算法设计的策略 B．问题的规模
C．编译程序产⽣的机器代码质量 D．计算机执⾏指令的速度
（3）⽤数量级形式表⽰的算法执⾏时间称为算法的
A．时间复杂度 B．空间复杂度 C．处理器复杂度 D．通信复杂度 （4）时间复杂性为多项式界的算法有：
A．快速排序算法 B．n-后问题 C．计算值 D．prim算法
（6）衡量近似算法性能的重要标准有：
A．算法复杂度 B．问题复杂度 C．解的最优近似度 D．算法的策略
（7）分治法的适⽤条件是，所解决的问题⼀般具有这些特征：
A．该问题的规模缩⼩到⼀定的程度就可以容易地解决；
B．该问题可以分解为若⼲个规模较⼩的相同问题；
C．利⽤该问题分解出的⼦问题的解可以合并为该问题的解张锷
D．该问题所分解出的各个⼦问题是相互独⽴的。
（8）具有最优⼦结构的算法有：
A．概率算法 B．回溯法 C．分⽀限界法 D．动态规划法
（10）适于递归实现的算法有：
A．并⾏算法 B．近似算法 C．分治法 D．回溯法
三、简答题（每⼩题5分，共10分）
（13）算法的复杂度分析涉及哪些⽅⾯？
（14）动态规划法的指导思想是什么？
四、计算题（每⼩题8分，共24分）
（15）⽤动态规划法求A10*30B30*20C20*10D10*200运算量最⼩的乘积顺序。要求写出求解过程，并将结果填⼊数组m[4][4]中。
(16) ⽤贪⼼法求下图的最⼩⽣成树
16
（17）马步问题：在n*n的⽅棋盘中，马只能⾛“⽇”字。马从初始位置（x0,y0）出发，
把棋盘的每⼀格都⾛⼀次，且只⾛⼀次（遍历）。求出n=5时马的⾏⾛路线。
五、分析设计题（每⼩题8分，共16分）
（18）有16个选⼿参加循环赛，循环赛⼀共进⾏15天，每个选⼿必须与其他的 15个选⼿
各赛⼀场，每个选⼿⼀天只⽐赛⼀次；设计⼀个满⾜上述要求的⽐赛⽇程表。
（19）某市场营销⼈员从他所在城市(顶点1)出发，到其他5个城市去做市场调查，如下图
19所⽰。请设计⾏⾛路线。
19
⼀、不定项选择题（每空3分，共60分）：
1、以下关于算法设计问题的叙述中正确的是__________。
A 、计算机与数值问题的求解——⽅程式求根、插值问题、数值积分、函数逼近
等有关
B 、利⽤计算机⽆法解决⾮数值问题
C 、计算机在解决分类、语⾔翻译、图形识别、解决⾼等代数和组合分析等⽅⾯
的数学问题、定理证明、公式推导乃⾄⽇常⽣活中各种过程的模拟等问题中，主要进⾏的是判断、⽐较，⽽不是算术运算
D 、算法设计与分析主要研究对象是⾮数值问题，当然也包含某些数值问题
2、算法的特征包括__________。
A 、有穷性
B 、确定性
C 、输⼊和输出
D 、能⾏性或可⾏性
6、在⼀个有向连通图中（如下图所⽰），出点A 到点B 的⼀条最短路为__________。
A 、最短路：1→3→5→8→10，耗费：20
B 、最短路：1→4→6→9→10，耗费：16
西南科技⼤学试题单（H ）
计算机学院：课程名称:《算法分析与设计》课程代码: 14314025命题单位：软件教研室学院：________ 专业班级：_______学号：□□□□□□□□命题共2页第1 页
C、最短路：1→4→6→9，耗费：12
D、最短路：4→6→9→10，耗费：13
⼆、填空（每空2分，共20分）：
1、快速排序法的基本思想是重新排列关键字，把⼀个⽂件分成两个⽂件，
使得第⼀个⽂件中所有元素均⼩于第⼆个⽂件中的元素；然后再对两个⼦⽂件进⾏同样的处理。其算法如下：
算法（快速排序是⼀种递归算法）：
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
ocd
if i<>j then L(j)=L(i),j=j-1
end
__________
End
2、有设备更新问题如下所⽰，
五年内收益最⼤的设备更新策略的最⼤收益为__________。
3、已知作业队列及其所需要运⾏的时间为t1=2，t2= 5，t3= 8，t4= 1，t5= 5，t6= 1），在三台处理器上运⾏，按贪⼼法调度总运⾏时间为__________，最佳运⾏时间为__________。
吉普车总装油量为500L，耗油量为1L/⾥，要⾃⾏设置燃料库穿越1000⾥的沙漠，使⽤倒推法⾸先应共设置__________个站点，第⼀个距离起点__________⾥，存放__________L油，总耗油量达到最少，即__________L。
三、解答题（要求给出解答步骤，尤其强调所⽤⽅法；共50分）：
1．给定M=45，(P1,P2,P3,P4,P5,P6)=(11,8,15,18,12,6),
苗颖
(W1,W2,W3,W4,W5,W6)=( 5,3, 2,10, 4,2)
利⽤贪⼼法出背包问题的最佳解，再⽤分枝限界法并进⾏⽐较。（20分）
2．⽤动态规划算法求以下⽹络的最短、最长路径。（15分）
3．算法设计：旅⾏售货员问题（即TSP问题）。（15分）
要求：1）说明所使⽤的算法策略；
2）写出算法实现的主要步骤；
3）分析算法的时间、空间复杂性。
⼀、填空题(选做5道，10分)
1．四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（）树；巡回售货员问题的搜索空间为（）树。2．（）法的求解⽬标是出解空间树中满⾜约束条件的所有解，⽽（）法的求解⽬标则是出满⾜约束条件的⼀个解，或是在满⾜约束条件的解中出在某种意义下的最优解。
3．回溯法⼀般以（）优先的⽅式搜索解空间树，
⽽分⽀限界法则⼀般以（）优先或以最⼩耗费优先的⽅式搜索解空间树。
⼆、单项选择题(10分)
1．下列哪些问题不能⽤贪⼼法求解？（）
A) 霍夫曼编码问题B) 单源最短路径问题
一期缝合C) 0-1背包问题D) 最⼩⽣成树问题
2．在快速排序算法中引⼊随机过程的主要⽬的是什么？（）
A) 改善确定性算法的平均运⾏时间
B) 保证算法总能在O(n lg n)时间内结束
C) 避免了算法最坏情况下的发⽣
D) 改善了确定性算法最坏情形下的平均运⾏时间
3．⽤Monte Carlo⽅法估计四后问题回溯算法的效率。（）五次实验结果分别为<1,4,2>、<2,4,1,3>、<4,2>、<3,1,4,2>、
<1,3>，则解空间中的结点数估计为？
A) 16 B) 16.2 C) 17 D) 16.5
1.流⽔作业调度问题中，作业,i j不满⾜Johnson不等式时，交换它们的加⼯顺
序后，加⼯时间（）（增加、不增加、减少、不减少、不变）。
2.动态规划算法通常以（）的⽅式解各⼦问题，⽽贪⼼算法通常以（
）的⽅式进⾏迭代。
3.优化问题主要由两个部分组成（）和（）。
4.贪⼼算法的核⼼问题是（）。
5.当所给的问题是从n个元素的集合S中出满⾜某种性质的⼦集时，相应的
解空间树称为（），通常有（）个叶⼦结点，遍历此空间树需要（）的计算时间。
6.按照活结点表的组织⽅式的不同，分⽀限界法包括（）和（
）两种形式。
7.最⼤优先队列分⽀限界法中，优先值较（）的结点优先级较⾼，通常
⽤（）实现，体现（）的原则。
8.算法复杂性依赖于（）、（）、（）。
9.递归的两个基本要素包括（）和（）。
10.⽤贪⼼算法求解的问题⼀般具有两个重要性质（）和（）。江阴市华西实验学校
11.背包问题和0－1背包问题中，可以⽤贪⼼算法求解的问题是（）。
12.含有n个顶点的连通图的⽣成树含有（）条边。
13.状态空间树的搜索⽅法主要包括深度优先搜索、⼴度优先搜索和（）
搜索。
14.所给的问题是确定n个元素满⾜某种性质的排列时，相应的解空间树称为（），通常有（）个叶⼦结点，遍历此空间树需要（）的计算时间。
15.分⽀限界法中，通常以（）作为活结点表的数据结构。
16.最⼩优先队列分⽀限界法中，优先值较（）的结点优先级较⾼，通常
⽤（）实现，体现（）的原则。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议