软件设计师历年试题-算法.ppt

软件设计师历年试题 算法 1990年下午试题五 阅读下列说明和流程图 回答问题1和2 有一个集合 集合中有n个元素 每个集合元素都是正整数 它们存放在一维数组A中 每个数组元素存放一个集合元素 对给定的整数total 假定集合中每个元素的值均小于total 流程图求出所有满足下列条件的子集 子集中各元素之和等于total 本题在使用试探法找出全部解答的过程中 依次选取当前的候选元素 尝试组成一个小于total的部分和 如果合适 则选取下一元素试探 若不合适 则回溯取另一个候选元素尝试 题中利用s栈存放候选元素的下标 用它实现回溯 如果候选元素加上部分和等于total 则表示找到一个解答 然后通过回溯 再试探寻找其它的解答 问题1 流程图中的 应与A D中的哪一点相连 并填充图中的 使之成为完整的流程图 问题2 设total 10 n 6 数组A中各元素的值为 8 4 1 2 5 3 若图中的 1 框改为sp 0 则执行该流程图后输出什么结果 1990年下午试题五 问题1 i s sp T A s sp T s sp 1 D 问题2 J 1时输出的解为 824123415253J 2时输出的解为 4123415253J 3时输出的解为 253J 4时输出的解为 253J 5 6时无解 1993年下午试题七 程序说明 对于正整数n 输出其和等于n且满足以下限制条件的所有正整数的和式 即组成和式的数字自左至右构成一个非递增的序列 如n 4 程序输出为4 44 3 14 2 24 2 1 14 1 1 1 1 k深度分解将要分解出的和数a k 应该为k 1度分解所分解出的和数a k 1 和其余数的较小者 因为和式要降序排列 1993年下午试题七 程序中给出了分别采用递归和非递归解法的两个函数rd 和nd 函数rd 采用递归解法 它有两个参数n和k 其意义分别是被分解和式的数n 及当前第k深度分解 算法思想是对n的所有合理的和式分解 将分解出的数 称为和数 存于数组a 中 当其中一个分解已不再需要进一步分解时 即找到一个解 将存于数组a 中的一个完整和式的和数输出 当还需要进一步分解时 以要进一步分解的数及分解深度为参数 递归调用分解和式函数 1993年下午试题七 函数nd 以要分解的数为参数 另开设一个数组r 用于存贮当前还未分解的余数 在求一个解的第k步时 a k 为第k个和数 r k 为相应的余数 当找到一个分解后 此步r k 等于0 输出解 并作回溯处理 从当前k退回到第一个不为1的和数 将其减1 并将其余数加1 准备去找另一个解 否则 生成下一步的分解和数与余数 defineMAXN100inta MAXN r MAXN rd intn intk 递归求解 intj i for j j 1 j 依次求解 a k j if 判断k深度分解是否为解 printf d d a 0 a 1 找到解for i 2 i k i printf d a i printf n else 不是解 递归求k 1深度的分解 执行过程rd 4 1 rd 3 2 rd 2 2 rd 2 3 rd 1 4 n a k 1 n a k 1 n a k 或n j rd n j k 1 重点 数组a的变化 nd intn 回溯法求解 inti k k 0 r 0 n do if 和 相同的判断 printf d d a 0 a 1 for i 2 i0 k 找到解后回溯if k 0 a k r k else a k 1 生成下一步分解的和数和余数r k 1 r k a k 1 k while k 0 r k 0 a k 1 a k r k a k r k 1993年下午试题七 inttest data 3 4 5 main inti for i 0 i sizeof test data sizeof int i a 0 test data i rd test data i 1 printf n n n nd test data i printf n n n 1995年下午试题七 程序说明 本程序用回溯算法来产生由0或1组成的2m个二进位串 使该串满足以下要求 视串为首尾相连的环 则由m位二进制数字组成的2m个子序列 每个可能的子序列都互不相同 例如 如果m 3 在串11101000首尾相连构成的环中 由3位二进制数字组成的每个可能的子序列都在环中恰好出现一次 它们依次是111 110 101 010 100 000 001 011 见图 1995年下午试题七 defineNl024 defineM10intb N M 1 intequal intk intj intm 判断数组b中保存的串中是否有相等子串 inti for i 0 i m i if b k i 1 return0 return1 b中k开始的m个字符是否与b中j开始的m个字符相等 一旦有不同 则子串不等 b j i 1995年下午试题七 intexchange intk intm intv 将b中新加入的从k开始的子串的最后一个0或1变成1或0 while b k m 1 v 需回溯 b k m 1 v 2 3 v returnk 不回溯 init intv intk for k 0 k N M 1 k b k v k b k m 1 1995年下午试题七 main intm v k n j printf Enterm 1 m 10 v v 0 v 1 n scanf d d k 1 1996年下午试题三 阅读以下说明和E R图 回答问题 讲解答写在答卷的对应栏内 说明 设有下列关于运动会管理系统的E R图 图中矩形表示实体 圆表示属性 双圆表示关键字属性 菱形表示实体之间的关系 假定已通过下列SQL语言建立了基本表 CREATETABLEATHLETE ANOCHAR 6 NOTNULL ANAMECHAR 20 ASEXCHAR 1 ATEAMCHAR 20 CREATETABLEITEM INOCHAR 6 NOTNULL INAMECHAR 20 ITIMECHAR 10 IPLACECHAR 20 CREATETABLEGAMES ANOCHAR 6 NOTNULL INOCHAR 6 NOTNULL SCORRECHAR 10 为了答题的方便 图中的实体和属性同时给出了中英文两种名字 回答问题时只需写出英文名即可 1996年下午试题三 E R图 1996年下午试题三 问题 填充下列SQL程序3 1 3 4中的 使它们分别完成相应的功能 程序3 1 统计参加比赛时运动员人数SELECT FROMATHLETEWHEREASEX M 程序3 2 查100872号运动员参加的所有项目及其比赛时间和地点SELECTITEM INO INAME ITIME IPLACEFROMGAMES ITEMWHERE AND 1996年下午试题三 程序3 3 查参加100035项目的所有运动员名单SELSECTANO ANAME ATEAMFROMATHLETEWHERE SELECT FROMGAMESWHEREGAMES ANO ATHLETE ANOANDINO 100035 程序3 4 建立运动员成绩视图 ATHLETE SCOREASSELECTATHLETE ANO ANAME ATEAM INAME SCOREFORM WHEREATHLETE ANO GAMES ANOANDGAMES INO ITEM INO 1996年下午试题三 1 COUNT 2 GAMES INO ITEM INO3 GAMES ANO 100872 注 2 3可互换4 EXISTS5 4 5也可为4 ANO IN5 ANO6 CREATEVIEW7 ATHLETE ITEM GAMES 三项可交换 1997年上午题第5题 从以下叙述中选出5条最确切的叙述 把相应编号依次写在答卷的A E栏内 在数据库系统中 数据独立性指数据之间的相互独立 互不依赖 SQL语言的视图定义和视图操作功能不支持逻辑数据的独立性 SQL语言中不提供显式地使用索引的功能 支持了物理数据的独立性 用户对 脏数据 的读出是由于数据库完整性规则受到了破坏 在数据库系统中 数据的安全性是指保护数据以防止未被授权用户的蓄意或者无意使用 1997年上午题第5题 实体完整性规则指主关键字值的任何组成部分都不可以是空值 引用完整性规则则不允许引用不存在的实体 即元组 在数据库系统中 数据的完整性是指数据的正确性和有效性 授权 是数据库系统中采用的完整性措施之一 事务处理 Transaction 是数据库运行的基本单位 如果一个事务处理成功 则全部数据行到更新和提交 如果失败 则已做的全部更新被恢复成原状 好象整个事务处理未进行过一样 这样使数据库保持了一致性 对数据库的查找 增添 删除 修改等操作都需由数据库管理员进行完整性定义和安全性授权 由数据库系统具体执行 1997年上午题第5题 答案 35679 1997年下午试题八 程序说明 一个相连的区域被不规则地分割成n个不同的小区域 每个小区域与若干其它小区域相邻接 现用cn种不同颜色为该区域着色 要求每个小区域着同一种颜色 相邻小区域着不同颜色 设小区域被顺序编号为0 1 n 1 每个小区域与其它小区域的邻接关系用两维数组bordering表示 元素bordering i j 表示i号小区域与j号小区域之间的邻接关系 0 j小区域与i小区域不邻接1 j小区域与i小区域相邻接 1997年下午试题八 程序中 把计算结果存入于两维数组colored中 颜色编号为0 1 cn 1 元素colored coler j 的含义是 0 j小区域不用颜色color着色1 j小区域用颜色color着色函数colorcountry bordering colored n cn 根据所给的小区域邻接关系数组bordering 小区域个数n 颜色数cn 将找到的着色方案记录在数组colored中 函数采用试探法找解 首先从第一个小区域着第一种颜色开始顺序为各小区域找着色方案 对某个小区域 当为它找到一种未被它的相邻小区域着色的颜色时 就用该颜色对该小区域着色 并准备处理下一个小区域 当不能为某个小区域找到一个未被它的相邻小区域着色的颜色时 就回溯 如最终为全部小区域找到着色方案 函数返回1 否则 函数返回0 程序假定小区域个数不超过20 颜色数为4 include definen20 defineCN4intcolorcountry intbordering N intcolored N intn intcn intcolor used i c for color 0 color cn color 设置所有区域均未着色for i 0 i n i colored color i 0 c 0 从第1个小区域开始color 0 从着第1种颜色开始试探 while c n 还未对全部小区域着色时循环while 1 顺序对每种颜色作试探 检查当前颜色是否已被某相邻小区域着色for i 0 used 0 used print intcolored N intn intcn 输出结果 char colortbl RED BLUE GREEN YELLOW intcolor i for color 0 color cn color printf n s n colortb1 color for i 0 i n i if colored color i printf t d i printf n intcolored CN N bordering N N main intc i j n printf Enternumberofareas scanf d 1 3分 color cn答color 4给3分 答color cn给2分 2 3分 bordering c i colored color i 答bordering c i 1 colored color i 1给3分 答bordering c i colored color i 1给3分 而将其中相等运算符 写成赋值运算符 时 只给1分 其中bordering c i 可写成bordering i c 左右只对一半给2分 3 3分 colored color c 答colored color c 给2分 答colored color 给1分 答c 给1分 4 3分 colored color c 0或 colored color c 或colored color c 1 5 3分 colored color c 答colored color c 给2分 答colored color 给1分 1998年下午试题七 程序说明 本程序的函数sum inti inttotal intsigma intrear intd intn 用来从已知数组d的前n个元素中找出所有部分元素序列之和等于total的元素序列 约定数组d的元素都是正整数 且都小于等于total 函数sum使用递归方法找出全部解答 参数i表示递归函数当前考虑元素d i 参数sigma是调用前已选取的部分序列的元素和 参数rear是后面还未考虑的那部分元素的元素和 函数对元素d i 有两种可能的选择方案 1998年下午试题七 1 考虑元素d i 被包含在新的部分元素序列中的可能性 如果在当前部分元素序列之后接上d i 新序列的元素和不超过total 则函数将d i 包含在当前部分元素序列中 如果新的部分元素序列的元素和等于total时 新的部分元素序列就是一个解答 函数将其输出 否则 若继续考虑后面的元素还有可能找到解答时 函数就递归去考虑后面的元素 寻找解答 最后 函数应恢复原来部分元素序列中不包含d i 的状态 2 考虑元素d i 不被包含在新的部分元素序列中的可能性 如果继续向d i 之后考虑还是有希望能得到和为total的部分元素序列时 函数将新序列不包含d i 也作为一种可能的选择 并递归去考虑后面的元素 寻找解答 1998年下午试题七 include stdio h defineN100inta N intflg N 1998年下午试题七 main inti j n total s d printf 输入total n scanf d s sum inti inttotal intsigma intrear intd intt intj 考虑d i 被包含在新的部分元素序列中的可能性if sigma d i total sum i 1 total 2 rear d i d n 3 sigma d i sigma d i flg i 0 1998年下午试题七 考虑元素d i 不被包含在新的部分元素序列中的可能性if i total sum i 1 total 4 rear d i d n sigma 1999年下午试题六 程序6说明 本程序从n种不同重量 不同价值的物品中选取一部分物品 要求在不超过限定重量limw的前提下 使被选取的那些物品的总价值较大 这里约定limw不超过n种物品的重量总和 也没有一种物品的重量超过limw 并且各物品的价值都大于0 程序中 n种物品被顺序编号为0 n 1 1999年下午试题六 include defineN100doublelimw intopts N 存储临时最佳的选择方案structelem doubleweight doublevalue a N 物品的重量和价值信息intk n struct intflg 物品的考虑状态 0不选 1将被考虑 2曾被选中doubletw 已达到的总重量doubletv 期望的总价值 twv N 当前候选解中各物品的考虑状态 以及候选解的状态 1999年下午试题六 main doublemaxv find printf Enternumberofmatter scanf d 1999年下午试题六 next inti doubletw doubletv 考虑i号物品 twv i flg 1 twv i tw tw twv i tv tv look inti int f double tw double tv 取i号物品在解中的状态信息 f twv i flg tw twv i tw tv twv i tv doublefind structelem a intn inti k f doublemaxv 0 tw tv totv 0 0 for k 0 k 0 look i totv a k value tw a i weight i 1 tw a i weight tv case0 i break 不选 回退default f 2 曾被选中twv i flg 0 if 4 不选i号物品可行吗if i n 1 后面还有物品吗next 5 i else maxv tv a i value for k 0 k n k opts k twv k flg 0 i break returnmaxv tv a i value maxv i 1 tw tv a i value 2001年试题11 12 递归算法的执行过程 一般来说 可先后分成 11 和 12 两个阶段 11 A 试探B 递推C 枚举D 分析 12 A 回溯B 回归C 返回D 合成BB 2001年试题13 14 若一个问题的求解既可以用递归算法 也可以用递推算法 则往往用 13 算法 因为 14 13 A 先递归后递推B 先递推后递归C 递归D 递推 14 A 递推的效率比递归高B 递归宜于问题分解C 递归的效率比递推高D 递推宜于问题分解DA 2001年试题15 贪心算法是一种 的算法 A 不求最优 只求满意B 只求最优C 求取全部可行解D 求取全部最优解A 贪心算法一般可以快速得到满意的解 因为它省去了为找到最优解而穷尽所有可能所耗费的大量时间 常以当前情况为基础做最优选择 而不考虑各种可能的整体情况 所以贪心算法不要回溯 2001年下午试题五 程序5说明 著名的四色定理指出任何平面区域图均可用四种颜色着色 使相邻区域着不同的颜色 本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案 程序中用1 4表示四种颜色 要着色的N个区域用0 N 1编号 区域相邻关系用adj 矩阵表示 矩阵的i行j列的元素为1 表示区域i与区域j相邻 矩阵的i行j列的元素为0 表示区域i与区域j不相邻 数组color 用来存储着色结果 color i 的值为区域i所着颜色 2001年下午试题五 include stdio h defineN10voidoutput intcolor 输出一种着色方案 inti for i 0 i N i printf 4d color i printf n 2001年下午试题五 intback int ip intcolor 回溯 intc 4 while c 4 if ip 0 return0 已回溯到0号区域 ip c 1 color ip 1 returnc 返回该区域原来的着色方案 1 color ip 2001年下午试题五 检查区域i对颜色c的可用性intcolorOK inti intc int N intcolor intj for j 0 j i j if 2 return0 return1 2 adj i j 1 color j c 2001年下午试题五 为区域i选一种可着的颜色intselect inti intc intadj N intcolor intk for k c k 4 k if colorOK 3 returnk return0 3 i k adj color intcoloring intadj N 寻找各种着色方案 intcolor N i c cnt for i 0 i N i color i 1 i c 0 cnt 0 while 1 if c 4 0 c back 4 select i c 1 adj color 5 color i c 2001年下午试题五 voidmain intadj N N 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 printf 共有 d组解 n coloring adj 2002年试题11 算法是对问题求解过程的一类精确描述 算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的 这说明算法具有 11 特性 A 正确性B 确定性C 能行性D 健壮性C 附 算法的性质 有穷性 一个算法必须保证在有限个操作步骤执行后终止 一般指操作步骤或完成操作的时间在合理的范围内确定性 算法中每个步骤含义明确 无二义性 可行性 算法中描述的操作都可通过有限次的基本运算来实现输入 一个算法应具有零个或多个输入 输出 一个算法应具有一个或多个输出 2002年试题12 快速排序算法采用的设计方法是 A 动态规划法 DynamicProgramming B 分治法 DivideandConquer C 回溯法 Backtracking D 分枝定界法 BranchandBound B 2002年试题13 14 在数据压缩编码的应用中 哈夫曼算法可以用来构造具有 的二叉树 这是一种采用了 的算法 A 前缀码B 最优前缀码C 后缀码D 最优后缀码A 贪心B 分治C 递推D 回溯BA 2002年试题17 下述函数中渐进时间最小的是 17 A T1 n nlog2n 100log2nB T2 n 2nlog2n 100log2nC T3 n n2 100log2nD T4 n 4nlog2n 100log2nA先考虑最高阶 再考虑相同阶的系数 2002年试题19 21 对于给定的一组关键字 12 2 16 30 8 28 4 10 20 6 18 按照下列算法进行递增排序 写出每种算法第一趟排序后得到的结果 快速排序 选第一个记录为基准元素 得到 19 二路归并排序得到 21 19 A 10 6 18 8 4 2 12 20 16 30 28B 4 2 6 10 8 12 28 30 20 16 18C 2 4 6 8 10 12 16 18 20 28 30D 6 10 8 28 20 18 2 4 12 30 16 21 A 2 12 16 8 28 30 4 6 10 18 20B 2 12 16 30 8 28 4 10 6 20 18C 12 2 16 8 28 30 4 6 10 28 18D 12 2 10 20 6 18 4 16 30 8 28答案 19 B21 B 2002年下午试题五 程序说明 背包问题 的基本描述是 有一个背包 能盛放的物品总重量为S 设有N件物品 其重量分别为w1 w2 wn 希望从N件物品中选择若干件物品 所选物品的重量之和恰能放入该背包 即所选物品的重量之和等于S 如下程序均能求得 背包问题 的一组解 其中程序5 1是 背包问题 的递归解法 而程序5 2是 背包问题 的非递归解法 2002年下午试题五 include defineN7 defineS15intw N 1 0 1 4 3 4 5 2 7 typedefstruct ints 背包剩余容量intn 物品的下标intjob 物品当前状态 KNAPTP 程序中用栈来保存已考查过的物品 结构KNAPTP表示经过考查的物品 2002年下午试题五 intknap ints intn 递归算法 if s 0 return1 if s0 n 1 return0 if 1 printf 4d w n return1 return 2 1 knap s w n n 1 2 knap s n 1 w N 1 0 1 4 3 4 5 2 7 intknap ints intn 非递归算法 KNAPTPstack 100 x inttop k rep x s s x n n x job 0 top 1 stack top x k 0 while 3 x stack top rep 1 while k rep if x s 0 k 1 已求得一组解elseif x s 0 x n 0 rep 0 else x s 4 x job 1 5 x 4 x s w x n 5 stack top if k rep 1 while top 1 rep x stack top 不选该物品if x job 1 x s w x n 1 x job 2 stack top x 6 结束循环考查下个 if k 输出一组解while top 1 x stack top if x job 1 printf d t w x n 1 returnk 6 rep 0 3 top 0 k 2002年下午试题五 main if knap S N printf OK n elseprintf NO n 2003年试题9 将两个长度为n的递增有序表归并成一个长度为2n的递增有序表 最少需要进行关键字比较 9 次 A iB n 1C nD 2nC 2003年试题64 对n个元素进行快速排序时 最坏情况下的时间复杂度为 64 A O 1og2n B O n C O nlog2n D O n2 D 2004年11月试题52 采用动态规划策略求解问题的显著特征是满足最优性原理 其含义是 52 A 当前所出的决策不会影响后面的决策B 原问题的最优解包含其子问题的最优解C 问题可以找到最优解 但利用贪心法不能找到最优解D 每次决策必须是当前看来最优决策才可以找到最优解B 2004年11月试题53 下面函数中渐进时间最小的是 53 A T1 n n nlognB T2 n 2n nlognC T3 n n2 lognD T4 n n 100lognD 2004年11月试题54 下面的程序段违反了算法的 54 原则 voidsam intn 2 while odd n n 2 printf n A 有穷性B 确定性C 可行性D 健壮性A 2004年11月试题55 拉斯维加斯 LasVegas 算法是一种常用的 55 算法 A 确定性B 近似C 概率D 加密C概率算法允许算法在执行过程中可随机地选择下一个计算步骤 在许多情况下 当算法在执行过程中面临一个选择时 随机性选择常比最优选择要省时 因此可在很大程度上降低算法的复杂度 还有是蒙特卡罗 MontaCarlo 算法 2004年11月试题56 在分支 界限算法设计策略中 通常采用 56 搜索问题的解空间 A 深度优先B 广度优先C 自底向上D 拓扑排序B 2004年11月试题57 58 在下列算法设计方法中 57 在求解问题的过程中并不从整体最优上加以考虑 而是做出在当前看来是最好的选择 利用该设计方法可以解决 58 问题 A 分治法B 贪心法C 动态规划法D 回溯法A 排序B 检索C 背包D 0 1背包BC 2004年11月试题59 60 以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O nlogn 下面的排序算法中 最坏情况下计算时间可以达到O nlogn 的是 59 该算法采用的设计方法是 60 A 归并算法B 插入算法C 选择算法D 冒泡算法A 分治法B 贪心法C 动态规划法D 回溯法AA 2005年5月试题53 54 为在状态空间树中 53 可以利用LC 检索 LeastCostSearch 快速找到一个答案结点 在进行LC 检索时 为避免算法过分偏向于做纵深检查 应该 54 53 A 找出任一个答案结点B 找出所有的答案结点C 找出最优的答案结点D 进行遍历 54 A 使用精确的成本函数c 来作LC 检索B 使用广度优先检索C 使用深度优先检索D 在成本估计函数 中考虑根结点到当前结点的成本 距离 CD 2005年5月试题56 利用动态规划方法求解每对结点之间的最短路径问题 allpairsshortestpathproblem 时 设有向图G 共有n个结点 结点编号1 n 设C是G的成本邻接矩阵 Dk i j 即为图G中结点i到j并且不经过编号比k还大的结点的最短路径的长度 Dn i j 即为图G中结点i到j的最短路径长度 则求解该问题的递推关系式为 A Dk i j Dk 1 i j C i j B Dk i j min Dk 1 i j Dk 1 i j C i j C Dk i j Dk 1 i k Dk 1 k j D Dk i j min Dk 1 i j Dk 1 i k Dk 1 k j D 2005年5月下午试题四 说明 假设需要将N个任务分配给N个工人同时去完成 每个人都能承担这N个任务 但费用不同 下面的程序用回溯法计算总费用最小的一种工作分配方案 在该方案中 为每个人分配1个不同的任务 程序中 N个任务从0开始依次编号 N个工人也从0开始依次编号 主要的变量说明如下 c i j 将任务i分配给工人j的费用 task i 值为0表示任务i未分配 值为j表示任务i分配给工人j worker k 值为0表示工人k未分配任务 值为1表示工人k已分配任务 mincost 最小总费用 2005年5月下午试题四 include defineN8 N表示任务数和工人数intc N N unsignedintmincost 65535 设置min的初始值 大于可能的总费用inttask N temp N worker N voidplan intk unsignedintcost k为任务号 inti if 1 k N cost c k i mincost i k 1 worker i 0 voidmain inti j for i 0 i N i 设置每个任务由不同工人承担时的费用及全局数组的初值worker i 0 task i 0 temp i 0 for j 0 j N j scanf d 2005年11月试题53 54 求解某问题的递归算法如右 求解该算法的计算时间时 仅考虑算法Move所做的计算为主要计算 且Move为常数级算法 则算法F的计算时间T n 的递推关系式为 设算法Move的计算时间为k 当n 4时 算法F的计算时间为 A T n T n 1 1B T n 2T n 1 C T n 2T n 1 1D T n 2T n 1 1A 14kB 15kC 16kD 17k F intn ifn 1Move 1 else F n 1 Move n F n 1 CB 2005年11月试题55 56 利用贪心法求解背包问题时 55 能够确保获得最优解 用动态规划方法求解0 1背包问题时 将 用前i个物品来装容量是X的背包 的0 1背包问题记为KNAP 1 i X 设fi X 是KNAP 1 i X 最优解的效益值 第j个物品的重量和放入背包后取得效益值分别为wj和pj j 1 n 则依次求解f0 X f1 X fn X 的过程中使用的递推关系式为 56 2005年11月试题55 56 A 优先选取重量最小的物品B 优先选取效益最大的物品C 优先选取单位重量效益最大的物品D 没有任何准则A fi X min fi 1 X fi 1 X pi B fi X max fi 1 X fi 1 X Wi pi C fi X min fi 1 X Wi fi 1 X Wi pi D fi X max fi 1 X Wi fi 1 X pi CB 2006年5月试题57 58 对于求取两个长度为n的最长公共子序列问题 利用 57 策略可以有效地避免最长公共子序列重复计算 得到时间复杂度为O n2 的正确算法 串和的最长公共子序列的长度为 58 A 分治法B 贪心法C 动态规划方法D 分支 限界A 3B 4C 5D 6CD 2006年5月试题59 设某算法的计算时间可用递推关系式T n 2T n 2 n表示 则该算法的时间复杂度为 59 A O lgn B O nlgn C O n D O n2 T n 2T n 2 n 4T n 4 n n 2kT 1 kn n 2k cn nlog2n 2006年11月试题57 求单源点最短路径的迪杰斯特拉 Dijkstra 算法是按 57 的顺序求源点到各顶点的最短路径的 A 路径长度递减B 路径长度递增C 顶点编号递减D 顶点编号递增答案 B 2006年11月试题58 算法策略与递归技术的联系最弱 A 动态规划B 贪心C 回溯D 分治B 2006年11月试题59 60 对于有n个元素的一个数据序列 若只需得到其中第k个元素之前的部分序列 最好采用 59 使用分治 DivideandConquer 策略的是 60 算法 59 A 希尔排序B 直接插入排序C 快速排序D 堆排序 60 A 冒泡排序B 插入排序C 快速排序D 堆排序DC 2006年11月下午试题四 阅读以下说明和图 填补流程图中的空缺 将解答填入答题纸的对应栏内 说明 某汽车制造工厂有两条装配线 汽车装配过程如图4 1所示 即汽车底盘进入装配线 零件在多个工位装配 结束时汽车自动完成下线工作 2006年11月下午试题四 1 e0和e1表示底盘分别进入装配线0和装配线1所需要的时间 2 每条装配线有n个工位 第一条装配线的工位为S0 0 S0 1 S0 n 1 第二条装配线的工位为S1 0 S1 1 S1 n 1 其中S0 k和S1 k 0 k n 1 完成相同的任务 但所需时间可能不同 3 ai j表示在工位Si j处的装配时间 其中i表示装配线 i 0或i 1 j表示工位号 0 j n 1 4 ti j表示从Si j处装配完成后转移到另一条装配线下一个工位的时间 5 x0和x1表示装配结束后 汽车分别从装配线0和装配线1下线所需要的时间 6 在同一条装配线上 底盘从一个工位转移到其下一个工位的时间可以忽略不计 2006年11月下午试题四 图4 2所示的流程图描述了求最短装配时间的算法 该算法的输入为 n 表示装配线上的工位数 e i 表示e1和e2 i取值为0或1 a i j 表示ai j i的取值为0或1 j的取值范围为0 n 1 t i j 表示ti j i的取值为0或1 j的取值范围为0 n 1 x i 表示x0和x1 i取值为0或1 算法的输出为 fi 最短的装配时间 li 获得最短装配时间的下线装配线号 0或者1 算法中使用的f i j 表示从开始点到Si j处的最短装配时间 2006年11月下午试题四 1 f 0 0 e 0 a 0 0 f 1 0 e 1 a 1 0 2 f 0 j 1 a 0 j 3 f 1 j 1 a 1 j f 0 j 1 t 0 j 1 a 1 j 4 fi f 0 n 1 x 0 li 0 5 fi f 1 n 1 x 1 li 1 2007年5月试题62 设商店有10元 5元 2元和1元的零币 每种零币的数量充足 售货员给顾客找零钱时 零币的数量越少越好 例如给顾客找零29元 先选2张10元币 然后选择1张5元币 再选择两张2元币 以上的找零钱方法采用了 62 策略 A 分治B 贪心C 动态规划D 回溯B 2007年5月试题64 65 2007年5月下午试题四 说明 在一条农村公路的一边稀疏地分布着房子 其分布如图4 1所示 某电信公司需要在某些位置放置蜂窝电话基站 由于基站的覆盖范围是6公里 因此必须使得每栋房子到某个基站的直线距离不超过6公里 为简化问题 假设所有房子在同一直线上 并且基站沿该直线放置 现采用贪心策略实现用尽可能少的基站覆盖所有的房子 2007年5月下午试题四 实现贪心算法的流程如图4 2所示 请填空并计算该算法的时间复杂度 其中 1 d i 1 i N 表示第i个房子到公路A端的距离 N表示房子的总数 按房子到公路A端的距离从小到大进行房子编号 2 s k 表示第k k 1 个基站到公路A端的距离 算法结束后k的值为基站的总数 分析 问题解的模型 该算法的时间复杂度为 5 k 0 j N k d i 6 O n 2007年11月试题63 迪杰斯特拉 Dijkstra 算法按照路径长度递增的方式求解单源点最短路径问题 该算法运用了 63 算法策略 A 贪心B 分而治之C 动态规划D 试探 回溯A 2007年11月试题64 关于算法与数据结构的关系 64 是正确的 A 算法的实现依赖于数据结构的设计B 算法的效率与数据结构无关C 数据结构越复杂 算法的效率越高D 数据结构越简单 算法的效率越高A 2007年11月试题65 若一个问题既可以用迭代方式也可以用递归方式求解 则 65 方法具有更高的时空效率 A 迭代B 递归C 先递归后迭代D 先迭代后递归A 2007年11月下午试题四 说明 某机器上需要处理n个作业job1 job2 jobn 其中 每个作业jobi 1 i n 的编号为i jobi有一个收益值p i 和最后期限值d i 机器在一个时刻只能处理一个作业 而且每个作业需要一个单位时间进行处理 一旦作业开始就不可中断 每个作业的最后期限值为单位时间的正整数倍 job1 jobn的收益值呈非递增顺序排列 即p 1 p 2 p n 如果作业jobi在其期限之内完成 则获得收益p i 如果在其期限之后完成 则没有收益 2007年11月下午试题四 为获得较高的收益 采用贪心策略求解在期限之内完成的作业序列 图4 1是基于贪心策略求解该问题的流程图 整型数组J 有n个存储单元 变量k表示在期限之内完成的作业数 J 1 k 存储所有能够在期限内完成的作业编号 数组J 1 k 里的作业按其最后期限非递减排序 即d J 1 d J k 为了方便于在数组J中加入作业 增加一个虚拟作业job0 并令d 0 0 J 0 0 2007年11月下午试题四 算法大致思想 先将作业job1的编号1放入J 1 然后 依次对每个作业jobi 2 i n 进行判定 看其能否插入到数组J中 若能 则将其编号插入到数组J的适当位置 并保证J中作业按其最后期限非递减排列 否则不插入 jobi能插入数组J的充要条件是 jobi和数组J中已有作业均能在其期限之内完成 流程图中的主要变量说明如下 i 循环控制变量 表示作业的编号 k 表示在期限内完成的作业数 r 若jobi能插入数组J 则其在数组J中的位置为r 1 q 循环控制变量 用于移动数组J中的元素 1 i n 2 d i d J r 3 J r 1 i 2007年11月下午试题四 问题1 9分 请填充图4 1中的空缺 1 2 和 3 处 2007年11月下午试题四 问题2 4分 假设有6个作业job1 job2 job6 完成作业的收益数组p p 1 p 2 p 3 p 4 p 5 p 6 90 80 50 30 20 10 每个作业的处理期限数组d d 1 d 2 d 3 d 4 d 5 d 6 1 2 1 3 4 3 请应用试题中描述的贪心策略算法 给出在期限之内处理的作业编号序列 4 按作业处理的顺序给出 得到的总收益为 5 1 2 4 5 220 2007年11月下午试题四 2007年11月下午试题四 问题3 2分 对于本题的作业处理问题 用图4 1的贪心算法策略 能否求得最高收益 6 用贪心算法求解任意给定问题时 是否一定能得到最优解 7 能 不能 2008年5月试题62 一个算法本是对某类给定问题求解过程的精确描述 算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现 这句话说明算法具有 62 特性 A 有穷性B 可行性C 确定性D 健壮性B 2008年5月试题63 64 斐波那契 Fibonacci 数列可以递归地定义为 用递归算法求解F 5 时需要执行 63 次 运算 该方法采用的算法策略是 64 63 A 5B 6C 7D 8 64 A 动态规划B 分治C 回溯D 分支限界CB 2008年5月试题下午试题四 说明 快速排序是一种典型的分治算法 采用快速排序对数组A p r 排序的三个步骤如下 分解 选择一个枢轴 pivot 元素划分数组 将数组A p r 划分为两个子数组 可能为空 A p q 1 和A q 1 r 使得A q 大于等于A p q 1 中的每个元素 小于A q 1 r 中的每个元素 q的值在划分过程中计算 递归求解 通过递归的调用快速排序 对子数组A p q 1 和A q 1 r 分别排序 合并 快速排序在原地排序 故不需合并操作 2008年5月试题下午试题四 问题1 6分 下面是快速排序的伪代码 请填空 主要变量说明如下 A 待排序数组p r 数组元素下标 从p到rq 划分的位置x 枢轴元素i 整型变量 用于描述数组下标 下标小于或等于i的元素的值小于或等于枢轴元素的值j 循环控制变量 表示数组元素下标 2008年5月试题下午试题四 QUICKSORT A p r if p r q PARTITION A p r QUICKSORT A p q 1 QUICKSORT A q 1 r PARTITION A p r x A r i p 1 for j p j r 1 j if A j x i i 1 交换A i 和A j 交换 1 和 2 1 和 2 答案可互换 但两空全部答对方可得分return 3 4938659776132749 A i 1 A r i 1 2008年5月试题下午试题四 问题2 5分 1 假设要排序包含n个元素的数组 请给出在各种不同的划分情况下 快速排序的时间复杂度 用O记号 最佳情况为 4 平均情况为 5 最坏情况为 6 2 假设要排序的n个元素都具有相同值时 快速排序的运行时间复杂度属于哪种情况 7 最佳 平均 最坏 答 o nlog2n o nlog2n o n2 最坏 2008年5月试题下午试题四 问题3 4分 1 待排序数组是否能被较均匀地划分对快速排序的性能有重要影响 因此枢轴元素的选取非常重要 有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素 下面是随机化快速排序划分的伪代码 利用原有的快速排序的划分操作 请填空 其中 RANDOM i j 表示随机取i到j之间的一个数 包括i和j 2008年5月试题下午试题四 RANDOMIZED PARTITION A p r i RANDOM p r 交换 8 和 9 8 和 9 答案可互换 但两空全部答对方可得分returnPARTITION A p r 2 随机化快速排序是否能够消除最坏情况的发生 10 是或否 答 A i A r 否 2008年11月试题62 某一维数组中依次存放了数据元素12 23 30 38 41 52 54 76 85 在用折半 二分 查找方法 向上取整 查找元素54时 所经历 比较 运算的数据元素依次为 62 A 41 52 54B 41 76 54C 41 76 52 54D 41 30 76 54答案