下半年程序员考试真题及答案下午卷.docx
- 文档编号:17732433
- 上传时间:2023-08-03
- 格式:DOCX
- 页数:16
- 大小:400.60KB
下半年程序员考试真题及答案下午卷.docx
《下半年程序员考试真题及答案下午卷.docx》由会员分享,可在线阅读,更多相关《下半年程序员考试真题及答案下午卷.docx(16页珍藏版)》请在冰点文库上搜索。
下半年程序员考试真题及答案下午卷
2012下半年程序员考试真题及答案-下午卷
试题一
【说明】
本流程图用于计算菲波那契数列{a1=1,a2=1,…,an=an-1+an-2!
n=3,4,…}的前n项(n>=2)之和S。
例如,菲波那契数列前6项之和为20。
计算过程中,当前项之前的两项分别动态地保存在变量A和B中。
【流程图】
阅读说明和流程图,填补流程图中的空缺
(1)〜(5)
(1)2或A+B
(2)n
(3)A+B
(4)B-A
(5)S+B
菲波那契数列的特点是首2项都是1,从第3项开始,每一项都是前两项之和。
该数列的前几项为1,1,2,3,5,8,…。
在流程图中,送初始值1—A,2—B后,显然前2项的和S应等于2,所以
(1)处应填2(或A+B)。
此时2→i(i表示动态的项编号),说明已经计算出前2项之和。
接着判断循环的结束条件。
显然当i=n时表示已经计算出前n项之和,循环可以结束了。
因此
(2)处填n。
判断框中用“>”或“≥”的效果是一样的,因为随着i的逐步增1,只要有i=n结束条件就不会遇到i>n的情况。
不过编程的习惯使循环结束条件扩大些,以防止逻辑出错时继续循环。
接下来i+1→i表示数列当前项的编号增1,继续往下计算。
原来的前两项值(分别在变量A和B中)将变更成新的前两项再放到变量A和B中。
首先可以用A+B—B实现(原A)+(原B)—(新B),因此(3)处填A+B。
为了填新A值(原来的B值),不能用B—A,因为变量B的内容已经改变为(原A)+(原B),而B-A正是((原A)+(原B))-(原A)=(原B),因此可以用B-A—A来实现新A的赋值。
这样,(4)处填B-A。
最后应是前n项和值的累加(比原来的S值增加了新B值),所以(5)处应填S+B。
填完各个空后,最好再用具体的数值来模拟流程图走几个循环检查所填的结果(这是防止逻辑上出错的好办法)。
试题二
【说明】
如果矩阵A中的元素AW]满足条件:
A[ij]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。
一个矩阵可能存在多个马鞍点,也可能不存在马鞍点。
下面的函数求解并输出一个矩阵中的所有马鞍点,最后返回该矩阵中马鞍点的个数。
【C函数】
阅读说明和C函数,填充函数中的空缺。
(1)M
(2)minElem=a[row][0]或其等价形式
(3)N
(4)a[i][k]或其等价形式
(5)M
本题考查C程序设计基本技术。
题目中涉及的主要知识点为二维数组和程序控制逻辑。
首先应认真阅读题目的说明部分,以了解函数代码的功能和大致的处理思路,然后理清代码的框架,明确各个变量(或数组元素)所起的作用,并以语句组分析各段代码的功能,从而完成空缺处的代码填充。
由于矩阵屮的马鞍点A[ij]是其所在行的最小元素,同时又是其所在列的最大元素,因此,对于矩阵中的每一行元素,先找出其最小者之值(用minElem表示),然后判断每一行的最小元素是否为其所在列的最大元素,若是则找到了一个马鞍点。
显然,空
(1)所在的表达式用于判断M行N列矩阵中的行数,因此应填入“M”。
空
(2)处应对变量minElem设置初始值。
根据注释,minElem用于表不第row行的最小元素值,其初值设为该行第0列的元素值,因此空
(2)处应填入“minElem=a[row][0]”。
空(3)所在的for语句用于找出一行中的最小元素,column应索引至每行的最后一个元素,因此空(3)处应填入“N”。
找出一行中的最小元素后,还要判断该元素是否为其所在列的最大元素。
由于可能存在多个马鞍点,因此,一行中的最小元素可能不唯一,所以需要重新扫描该行的所有元素,一旦其等于最小元素值,则有可能成为马鞍点。
实现该功能的代码如下:
由于k的取值范围为[0,N),且k作为元素a[r0w][k]的列下标(或第二下标),因此当“a[row][k]==minElem”时,即在第row行上找到了一个最小元素a[row][k],接下来就判断它是否为所在列的最大元素了,空(4)所在的语句“for(i=0;i 若空(4)处所在的表达式为真,则通过break跳出i作为循环控制的for语句。 显然,根据该表达式的作用,当元素a[i][k]大于minElem时(minElem与a[row][k]相等),说明a[row][k]虽然是其所在行的最小元素,但它不是其所在列(第k列)的最大元素,因此,可确定a[row][k]不是马鞍点。 当然,如果在第k列上没有找到比a[roW][k]更大的元素,则a[row][k]即是马鞍点。 结合空(4),可知空(5)应填入“M”。 试题三 【说明】 函数Insert_key(*root,key)的功能是将键值key插入到*root指向根结点的二叉查找 树中(二叉查找树为空时*root为空指针)。 若给定的二叉查找树中已经包含键值为key的结点,则不进行插入操作并返回0;否则申请新结点、存入key的值并将新结点加入树中,返回1。 提示: 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值; •左、右子树本身就是二叉查找树。 设二叉查找树采用二叉链表存储结构,链表结点类型定义如下: 【c函数】 阅读说明和C函数,填充函数中的空缺。 (1)p或p! =NULL (2)p->left (3)p->right (4)sizeof(BiTnode) (5)*root=s 本题考查c程序设计基本技术及指针的应用。 题目中涉及的考点主要有链表的査找、插入运算以及程序逻辑,分析程序时首先要明确各个变量所起的作用,并按照语句组分析各段代码的功能,从而完成空缺处的代码填充。 在二叉排序树上插入结点时,首先应通过查找运算确定结点的插入位置。 空 (1)〜(3)所在代码段即用来实现二叉排序树的查找运算。 根据说明,指针变量p的初始值设置为指向根结点(p=*r0ot),在通过指针访问链表中的结点时,应确保p的值为非空指针才行,因此空 (2)处应填入“p”或“p! =NULL”。 若待查找的键值key等于p指向结点的键值key—value,则査找成功且p正指向所找到的结点;若key (2)处应填入“p->left”;否则令p指向右子树结点,即空(3)处应填入“p->right”,从而根据待查找键值的大小进入了结点的子树。 空(4)所在代码生成待插入键值所需结点,根据链表结点类型的定义,此处应填入“sizeof(BiTnode)”。 空(5)所在语句处理将新结点作为二叉查找树的根结点的情况,根据参数root的作用,此处应填入“*root=s”。 试题四 【说明】 已知两个整数数组A和B中分别存放了长度为m和n的两个非递减有序序列,函数Adjustment(A,B,m,n)的功能是合并两个非递减序列,并将序列的前m个整数存入A中,其余元素依序存入B中。 合并过程如下: 从数组A的第一个元素开始处理。 用数组B的最小元素B[0]与数组A的当前元素比较,若A的元素较小,则继续考查A的下一个元素;否则,先将A的最大元素暂存入temp,然后移动A中的元素挪出空闲单元并将B[0]插入数组A,最后将暂存在temp中的数据插入数组B的适当位置(保持B的有序性)。 如此重复,直到A中所有元素都不大于B中所有元素为止。 【C函数】 阅读以下说明和C函数,填充函数中的空缺。 (1)A[m-1],或*(A+m-l),或其等价表示 (2)k>i,或其等价表示 (3)B[0],或*B (4)temp>B[k],或temp>*(B+k),或其等价表示 (5)temp 本题考查c程序设计基本技术。 题目中涉及的考点主要有一维数组及程序的运算逻辑,分析代码时首先要明确各个变量所起的作用,并按照语句组分析各段代码的功能,从而完成空缺处的代码。 根据题目中的说明和注释,此题的代码逻辑较为清楚。 显然,A的最大元素总是其最后一个元素,因此,空 (1)处应填入 空 (2)所在语句从后往前移动A的元素,然后将来自B的最小元素插入A数组的适当位置,显然需要通过比较B[0]与A中的元素来查找插入位置。 对于B[0]与A中的元素的比较处理,其对应的语句如下: 该语句的作用是将i的值增加到A[i]>B[0]时为止,即B[0]是正好小于A[i]且最接近A[i]的元素时i的值。 因此,空 (2)处应填入“k>i”,使得其所在的for语句能完成将大于或等于B[0]的元素向后移动(A[k]=A[k-1]),接下来在空(3)处将元素B[0]的值放入A[i],即空(3)处应填入“B[0]”。 最后需要将备份在temp的数据插入数组B的适当位置。 由于原来保存在B[0]中的值已插入A中,因此B[0]目前是一个空闲单元,如果temp的值比B[1]、B[2]等元素都要大,则需要将B[1]、B[2]等元素的值依次前移,因此空(4)处应填入“temp>B[k]”。 完成元素的移动后,将暂存于temp中的元素放入B的适当位置,即空(5)处应填入“temp”。 试题五 【说明】 下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对,则输出其中的一对即可)。 程序运行时,先输入点的个数和一组互异的点的坐标,通过计算每对点之间的距离,从而确定出距离最近的点对。 例如,在图5-1所示的8个点中,点(1,1)与(2,0.5)是间距最近的点对。 【C++代码】 阅读说明和Java程序,填充程序中的空缺。 (1)GPoint* (2)ComputeDistance* (3)numberOfPoints (4)distance(points[i],points[j]) (5)shortestDistance>tmpDistance 本题考查C++语言程序设计的能力,涉及类、对象、函数的定义和相关操作。 要求考生根据给出的案例和执行过程说明,认真阅读理清程序思路,然后完成题目。 先考察题目说明。 计算平面或空间中点之间的距离是目前很多应用中需要的,如GPS计算等。 本题目简化了点之间距离的要求,其主要任务是计算并寻找平面坐标系中给定点中最近的点对(若存在多对,则输出其中的一对即可)。 数轴上两点之间的距离等于相应两数差的绝对值,而平面坐标系中两点之间的距离等于相应两点的横坐标差和纵坐标差的平方和的算数平方根。 假设平面左边系中的两点P(x1,y1)和P(x2,y2)两者之间的距离 如题中图5-1所示的8个点中,点(1,1)和 (2,0.5)之间的距离为。 根据说明,点是一种类型,设计为类GPoint,点之间的距离设计为类ComputeDistance,整体主逻辑代码在main函数中实现。 类设计时,一般将属性设置为private,而对其的获取和更改等操作通过其中public方法进行。 因此,在GPoint设计时,将x和y坐标设计为private属性,将读取和设置x和y坐标的值设计为相应的get和set函数;在设计点之间的距离类ComputeDistance时,将两个GPoint类的对象作为distance函数的参数传递。 main函数中实现控制流程,在程序运行时,先输入点的个数,创建相应大小的数组,再输入相应个数的一组互异的点的坐标,将点保存在一个数组中。 C++中定义指向对象数组的指针的创建方式为: ClassName*varName=newClassName[numberOfArray]; 用new创建对象数据返回的是指针类型,此处需要ClassName*。 然后在对数组内存空间清零之后,输入相应个数的互异的点的坐标,存入点数组,然后通过计算每对点之间的距离,从而确定距离最近的点对。 其计算方式是: 预设定第一次参与运算的两个点之间的距离为最短距离,然后计算每一对点之间的距离,其计算过程为从第一个点开始依次和其后所有的点之间调用两点之间距离计算函数计算其他点之间距离,每次计算和设定的最短距离进行比较,如果比当前最短距离短,则更新最短距离并记录相应的点。 最后输出所记录的最短距离和相应的点。 因此,空 (1)需要指向GPoint类型的对象数组的指针,即为GPoint*;空 (2)需要计算两点之间距离的对象,用new创建,所以ComputeDistance*.空(3)处判定是否所有与当前点还没有比较过的点之间的距离都计算完成,因为当前点和在数组前面的点的比较在前面计算时已经计算过,所以从和后一个点计算直到数组的最后一个点计算完成,即j 试题六 【说明】 下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对,则输出其中的一对即可)。 程序运行时,先输入点的个数和一组互异的点的坐标,通过计算每对点之间的距离,从而确定出距离最近的点对。 例如,在图6-1所示的8个点中,点(1,1)与(2,0.5)是间距最近的点对。 【Java代码】 阅读说明和Java程序,填充程序中的空缺。 (1)GPoint[] (2)newGPoint() (3)points.length或numberOfPoints (4)getDistance(points[i],points[j]) (5)shortestDistance>tmpDistance 本题考查Java语言程序设计的能力,涉及类、对象、方法的定义和相关操作。 要求考生根据给出的案例和执行过程说明,认真阅读理清程序思路,然后完成题目。 先考察题目说明。 计算平面或空间中点之间的距离是目前很多应用中需要的,如GPS计算等。 本题目简化了点之间距离的要求,其主要任务是计算并寻找平面坐标系中给定点中最近的点对(若存在多对,则输出其中的一对即可)。 数轴上两点之间的距离等于相应两数差的绝对值,而平面坐标系中两点之间的距离等于相应两点的横坐标差和纵坐标差的平方和的算数平方根。 假设平面左边系中的两点P(x1,y1)和P(x2,y2),两者之间的距离 如题中图6-1所示的8个点中,点(1,1)和(2,0.5)之间的距离为 根据说明,点是一种类型,设计为类GPoint;寻找点之间的距离设计为类FindNearestPoints,整体主逻辑代码在其中的main方法中实现。 类设计时,一般将属性设置为private,而对其的获取和更改等操作通过其中public方法进行。 因此,在GPoint设计时,将x和y坐标设计为private属性,将读取和设置x和y坐标的值设计相应的get和set方法;在设计寻找距离最近的点的类FindNearestPoints时,其主要方法包括计算两个点之间的距离方法getDistance,将两个GPoint类的对象作为distance方法的参数传递。 FindNearestPoints中的main方法执行控制流程,在程序运行时,先输入点的个数,创建相应大小的数组,再输入相应个数的一组互异的点的坐标,将点保存在一个数points中。 Java中对象数组的创建方式为: ClassName[]varName=newClassName[numberOfArray]; 或者: ClassNamevarName[]=newClassName[numberOfArray]; 然后输入相应个数的互异的点的坐标,存入点数组,然后通过计算每对点之间的距离,从而确定出距离最近的点对。 其计算方式是: 预设定第一次参与运算的两个点之间的距离为最短距离,然后计算每一对点之间的距离,其计算过程为从第一个点开始依次和其后所有的点之间调用两点之间距离计算函数计算其他点之间距离,每次计算和设定的最短距离进行比较,如果比当前最短距离短,则更新最短距离并记录相应的点。 最后输出所记录的最短距离和相应的点。 因此空 (1)需要声明GPoint类型的对象数组,即为GPoint[];空 (2)需要对数组中的每个对象进行初始化,即newGPoint();空(3)处判定是否所有与当前点还没有比较过的点之间的距离都计算完成,因为当前点和在数组前面的点的比较在前面计算时已经计算过所以从和后一个点计算直到数组的最后一个点计算完成,即j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 下半年 程序员 考试 答案 下午