1、软件设计师-18 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：39，分数：100.00)某个算法的时间复杂度递归式 T(n)=T(n-1)+n，其中 n 为问题的规模，则该算法的渐进时间复杂度为_，若问题的规模增加了 16 倍，则运行时间增加_倍。（分数：4.00）(1). A.O(n) B.O(nlgn) C.O(n2) D.O(n2lgn)（分数：2.00）A.B.C.D.A.16B.64C.256D.1024Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法，Prim 算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的
2、生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal 算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一棵最小生成树，这两个算法都采用了_设计策略，且_。（分数：4.00）A.分治B.贪心C.动态规划D.回溯A.若网较稠密，则 Prim 算法更好B.两个算法得到的最小生成树是一样的C.Prim 算法比 Kruscal 算法效率更高D.Kruscal 算法比 Prim 算法效率更高考虑下述背包问题的实例。有 5 件物品，背包容量为 100，每件物品的价值和重量如下图所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略
3、装入背包中，则采用了_设计策略。考虑 0/1 背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包)，求解该实例得到的最大价值分别为_。 （分数：4.00）A.分治B.贪心C.动态规划D.回溯A.605 和 630B.605 和 605C.430 和 630D.630 和 430给定 n 个整数构成的数组 A=a 1 ，a 2 ，a n 和整数 x，判断 A 中是否存在两个元素 a i 和 a j ，使的 a i +a j =x。为了求解问题，首先用归并排序算法对数组 A 进行从大到小排序；然后判断是否存在a i +a j =x，具体的方法如下列伪代码所示。则
4、求解该问题时排序算法应用了_算法设计策略，整个算法的时间复杂度为_。 i=1;j=n While ij If a i +a j =x return true Else if a i +a j x J-; Else I+; Return false;（分数：4.00）A.分治B.贪心C.动态规划D.回溯(2). A.O(n) B.O(nlgn) C.O(n2) D.O(nlog2n)（分数：2.00）A.B.C.D.在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用_算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用_算法设计策略。（分数：
5、4.00）A.分治B.动态规划C.贪心D.回溯A.动态规划B.贪心C.回溯D.分支限界哈夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：)以每个字符的出现频率作为关键字构建最小优先级队列；)取出关键字最小的两个节点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入到最小优先级队列中，直至得到一棵最优编码树。哈夫曼编码方案是基于_策略的，用该方案对包含 a 到 f 六个字符的文件进行编码，文件包含 100000 个字符，每个字符的出现频率(用百分比表示)如下表所示，则与固定长度编码相比，该编码方案节省了_存储空间。 字符 a b c d e f 出现
6、频率 18 32 4 8 12 26 （分数：4.00）A.分治B.贪心C.动态规划D.回溯A.21%B.27%C.18%D.36%1.以下关于渐近符号的表示中，不正确的是_。 A.n2=O(n2) B.n=O(n2) C.n2=O(n) D.n2=O(n3)（分数：2.00）A.B.C.D.某货车运输公司有一个中央仓库和 n 个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点 i 和 j 之间运输货物存在费用 C ij ，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地 1，然后选择离运输目
7、的地 1 最近的运输目的地 2每次在访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。则该算法采用了_算法设计策略，其时间复杂度为_。（分数：4.00）A.分治B.动态规划C.贪心D.回溯(2). A.O(n2) B.O(n) C.O(nlgn) D.O(1)（分数：2.00）A.B.C.D.2.现要对 n 个实数(仅包含正实数和负实数)组成的数组 A 进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_。 i=0;j=n-1 while ij do while Ai0 do i=i+1; while Aj0
8、 do j=j-1; if ij do 交换 Ai和 Aj（分数：2.00）A.O(n)和 O(n)B.O(1)和 O(n)C.O(n)和 O(1)D.O(1)和 O(1)3.迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于_策略的算法。（分数：2.00）A.分治B.动态规划C.贪心D.回溯4.在有 n 个无序无重复元素值的数组中查找第 i 小的数的算法描述如下：任意取一个元素 r，用划分操作确定其在数组中的位置，假设元素 r 为第 k 小的数。若 i 等于 k，则返回该元素值；若 i 小于 k，则在划分的前半部分
9、递归进行划分操作查找第 i 小的数；否则在划分的后半部分递归进行划分操作查找第 k-i 小的数。该算法是一种基于_策略的算法。（分数：2.00）A.分治B.动态规划C.贪心D.回溯5.要在 88 的棋盘上摆放 8 个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能再同一行、同一列和相同的对角线上，则一般采用_来实现。（分数：2.00）A.分治法B.动态规划法C.贪心法D.回溯法6.分治算法设计技术_。（分数：2.00）A.一般由三个步骤组成：问题划分、递归求解、合并解B.一定是用递归技术来实现C.将问题划分为 k 个规模相等的子问题D.划分代价很小而合并代价很大7.某算法的时间复
10、杂度可用递归式 表示，若由 表示，则正确的是_。 A B(n 2 ) C(n) D （分数：2.00）A.B.C.D.8.设算法 A 的时间复杂度可用递归式 表示，算法 B 的时间复杂度可用递归式 （分数：2.00）A.48B.49C.13D.149.用动态规划策略求解矩阵连乘问题 M1M2M3M4，其中 M 1 (205)、M 2 (535)、M 3 (354)和M 4 (425)，则最优的计算次序为_。（分数：2.00）A.(M1M2)M3)MB.(M1M2)(M3M4)C.(M1(M2M3)M4D.M1(M2(M3M4)10._不能保证求得 0-1 背包问题的最优解。（分数：2.00）A
11、.分支限界法B.贪心算法C.回溯法D.动态规划策略11.类_之间存在着一般和特殊的关系。（分数：2.00）A.汽车与轮船B.交通工具与飞机C.轮船与飞机D.汽车与飞机12.多态分为参数多态、包含多态、过载多态和强制多态共 4 种不同形式，其中_多态在许多语言中都存在，最常见的例子就是子类型化。（分数：2.00）A.参数B.包含C.过载D.强制在面向对象程序设计语言中，对象之间通过_方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是_。（分数：4.00）A.消息传递B.继承C.引用D.多态A.应该支持被封装的对象B.应该支持类写实例的概念C.应该支持通过指针进行引用D.应该支持继
12、承和多态13._是一个类与它的一个或多个细化类之间的关系，即一般与特殊的关系。（分数：2.00）A.泛化B.关联C.聚集D.组合14.在某些程序设计语言中，在运行过程中当一个对象发送消息请求服务时，根据接收对象的具体情况将请求的操作与实现的方法进行连接，称为_。（分数：2.00）A.静态绑定B.通用绑定C.动态绑定D.过载绑定在面向对象技术中，不同的对象在收到同一消息时可以产生完全不同的结果，这一现象称为_，它由_机制来支持。利用类的层次关系，把具有通用功能的消息存放在高层次，而实现这一功能的行为放在较低层次，在这些低层次上生成的对象能够给通用消息以不同的响应。（分数：4.00）A.绑定B.继
13、承C.消息D.多态A.绑定B.继承C.消息D.多态15.在多态的几种不同形式中，_多态是一种特定的多态，指同一个名字在不同上下文中可代表不同的含义。（分数：2.00）A.参数B.包含C.过载D.强制继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是_。有关下图中doIt()方法的叙述中，正确的是_。 （分数：4.00）A.一个父类可以有多个子类，这些子类都是父类的特例B.父类描述了这些子类的公共属性和操作C.子类可以继承它的父类(或祖先类)中的属性和操作而不必自己定义D.子类中可以定义自己的新操作而不能定义和父类同名的操作A.doIt()必须由 Thing3 实现，同时
14、可能由 Thing4 实现B.doIt()必须由 Thing5 实现C.doIt()必须由 Thing2、Thing3、Thing4 和 Thing5 实现D.doIt()已经由 Thing1 实现，因此无需其他类实现在面向对象技术中，_定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为_，不同类的对象通过_相互通信。（分数：6.00）A.覆盖B.继承C.消息D.多态A.覆盖B.继承C.消息D.多态A.覆盖B.继承C.消息D.多态16.在面向对象技术中，对象具有以下特性：_。 清晰的边界 良好定义的行为 确定的位置和数量 可扩展性（分数：2.00）A.B.C.D.在面向
15、对象技术中，_说明一个对象具有多种形态，_定义超类与子类之间的关系。（分数：4.00）A.继承B.组合C.封装D.多态A.继承B.组合C.封装D.多态17.以下关于封装在软件复用中所充当的角色的叙述，正确的是_。（分数：2.00）A.封装使得其他开发人员不需要知道一个软件组织内部是如何工作B.封装使得软件组织更有效地工作C.封装使得软件开发人员不需要编制开发文档D.封装使得软件组件开发更加容易18.在有些程序设计语言中，过程调用和响应调用需执行的代码的绑定直到运行时才进行，这种绑定称为_。（分数：2.00）A.静态绑定B.动态绑定C.过载绑定D.强制绑定19.在面向对象软件开发中，封装是一种_
16、技术，其目的是使对象的使用者和生产者分离。（分数：2.00）A.接口管理B.信息隐藏C.多态D.聚合一个类是_。在定义类时，将属性声明为 private 的目的是_。（分数：4.00）A.一组对象的封装B.表示一组对象的层次关系C.一组对象的实例D.一组对象的抽象定义A.实现数据隐藏，以免意外更改B.操作符重载C.实现属性值不可更改D.实现属性值对类的所有对象共享20.面向对象分析的第一步是_（分数：1.00）A.定义服务B.确定附加的系统约束C.确定问题域D.定义类和对象21.下列关于一个类的静态成员的描述中，不正确的是_。（分数：1.00）A.类的静态方法只能访问该类的静态数据成员B.静态
17、数据成员可被该类的所有方法访问C.该类的对象共享其静态数据成员的值D.该类的静态数据成员的值不可修改22.属于面向对象、解释型程序设计语言的是_。（分数：1.00）A.XMLB.PythonC.PrologD.C+23.以下程序设计语言中，_更适合用来进行动态网页处理。（分数：1.00）A.HTMLB.LISPC.PHPD.Java/C+24.某程序设计语言规定在源程序中的数据都必须具有类型，然而，_并不是做出此规定的理由。（分数：1.00）A.为数据合理分配存储单元B.可以定义和使用动态数据结构C.可以规定数据对象的取值范围及能够进行的运算D.对参与表达式求值的数据对象可以进行合法性检查25
18、.采用面向对象开发方法时，对象是系统运行的基本实体。以下关于对象的叙述中，正确的是_。（分数：1.00）A.对象只能包括数据(属性)B.对象只能包括操作(行为)C.对象一定有相同的属性和行为D.对象通常由对象名、属性和操作三个部分组成UML 中有 4 种事物：结构事物、行为事物、分组事物和注释事物。类、接口、构建属于_事物；依附于一个元素或一组元素之上，对其进行约束或解释的简单符号为_事物。（分数：2.00）A.结构B.行为C.分组D.注释A.结构B.行为C.分组D.注释软件设计师-18 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：39，分数：100.00)某个
19、算法的时间复杂度递归式 T(n)=T(n-1)+n，其中 n 为问题的规模，则该算法的渐进时间复杂度为_，若问题的规模增加了 16 倍，则运行时间增加_倍。（分数：4.00）(1). A.O(n) B.O(nlgn) C.O(n2) D.O(n2lgn)（分数：2.00）A.B.C. D.解析：A.16B.64C.256 D.1024解析：解析 对于递归式，假设 T(1)=1，则： T(n)=T(n-1)+n =T(n-2)+n-1+n =T(n-3)+n-2+n-1+n = =1+2+n-1+n =n(n+1)/2 可见，时间复杂度为 O(n 2 )。若问题的规模增加了 16 倍，则运行时间
20、增加了 16 2 =256 倍。Prim 算法和 Kruscal 算法都是无向连通网的最小生成树的算法，Prim 算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal 算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一棵最小生成树，这两个算法都采用了_设计策略，且_。（分数：4.00）A.分治B.贪心 C.动态规划D.回溯解析：A.若网较稠密，则 Prim 算法更好 B.两个算法得到的最小生成树是一样的C.Prim 算法比 Kruscal 算法效率更高D.Kruscal 算法比
21、Prim 算法效率更高解析：解析 Prim 算法和 Kruscal 算法都是基于贪心算法的应用。Prim 算法的时间复杂度为 O(n 2 )，与图中边数无关，该算法适合于稠密图。Kruskal 算法的时间复杂度只和边有关系，为 O(elog 2 e)，由于 Kruskal 算法只与边有关，因此适合求稀疏图的最小生成树。考虑下述背包问题的实例。有 5 件物品，背包容量为 100，每件物品的价值和重量如下图所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了_设计策略。考虑 0/1 背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(
22、物品可以部分装入背包)，求解该实例得到的最大价值分别为_。 （分数：4.00）A.分治B.贪心 C.动态规划D.回溯解析：A.605 和 630B.605 和 605C.430 和 630 D.630 和 430解析：解析 本题考查贪心算法和背包问题的知识点。 贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 采用 0/1 背包考虑该问题时，只能放入 1、2、3 号物品，故总价值为
23、 430，采用部分背包可以将物品拆分，故放入 1、2、3 号物品后还可以将编号 4 的物品部分的装入，使得背包容量尽量的满，故总容量为 630。给定 n 个整数构成的数组 A=a 1 ，a 2 ，a n 和整数 x，判断 A 中是否存在两个元素 a i 和 a j ，使的 a i +a j =x。为了求解问题，首先用归并排序算法对数组 A 进行从大到小排序；然后判断是否存在a i +a j =x，具体的方法如下列伪代码所示。则求解该问题时排序算法应用了_算法设计策略，整个算法的时间复杂度为_。 i=1;j=n While ij If a i +a j =x return true Else i
24、f a i +a j x J-; Else I+; Return false;（分数：4.00）A.分治 B.贪心C.动态规划D.回溯解析：(2). A.O(n) B.O(nlgn) C.O(n2) D.O(nlog2n)（分数：2.00）A.B. C.D.解析：解析 分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分支算法的时间复杂度为O(nlgn)。在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用_算法设计策略；若定义问题的解空间，以深度优先的方式搜
25、索解空间，则采用_算法设计策略。（分数：4.00）A.分治B.动态规划 C.贪心D.回溯解析：A.动态规划B.贪心C.回溯 D.分支限界解析：解析 最优子结构和高度重复性是适用动态规划方法求解的主要特征；而回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不好或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。哈夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：)以每个字符的出现频
26、率作为关键字构建最小优先级队列；)取出关键字最小的两个节点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入到最小优先级队列中，直至得到一棵最优编码树。哈夫曼编码方案是基于_策略的，用该方案对包含 a 到 f 六个字符的文件进行编码，文件包含 100000 个字符，每个字符的出现频率(用百分比表示)如下表所示，则与固定长度编码相比，该编码方案节省了_存储空间。 字符 a b c d e f 出现频率 18 32 4 8 12 26 （分数：4.00）A.分治B.贪心 C.动态规划D.回溯解析：A.21%B.27%C.18% D.36%解析：解析 贪心算法在解决最优化问题上是仅根据当前
27、已有的信息作出选择，即不是从整体最优考虑，它所作出的选择只是力求局部最优。本题给出的哈夫曼编码操作过程基于典型的贪心策略。 采用固定长度编码，需要 3 位二进制数字来表示 6 个字符，即a=000，b=001，c=010，d=011，e=100，f=101。这种方法需要 300000 位来对整个源文件编码。采用哈夫曼编码，频繁出现的字符采用短编码，出现频率较低的字符采用长编码，这种编码方式需要(32*1+26*3+18*3+12*3+4*4+8*4)*1000=248000 位。因此与固定长度编码相比，该编码方案节省的存储空间为(300000-248000)/300000=17.3%。1.以下
28、关于渐近符号的表示中，不正确的是_。 A.n2=O(n2) B.n=O(n2) C.n2=O(n) D.n2=O(n3)（分数：2.00）A.B.C. D.解析：解析 如果存在正常数 c 和 n 0 ，使得当 nn 0 时，T(n)cf(n)，则记为 T(n)=O(f(n)。T 和f 的关系可以理解为 f(n)为 T(n)的一个上界，也可以理解为 T 至多增长得和 f 一样快。 如果存在正常数 c 1 ，c 2 和 n 0 ，使得当 nn 0 时，c 1 f(n)T(n)c 2 f(n)，则记为 T(n)=O(f(n)。T 与 f 有着相同的阶数，或者两者最终与相同的阶数增长。 对于选项 A，
29、T(n)=f(n)=n 2 ，只要 c 2 c 1 1，n 0 0，就有 c 1 f(n)T(n)c 2 f(n)，因此有T(n)=O(f(n)，即 n 2 =O(n 2 )。 对于选项 B，T(n)=f(n)=n 2 ，只要 c1，n 0 0，就有 T(n)cf(n)，因此有 T(n)=O(f(n)，即 n 2 =O(n 2 )。 对于选项 D，T(n)=n 2 ，f(n)=n 3 ，只要 c1，n 0 1，就有 T(n)cf(n)，因此有 T(n)=O(f(n)，即n 2 =O(n 3 )。 对于选项 C，当 n1 时，n 2 的增长比 n 快，因此 n 2 =O(n)的关系不成立。某货车
30、运输公司有一个中央仓库和 n 个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点 i 和 j 之间运输货物存在费用 C ij ，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地 1，然后选择离运输目的地 1 最近的运输目的地 2每次在访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。则该算法采用了_算法设计策略，其时间复杂度为_。（分数：4.00）A.分治B.动态规划C.贪心 D.回溯解析：(2). A.O(n2) B.O(n) C.O(nlgn) D.O(1)（分数
31、：2.00）A. B.C.D.解析：解析 贪心算法不考虑整体情况，以当前情况为基础作出最优选择。很明显，题目中用到的是贪心算法。分值算法是将规模为 n 的问题分解为 k 个子问题，这些子问题相互独立，且与原问题相同，然后将子问题的解合并得到原问题的解。动态规划算法与分值算法类似，但分解后的子问题往往不是独立的。回溯法要在包含问题的所有解的解空间中，按照深度优先的策略，从根节点出发搜索解空间。 在选择路径时，首先选择离中央仓库最近的运输目的地 1，需要将所有 n 个目的地到中央仓库的距离进行比较，选择最近的作为目的地 1，相当于从 n 个数中选择一个最小数，此时比较了 n-1 次；然后选择离目的
32、地 1 最近的目的地 2，此时需要将其余 n-1 个目的地到目的地 1 的距离进行比较，相当于从 n-1 个数中选择一个最小数，此时比较了 n-2 次，以此类推，共需比较 n-1+n-2+n-3+2+1=(n-1)(n-2)/2=(n 2 -3n+2)/2，算法的时间复杂度为 O(n 2 )。2.现要对 n 个实数(仅包含正实数和负实数)组成的数组 A 进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_。 i=0;j=n-1 while ij do while Ai0 do i=i+1; while Aj0 do j=j-1; if
33、 ij do 交换 Ai和 Aj（分数：2.00）A.O(n)和 O(n)B.O(1)和 O(n)C.O(n)和 O(1) D.O(1)和 O(1)解析：解析 算法中用到了两个辅助变量 i 和 i，算法的空间复杂度为 O(1)。在重新排列过程中，从数组的两端进行比较，从 i=O 开始判断 Ai是否为负数，i 为负数的时候，i=i+1，直到 Ai为正数；从j=n-1 开始判断 Ai是否为正数，如果为正数，j=j-1，直到 Aj为负数。当 ij 的时候交换 Ai和Aj的值。然后继续判断 Ai和 Aj的值。数组 A 中的元素个数为 n，Ai0 和 Aj0 的比较次数共为 n+2，i=i+1 和 j=
34、j-1 执行的次数最多为 n+2 次，if 语句中的 ij 的比较和交换 Ai和 Aj的操作分别最多执行 n-1 次，while 循序的条件判断至多执行 n 次。可见，算法的时间复杂度为 O(n)。3.迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于_策略的算法。（分数：2.00）A.分治B.动态规划C.贪心 D.回溯解析：解析 Dijkstra 用来解决从顶点 V 0 出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径：对于图 G=(V，E)，将图中的顶点分成两组 S 和 T，S 为已求出
35、的最短路径的终点集合(开始为V 0 )，T 为尚未求出最短路径的终点集合(开始为 V-V 0 的全部节点)。算法将按最短路径长度的递增顺序逐个将 T 的顶点加入到 S 中，直到所有顶点都被加入到顶点集 S 为止。本质上说，该算法是一种基于贪心策略的算法。贪心算法根据当前已有的信息作出选择，所作出的选择是局部上的最优。4.在有 n 个无序无重复元素值的数组中查找第 i 小的数的算法描述如下：任意取一个元素 r，用划分操作确定其在数组中的位置，假设元素 r 为第 k 小的数。若 i 等于 k，则返回该元素值；若 i 小于 k，则在划分的前半部分递归进行划分操作查找第 i 小的数；否则在划分的后半部
36、分递归进行划分操作查找第 k-i 小的数。该算法是一种基于_策略的算法。（分数：2.00）A.分治 B.动态规划C.贪心D.回溯解析：解析 分治算法的基本思想是：将一个难以直接解决的大问题分解成一些规模较小的小问题以便各个击破，分而治之。分支算法的每一层都有 3 个步骤：分解、求解和合并。本题的查找算法，不断划分数组，缩小查找范围，可见该算法是基于分支策略的算法。5.要在 88 的棋盘上摆放 8 个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能再同一行、同一列和相同的对角线上，则一般采用_来实现。（分数：2.00）A.分治法B.动态规划法C.贪心法D.回溯法 解析：解析 8 皇
37、后问题等价于要求在一个 88 格的棋盘上放置 8 个皇后，使得任意两个皇后不能放在同一行或同一列或同意斜线上。求解过程从空棋盘开始，设在第 1 行至第 m 行都已经正确放置了 m 个皇后的基础上，再在第 m+1 行上找合适的位置放置第 m+1 个皇后，直至第 8 行也找到合适的位置放置第 8 个皇后。在任一行上都有 8 种选择，开始时，位置在第 1 列，以后改变时，顺序选择第 2 列，第 3 列，第8 列。当第 8 列也不是一个合适的位置时，就要回溯，去改变前一行的位置。 分治法将复杂的大问题分解成规模小的问题以各个击破。归并排序等算法用到的是分治法实现。动态规划法与分治法类似，基本思想也是将
38、待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解，背包问题、LCS 问题等是采用动态规划法实现的。贪心法跟动态规划法一样，也是用来解决最优问题的，但贪心法并不从整体最优考虑，它所做出的选择只是某种意义上的局部最优。6.分治算法设计技术_。（分数：2.00）A.一般由三个步骤组成：问题划分、递归求解、合并解 B.一定是用递归技术来实现C.将问题划分为 k 个规模相等的子问题D.划分代价很小而合并代价很大解析：解析 分治算法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。分治算法产生的子问题往往是原问题的较小模式。一般来说，分
39、支算法分为三个步骤：将原问题分解成一系列子问题：递归求解各个子问题；将子问题的解合并成原问题的解。7.某算法的时间复杂度可用递归式 表示，若由 表示，则正确的是_。 A B(n 2 ) C(n) D （分数：2.00）A. B.C.D.解析：解析 a=6，b=5，f(n)=n，log b a=1.113，存在 =0.113，使得 ，因此 8.设算法 A 的时间复杂度可用递归式 表示，算法 B 的时间复杂度可用递归式 （分数：2.00）A.48 B.49C.13D.14解析：解析 对于算法 A，设 a=7，b=2，f(n)=n 2 ，则 log b a2，因此存在常数 ，使得 ，因此 。 如果要
40、使 B 渐进地快于算法 A，则有 9.用动态规划策略求解矩阵连乘问题 M1M2M3M4，其中 M 1 (205)、M 2 (535)、M 3 (354)和M 4 (425)，则最优的计算次序为_。（分数：2.00）A.(M1M2)M3)MB.(M1M2)(M3M4)C.(M1(M2M3)M4 D.M1(M2(M3M4)解析：解析 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，最优的计算次序是使得矩阵连乘中乘法次数最少的次序。 选项 A，乘法的次数为 20355+20435+20254=6700 选项 B，乘法的次数为 20355+35254+202535=24500 选项
41、 C，乘法的次数为 5435+2045+20254=3100 选项 D，乘法的次数为 35254+52535+20255=10375 可见，选项 C 中的计算次序为最优的计算次序。10._不能保证求得 0-1 背包问题的最优解。（分数：2.00）A.分支限界法B.贪心算法 C.回溯法D.动态规划策略解析：解析 贪心法在解决问题的策略上仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。也就是说，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。11.类_之间存在
42、着一般和特殊的关系。（分数：2.00）A.汽车与轮船B.交通工具与飞机 C.轮船与飞机D.汽车与飞机解析：解析 一般是统称，特殊是特定具体的。12.多态分为参数多态、包含多态、过载多态和强制多态共 4 种不同形式，其中_多态在许多语言中都存在，最常见的例子就是子类型化。（分数：2.00）A.参数B.包含 C.过载D.强制解析：解析 多态分为两种：通用的多态和特定的多态。两者的区别是前者对工作的类型不加限制，允许对不同类型的值执行相同的代码：后者只对有限数量的类型有效，而对不同类型的值可能要执行不同的代码。 通用的多态又分为参数多态(parametric)和包含多态(Inclusion)；特定的
43、多态分为过载多态(overloading)和强制多态(coercion)。 强制多态：编译程序通过语义操作，把操作对象的类型强行加以变换，以符合函数成操作符的要求。程序设计语言中基本类型的大多数操作符，在不同类型的数据进行混合运算时，编译程序一般都进行强制多态。过载(overloading)多态：同一个名(操作符、函数名)在不同的上下文中有不同的类型，程序设计语言中基本类型的大多数操作符都是过载多态的。 参数多态：采用参数化模板，通过给出不同的类型参数，使得一个结构有多种类型。 包含多态：同样的操作可用于一个类型及其子类型(注意是子类型，不是子类)。包含多态一般需要进行运行时的类型检查。在面向
44、对象程序设计语言中，对象之间通过_方式进行通信。以下关于好的面向对象程序设计语言的叙述中，不正确的是_。（分数：4.00）A.消息传递 B.继承C.引用D.多态解析：A.应该支持被封装的对象B.应该支持类写实例的概念C.应该支持通过指针进行引用 D.应该支持继承和多态解析：解析 对象间通过接口传递消息，实现通信。在第二个空中，A、B、D 为实现概念，C 只针对部分语言，如 C+，不具有代表性。13._是一个类与它的一个或多个细化类之间的关系，即一般与特殊的关系。（分数：2.00）A.泛化 B.关联C.聚集D.组合解析：解析 泛化表示类与类之间的继承关系，接口与接口之间的继承关系，或类对接口的实
45、现关系。一般情况下泛化关系是从子类指向父类的。 对于两个相对独立的对象，当一个对象的实例与另一个对象的特定实例存在固定的对应关系时，这两个对象之间为关联关系。关联体现的是两个类，或者类与接口之间语义级别的一种强依赖关系，这种关系一般是长期性的，而且双方的关系一般是平等的。关联可以是单向、双向的。 聚合是关联关系的一种特例，体现的是整体与部分、拥有的关系，即 has-a 的关系，此时整体与部分之间是可分离的，它们可以具有各自的生命周期，部分可以属于多个整体对象，也可以为多个整体对象共享。 组合也是关联关系的一种特例，体现的是一种 contains-a 的关系，这种关系比聚合更强，也称为强聚合；它
46、同样体现整体与部分间的关系，但此时整体与部分是不可分的，整体的生命周期结束也就意味着部分的生命周期结束。14.在某些程序设计语言中，在运行过程中当一个对象发送消息请求服务时，根据接收对象的具体情况将请求的操作与实现的方法进行连接，称为_。（分数：2.00）A.静态绑定B.通用绑定C.动态绑定 D.过载绑定解析：解析 所谓静态绑定是指在程序编译过程中，把函数(方法或者过程)调用与响应调用所需的代码结合的过程；动态绑定是指在执行期间判断所引用对象的实际类型，根据其实际的类型调用其相应的方法。在面向对象技术中，不同的对象在收到同一消息时可以产生完全不同的结果，这一现象称为_，它由_机制来支持。利用类
47、的层次关系，把具有通用功能的消息存放在高层次，而实现这一功能的行为放在较低层次，在这些低层次上生成的对象能够给通用消息以不同的响应。（分数：4.00）A.绑定B.继承C.消息D.多态 解析：A.绑定B.继承 C.消息D.多态解析：解析 多态性是同一操作作用于不同的类的实例，将产生不同的执行结果，即不同类的对象收到相同的消息时，得到不同的结果。在运行时，可以通过指向基类的指针来调用实现派生类中的方法。多态是面向对象程序设计的重要特征之一，是扩展性在“继承”之后的又一重大表现。如果一个语言只支持类而不支持多态，只能说明它是基于对象的，而不是面向对象的。15.在多态的几种不同形式中，_多态是一种特定的多态，指同一个名字在不同上下文中可代表不同的含义。（分数：2.00）A.参数B.包含C.过载 D.强制解析：解析 一般将多态分为通用多态和特殊多态。其中通用多态包括参数多态和包含多态，参数多态利用泛型编程，是发散式的，是静态绑定的，让相同的实现代码应用于不同的场合，看重的是算
