1、软件水平考试中级软件设计师上午基础知识（数据结构、算法设计和分析、面向对象技术、标准化和软件知识产权基础知识、计算机专业英语）模拟试卷 1及答案与解析 1 在 KMP模式匹配算法中，需要求解模式串 p的 next函数值，其定义如下 (其中，j为模式串字符的序号 )。对于模式串 “abaabaca”，其 next函数值序列为 _。（ A） 01111111 （ B） 01122341 （ C） 01234567 （ D） 01122334 2 对于线性表 (由 n个同类元素构成的线性序列 )，采用单向循环链表存储的特 定之一是 _。 （ A）从表中任意节点出发都能遍历整个链表 （ B）对表中的任
2、意节点可以进行随机访问 （ C）对于表中的任意一个节点，访问其直接前趋和直接后继节点所用时间相同 （ D）第一个节点必须是头节点 3 无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图 G中的顶点数为 n，边数为 e，则所有顶点的度数之和为 _。 （ A） ne （ B） n+e （ C） 2n （ D） 2e 4 一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从 l开始顺序编号，即根节点编号 为 1，其左、右孩子节点编号分别为 2和 3，再下一层从左到右的编号为 4、 5、 6、 7，依次类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用 _可判定编号为 m和
3、 n的两个节点是否在同一层。 （ A） log2m=log2n （ B） log2m=log2n （ C） log2m+1=log2n （ D） log2m=log2n+1 5 _是由权值集合 8， 5， 6， 2构造的哈夫曼树 (最优二叉树 )。6 在有 n个无序无重复元素值的数组中查找第 i小的数的算法描 述如下：任意取一个元素 r，用划分操作确定其在数组中的位置，假设元素 r为第 k小的数。若 i等于 k，则返回该元素值；若 i小于 k，则在划分的前半部分递归进行划分操作找第 i小的数；否则在划分的后半部分递归进行划分操作找第 k-i小的数。该算法是一种基于 _策略的算法。 （ A）分治
4、 （ B）动态规划 （ C）贪心 （ D）回溯 7 对 n个元素值分别为 -1、 0或 1的整型数组 A进行升序排序的算法描述如下：统计 A中 -1、 0和 1的个数，设分别为 n1、 n2和 n3，然后将 A中的前 n1个元素赋值为 -1，第 n1+1到 n1+n2个元素赋值为 0，最后 n3个元素赋值为 1。该算法的时间复杂度和空间复杂度分别为 _。 （ A） (n)和 (1) （ B） (n)和 (n) （ C） (n2)和 (1) （ D） (n2)和 (n) 8 设算法 A的时间复杂度可用递归式 表示，算法 B的时间复杂度可用递归式 表示，若要使得算法 B渐进地快于算法 A，则 a的
5、最大整数为 _。 （ A） 48 （ B） 49 （ C） 13 （ D） 14 9 要在 88的棋盘上摆放 8个 “皇后 ”，要求 “皇后 ”之间不能发生冲突，即任何两个“皇后 ”不能在 同一行、同一列和相同的对角线上，则一般采用 _来实现。 （ A）分治法 （ B）动态规划法 （ C）贪心法 （ D）回溯法 10 分治算法设计技术 _。 （ A）一般由三个步骤组成：问题划分、递归求解、合并解 （ B）一定是用递归技术来实现 （ C）将问题划分为 k个规模相等的子问题 （ D）划分代价很小而合并代价很大 11 某算法的时间复杂度可用递归式 表示，若由 表示，则正确的是 _。 （ A） (nl
6、og56) （ B） (n2) （ C） (n) （ D） (nlog65) 12 采用面向对象开发方法时，对象是系统运行的基本实体。以下关于对象的叙述中，正确的是 _。 （ A）对象只能包括数据 (属性 ) （ B）对象只能包括操作 (行为 ) （ C）对象一定有相同的属性和行为 （ D）对象通常由对象名、属性和操作三个部分组成 12 一个类是 _(2)。在定义类时，将属性声明为 private的目的是 _(3)。 13 (2) （ A）一组对象的封装 （ B）表示一组对象的层次关系 （ C）一组对象的实例 （ D）一组对象的抽象定义 14 (3) （ A）实现数据隐藏，以免意外更改 （ B
7、）操作符重载 （ C）实现属性值不可更改 （ D）实现属性值对类的所有对象共享 14 _(4)设计模式允许一个对象在其状态改变时，通知依赖它的所有对象。该设计模式的类图如图 10 32所示，其中， _(5)在其状态发生改变时，向它的各个观察者发出通知。15 (4) （ A）命令 (Command) （ B）责任链 (Chain of Responsibility) （ C）观察者 (Observer) （ D）迭代器 (Iterator) 16 (5) （ A） Subject （ B） ConcreteSubject （ C） Observer （ D） ConcreteObserver 1
8、7 在面向对象软件开发中，封装是一种 _技术，其目的是使对象的使用者和生产者分离。 （ A）接口管理 （ B）信息隐藏 （ C）多态 （ D）聚合 18 欲动态地给一个对象添加职责，宜采用 _模式。 （ A）适配器 (Adapter) （ B）桥接 (Bridge) （ C）组合 (Composite) （ D）装饰器 (Decorator) 19 _模式通过提供与对象相同的接口来控制对这个对象的访问。 （ A）适配器 (Adapter) （ B）代理 (Proxy) （ C）组合 (Composite) （ D）装饰器 (Decorator) 20 采用 UML进行面向对象开发时，部署图通常
9、在 _阶段使用。 （ A）需求分析 （ B）架构设计 （ C）实现 （ D）实施 20 业务用例和参与者一起描述 _(10)，而业务对象模型描述 _(11)。 21 (10) （ A）工作过程中的静态元素 （ B）工作过 程中的动态元素 （ C）工作过程中的逻辑视图 （ D）组织支持的业务过程 22 (11) （ A）业务结构 （ B）结构元素如何完成业务用例 （ C）业务结构以及元素如何完成业务用例 （ D）组织支持的业务过程 23 面向对象分析的第一步是 _。 （ A）定义服务 （ B）确定附加的系统约束 （ C）确定问题域 （ D）定义类和对象 24 _指可以不经著作权人许可，不需要支付
10、报酬，使用其作品。 （ A）合理使用 （ B）许可使用 （ C）强制许可使用 （ D）法定许可使用 25 王某是 M国际运输有限公司计算机系统管理员。任职期间，王某根据公司的业务要求开发了 “海运出口业务系统 ”，并由公司使用，随后，王某向国家版权局申请了计算机软件著作权登记，并取得了计算机软件著作权登记证书。证书明确软件名称是 “海运出口业务系统 V1 0”，著作权人为王某。以下说法中，正确的是_。 （ A）海运出口业务系统 V1 0的著作权属于王某 （ B）海运出口业务系统 V1 0的著作权属于 M公司 （ C）海运出口业务系统 V1 0的著作权属于王某和 M公司 （ D）王某获取的软件著
11、作权登记证是 不可以撤销的 25 Extreme Programming(XP)is a discipline of software development with_【 C1】 of simplicity， communication， feedback and courage Successful software development is a team effort-not just the development team， but the larger team consisting of customer， management and developers XP is a
12、simple process that brings these people together and helps them to success together XP is aimed primarily at object-oriented projects using teams of a dozen or fewer programmers in one location The principles of XP apply to any_【 C2】 project that needs to deliver quality software rapidly and flexibl
13、y An XP project needs a_【 C3】 customer to provide guidance Customers，programmers， managers， are all working _【 C4】 to build the system thats needed Customers-those who have software that needs to be developedwill learn simple， effective way to _【 C5】 what they need， to be sure that they are getting
14、what they need， and to steer the proj ect to success 26 【 C1】 （ A） importance （ B） keys （ C） roles （ D） values 27 【 C2】 （ A） small-sized （ B） moderately-sized （ C） large-sized （ D） huge-sized 28 【 C3】 （ A） part-time （ B） casual （ C） seldom （ D） full-time 29 【 C4】 （ A） together （ B） by themselves （ C
15、） separately （ D） alone 30 【 C5】 （ A） tell （ B） know （ C） communicate （ D） feedback 30 Ravi， like many project_【 C1】， had studied the waterfall model of software development as the primary software life-cycle _【 C2】 He has all set to use it for an upcoming project， his first assignment However Ravi
16、found that the waterfall model could not be used because the customer wanted the software delivered in stages，something that implied that the system had to be delivered and built in_【 C3】 and not as_【 C4】 The situation in many other proj ects is not very different The real world rarely presents a pr
17、oblem in which a standard process， or the process used in a previous project， is the best choice To be the most situation， an existing process must be _【 C5】 to the new problem A development process， even after tailoring， generally cannot handle change requests To accommodate change requests without
18、 losing control of the project， you must supplement the development process with a requirement change management process 31 【 C1】 （ A） customers （ B） managers （ C） users （ D） administrators 32 【 C2】 （ A） activity （ B） procedure （ C） process （ D） progress 33 【 C3】 （ A） pans （ B） modules （ C） software
19、 （ D） a whole 34 【 C4】 （ A） pans （ B） modules （ C） software （ D） a whole 35 【 C5】 （ A） modified （ B） used （ C） suited （ D） tailored 软件水平考试中级软件设计师上午基础知识（数据结构、算法设计和分析、面向对 象技术、标准化和软件知识产权基础知识、计算机专业英语）模拟试卷 1答案与解析 1 【正确答案】 B 【试题解析】 模式串 “abaabaca”的 next函数值序列如下：当 j=1时， next1=0；当 j=2时， k不存在，next2=1；当 j=3时，不存
20、在满足条件的 k， next3=1；当 j=4时， p1=p3=a，存在 k=2，使得 p1p2p k-1=pj-k+1pj-k+2p j-1，故 next4=2；当 j=5时，存在 k=2，使得 p1p2p k-1=pj-k+1+pj-k+2p j-1，即 p1=p4=a，故 next5=2；当 j=6时，存在k=3，使得 p1p2=p4p5，故 next6=3；当 j=7时，存在 k=4，使得p1p2p3=p4p5p6，故 next7=4；当 j=8时，不存在满足条件的 k值，故next8=1。 【知识模块】 数据结构 2 【正确答案】 A 【试题解析】 对于单向循环链表，从表中任意节点出
21、发都能遍历整个链表，但并不能对表中的任意节点进行随机访问，需要从设置的第一个节点开始，沿着指针访问表中的节点。当然访问某一节点的直接后继节点最快，访问其直接前趋节点最慢，因为首先要遍历到表尾，然后从表头遍历到其前趋节点。 【知识模块】 数据结构 3 【正确答案】 A 【试题解析】 在无向图中，一条边与两个顶点相连，边数为 e的无向图所有顶点的度数之和为 2e。 【知识模块】 数据结构 4 【正确答案】 B 【试题解析】 由于是满二叉 树，只有 m个节点的二叉树一定是完全二叉树，只有n个节点的二叉树也一定是完全二叉树，因此，具有 m个节点的完全二叉树的深度为 log2m+1，具有 n个节点的完全
22、二叉树的深度为 log2n+1。如果编号为 m和n的两个节点是在同一层，则有 log2m+1=log2n+1，即 log2m=log2n。 【知识模块】 数据结构 5 【正确答案】 C 【试题解析】 哈夫曼树是带权路径最短的树。选项 A、 B、 C、 D四棵树的带权路径长度分别如下。 选项 A： 82+52+62+22=42 选项 B： 83+53+62+2=53 选项 C： 8+62+23+53=44 选项 D： 2+52+63+83=54 【知识模块】 数据结构 6 【正确答案】 A 【试题解析】 分治算法的基本思想是将个难以直接解决的大问题分解成一些规模较小的小问题以便各个击破，分而治之
23、。分治算法的每一层都有 3个步骤：分解、求解和合并。本题的查找算法，不断划分数组，缩小查找范围，可见该算法是基于分治策略的算法。 【知识模块】 算法设计和分析 7 【正确答案】 A 【试题解析】 本题需要用 3个辅助变量 n1、 n2和 n3来保存数组 A中 -1、 0和 1的个数，空间复杂度为 (1)。 在统计时，需要使用一循环语句遍历数组 A。统计完成后，再使用一次循环语句遍历数组 A，并将 A中的前 n1个元素赋值为 -1，第n1+1到 n1+n2个元素赋值为 0，最后 n3个元 素赋值为 1。数组 A的元素个数为n，因此算法的时间复杂度为 (n)。 【知识模块】 算法设计和分析 8 【
24、正确答案】 A 【试题解析】 对于算法 A，设 a=7， b=2， f(n)=n2，则 logba 2，因此存在常数，使 得 f(n)=O(nlogba-)，因此 T(n)=(nlogba)=(nlog27)。 如果要使 B渐进地快于算法 A，则有 nlog27 nlog4a，得 log27 log4a，求得 a 49，冈此 a的最大整数为 48。 【知识模块】 算法设计和分析 9 【正确答案】 D 【试题解析】 8皇后问题等价于要求在一个 88格的棋盘上放置 8个皇后，使得任意两个皇后不能放在同一行或同一列或同一斜线上。求解过程从空棋盘开始，设在第 1行至第 m行都已经正确放置了 m个皇后的
25、基础上，再在第 m+1行上找合适的位置放 置第 m+1个皇后，直至第 8行也找到合适的位置放置第 8个皇后。在任一行上都有 8种选择，开始时，位置在第 1列，以后改变时，顺序选择第 2列、第 3列、 、第 8列。当第 8列也不是一个合适的位置时，就要回溯，去改变前一行的位置。 分治法将复杂的大问题分解成规模小的问题以各个击破。归并排序等算法是采用分治法实现的。动态规划法与分治法类似，基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解，背包问题、 LCS问题等是采用动态规划法实现的。贪心法跟动态规划法一样，也是用来解决最优 问题的，但贪心法并不从整体最优考
26、虑，它所做出的选择只是某种意义上的局部最优。 【知识模块】 算法设计和分析 10 【正确答案】 A 【试题解析】 分治算法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。分治算法产生的子问题往往是原问题的较小模式。一般来说，分治算法分为三个步骤：将原问题分解成一系列子问题；递归求解各个子问题；将子问题的解合并成原问题的解。 【知识模块】 算法设计和分析 11 【正确答案】 A 【试题解析】 a=6， b=5， f(n)=n， logba=1 113，存在 =0 113，使得f(n)=O(nlogba-)，因此 T(n)=(nlogba)=(nlog5
27、6)。 【知识模块】 算法设计和分析 12 【正确答案】 D 【试题解析】 在面向对象的系统中，对象是基本的运行实体，它既包括数据 (属性 )，也包括作用于数据的操作 (行为 )。一个对象通常可由对象名、属性和操作三个部分组成。 【知识模块】 面向对象技术 【知识模块】 面向对象技术 13 【正确答案】 D 【试题解析】 类是现实世界 或思维世界中的实体在计算机中的反映，它将数据以及这些数据上的操作封装在一起。类是对象的抽象，而对象是类的具体实例。 在类中，可将数据声明为 private、 protected和 public。声明为 private的数据为私有的，只能被类中的成员函数调用，不能
28、在类外访问，从而实现数据隐藏的目的，可防止意外更改。 【知识模块】 面向对象技术 14 【正确答案】 A 【知识模块】 面向对象技术 【知识模块】 面向对象技术 15 【正确答案】 C 【试题解析】 观察者模式定义并保 持对象间的依赖关系，它允许一个对象在其状态改变时，通知依赖它的所有对象。 命令模式将请求封装在对象中，把它作为参数来传递。迭代器抽象了访问和遍历一个集合中的对象的方式。 责任链是用一系列类试图处理一个请求，这些类之间是一个松散的耦合，唯一共同点是在它们之间传递请求。也就是说，来了一个请求， A类先处理，如果 A类没有处理，就传递到 B类处理，如果 B类没有处理，就传递到 C类处
29、理，就这样像一个链条一样传递下去。引入责任链的目的是为了解除耦合。 在观察者设计模式中， Subiect和 Observor分别表示抽象的被观察者和观察者。通常一个观察者观察一个被观察者，而一个被观察者可以被多个观察者关注。但 Subject的状态发生变化时， Subiect将通知所有的 Observor，告知其状态已发生变化，而 Observor收到通知后将查询 Subiect的状态。 【知识模块】 面向对象技术 16 【正确答案】 B 【知识模块】 面向对象技术 17 【正确答案】 B 【试题解析】 封装是面向对象的三大要素之一。面向对象软件开发中，通过类将数据 (属性 )和函数 (行为
30、)封装在一起，在类中通过设 定访问权限，实现对信息的隐藏或公开，隐藏类的内部实现，留下一些接口与外界进行信息交换。 【知识模块】 面向对象技术 18 【正确答案】 D 【试题解析】 适配器 (Adapter)、桥接 (Bridge)、组合 (Composite)、装饰器(Decorator)都是结构型设计模式，用于处理类或对象的组合。适配器使得一个接口与其他接口兼容，从而给出了多个不同接口的统一抽象；桥接模式将对象的抽象和其实现分离；组合模式描述了如何构造一个类层次式结构；装饰器模式描述了如何动态地为对象添加职责。 【 知识模块】 面向对象技术 19 【正确答案】 B 【试题解析】 代理模式是
31、一种结构型设计模式，主要解决的问题是在直接访问对象时带来的问题，如要访问的对象在远程的机器上。在面向对象系统中，有些对象由于某些原因 (比如对象创建开销很大，或者某些操作需要安全控制，或者需要进程外的访问 )，直接访问会给使用者或者系统结构带来很多麻烦，此时可以在访问此对象时加上一个对此对象的访问层，如图 10 45所示。【知识模块】 面向对象技术 20 【正确答案】 D 【试题解析】 部署图展现了运行处理节点以及 其中构件的配置，给出了体系结构的静态实施视图。 【知识模块】 面向对象技术 【知识模块】 面向对象技术 21 【正确答案】 D 【试题解析】 业务用例模型描述一个业务的流程以及它们
32、与外部各方 (如客户和合作伙伴 )之间的交互。业务用例模型描述的是业务范围，与系统用例模型讲述的系统范围是不同的。 业务对象模型是描述业务用例实现的对象模型。业务对象模型是一种根据职责、可交付工件和协作行为来说明业务流程的方法。没有业务对象模型意味着存在一定风险，因为开发人员只是肤浅地注意业务的进行方式， 他们将做自己所熟悉的工作，即在缺乏业务流程观念的前提下设计和创建软件，其结果可能是构建出来的系统无法满足业务需要。 【知识模块】 面向对象技术 22 【正确答案】 C 【知识模块】 面向对象技术 23 【正确答案】 C 【试题解析】 面向对象分析 (OOA)需要将真实世界进行抽象，通过问题的
33、叙述，将真实世界系统加以描述。分析的目的是为了构造一个系统属性和系统行为的模型，该模型是根据对象和对象之间的关系、动态控制和功能转移来确定的。 OOA应该包含以下几个步骤： 分析问题域，建立用例模型 ； 发现和定义对象和类； 识别对象的内部特征； 识别对象的外部联系； 识别对象之间的交互。 面向对象分析的基础就是问题域以及用户的需求，研究问题域和系统需求的主要目的是通过对问题域的深入研究，建立一个能够满足用户需求的系统模型。面向对象分析的第一步就是分析用户需求，确定问题域，在此基础上建立用例模型。 【知识模块】 面向对象技术 24 【正确答案】 A 【试题解析】 著作权的合理使用属于著作权的一
34、种限制，它是指自然人、法人或者其他组织为了个人欣赏、评论、新闻报道、教学与学术研究以及公 益事业等目的，根据著作权法的规定，可以不经过作者同意而使用其已经发表的作品，不需要向其支付报酬。合理使用的对象是已经发表的作品。合理使用应尊重作者的人身权利，应当指明作者姓名、作品名称，并且不得影响作品的正常使用，也不得不合理损害著作权人的合法利益。合理使用成立的条件都是由法律予以规定的，因此可以说合理使用也是一种特别的法定许可使用。 许可使用是指软件著作权人或权利合法受让者，通过合同方式许可他人使用其软件，并获得报酬的一种软件贸易形式。法定许可使用和强制许可使用都属于许可使用。法定许可，是指由法律 规定
35、使用他人作品时，不需要征得著作权人的同意，但需要向著作权人支付报酬。强制许可，是指在著作权人无正当理由而拒绝与使用人达成使用作品的协议时，被拒绝人可以向法定部门申请并获得授权使用作品，但是应当尊重著作权人的人身权利，并且支付报酬。 【知识模块】 标准化和软件知识产权基础知识 25 【正确答案】 B 【试题解析】 软件开发完成后，著作权自动产生，不论是否登记都享有著作权。软件著作权登记证书是对等级事项的初步证明，可以帮助持有者在诉讼中起到减轻举证责任的作用。 王某在单位任职期间，针 对本职工作中明确指定的任务所开发的软件为职务开发软件，该软件的著作权由单位享有。因此，海运出口业务系统 V1 0的
36、著作权属于 M公司。 中国版权保护中心可以根据申请人的申请，撤销软件著作权登记证。 【知识模块】 标准化和软件知识产权基础知识 【知识模块】 计算机专业英语 26 【正确答案】 D 【试题解析】 参考译文：极限编程 (XP)是一种软件开发方法，其价值观是简单、沟通、反馈和勇气。成功的软件开发是团队努力的结果，这里的团队不仅仅是开发团队，而是包括了客户、管理者和开发者在内的 更大的团队。 XP是一种将上述人员组织起来并帮助他们取得成功的简单的过程。 XP主要针对那些由十几个或更少的在同一地点工作的程序员组成的团队所进行的面向对象的项目。 XP原则适用于需要快速且灵活地交付高质量软件的中等规模项目
37、组。 一个 XP项目需要一个全程参与的客户给予指导。客户、程序员和项目经理协同工作来构建需要的系统。客户，也就是需要软件的人，将学到简单而有效的沟通方法，来确保获得他们所需要的，从而引导项目走向成功。 【知识模块】 计算机专业英语 27 【正确答案】 B 【知识模块】 计 算机专业英语 28 【正确答案】 D 【知识模块】 计算机专业英语 29 【正确答案】 A 【知识模块】 计算机专业英语 30 【正确答案】 C 【知识模块】 计算机专业英语 【知识模块】 计算机专业英语 31 【正确答案】 B 【试题解析】 参考译文：和许多项目经理一样， Ravi研究了作为主要软件生命周期过程的瀑布模型。
38、他打算在首个任务，也就是即将开始的项目中使用瀑布模型。但是，他发现瀑布模型不能满足要求，原因是客户希望软件分阶段交付，也就意味着系统必须一部分 一部分地交付和构建，而不是作为一个整体进行。 这种情况在很多其他项目中也类似。现实世界中，很难有一种标准的过程或在前期的项目中使用的过程作为目前项目的最佳选择。对于大部分情况，必须对已存在的过程进行调整，以适应新的问题。 但是，即使经过调整，一个开发过程也很难处理变化的需求。为了适应变化的需求而不失去对项目的控制，你必须用需求变更管理过程从而对开发过程进行补充。 【知识模块】 计算机专业英语 32 【正确答案】 C 【知识模块】 计算机专业英语 33 【正确答案】 A 【知识模块】 计算机专业英语 34 【正确答案】 D 【知识模块】 计算机专业英语 35 【正确答案】 D 【知识模块】 计算机专业英语
