西安邮电大学算法考试

1、第1章算法概述(1) 算法的性质包括输入、输出、确定性、有限性。(2) 算法复杂性：算法所运行所需要的计算机资源的量，所需资源多，算法的复杂性高； 反之则复杂性低。时间复杂性：需要时间资源的量(指令数)空间复杂性：需要空间资源的量(存储器的大小)(3) 计算题对于下列国數f(/i)和确足谀黑(旳)或=仗)井简述理由.(1) j (jt) = log rf, g(w) = log 川 + 5(3)/() = w Log h + 歇= log h f(n) = 2rg(ii) = 3n* (I) /(rt= log fl = log h 5 B!l /() = 2lo w 5t?, 弟当r=2时便

2、可H祁在g滿足*则ft =(Xlf(rtl):另一方面* c = l ffj -励;粽上所述则肖/W = #(歆咖*C2 J S为/町荊貞耐鄱星卅L軽掘算泄渐近空羽性阶的含文.液審鸟再到站论：/W 殛0013) /(J2)=MlogW + n. g(n) = bg H I虫c = L时+当、；取2时便可H満是N全儿时2根据递推公式推导出该复杂性表达式二 r(r；h= Z 3Z1 f-2 +2L 2醇式中的报呦为理推第Jfc-1朋;的黄赢 显熬住心+护+2丄+曲构成 祥比教捌本啊中和顶和介叱分别为业= 2,? = X 呦仃ji +1 = log Jt = log -1 代入 h”)2*r(丄+2

3、叭2 有h r(n) = 2* H2) + 2iM-2 = 2十2日4+対J “ - 2 =兰- 2推坤完毕呦卩列寻卄旷讨 冊定 運憶 第卜I次 席71（r） = 71（2）l RJJ 二 2 n “ 耳 23） 分治法所能解决的问题具有的特征.（1 ）该问题规模缩小到一定的程度就可以容易地解决；因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。（2）该问题可分解为若干个规模较小相同问题，即该问题具有“最优子结构性质”。 这条特征是应用分治法前提，它也是大多数问题可满足的，反映了递归思想的应用。（3 ）禾9用该问题分解出的子问题的解可以合并为该问题的解。能否利用分

4、治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。（4 ）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作， 重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。4） 数组A含有9个元素，这些元素恰好是第 2至第10个Fibonacci 数，写出在数组 A 中查找x = 17 的二分查找过程（写出过程即可，不需要写代码）。5/Vi 木河也的上啦止十*材卜肛伽 丸II;tibuHUJci袒刈Rd创公成:1叶=0巩町1冲】n

5、rfi m汁畀时列Hi io r用忘临i皿戏为；F(n -1)+ Fin - 2) 1I. 1,參氛礼X. K, 21, +节則改爼人鬧内冷为h 2.乩?,乳13t 21, 3455很容第歸出誉找3(17的二分査諛过程略)(5 )下面给出了非递归形式的二分搜索方法代码，请补充下划线处的代码。template int Bin arySearch( Type a, const Type& x, int n )II 在a 0 = a 1 = . = a n- 1 中搜索x，找到x时返回其在数组中的位置，否则返回-1int left = 0; int right = n -1;while ( left

6、 a middle ) left = middle +else right = middle - 1;return -1; II未找到 x(6) 判断下列递归算法(计算 n!)是否正确，如果不正确，请说明原因，并改正。int factoral( int i) if ( n 0 )return( n * factoral( n - 1 ) ); 【分析】不正确，因为递归函数没有边界值的判断，无法得出正确的值。另外入口参数与下面的使用不一致。修改如下：int factoral( int n ) if ( n = = 0 ) return 1;retur n( n * factoral( n- 1

7、) ); 第3章动态规划(1) 备忘录法是那种算法的变形( B )。A、分治算法B、动态规划算法C、贪心算法D 、回溯法(2 )分治法与动态规划算法的相同点和不同点是什么？(3 )利用动态规划法设计如下的矩阵连乘最小次数问题，写出动态规划法求解过程。A1: 40X 25 A2 : 25X 25 A3 : 25X 15解：m00=m11 =m22 =m33=0r=2 i=1 j=2m12=40*25*10=10000i=2 j=3m23= 25*10*15=3750r=3 i=1 j=3m13= m11+ m23+ 40*25*15=18750k=2t= m12+ m33+ 40*10*15=1

