下半年下午程序员试题及答案与解析软考考试真题案例分析.docx

全国计算机技术与软件专业技术资格（水平）、考试库 china_nejcer2013年下半年下午 程序员 考试试题-案例分析-答案与解析试题一（共15分）【说明】两个包含有限个元素的非空集合A、B的相似度定义为|AB|/|AB|，即它们的交集大小(元素个数)与并集大小之比。以下的流程图计算两个非空整数集合(以数组表示)的交集和并集，并计算其相似度。已知整数组A1:m和B1:n分别存储了集合A和B的元素(每个集合中包含的元素各不相同)，其交集存放于数组C1:s，并集存放于数组D1:t，集合A和B的相似度存放于SIM。例如，假设A=1,2,3,4,B=1,4,5,6,则C=1,4,D=1,2,3,4,5,6,A与B的相似度SIM=1/3。 阅读以上说明和流程图，填补流程图中的空缺(1)(5)，将解答填入答题纸的对应栏内。【参考答案】(1)、s (2)、t (3)、Cs (4)、Dt (5)、s/t【答案解析】首先我们来理解两个有限集合的相似度的含义。两个包含有限个元素的非空集合A、B的相似度定义为它们的交集大小(元素个数)与并集大小之比。如果两集合完全相等，则相似度必然为1(100%);如果两集合完全不同(没有公共元素)，则相似度必然为0;如果集合A中有一半元素就是集合B的全部元素，而另一半元素不属于集合B，则这两个集合的相似度为0.5(50%)。因此，这个定义符合人们的常理性认识。在大数据应用中，经常要将很多有限集进行分类。例如，每天都有大量的新闻稿。为了方便用户检索，需要将新闻稿分类。用什么标准来分类呢？每一篇新闻稿可以用其中所有的关键词来表征。这些关键词的集合称为这篇新闻稿的特征向量。两篇新闻稿是否属于同一类，依赖于它们的关键词集合是否具有较高的相似度(公共关键词个数除以总关键词个数)。搜索引擎可以将相似度超过一定水平的新闻稿作为同一类。从而，可以将每天的新闻稿进行分类，就可以按用户的需要将某些类的新闻稿推送给相关的用户。本题中的集合用整数组表示，因此，需要规定同一数组中的元素各不相同(集合中的元素是各不相同的)。题中，整数组A1:m和B1:n分别存储了集合A和B的元素。流程图的目标是将A、B中相同的元素存放入数组C1:s(共s个元素)，并将A、B中的所有元素(相同元素只取一次)存放入数组D1:t(共t个元素)，最后再计算集合A和B相似度s/t。流程图中的第一步显然是将数组A中的全部元素放入数组D中。随后，只需要对数组B中的每个元素进行判断，凡与数组A中某个元素相同时，就将其存入数组C;否则就续存入数组D(注意，数组D中已有m个元素)。这需要对j(遍历数组B)与i(遍历数组A)进行两重循环。判断框Bj=Ai成立时，Bj应存入数组C;否则应继续i循环，直到循环结束仍没有相等情况出现时，就应将Bj存入数组D。存入数组C之前，需要将其下标s增1;存入数组D之前，需要将其下标t增1。因此，初始时，应当给j赋0,使数组C的存数从Cl开始。从而，(1)处应填s，(3)处应填Cs。而数组D是在已有m个元素后续存，所以，初始时，数组D的下标t应当是m，续存是从Dm+1幵始的。因此，(2)处应填t，(4)处应填Dt。两重循环结束后，就要计算相似度s/t，将其赋予SIM，因此(5)处应填s/t。试题二（10分）【说明】下面的函数sort(intn，inta)对保存在数组a中的整数序列进行非递减排序。由于该序列中的元素在一定范围内重复取值，因此排序方法是先计算出每个元素出现的次数并记录在数组b中，再从小到大顺序地排列各元素即可得到一个非递减有序序列。例如，对于序列6,5,6,9,6,4,8,6,5,其元素在整数区间4,9内取值，因此使数组元素b0b5的下标05分别对应数值49,顺序地扫描序列的每一个元素并累计其出现的次数，即将4的个数记入b0，5的个数记入b1，依此类推，9的个数记入b5。最后依次判断数组b的每个元素值，并将相应个数的数值顺序地写入结果序列即可。对于上例，所得数组b的各个元素值如下：B0B1B2B3B4B5124011那么在输出序列中写入1个4、2个5、4个6、1个8、1个9,即得4,5,5,6,6,6,6,8,9,从而完成排序处理。【C函数】 阅读以上说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。【参考答案】(1)、afiminimum,或aimaximum,或ai=maximum,或其等价形式(3)、0(4)、bk,或bk0,或bk!=0,或其等价形式(5)、k【答案解析】首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。空(1)和(2)所在for语句的功能是求出数组a中的最小元素minimum和最大元素maximum。在设置了minimum和maximum的初始值后，空(1)处的判断条件是只要目前的元素ai小于minimum,就需要更新minimum，反之，空(2)处的判断条件是只要目前的元素ai大于maximum，就需要更新maximum，因此空(1)处应填入aimaximum或其等价方式。minimum和maximum的作用是要确定计数数组b的大小。根据题目中的描述，序列中的每个元素ai都对应到计数数组b的一个元素bk，对应方式为：k=ai-minimum,其中minimum是数组a中的最小元素，显然在计数时，一个数值出现一次，就在对应的bk中累加一次。空(3)(5)所在的语句组是产生排序后的序列，重新写入数组a。首先需明确变量i和k的作用，根据它们在该语句组中的出现位置，i用于表示数组a的元素下标，k用于表示数组b中元素的下标，因此，空(3)处应填入0,使得从数组a中下标为0的数组元素开始。通过循环控制“for(k=0;k0”或其等价形式。由于bk中记录的是元素k+minimum的出现次数，所以空(5)处应填入k，从而将元素值恢复后再写回去。 试题三【说明1】F面的函数countChar(char*text)统计字符串text中不同的英文字母数和每个英文字母出现的次数(英文字母不区分大小写)。【C代码1】【说明2】将下面C代码2中的空缺补全后运行，使其产生以下输出。f2:f2:f2:2f3:f3:1【C代码2】 阅读以上说明和C代码，填充代码中的空缺，将解答填入答题纸的对应栏内。【参考答案】(1)、text,或&text0,或其等价形式(2)、ptr+,或+ptr,或ptr=ptr+l,或ptr+=l(3)、ci,或*(c+i)(4)、f2(5)、f3(6)、f(n),或(*f)(n)【答案解析】首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。在函数countChar(char*text)中来统计字符串text中不同的英文字母数和每个英文字母出现的次数。用来表示计数值的数组元素ci需要与英文字母对应起来，方式为c0记录字母A或a的次数，cl记录字母B或b的次数，依此类推，因此i=英文字母-A(英文字母为大写)或i=英文字母-a(英文字母为小写)。数据指针是指向数据的指针变量。数据指针ptr用来表示text中的每一个字符，初始时ptr指向第一个字符，因此空(1)处应填入“text”或其等价方式，(2)处的作用是随循环控制逐个指出text中的后续字符，因此空(2)处应填入“ptr+”或其等价方式。显然，若ci的值不为0则表示字符A+i或a+i出现了，反之，则表示字符A+i或a+i未出现，因此在计算字符种类时只要判断ci是否为0即可，因此空(3)处应填入“ci”或其等价形式。函数指针是指向函数的指针变量。根据代码2的声明“intfl(int(*f)(int)；w可知调用函数fl时，实参应该是函数名或函数指针，且函数名或函数指针指向的函数应有一个整型参数，返回值为整型，而f2和fi都是符合这种定义类型的函数。C代码2中，在main函数中两次调用了函数fl，分析运行结果可知，是先以f2为实参调用fl,然后以fi为实参调用fl,因此空(4)和(5)分别填入“f2”或“f3”或它们的等价形式，在空(6)处应填入“f(n)”或其等价形式来实现最后对f2和f3的调用。 试题四【说明】正整数n若是其平方数的尾部，则称n为同构数。例如，6是其平方数36的尾部，76是其平方数5776的尾部，6与76都是同构数。下面的程序求解不超过10000的所有同构数。已知一位的同构数有三个：1，5，6，因此二位同构数的个位数字只可能是1，5，6这三个数字。依此类推，更高位数同构数的个位数字也只可能是1，5，6这三个数字。下面程序的处理思路是：对不超过10000的每一个整数a，判断其个位数字，若为1、5或6,则将a转换为字符串as，然后对a进行平方运算，并截取其尾部与as长度相等的若干字符形成字符串后与as比较，根据它们相等与否来断定a是否为同构数。【C程序】 阅读以上说明和C程序，填充程序中的空缺，将解答填入答题纸的对应栏内。【参考答案】(1)、a%10,或其等价形式(2)、right(rs,len)(3)、num%10,或其等价形式(4)、ch=si,或ch=*(s+i)(5)、i+,ms-,或ms-，i+,或其等价形式【答案解析】本题考查C语言语法、数据指针和运算逻辑的应用。首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。根据题目中的叙述，同构数的个位数为1、5或6，因此，对于不超过10000的每个整数，应先获取其个位数字，因此空(1)处应填入“a%10”或其等价形式，从而可以先过滤掉不可能是同构数的数。根据代码中的注释，通过以下运算后，得到由a中数值转换所得的字符串as，以及a的平方所得数值转换得到的字符串rs,此后通过字符串比较运算来判断是否为同构数。Len = myitoa(a,as); /*数a转换为字符串，存入as*/Myitoa(a*a,rs); /*数a的平方转换为字符串，存入rs */函数myitoa(int num,char*s)的功能是将整数num转换为字符串s，这就需要将整数num的每个数字分离出来，通常通过整除取余运算实现，即以下代码所实现的。While(num) /*从个数开始，取num的每一位数字转换为字符后放入s*/ Sn+ = (3) +0; Num = num/10 Sn=0;其中，空(3)处应填入“num%10”或其等价形式。函数right(char*ms，int length)取字符串ms尾部长度为length的子串，返回所得子串的首字符指针。该函数的处理思路是先找到ms中字符串的结尾，然后倒着数出length个字符，从而得到所需字符串的首字符指针。空(5)处应填入“i+，ms-”或其等价形式。另一个更简便的方式是在得到ms的结尾指针后，再减去length即可，即最后返回ms-length即可。试题五【说明】某应急交通控制系统(TraficControlSystem)在红灯时控制各类车辆(Vehicle)的通行，其类图如图5-1所示，在紧急状态下应急车辆红灯时也可通行，其余车辆按正常规则通行。下面的C+代码实现以上设计，请完善其中的空缺。 阅读以下说明和C+代码，填充代码中的空缺，将解答填入答题纸的对应栏内。【参考答案】(1)、virtual bool isEmergent()(2)、virtual void runRedLight()(3)、public Car，public Emergency(4)、this-isEmergency(5)、ev (6)、vi【答案解析】本题考查C+语言程序设计的能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。根据题目描述，以交通控制系统(TraficControlSystem)为背景，本题目中涉及的各类车辆和是否应急状态下在红灯时的通行情况。根据说明进行设计，题目给出了类图(图5-1类图所示)。图中父类Vehicle代表交通工具，设计为抽象类，包含一个方法：run()，表示行驶某一个具体的交通工具对象，行驶的方法由具体子类型完成，所以Vehicle的run()为一个纯虚函数：Virtual void run() = 0Car和Truck都继承自Vehicle的两个子类型，所以它们都继承了Vehicle的run()方法，各自行驶方式有所不同，所以都覆盖了Vehicle的run()方法，并加以实现：Void run()/*代码略*/Car的两个子类型PoliceCar和Ambulance都继承自Car,从而PoliceCar和Ambulance也都继承了Car中的run()方法。Truck的子类FireEngine也继承了Truck中的run()方法。图中接口Emergency在C+中釆用抽象基类的方法实现，其中约定红灯时通行的相关接口函数为：isEmergent()和runRedLight()，均为纯虚函数，原型中=0表示纯虚函数，实现由子类完成：Virtual bool isemergent() = 0Virtual void runredlight() = 0isEmergentO函数接口约定应急车辆返回自身紧急情况状态，用bod类型的isEmergency表示：this-isEmergency,其值在紧急情况下为bool值true，非紧急情况下为bool值false。mnRedLight()函数接口约定应急车辆在红灯时如何通行(isEmergency为true,则通行，isEmergency为false,和普通车辆一样通行)。Emergency的子类有PoliceCar、Ambulance和FireEngine,所以在这三个类中都要实现Emergency中定义的纯虚函数接口。交通控制类TraficControlSystem对运行的交通工具进行控制，所有交通工具用Vehicle数组v表示；numVehicles表示交通工具数量；control函数进行控制在紧急情况下应急车辆红灯通行，其他情况按常规通行；add()表示有车辆加入系统，shutDown()在系统关闭时清除每个对象数组元素：deletevi;。Vehicle的子类具体类型有Car、Truck、PoliceCar、Ambulance和FireEngine,所以v数组中对象有这些类型的对象，加入v时会自动向上转型成为Vehicle类型，而实现了Emergency接口的应急车辆有runRedLight()函数，其他Car和Truck只有run()函数。因此，用for循环对每个vi，判定是否是Emergency类型，即是否继承了Emergency,调用时动态绑定每个数组元素的实际类型，需要通过动态类型转换：Emergency*ev = dynamic_cast(vi);如果转换成功，说明是Emergency的子类，实现了runRedLight()，可以调用runRedLight()，否则调用run():If (ev != 0) ev_-runredlight(); Else v-run();主控逻辑代码在main函数中实现。初始化TraficControlSystem，用tcs表示，调用tcs的add()函数添加具体的交通工具，这里会自动向上转型成为Vehicle类型，调用control()对各车辆进行控制，调用shutDown()系统关闭，使用完数组对象之后，需要用delete操作进行释放对象，即deletetcs;因此，空(1)和空(2)需要定义纯虚函数isEmergent()和runRedLight()，原型中=0题目代码中己经给出，所以空(1)和空(2)分别为“virtualboolisEmergent()”和“virtualvoidrunRedLight()”;空(3)需要继承Car和Emergency,即“public Car,public Emergency”；空(4)要返回应急车辆对象的状态，即“this-isEmergency”；空(5)处动态类型转换成功的对象ev;空(6)处为普通车辆对象vi。试题六【说明】某应急交通控制系统(TraficControlSystem)在红灯时控制各类车辆(Vehicle)的通行，其类图如图6-1所示，在紧急状态下应急车辆在红灯时可通行，其余车辆按正常规则通行。下面的Java代码实现以上设计，请完善其中的空缺。【Java代码】 阅读以上说明和Java代码，填充程序中的空缺，将解答填入答题纸的对应栏内。【参考答案】(1)、booleanisEmergent() (2)、voidrunRedLight()(3)、extendsCarimplementsEmergency(4)、this.isEmergency(5)、(Emergency)vi (6)、vi【答案解析】本题考査Java语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。根据题目说明，以交通控制系统(TraficControlSystem)为背景，本题目中涉及的各类车辆和是否应急状态下在红灯时的通行情况。根据说明进行设计，题目给出了类图(图6-1类图所示)。图中父类Vehicle,代表交通工具，设计为抽象类。在Java用abstract关键字表示，表示行驶某一个具体的交通工具。Vehicle包含一个抽象方法：mn()，方法后没有实现，直接用;来表示抽象方法，表示行驶的方法由具体子类型完成，所以Vehicle的mn()为一个抽象方法：Abstract void run();Car和Truck都继承自Vehicle的两个子类型，所以他们都继承了Vehicle的run()方法，各自行驶方式有所不同，所以都覆盖了Vehicle的run()方法，并加以实现：Void run()/*代码略*/Car的两个子类型PoliceCar和Ambulance都继承自Car，从而PoliceCar和Ambulance也都继承了Car中的run()方法。Truck的子类FireEngine也继承了Truck的run()方法。图6-1中Emergency在Java中采用接口实现，其中约定红灯时通行的相关接口为：isEmergent()和runRedLight()。isEmergent()接口约定应急车辆返回自身紧急情况状态，用bool类型的isEmergency表示：this.isEmergency,其值在紧急情况下为true,非紧急情况下为false。runRedLight()接口约定应急车辆在红灯时如何通行(isEmergency为true,则通行，isEmergency为false，和普通车辆一样通行)。实现Emergency的类有PoliceCar、Ambulance和FireEngine，所以在这三个类中都要实现Emergency中定义的接口。在Java中，实现接口用implements关键字，后面加上所要实现的接口，即:classname ieplements interfacename交通控制类TraficControlSystem对运行的交通工具进行控制，所有交通工具用Vehicle数组v表示；numVehicles表示交通工具数量；control函数进行控制在紧急情况下应急车辆红灯通行，其他情况按常规通行；add()表示有车辆加入系统，shutDown()表示系统关闭。Vehicle的子类具体类型有Car、Truck、PoliceCar、Ambulance和FireEngine，所以v数组中对象有这些类型的对象，加入v时会自动向上转型成为Vehicle类型，Emergency接口的应急车辆有runRedLight()方法，其他Car和Truck只有run()方法。因此，用for循环中对每个vi，判定是否是Emergency类型的实例，即是否实现了Emergency。Java中判断一个对象是否是某个类型的实例用instanceof关键字。即：viinstanceofEmergency,如果是，说明是应急车辆，接着判定应急车辆的状态，在判定之前先要将应急车辆进行向下转型，Java中向下转型直接在对象前加上用括号括起来的转换的目标类型即可，即：(Emergency)vi).isEmergent()，如果判定为真，执行runRedLight(),判定不成功，则调用run()，调用时动态绑定每个数组元素的实际类型，需要通过动态类型转换并调用nmRedLight():If (vi instanceof emergency & (emergency)vi).isemergent() (emergency)vi.runredlight();elseVi-run();主控逻辑代码在main方法中实现。初始化TraficControlSystem,用tcs表示，调用tcs的add()函数添加具体的交通工具,这里会自动向上转型成为Vehicle类型，调用control()对各车辆进行控制，调用shutDown()系统关闭。因此，空(1)和空(2)需要定义接口isEmergent()和runRedLight(),题目代码中已经给出用分号结尾，所以空(1)和空(2)分别为“bool isEmergent()”和“voidrunRedLight()”;空(3)需要继承父类Car和实现接口Emergency,Java中继承釆用extends关键字，即应填入“extends Car implements Emergency”；空(4)要返回应急车辆对象的状态，即填入“this.isEmergency”；空(5)处为动态类型转换后的对象(Emergency)vi;空(6)处为普通车辆对象vi。2013年下半年下午-程序员-下午试题及答案与解析（软考真题-案例分析） 17 / 17