1、软件水平考试中级软件设计师上午（基础知识）历年真题试卷汇编 9及答案与解析 0 (2013年上半年上午试题 62、 63)给定 n个整数构成的数组 A=a1， a2， ， an和整数 x，判断 A中是否存在两个元素 ai和 aj，使得 ai+aj=x。为了求解问题，首先用归并排序算法对数组 A进行从大到小排序；然后判断是否存在 ai+aj=x，具体的方法如下列伪代码所示。则求解该问题时排序算法应用了 _(62)算法设计策略，整个算法的时间复杂度为 _(63)。 i=1； j=n while i j If ai+aj=x return true Else if ai+aj x J-； Else
2、I+； Return false； 1 (62) （ A）分治 （ B）贪心 （ C）动态规划 （ D）回溯 2 (63) （ A） O(n) （ B） O(nlgn) （ C） O(n2) （ D） O(nlg2n) 2 (2012年下半年上午试题 62、 63)将数组 1， 1， 2， 4， 7， 5从小到大排序，若采用 _(62)排序算法，则元素之间需要进行的比较次数最少，共需要进行_(63)次 元素之间的比较。 3 (62) （ A）直接插入 （ B）归并 （ C）堆 （ D）快速 4 (63) （ A） 5 （ B） 6 （ C） 7 （ D） 8 4 (2012年下半年上午试题 6
3、4、 65)哈夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为： i)以每个字符的出现频率作为关键字构建最小优先级队列； ii)取出关键字最小的两个节点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入最小优先级队列中，直至得到一棵最优编码树。哈夫曼编码方案是基于 _(64)策略的，用该方案对包含 a到 f六个字符的文件进行编码，文件包含 100000 个字符，每个字符的出现频率 (用百分比表示 )如表 9 3所示，则与固定长度编码相比，该编码方案节省了 _(65)存储空间。5 (64) （ A）分治 （ B）贪心 （ C）动态规划 （ D）回溯 6
4、 (65) （ A） 21 （ B） 27 （ C） 18 （ D） 36 7 (2012年上半年上午试题 61)递增序列 A(a1， a2， ， an)和 B(b1， b2， ， bn)的元素互不相同，若需将它们合并为一个长度为 2n的递增序列，则当最终的排列结果为 _时，归并过程中元素的比较次数最多。 （ A） a1， a2， ， an， b1， b2， ， bn （ B） b1， b2， ， bn， a1， a2， ， an （ C） a1， b1， a2， b2， ， ai， bi， ， an， bn （ D） a1， a2， ， ai 2， b1， b2， ， bi 2， ai 2+
5、1， ai 2+2， a n， bi 2+1， bi2+2， ， bn 8 (2012年上半年上午试题 62)以下关于渐进符号的表示中，不正确的是 _。 （ A） n2=(n2) （ B） n2=O(n2) （ C） n2=O(n) （ D） n2=O(n3) 8 (2012年上半年上午试题 63、 64)某货车运输公司有一个中央仓库和 n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点 i和 j之间运输货物存在费用 Cij，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地 1，然后选择离运
6、输目的地 1最近的运输目的地 2， ，每次在未访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中 央仓库。则该算法采用了 _(63)算法设计策略，其时间复杂度为 _(64)。 9 (63) （ A）分治 （ B）动态规划 （ C）贪心 （ D）回溯 10 (64) （ A） (n2) （ B） (n) （ C） (nlgn) （ D） (1) 11 (2012年上半年上午试题 65)现要对 n个实数 (仅包含正实数和负实数 )组成的数组 A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为 _。 i=0； j=n-1
7、 while i 1 do while Ai 0 do i=i+1; while Aj 0 do j=j-1； if i 1 do 交换 Ai和 Aj （ A） (n)和 (n) （ B） (1)和 (n) （ C） (n)和 (1) （ D） (1)和 (1) 12 (2013年下半年上午试题 38)在执行如图 10 2所示的 UML活动图时，能同时运行的最大线程数为 _。 （ A） 4 （ B） 3 （ C） 2 （ D） 1 12 (2013年下半年上午试题 39、 40)如图 10 3所示的 UML序列图中， _(39)表示返回消息， Account应该实现的方法有 _(40)。13
8、(39) （ A） xfer （ B） check （ C） evaluation （ D） minus 14 (40) （ A） xfer() （ B） xfer()、 plus()和 minus() （ C） check()、 plus()和 minus() （ D） xfer()、 evaluation()、 plus()和 minus() 14 (2013年 下半年上午试题 41 43)在面向对象技术中， _(41)定义了超类和子类之间的关系，子类中以更具体的方式实现从父类继承来的方法称为_(42)，不同类的对象通过 _(43)相互通信。 15 (41) （ A）覆盖 （ B）继承 （
9、 C）消息 （ D）多态 16 (42) （ A）覆盖 （ B）继承 （ C）消息 （ D）多态 17 (43) （ A）覆盖 （ B）继承 （ C）消息 （ D）多态 18 (2013年下半年上午试题 44)_设计模式定义一系列算法 ，把它们一个个封装起来，并且使它们可相互替换。这一模式使得算法可独立于它的客户而变化。 （ A）策略 (Strategy) （ B）抽象工厂 (Abstract Factory) （ C）观察者 (Visitor) （ D）状态 (State) 19 (2013年下半年上午试题 45)在发布一订阅 (Publish-Subscribe)消息模型中，订阅者订阅一个
10、主题后，当该主题有新消息到达时，所有订阅者都会收到通知。_设计模式最适合这一模型。 （ A）适配器 (Adapter) （ B）通知 (Notitier) （ C）状态 (State) （ D）观察者 (Observer) 19 (2013年下半年上午试题 46、 47)图 10 4所示为 _(46)设计模式，适用于： _(47)。20 (46) （ A）组件 (Component) （ B）适配器 (Adapter) （ C）组合 (Composite) （ D）装饰器 (Decorator) 21 (47) （ A）表示对象的部分一整体层次结构 （ B）不希望在抽象和它的实现部分之间有一个
11、固定的绑定关系 （ C）在不影响其他对象 的情况下，以动态、透明的方式给单个对象添加职责 （ D）使所有接口不兼容类可以一起工作 22 (2013年上半年上午试题 37)在多态的几种不同形式中， _多态是一种特定的多态，指同一个名字在不同上下文中可代表不同的含义。 （ A）参数 （ B）包含 （ C）过载 （ D）强制 22 (2013年上半年上午试题 38、 39)继承是父类和子类之间共享数据和方法的机制。以下关于继承的叙述中，不正确的是 _(38)。有关图 10 5中 doIt()方法的叙述中，正确的是 _(39)。 23 (38) （ A）一个父类可以有多个子类，这些子类都是父类的特例
12、（ B）父类描述了这些子类的公共属性和操作 （ C）子类可以继承它的父类 (或祖先类 )中的属性和操作而不必自己定义 （ D）子类中可以定义自己的新操作而不能定义和父类同名的操作 24 (39) （ A） doIt()必须由 Thing3实现，同时可能用 Thing4实现 （ B） dolt()必须由 Thing5实现 （ C） doIt()必须由 Thing2、 Thing3、 Thing4和 Thing5实现 （ D） doIt()已经由 Thing1实现，因此无须其他类实现 25 (2013年上半年上午试题 40)以下关于 UML部署图的叙述中，正确的是_。 （ A）因为一条消息总是有某
13、种响应，部署组件之间的依赖是双向的 （ B）部署组件之间的依赖关系类似于包图 （ C）部署图小用于描述代码的物理模块 （ D）部署图不用于描述系统在不同计算机系统的物理分布 25 (2013年上半年上午试题 41、 42)以下关于 UML状态图的叙述中，不正确的是_(41)。对图 10 6的描述正确的是 _(42)。26 (41) （ A）用于描述一个对象在多个用例中的行为 （ B）用于某些具有多个状态的对象而不是系统中大多数或全部对象 （ C）用于描述多个对象之间的交互 （ D）可以用于用户界面或控制对象 27 (42) （ A） ON是一个并发状态 （ B）因为此状态图中没有终止 (fin
14、al)状态，所以此图是无效的 （ C） play、 stop和 rew是动作 （ D） ON是超状态 软件水平考试中级软件设计师上午（基础知识）历年真题试卷汇编 9答案与解析 【知识模块】 算法设计和分析 1 【正确答案】 A 【试题解析】 分 治算法的基本思想是将一个规模为 n的问题分解为 k个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。 【知识模块】 算法设计和分析 2 【正确答案】 B 【知识模块】 算法设计和分析 【知识模块】 算法设计和分析 3 【正确答案】 A 【试题解析】 直接插入排序算法的基本思想是将待排序数组分为两个部分：已排好
15、序部分和未排序部分。其主要步骤为：开始时，第一个元素在已排好序部分中，其余部分在未排序部分。然后依次从未排序部分中取出第一个元素， 从后向前与排好序部分的元素进行比较并将其插入已排好序部分的正确位置，直到所有元素排好序。当序列基本有序时，直接插入排序过程中元素比较的次数较少；当序列为逆序时，元素的比较次数最多。使用直接插入排序算法，数组 1， 1， 2，4， 7， 5需要比较 6次，依次为： 1与 1比较、 2与 1比较、 4与 2比较、 7与 4比较、 5与 7比较、 5与 4比较。 归并排序的基本思想是将待排序数组划分为子问题，对子问题求解，然后合并解。其主要步骤为：将数组分为两个相同规模
16、的子数组，分别包含前 n 2个元素和后 n 2个元素；递归地排序这两个子 数组；合并排好序的两个子数组，依次比较两个排好序的子数组的元素，得到整个数组的排好序的序列。使用归并排序算法，数组 1， 1， 2， 4， 7， 5需要比较 8次。 【知识模块】 算法设计和分析 4 【正确答案】 B 【知识模块】 算法设计和分析 【知识模块】 算法设计和分析 5 【正确答案】 B 【试题解析】 贪心算法在解决最优化问题上是仅根据当前已有的信息做出选择，即不是从整体最优考虑，它所做出的选择只是力求局部最优。本题给出的哈夫曼编码操作过程基于典型的贪心策略。 采用固定长度编码，需要 3位二进制数字来表示 6个
17、字符，即 a=000， b=001，c=010， d=011， e=100， f=101。这种方法需要 300000位来对整个原文件编码。采用哈夫曼编码，频繁出现的字符采用短编码，出现频率较低的字符采用长编码，这种编码方式需要 (321+263+183+123+44+84)1000=248000位。因此，与固定长度编码相比，该编码方案节省的存储空间为 (300000-248000)300000=17 3。 【知识模块】 算法设计和分析 6 【 正确答案】 C 【知识模块】 算法设计和分析 7 【正确答案】 C 【试题解析】 归并排序是将两个排好序的序列合并成一个有序的序列。由选项 A给出的结果
18、可知，递增序列 B的每一个元素都比 A中的元素要大，也就是说ai(1in)比 b1小，在排序的过程中，只需要将 ai与 b1进行比较，共比较了 n次。由选项 B给出的结果可知，递增序列 B的每一个元素都比 A中的元素要小，在排序的过程中，只需要将 bi(1in)与 a1进行比较，共比较了 n次。由选项 C给出的结果可知， ai bi ai+1，在排序的过程中，将 a1与 b1进行比较， a1小，然后将 a2与 b1进行比较， a2大，则已排好的部分为 a1b1，共比较了 2次；然后将 a2与 b2进行比较， a2小，再将 a3与 b2进行比较， a3大，则已排好的部分为 a1b1a2b2，共比
19、较了 4次；以此类推，完全排好时共比较了 2(n-1)+1=2n-1次。由选项 D给出的结果可知，递增序列 B的前 i 2个元素都比 A中的前 i 2个元素要大，但比 A中的后 i 2个元素要小， B的后 i 2个元素都比 A中的后 i 2个元素要大，因此在排序的时候， A中的前 i 2个元素只需与 b1进行比较，当比较到 ai 2+1时， ai 2+1比 b1大，则已排好的部分为 a1， a2， ， ai 2，共比较了 i 2+1次；然后将 b2，b3， ， bi 2与 ai 2+1进行比较，都比 ai 2+1小，当比较到 bi 2+1时， bi 2+1比 ai 2+1大，则已排好的部分为
20、a1， a2， ， ai 2， b1， b2， ， bi 2，共比较了 i+1次；然后将 ai 2+2， ai 2+3， ， an分别与 bi 2+1进行比较，共比较了 n-i 2-2次，完全排好时共比较了 i+1+n-i 2-2=n+i 2-1次。 【知识模块】 算法设计和分析 8 【正确答案】 C 【试题解析】 如果存在正常数 c和 n0，使得当 nn0时， T(n)cf(n)，则记为T(n)=O(f(n)。 T和 f的关系可以理解为 f(n)为 T(n)的一个上界，也可以理解为 T至多增长得和 f一样快。 如果存在正常数 c1、 c2和 n0，使得当 nn0时，c1f(n)T(n)c2f
21、(n)，则记为 T(n)= (f(n)。 T与 f有着相同的阶数，或者两者最终与相同的阶数增长。 对于选项 A， T(n)=f(n)=n2，只要 c2c11， n0 0，就有c1f(n)T(n)c2f(n)，因此有 T(n)=O(f(n)，即 n2=(n2)。 对于选项 B，T(n)=f(n)=n2，只要 c1， n0 0，就有 T(n)cf(n)，因此有 T(n)=O(f(n)，即n2=O(n2)。 对于选项 D， T(n)=n2， f(n)=n3，只要 c1， no 1，就有 T(n)cf(n)，因此有 T(n)=O(f(n)，即 n2=O(n3)。 对于选项 C，当 n 1时， n2的增
22、长比 n快，因此 n2=O(n)的关系不成立。 【知识模块】 算法设计和分析 【知识模块】 算法设计和分析 9 【正确答案】 C 【试题解析】 贪 心算法不考虑整体情况，以当前情况为基础做出最优选择。很明显，题目中用到的是贪心算法。分治算法是将规模为 n的问题分解为 k个子问题，这些子问题相互独立，且与原问题相同，然后将子问题的解合并得到原问题的解。动态规划算法与分治算法类似，但分解后的子问题往往不是独立的。回溯法要在包含问题的所有解的解空间中，按照深度优先的策略，从根节点出发搜索解空间。 在选择路径时，首先选择离中央仓库最近的运输目的地 1，需要将所有 n个目的地到中央仓库的距离进行比较，选
23、择最近的作为目的地 1，相当于从 n个数中选择一个最小数，此时比较了 n-1次；然后选择离目的地 1最近的目的地 2，此时需要将其余 n-1个目的地到目的地 1的距离进行比较，相当于从 n-1个数中选择一个最小数，此时比较了 n-2次，以此类推，共需比较 n-1+n-2+n-3+2+1=(n -1)(n-2) 2=(n2-3n+2) 2，算法的时间复杂度为 (n2)。 【知识模块】 算法设计和分析 10 【正确答案】 A 【知识模块】 算法设计和分析 11 【正确答案】 C 【试题解析】 算法中用到了两个辅助变量 i和 i，算法的空间复杂度为 (1)。在重新排列过程中， 从数组的两端进行比较，
24、从 i=0开始判断 Ai是否为负数， i为负数的时候， i=i+1，直到 Ai为正数；从 j=n-1开始判断 Ai是否为正数，如果为正数， j=j-1，直到 Aj为负数。当 ij的时候交换 Ai和 Aj的值，然后继续判断Ai和 Aj的值。数组 A中的元素个数为 n， Ai 0和 Aj的比较次数共为 n+2次， i=i+l和 j=j-1执行的次数最多为 n+2次， if语句中的 i j的比较和交换 Ai和Aj的操作分别最多执行 n-1次， While循序的条件判断至多执行 n次。可见，算法 的时间复杂度为 (n)。 【知识模块】 算法设计和分析 12 【正确答案】 C 【试题解析】 从 UML活
25、动图中可以看出，能够同时运行的线程为 A3、 A4，答案选 C。 【知识模块】 面向对象技术 【知识模块】 面向对象技术 13 【正确答案】 C 【知识模块】 面向对象技术 14 【正确答案】 C 【试题解析】 一个返回消息画作一个带开放箭头的虚线，向后指向来源的生命线，在这条虚线上面，放置操作的返回值，所以返回消息为 evaluation。实现Account的方法 就是指向调用它的语句，故第 (40)题答案选 C。 【知识模块】 面向对象技术 【知识模块】 面向对象技术 15 【正确答案】 B 【试题解析】 本题主要考察 C+的基本概念。继承是一种联结类的层次模型，并且允许和鼓励类的重用，它
26、提供了一种明确表述共性的方法。 【知识模块】 面向对象技术 16 【正确答案】 A 【知识模块】 面向对象技术 17 【正确答案】 C 【知识模块】 面向对象技术 18 【正确答案】 A 【试题解析】 策略设计模式定义了一系列的 算法，并将每一个算法封装起来，而且使它们还可以相互替换。策略设计模式让算法独立于使用它的客户而独立变化。抽象工厂设计模式是所有形态的工厂模式中最为抽象和最具一般性的一种形态。观察者设计模式定义了一种一对多的依赖关系，让多个观察者对象同时监听某一个主题对象。这个主题对象在状态发生变化时，会通知所有观察者对象，使它们能够自动更新自己。状态设计模式允许一个对象在其内部状态改
27、变时改变它的行为，对象看起来似乎修改了它的类。所以本题答案为 A。 【知识模块】 面向对象技术 19 【正确答案】 D 【试题解 析】 适配器设计模式是将一个类的接口转换成客户希望的另外一个接口。通知是一个对象对多个对象的同步操作。观察者设计模式定义了一种一对多的依赖关系，让多个观察者对象同时监听某一个主题对象。这个主题对象在状态发生变化时，会通知所有观察者对象，使它们能够自动更新自己。状态设计模式允许一个对象在其内部状态改变时改变它的行为，对象看起来似乎修改了它的类。依题意可知答案选 D。 【知识模块】 面向对象技术 【知识模块】 面向对象技术 20 【正确答案】 C 【试题解析】 组合 (
28、Composite)设计 模式将对象组合成树形结构以表示 “部分一整体 ”的层次结构，其中的组合对象使用户可以组合基元对象以及其他对象，从而形成任意复杂的结构。类 Component为组合中的对象声明接口。类 Leaf在组合中表示叶节点对象，并在组合中定义图元对象的行为。类 Composite定义有子部件的那些部件的行为、存储子部件，并在 Component接口中实现与子部件的有关操作。类 Client通过 Component接口操纵组合部件的对象。 【知识模块】 面向对象技术 21 【正确答案】 A 【知识模块】 面向对象技术 22 【正确答案】 C 【试题解析】 一般将多态分为通用多态和特
29、殊多态。其中通用多态包括参数多态和包含多态，参数多态利用泛型编程，是发散式的，是静态绑定的，让相同的实现代码应用于不同的场合，看重的是算法的普适性；包含多态利用 OOP，是收敛式的，是动态绑定的，让不同的实现代码应用于相同的场合，看重的是接口与实现的分离度。特殊多态包括强制多态和过载多态，其中强制多态是指一种类型的变量在作为参数传递时隐式转换成另一种类型，比如一个整型变量可以匹配浮点型变量的函数参数；过载多态是指同一个名 (操作符、函数名 )在不同的上下文中有不同的类型。程序设计语言中基本类型的大多数操作符都是过载多态。所以该题考查的是过载多态。 【知识模块】 面向对象技术 【知识模块】 面向
30、对象技术 23 【正确答案】 D 【试题解析】 继承是父类和子类之间共享数据和方法的机制。这是类之间的一种关系，在定义和实现一个类 (子类 )的时候，可以在一个已经存在的类 (父类 )的基础上进行，把这个已经存在的类所定义的内容作为自己的内容，并加入若干新的内容。一个父类可以有多个子类，这些子类都是父类的特例，父类描述了这些子类的共有属性和操 作。一个子类可以继承它的父类 (或祖先类 )中的属性和操作，这些属性和操作在子类中不必定义，子类中还可以定义自己的属性和操作。所以选项D错误。 题中的 Thing1为接口，那么 doIt()为接口中的抽象方法，必须由实现它的类去实现该方法。冈此在 Thi
31、ng3中必须实现，而 Thing4也是 Thing1的子类，但不是商接子类，所以可能由 Thing4实现。 【知识模块】 面向对象技术 24 【正确答案】 A 【知识模块】 面向对象技术 25 【正确答案】 B 【试题解析】 部署图展现了运 行处理节点以及其中构件的配置。部署图给出了体系结构的静态实施视图。它与构件图相关，通常一个节点包含一个或多个构件。 【知识模块】 面向对象技术 【知识模块】 面向对象技术 26 【正确答案】 C 【试题解析】 状态图展现了一个状态机，它由状态、转换、事件和活动组成。状态图关注系统的动态视图，它对接口、类和协作的行为建模尤为重要，它强调对象行为的事件顺序。状态图通常包含简单状态和组合状态、转换 (事件和动作 )。可以用状态图对系统的动态方面建模。这些动态方面可以包括出现在系统体系结构的任何视 图中的任何一种对象的按事件排序的行为，这些对象包括类 (主动类 )、接口、构件和节点。所以状态图不表示多个对象之间的交互。根据图中 ON状态的内部行为可以发现该状态为超状态。 【知识模块】 面向对象技术 27 【正确答案】 D 【知识模块】 面向对象技术
