201111程序员下午真题
第 1 题
试题一(共15分)
阅读以下说明和流程图,填补流程图中的空缺(1)~(5),将解答填入答题纸的对应栏内。
【说明】
下图所示的流程图用于检查数组A[1:n]中的元素是否为自然数1~n的一个排序(含有1~n各数),若是,则输出OK,否则输出所缺的自然数及其个数m。
为检查A[1:n]中是否含有k,只要判断P(k)=(A(1)-k)*(A(2)-k)*.....*(A(n)-k)是否等于0即可。
【流程图】
答案与解析
- 试题难度:较难
- 知识点:流程图>流程图
- 试题答案:(1)0
(2)1
(3)P*(A(i)-k)或等价表示
(4))P=0 或等价表示
(5)m+1 或等价表示 - 试题解析:分析流程图,为检查A[1:n]中是否含有k,只要判断P(k)=(A(1)-k)(A(2)-k).....(A(n)-k)是否等于0即可。
m的初值为0,p的初值为1,表示不缺失。
进而计算P(k)=(A(1)-k)(A(2)-k).....(A(n)-k)即可用P*(A(i)-k),(i=1,n)表示
p=0表示缺失,每缺失一个m要增加1。
第 2 题
试题二(共15分)
阅读以下说明和C程序代码,将解答写在答题纸的对应栏内。
【说明】
下面是一个待修改的C程序,其应该完成的功能是:对于输入的一个整数num,计算机其位数k,然后将其各位数字逆序转换为字符串保存并输出。若num为负整数,则输出字符串应有前缀“-”。例如,将该程序修改正确后,运行时若输入“14251”,则输出“15241”;若输入“-6319870”,则输出“-0789136”。
下面给出的C程序代码中有五处错误,请指出错误代码所在的行号并给出修改正确后的完整代码行。
【C程序代码】
答案与解析
- 试题难度:较难
- 知识点:C程序设计>C程序设计
- 试题答案:
- 试题解析:本题考查 C 程序员查找错误和排除错误的基本能力。 程序中的错误主要分为语法错误和语义错误两类。语法错误是指语言结构上的错误,例如,是否引用了未定义的变量,表达式中缺少操作数等等。语义错误是指语言结构含义不正确或程序的运算逻辑有错误,这类错误可能在编译阶段发现(静态语义),也可能推迟到运行阶段才暴露。例如,表达式中运算符号不能处理所引用的运算对象 ,无穷循环等。
考生需要非常熟悉C语言的基本语法,从而通过走查源代码来发现语法错误。查找语义错误则需要充分理解程序的逻辑,也就是整个程序的结构和每条语句所起的作用。
前 2 行为预处理命令行,对于最常使用的 include 命令,考生应该非常熟悉,以便检查程序中对常用函数的调用是否正确。本程序中前两行无错误。
显然,接下来的四行分别为 mam 函数的首部,函数体的开始符号"{"、变量定义语句和空白行,这里也没有错误。
第 7 行为格式化输入函数 scanf 的调用语句,这是比较容易出错的地方,常见的错误是格式控制串与输入表列中的变量不匹配,或者是丢失变量前的取地址运算符号" &",该行的错误即在这里。
第 8行至第 12 行用于计算所输入整数的位数并用 k 来计算(记录),这几行代码应作为一个整体来理解。程序中首先将num的值备份至 t ,并对k 赋值,然后通过循环对t 进行辗转除以 10 的运算,使 t 每次都丢掉其个位数,即 t 的位数逐渐减少(t 每减少 l位, k 就增加1),直到 t 的值为 0时为止,此时 k 的值即为num的位数。第 9 行的循环条件错误导致了无穷循环(t 等于 0 时也继续循环),由于 t 的初值也可能是负数,因此应将其中的"t>=0" 改为"t!=0"。
第 14 行没有错误。
第 15 行的错误很明显,也很常见,即将"="误用为"=",从而改变其所在语句 的语义,其中的 "pstr=0"则将pstr的值重置为 0,使pstr所记录的字符串存储空间首地址信息丢失,此后针对 pstr[]的运算都会出错。
第 17 行至第 21 行用于处理 num 为负数时输出字符串应包含前缀"一"的要求,这几行没有错误。
第 22 行至第 25 行用于从 num 得到其逆置的数字字符串,其错误在第23行,属于逻辑错误。num%10 的运算结果为 num 的个位数字,而 pstr[]中要存储的是数字字符(即 ASCII 值),因此应将num%10 的运算结果加上字符 '0' (或字符 '0'的 ASCII 码值 48)。
第 26 行用于设置字符串结束标志,需要注意的是串结束标志的位置。由于 num 可能为负数,因此将字符串结束标志字符设置在 k 下标处可能出错,保险的做法是继续用 i作为下标,使得'\0'正好跟在最后一个数字字符的后面。
第 27 行至第 30 行没有错误。
第 3 题
试题三(共15分)
阅读以下说明和C代码,填补C代码中的空缺(1)~(5),将解答写在答题纸的对应栏内。
【说明】
某市在进行市长选举,该市共分为M个选区(1<M<6,从1开始顺序编号),共有N个候选者参选(1<N<5,从A开始顺序编号)。经投票后,所得选票数据如下表所示。
现已将选票数据存入文本文件data.txt,该文件内容格式如下:共有M行,每行N+1个整数,第一个整数为选区编号,随后为N个候选者在该选区所得票数。
下面的程序先从文件中读入选票数据存入二维数组data,然后完成下列功能:
a.计算并显示每个竞选者获得的选票数及占总选票数的百分比;
b.如果任一竞选者获得的选票数超过总票数的50%,则显示竞选者获胜;
c.如果没有竞选者获得总选票数的50%以上,则显示两位得票最高的竞选者需再进行决选。
在下面的程序代码中,竞选者A的编号为1,竞选者B的编号为2,以此类推。
/*data[ ][0]存放选区编号,data[M][J]存放j号竞选者得票总数*/
else
答案与解析
- 试题难度:较难
- 知识点:C程序设计>C程序设计
- 试题答案:(1)j++,或++j,或其等价表示(2)0(3)MAXP2=MAXP1(4)totalP+=data[M][j],或totalP+=totalP+data[M][j],或其等价表示(5)(double)MAxP1/totalP,或(float)MAXP1/totalP,或其等价表示。其中,将(double)或(float)写在totalP之前亦可
- 试题解析:本题考查 C 程序设计基本能力。题目中涉及的知识点主要有数组、文件、循环和类型转换,分析程序时首先要明确各个变量(或数组元素)所起的作用,并以语句组分析各段代码的功能,从而完成空缺处的代码填充。根据题目描述,首先将文件中的数据读入数组 data 。显然,i 和 j 分别起行号、列号的作用。行号 i应在一行的数据都读入后增加1,而列号 j 则每读入一个数据就要增加1, 因此空(1)处应填写 "j++" 或其等价形式的语句。
将数据读入数组 data 后,以题中的数据为例,data 数组的内容可表示如下:由于 data[M][i] 存放 i 号竞选者的得票总数,data[][0]存放的是选区编号,因此 data[M][0]不用。
以上表为例,需要将 data[0][l] 、data[l][l] 、...、data[M-l][l]加起来存入data[M] [1] ,因此,空(2) 处应填入 0,以设置data[M][l] 、data[M][2]、..d.ata[M][N]的初始值。空(3)所在的语句组用于找出得票数最多的竞选者,此时,因此之前的最多票数(MAXPl)将成为次多数(MAXP2),即空(3)处填入"MAXP2= MAXPl" 。
空(4)处为计算总票数的语句,根据说明,应填入 "totalP += data[M] [j]"或其等价形式。
空(5)处为计算票数最多者得票率的表达式,根据说明是将 MAXPl 除以 totalP ,需要注意的是: MAXPl 和 totalP都是整数且 MAXPl 小于totalP,因此应至少对其中的一个数值进行整数到实数的类型转换,否则其结果为0,因此,空(5)处应填入"(double)MAXPl/tota1P"或其等价形式。
第 4 题
试题四(共15分)
阅读以下说明和c函数,填补c函数中的空缺(1)—(5),将解答写在答题纸的对应栏内。
【说明】
约瑟夫问题如下所述:有n个人(编号为1~n)围成一圈,从第一个人开始,按照顺时针方向从1开始计数到m(即数到第m个人),让其出圈,然后再从其顺时针方向的下一个人开始,依次计数到m并让其出圈,重复这个过程,直到所有人都出圈,试给出出圈者的顺序。
以n=5,m=3为例,其中圈顺序为3,1,5,2,4,过程如下图所示。
下面的函数Joseph()在单向循环链表表示的基础上诉出圈的过程。
n为5时的单向循环链表结构如下图所示。
链表的结合类型定义如下:
typedef struct Node {
int no;
struct Node*next;
}Node,*LinkList;
函数Joseph(LinkList tail,int n,int m)的处理思路如下:
(1)用k计数,每次都从0开始,当计数到m-1时结束本次计数;
(2)通过指针p查找出圈者所对应的结点,当K的值等于是m-1时,P应指向出圈者对应结点的前驱结点;
(3)通过删除结点表示出圈处理;
(4)当m大于圈中剩余人数时,为了避免重复计数,用模运算修改m的值;
(5)计数和删除操作完成后再恢复m的原值;
k++;
}
答案与解析
- 试题难度:较难
- 知识点:C程序设计>C程序设计
- 试题答案:(1)i(2)m-1(3)p=p->next(4)p->next->No(5)p->next
- 试题解析:本题考查 C 程序设计基本能力及指针的应用。
题目中涉及的考点主要有链表运算和程序逻辑,分析程序时首先要明确各个变量所起的作用,并按照语句组分析各段代码的功能,从而完成空缺处的代码填充。
根据函数 Joseph 的处理思路, "m= m%i" 可避免计数过程重复(通俗来说,就是计数时绕着圈地数),需要考虑的特殊情况是 m 可能取值为 0,此时对应的情况应该是正好要数到目前所在位置的前一个人,由于链表指针的单向特点,还需逐个结点数过去才行,即当圈中还剩下 i 个人时,最多计数到 i,因此空(1)处应填入"i"
下面的语句组在单循环链表中扫描结点并完成计数。
k = 0;
while (k< (2) ) {
(3) ;
k++;
}
由于计数器 k 从 0 开始计数,因此,while 语句的循环条件应为 "k<m-1",因此,空(2)处应填入 "m-1"。由于在链表中通过指针p 指向结点并进行遍历,所以空(3)处应填入 "p = p->next"。
根据题目中函数 Joseph 的处理思路说明,当 k 的值等于 m-1 时,p指向出圈者对应结点的前驱结点,因此,p->next 所指向的结点是要被删除的结点,其编号为 p->next->No , 因此空(4)处应填入"p->next->No"。
删除 p 所指结点的后继结点的处理如下图所示,即要删除数据域为 y 的结点,需要将 p 所指结点的指针域指向 z 结点,对应的处理是:p->next = p->next->next ,由于己经使得 q 指向了 y 结点,从而有等同的处理:p->next = q->next ,因此空(5)处应填入"p->next"。
第 5 题
试题五(共15分)
阅读以下说明、图和C++代码,填补C++代码中的空缺(1)—(5),将解答写在答题纸的对应栏内。
【说明】
已知某公司主要有两大类耗电资产(Asset):计算机(ComputerAsset)和建筑物(BuildingAsset)。为了节约能源,通过控制各种电源,将可关闭的房灯、计算机显示器等在夜间关闭。
为了实现上述需求,设计了如下图所示的类图,并用下面的C++代码加以实现。
PowerSwitchable( ){ }
~ComputerMonitor ( ){ }
答案与解析
- 试题难度:较难
- 知识点:C++程序设计>C++程序设计
- 试题答案:(1):public ComputerAsset(2):public ComputerAsset, public PowerSwitchable(3)PowerSwitchable*(4)numItems++(5)new
- 试题解析:本题考查面向对象程序设计及其 C++语言实现的能力,涉及类和抽象类、对象、函 数和虚函数的定义和相关操作以及继承关系。要求考生根据给出的案例、类图和执行过程说明,认真阅读理清程序思路,然后完成题目。
先考查针对案例的特定需求,构建类图整体结构。本题中根据类图定义了以下类:BuildingManagement、Asset、ComputerAsset 、BuildingAsset 、ComputerCPU 、ComputerMoniter 、BuildingLight、RoomLights、EmergencyLight 和 PowerSwitchable。其中,Asset为抽象类,表示通用资产,作为所有资产类的基类;ComputerAsset 表示计算 机有关资产、BuildingAsset表示建筑物有关资产,两者作为 Asset的子类,继承了Asset类;ComputerCPU、ComputerMoniter 分别表示计算机 CPU 和显示器,继承了ComputerAsset。BuildingLight 是一种建筑物资产,表示建筑物内的照明设备,继承了BuildingAsset ,而照明设备有RoomLights 和 EmergencyLight,作为BuildingLight的子类。由于案例中两大类耗电资产(Asset);计算机(ComputerAsset)和建筑物(Building Asset), 可在夜间关闭的房灯(RoomLights)、计算机显示器(ComputerMoniter)属于不同的资产类型,所以将可关闭的资产设计为抽象基类PowerSwitchable,规定可在夜间关闭电源的物体的开关电源接口,即包含两个纯虚拟(virtual)函数。因此,RoomLights 和 ComputerMoniter 继承了 PowerSwitchable。
C++ 中有不同种类的继承方式,本题目中,ComputerCPU 是ComputerAsset 的子类,并且在子类的构造函数中,调用父类的构造函数,所以继承的权限为public。其语法为:public 后加父类名。ComputerMonitor 是 ComputerAsset 的子类,而且均是可关闭的,具有开关电源的相同接口,均继承了 PowerSwitchable ,并且在子类的构造函数中,调用父类的构造函数,所以继承的权限均为 public ,多个父类的继承语法是:public 父类名1,public 父类名 2。
系统中有各类资产,在BuildingManagement 中使用 Asset 通用资产类型数组,用 add 函数依次为建筑添加资产。由于add函数中对数组添加元素只有一条语句,需要在下标中完成指明当前添加资产元素的下标,并将下标后移。在 goodNight 函数中对可关闭的资产进行控制,需要判定其是否可关闭,也就是资产是否为 PowerSwitchable 类的子类。通过动态类型转换进行判定,如果资产类型是PowerSwitchable的子类,则转换后的类型调用相应接口,并绑定到具体对象,执行对象的关闭电源行为。
类 BuildingManagement 中没有定义构造函数,编译器会生成一个缺省的构造函数,采用 new关键宇进行对象创建。使用完成之后,通过 delete 进行释放。
因此空(1)需要表现出公有继承:public ComputerAsset;空 (2)处添加继承两个父类,并且权限均为 public,即:public ComputerAsset ,public PowerSwitchable;空(3)处动态类型转换为抽象类,即 PowerSwitchable* ;空(4)处完成指明当前添加资产元素的下标,并将下标后移,即 numItems++;空(5)处补充通过使用编译器生成的缺省构造函数创建对象,即应填入"new"。
第 6 题
试题六(共15分)
阅读以下说明、图和Java代码,填补Java代码中的空缺(1)—(5),将解答写在答题纸的对应栏内。
【说明】
已知某公司主要有两大类耗电资产(Asset):计算机(ComputerAsset)和建筑物(BuildingAsset)。为了节约能源,通过控制各种电源,将可关闭的房灯、计算机显示器等在夜间关闭。
为了实现上述需求,设计了如下图所示的类图,并用下面的Java代码加以实现。
//灯的通用信息:fluorescent / incandescent 等,略
答案与解析
- 试题难度:较难
- 知识点:Java程序设计>Java程序设计案例
- 试题答案:(1)extends BuildingLight(2)extends BuildingLight implements PowerSwitchable(3)PowerSwitchable(4)numItems++(5)new
- 试题解析:本题考查面向对象程序设计及其 Java 语言实现的能力,涉及类和接口、抽象类、对象、方法的定义和相关操作,以及继承和实现关系。要求考生根据给出的案例、类图和执行过程说明,认真阅读理清程序思路,然后完成题目。
先考查针对案例的特定需求,构建类图整体结构。本题中根据类图定义了类:BuildingManagement、 Asset、ComputerAsset、BuildingAsset、ComputerCPU、ComputerMoniter、BuildingLight、RoomLights、EmergencyLight和 PowerSwitchable。其中 Asset 为抽象类,表示通用资产,作为所有资产类的基类。ComputerAsset 表示计算机有关资产、BuildingAsset 表示建筑物有关资产,两者作为 Asset 的子类,继承了 Asset类,ComputerCPU、ComputerMoniter分别表示计算机 CPU和显示器,继承了 ComputerAsset, BuildingLight是一种建筑物资产,表示建筑物内的照明设备,继承了Bui1dingAsset ,而照明设备有RoomLights和 EmergencyLight,作为Bui1dingLight的子类。由于案例中两大类耗电资产(Asset):计算机(ComputerAsset)和建筑物(Building Asset)中,可在夜间关闭的房灯(RoomLights)、计算机显示器(ComputerMoniter)属于不同 的资产类型,所以将可关闭的资产单独进行设计为一种类型PowerSwitchable ,规定可在夜间关闭电源的物体的开关电源接口,即包含两个方法声明。因此,RoomLights和 ComputerMoniter实现了 PowerSwitchable。
Java 中继承用关键字extends后加父类名。本题目中,Emergency Light是 BuildingLight的子类,并且在子类的构造方法中,调用父类的构造方法,采用 super(),并且调用父类的构造方法必须要是构造方法中的第一条语句。RoomLights是 BuildingLight 的子类,在子类的构造方法中,同 EmergencyLight,调用父类的构造方法super()。同时RoomLights和 ComputerMonitor均是可关闭的,具有开关电源的相同接口。Java 中的继承是单根继承,即只能有一个父类,而接口可以实现多个,因此将PowerSwitchable定义为接口,也一样可作为引用数据类型,和类继承一样也表达"是一种"关系,采用 interface 关键字。RoomLights 和 ComputerMonitor均实现 PowerSwitchable接口,用 implements关键字。
系统中有各类资产,在BuildingManagement中使用 Asset通用资产类型数组,用 add函数依次为建筑添加资产。由于 add方法中对数组添加元素只有一条语句,需要在下标中完成指明当前添加资产元素的下标,并将下标后移。在 goodNight方法中对可关闭电源的资产进行控制,需要判定其是否可关闭,也就是资产是否为PowerSwitchable类型的实例,用 instanceof 关键字,判定对象是否为实现通用接口PowerSwitchable 类型的实例。如果对象的类型是实现 PowerSwitchable接口的类型,则转换为PowerSwitchable 接口类型,并利用动态绑定机制,正确绑定到具体对象,执行对象的关闭电源行为。
类BuildingManagement中没有定义构造方法,编译器会生成一个缺省的构造方法,采用 new 关键字进行对象创建。
因此空(1)需要表现出继承extends BuildingLight;空(2)处添加继承和实现接口,即extends BuildingLight implements PowerSwitchable;空(3)处将接口作为一种引用类型,用 instanceof 判断对象是否为接口类型,即 PowerSwitchable;空(4)处完成指明当前添加资产元素的下标,并将下标后移,即 numItems++;空(5)处补充通过使用编译器生成的缺省构造方法创建对象,即 new。