当前位置:首页 >> IT/计算机 >>

算法分析与设计_西南科技大学试题单(I)

西南科技大学试题单(I)
计算机学院:课程名称:《算法分析与设计》课程代码: 14314025 命题单位:软件教研室

学院:________ 专业班级:_______学号:□□□□□□□□ 命题共 3 页第 1 页

一、填空题:
说明:本题包含 8 个小题,15 个空,每空 2 分,小计 30 分。

1、按照渐近阶从低到高的顺序排列下列表达式: 20n,4n2,logn,3n,2,n2/3,n!,2n。 ______________________________________________________________ 2、分治法的基本思想是将一个规模为 n 的问题分解为与原问题 ____________(相同/不相同)的 k 个规模较小且____________(互相独立/相 关)的子问题。 3、一个直接或间接地调用自身的算法称为____________,它有两个条件, 一个是要直接或间接地调用自身,另一个是必须有____________。 4、在一个 n×n(n=2k)个方格组成的特殊棋盘中,需要____________个 L 型骨牌完成棋盘覆盖。 5、在循环赛日程表问题中,若给定的运动员数 n=2k-1,则至少需要 ____________天完成比赛;n=2k 时,则需要____________天。其中,k 为自然 数。 6、 动态规划算法的主要步骤包括刻画最优解的性质和结构、 递归定义最优 值、以自底向上的方式计算最优值、根据计算最优值的相关信息构造最优解, 在分析了最优解的性质和结构之后,一个比较至关重要的步骤是给出最优值的 递归定义,请给出下面几个问题的最优值的递归定义: (1) 矩阵连乘积问题中,A[i:j]连乘所需的最少乘法次数定义为 m[i,j](1 ≤i≤j≤n) ,m[i,j]的初始值定义为 0(i=j) ,则 m[i,j]递归定义为: m[i, ,j]=________________________________________________ (2) 最长公共子序列问题中,c[i,j]表示序列 Xi 和 Yj 的最长公共子序列的长 度,则 c[i,j]可递归定义为:

i = 0, j = 0 ?0 ? c[i, j ] = ? _ _____________________________ i, j > 0; xi = y j ? _ _____________________________ i, j > 0; x ≠ y i j ?
7、 在使用回溯法考虑求解一个具体问题时, 往往需要设计出约束条件和限 界条件。 装载问题的约束条件是____________; 限界条件是 bestw>cw+r, 其中, bestw 是当前最优值,cw=____________,r=____________。 8、0-1 背包问题的回溯法和分支限接法求界中都涉及到活结点的上界函数 uProfit 的计算问题,它是由两部分组成,一是该活结点已经获得的价值之和

Profit , 另 一 个 则 是 剩 余 未 考 虑 物 品 的 价 值 上 界 rProfit , 这 个 值 可 通 过 ______________________________________________________获得。

二、求解题:
说明:本题包含 6 个小题,1~3每题 7 分,4~6 每题 10 分,小计 51 分。

1、请用快速排序法升序排序下面实例,给出每一趟排序的结果。 .......... (3,20,5,9,2,30,25,18,16,3) 2、已知元素 a,b,…,h 依次有概率 0.1,0.2,0.05,0.1,0.3,0.05,0.15, 0.05,其余情况的概率为 0,请建立其最优二叉搜索树。 ....... 3、用动态规划算法求下面网络的最短路: .....
6 2 4 1 5 3 8 5 7 6 4 9 6 8 9 4 7 5 5

4、求解如下递归式,已知 T(1)=1,a、b、c 均为常数且 a=b=c=1。 (1)T(n)=aT(n-1)+bn (2)T(n)=aT(n/2)+bnc 5、有 0-1 背包问题如下: n=6,c=20,P=(11,8,15,18,12,6) ,W=(5,3,2,10,4,2) 。 试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。 6、有如下城市网络图:
1 1 5 5 2 3 4 1 3 3 4 4 7 2 2

试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。

三、证明题:
说明:本题包含 2 个小题,第 1 题 8 分,堤 2 题 11 分,小计 19 分。

1、若 T(n2/2r)=nT(n)+bn2(其中 r=0,T(2)=2)则 T(n)=O(n(logn)rloglogn)。 2、试证明流水作业调度问题的 Johnson 算法是满足 Johnson 法则的最优调

度。
其中: ·流水作业调度问题的 Johnson 算法是: (1)令 N1={i|ai<bi},N2={i|ai≥bi}; (2)将 N1 中的作业按 ai 非减序排序,将 N2 中的作业按 bi 非增序排列; (3)N1 中的作业接 N2 中的作业就构成满足 Johnson 法则的最优调度。 ·满足 Johnson 法则的调度是最优调度,调度π满足 Johnson 法则,当且仅当对任 意 i<j,有 min{bπ(i),aπ(j)}≥min{bπ(j),aπ(i)}