8、6000m13=t=16000(4) 具有最优子结构的算法有( D )。A.概率算法B 回溯法 C 分支限界法 D 动态规划法(5 )证明题。wm X=环曲斗沖y三侨旳5儿的星幺公共子佯刊为N殆巧则；诞明；軒,口 h儿ft心去.和一则上和y tn仍口鱼具序列【证明】采周反证法；同山玉 芯斗片耳山肚X枷F的械也公真予序列川丄/Y的性共产U 1 jX中:仲的心甫心 d 中】切衆心 小卩肓I：眩人于疋的仑拽亍IMJJT 也即民度为占的呼列才不是|和的#公共子洋列”丁岸也地X训F的丘度太严止的瓷戻子库弼国旳才 册寸于盘*1斥增加了兀需】IU就少无査 iAuLHl的“】咧X = *心宀亦”和F =岀J订

9、的就饪公共尹序列人/.応忙唯旳眉才卅 冈此E竝兀飪曲子疔恻 谒证(6) 计算题| (如吟务 atfq) = (-2J 1,-4J3, -5, -2)K*, AtXTH 和为工还=20k-2(7) 有一个箱子容量为 V (正整数)，同时有n个物品，每个物品有一个体积(正整数)。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。编写程序实现，自定义输入和输出。【提示】使用二维数组f i j ,表示前i个物品装入容量为j的箱子能获得的最大体积，则状态转移方程：f i j = max( f i - 1 j , f i -1 j - a i + a i )；(8) 已知字符串A的值是sot

10、,字符串B的值是stop ,将字符串A转换为字符串B的 编辑距离值为()。A. 1 B 2 C 3 D 4【分析】根据“编辑距离”的定义，可知答案为B。sot通过一个“增加”操作变为stot，然后通过一个“编辑”操作就可以变为stop。注意答案C是错误的。(9) 有一辆货车，货车有载重为D，有n件货物，每个货物有重量 wi ,价值pi。问怎么 装能够使装上货车的物品的总价值最大(使用动态规划算法)【分析】“ 0-1 ”背包问题。第4章贪心算法（1）简述贪心法的基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源

11、。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist 记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S（顶点集合 V “减去”集合S）中取出具有最短特殊路长度的顶点u，将u添加到S中,同时对数组 dist作必要的修改。一旦 S包含了所有V中顶点，dist就记录了从源到所 有其它顶点之间的最短路径长度。贪心算法的两个重要性质：贪心选择性质和最优子结构性质贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。（1） 对于具有最优子结构的问题应该选用贪心算法？（2）是否能用动态规划算法求解的问 题也能用贪

12、心算法求解 ？（2）叶批集装箱要装壬二艘載重星为C的轮船n其中集装箱/的重拭为忖最优装朝间题理求春装載休积不受限制的情况下*将尽可能多的集装筍转上轮那茂问題可KilitZj；max工兀斗 0口。三冲k式中变电召衣可;不装人毎装箱讥可匸1衣们装人朋装箱？证明上述问题具有“贪心选择性质”和“最优子结构性质”。设峯装霜已经按照其卓量从小到大排序.丹,舟“兀是绘吮装栽问题的一个最优解匚又设-1 ”表示装箱的竝小集装箱佯号九则如果给定的最优装戦问题有解，则时，取j, =iyk=0iyI = xIIli 1 w（ 可知因为”最优装救问理求将徭町能多的臺装箱装上轮鄒,j=L曰”.比“儿是满足贪心选择性帧的最

13、优解匚所以垠忧装栽何题員有京心选择性嚴.【迓明】采用反证法.如衆诜找到”轮船诙前i了装船耶装K为謀3”.irrHlh*攝 址处叔同題外 叫解JT.它相对于IT斗=1/屁去，、JQ町凶裳戟更赛的集披韓则耙低诜谄1加入到R中粽产十匝蛤问題的 个解，可L1包含电g的幣饕荷.逍与片尽，,召是堆优解利0得证*(3) 设7个独立作业 1 , 2, 3, 4, 5, 6, 7 由3台相同机器 M1, M2 M3加工处理。 各作业所需的处理时间分别 2 , 14, 4, 16, 6, 5, 3 。任何作业可以在任何一台机器上 加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。按贪心算法产生作

14、业调度，所需加工时间为多少？采用最长处理时间作业优先的贪心选择策略可以设计出解若机调度问删的校好的近似算法，按此第略(设有材个独立的作业山2卅由脇台相同的机器进厅加工处理作业i所需的处理时间为片)*(1)nm时，只嘤将机器f的巴占一时阖IK倒分配命作业即可|2) X心脚呗 嵌将”牛作业依其所需的处理时间从大到小排序=虧依此顺序将作ti is n业分配给空闲的处理机榨业m1245h社豐时hd2144165J址强时冋从大俱1小拙序7*f1i4fr作业数机器S1D-3所需的加T时间为17巾(4) 某体育馆有一篮球球场出租，共有10位客户申请租用。每个客户申请租用的时间单元如下表所示，其中i表示客户编

15、号，s(i)表示开始租用时刻，f(i) 表示结束租用时刻。 同一时刻该篮球球场只能租借给一位客户。请使用贪心算法设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求。并计算出针对上表的10个客户申请，最多可以安排几位客户申请。I12i456791U13I5351166_S4971J121110【分析】这是一个活动安排问题。将这10位客户的申请按照结束时间f(i)递增排序，如F表：i2J4731011)536II4567yIV1!12U(1 )选择申请1 (1,4 )。(2 )依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到所有 申请检查完毕。申请

16、 4( 5,7 )、申请8 ( 8,11 )、申请10 ( 11,13 )。(3) 最后可以满足：申请1 ( 1,4 )、申请4 (5,7 )、申请8( 8,11 )、申请10( 11,13 ) 共4个客户申请。这是可以满足的最大客户人数。(5) 下列哪个问题不能用贪心法求解？()A.最优装载问题 B 活动安排问题 C. 0-1背包问题D 多机调度问题【分析】答案为C。(6) 设有n个程序1,2,.,n要存放在长度为L的磁带上，程序i存放在磁带上的长度为li, 1=i n ) output( x );elsefor ( int i = t; i n ) & rouni t cnunl； rel

17、um ；lf( CDUILt C(Kt )(fori ini j * l；J *n;J+) ift:i|j| = hSetWnrlLA3Algpmat( 1+ ltroust *bt| 1)( J Mil-Os第6章分支限界法(1 )简述回溯法和分支限界法的异同点。分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。二者的不同之 处在于：(1)回溯法的求解目标往往是找出解空间树中满足约束条件的所有解，而分支限 界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解；(2)回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先 或以最小耗费(

18、最大效益)优先的方式搜索解空间树。(2)给定 0/1背包问题，参数为：n = 3, w = 16, 15, 15 , p = 45, 25, 25 , c=30。用队列式分支限界法求解此问题。给出求解过程(包括在求解过程中队列内容的变化 情况)。(3 )布线问题的解空间是图1：程序与算法的区别：算法是给人来读的，直接给计算机是不能执行的；程序可以不满足算法的有限性2:简述分治法的主要思想。将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。 因此分治法可以分为两个重要步骤：(1) 自顶向下：将问题不断分割成小的问题。(2) 自底而上：将小问题解决来构建大问题的解。3：分治

19、法能解决问题所具有的性质 （1）该问题规模缩小到一定的程度就可以容易地解决；因为问题的计算复杂性一般是随着 问题规模的增加而增加，因此大部分问题满足这个特征。（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有“最优子结构性质”。 这条特征是应用分治法的前提， 它也是大多数问题可以满足的， 此特征反映了递归思想的应 用。（3）利用该问题分解出的子问题的解可以合并为该问题的解。 4：动态规划与分治法的相同点和不同点1共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。2. 不同点：01、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独

20、立的； 而分治法中子问题相互独立。02、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解， 而只需查询答案，故可获得多项式级时间复杂度， 效率较高；而分治法中对于每 次出现的子问题均求解， 导致同样的子问题被反复求解， 故产生指数增长的时间复杂度， 效 率较低5：简述贪心算法的基本思想 所谓贪心算法指的是为了解决在不回溯的前提之下， 找出整体最优或者接近最优解的这样一 种类型的问题而设计出来的算法。 贪心算法的基本思想是找出整体当中每个小的局部的最优 解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。 因此能够使用贪心算法 的问题必须满足下面的两个性质： 1