相关文章:
西南科技大学试题单(J).doc
西南科技大学试题单(J)计算机学院:课程名称:《算法分析与设计》课程代码: ..
一、填空(每空3分,共30分)解读.doc
一、填空(每空3分,共30分)解读 - 西南科技大学试题单(E) 计算机学院:课程名称:《算法分析与设计》课程代码: 14314025 命题单位:软件教研室 学院:___...
西南科技大学试题单(B).doc
西南科技大学试题单(B)计算机学院:课程名称:《算法分析与设计》课程代码: 14
西南科技大学网络教育学院(学年第 学期试题单〈I卷〉.doc
西南科技大学网络教育学院(课程名称: 语言学概论 ) /( )学年第 学期试题单I 卷〉 专业班级: 命题教师: 郑剑平 学生姓名: 学号: 成绩: 考试时间: 月日第...
西南科技大学网络教育学院试题答案单〈A卷〉.doc
西南科技大学网络教育学院试题答案单〈A卷〉_医药卫生_专业资料。西南科技大学...i =1 S 2 (n) = 1 n ∑ ( X i ? X ) 2 (10 分) n i =1 ...
西南科技大学材料分析方法复习题(含答案)_图文.pdf
西南科技大学材料分析方法复习题(含答案)_其它_高等教育_教育专区。西南科技大学...(3)把待测相的三强线的 d 值 I/I1 值与这些卡片上各物质的三强线 d ...
2007西南科技大学试题单 (B 卷)答案.doc
2007西南科技大学试题单 (B 卷)答案_理学_高等教育_教育专区。光电子技术
西南科技大学网络教育学院试题答案单〈J卷〉.doc
个人资料整理,仅限个人学习使用,请勿商用 西南科技大学网络教育学院试题答案单〈 ...包括方案设计、组织、实施、监察、 稽查、记录、分析结果和报告,共十三章七十条...
西南科技大学C语言程序设计复习题(含答案).pdf
西南科技大学C语言程序设计复习题(含答案)_工学_...制定正确的算法 C.制定正确的算法和选择合理的数据...D.for(i=1;i<5;i++) ww D.C 语言源程序...
西南科技大学网络教育学院( )( )学年第学期试题单〈 A卷〉.doc
西南科技大学网络教育学院( )( )学年第学期试题单〈 A卷〉_远程、网络教育_...A.按职能设计 B.按行业设计 C.接服务对象设计 D.按重要性设计 13.公共...
西南科技大学线性代数期末试题(含答案).pdf
西南科技大学线性代数期末考试题一、填空题(将正确答案填在题中横线上。每小题...(I + A) ∴ 2 (I + A) = 0 ,∵ (I + A) = 0 ww w. z 五...
2005西南科技大学期末无机及分析化学A卷及答案解析.doc
2005西南科技大学期末无机及分析化学A卷及答案解析 - 西南科技大学试题单(A 卷) 院别:材料 课程名称:无机及分析化学 A 课程代码:2861 命题人:化学系 学院: ...
西南科技大学高频电子线路期末复习题单.pdf
西南科技大学高频电子线路期末复习题单 - 一、填空题 1.电磁波在自由空间传播,
西南科技大学网络教育学院试题答案单〈 B卷〉_图文.doc
西南科技大学网络教育学院试题答案单〈 B卷〉_医药...I A / I > ξ 、整体剪力墙、整体小开口剪力墙...分析和构件内力计算,按规范进行截面设计,然后采取相应...
西南科技大学电路分析期末考试试卷及答案分析.doc
(12 分) i 2i + 4? R 2? + 2? 图 10 6V - 第 3 页共 11 页 *密* 西南科技大学 20092010 学年第 2 学期 《 电路分析 1 》期末考试试卷...
西南科技大学网络学院 程序设计语言VB试卷_图文.pdf
西南科技大学网络学院 程序设计语言VB试卷 - 西南科技大学试题 程序设计语言
西南科技大学网络教育学院试题答案单〈A卷〉.doc
西南科技大学网络教育学院试题答案单〈A卷〉 - 西南科技大学网络教育学院试题答案单〈A 卷〉 课程名称: 动态网页设计(jsp) 命题教师: 第一、单项选择题(每小题...
现代设计方法_习题集(含答案).doc
《现代设计方法》课程习题集西南科技大学成人、网络教育学院 版权所有习题【说明】 :本课程《现代设计方法》 (编号为 09021)共有单选题,计算题,简答 题, 填空题...
西南科技大学微型计算机控制技术复习题答案.pdf
西南科技大学微型计算机控制技术复习题答案_IT认证_...N 次采样值相加, 然后把所得的数除 增量型算法与...( 积分( I )控制 在积分控制中,控制器的输出与...
西南科技大学大学物理(A1)期末考试试题(第四套).doc
西南科技大学大学物理(A1)期末考试试题(第四套)_...(A) i ? 5j (B) 2i ? 7 j (C) 0 (D)...(D) 8 6 7 8 9 11、对于一定质量的单原子分子...