《程序员模拟试题下午试卷答案》由会员分享，可在线阅读，更多相关《程序员模拟试题下午试卷答案（9页珍藏版）》请在金锄头文库上搜索。
1、程序员考试模拟试题 2 下午试题一阅读下列说明和流程图，将应填入(n)处的语句写在答题纸的对应栏内。【说明】下列流程图用于从数组 K 中找出一切满足： K(I)+K(J)=M 的元素对(K(I)，K(J)(1I JN)。假定数组 K 中的N 个不同的整数已按从小到大的顺序排列， M 是给定的常数。【流程图】此流程图 1 中，比较K(I)+K(J)M最少执行次数约为 (5) 。图 1试题一【答案】(1)(2)I(4)J-1-J (5) N 2【解析】该算法的思路是：设置了两个变量 I 和 J，初始时分别指向数组 K 的第一个元素和最后一个元素。如果这两个元素之和等于 M 时，输出结果，并这两个指
2、针都向中间移动；如果小于 M，则将指针 I 向中间移动(因为数组 K 已按从小到大的顺序排列)；如果大于 M，则将指针 J 向中间移动(因为数组 K 已按从小到大的顺序排列)。当 IJ 时，说明所有的元素都搜索完毕，退出循环。根据上面的分析，(1)、(2) 空要求填写循环结束条件，显然，(1)空处应填写，(2) 空处应填写I。同样的道理，(4)空处应填写J-1-J。比较K(I)+K(J)：M最少执行次数发生在第 1 元素与第 N 个元素之和等于 M、第 2 元素与第 N-1 个元素之和等于 M、，这样每次比较，两种指针都向中间移动，因此最小执行次数约为N-2。试题二阅读下列函数说明和 C 代码
3、，将应填入 (n)处的字句写在答题纸的对应栏内。【说明】函数 print(BinTreeNode*t；DateType x)的功能是在二叉树中查找值为 x 的结点，并打印该结点所有祖先结点。在此算法中，假设值为 x 的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈 ST 保存结点指针 ptr 以及标志 tag，Top 是栈顶指针。【函数】void print(BinTreeNode*t；DateType x)stack ST；int i，top；top=0；置空栈while(t!=NULL t-data!=xtop!=0)while(t!=NULL t-
4、data!=x)寻找值为 x 的结点(1) ；STtop ptr=t；STtop tag=0；(2) ；if(t!=Null t-data=x)找到值为 x 的结点for(i=1； (3) ；i)printf(d，STtop ptr-data)；elsewhile( (4) )top-；if(top0)STtop tag=1；(5) ；试题二【答案】(1)top(2)t=t-leftChild(3)i=top(4)top0 STtop tag=1(5)t=STtop ptr-rightChild【解析】这个程序是一个典型二叉树后序遍历非递归算法的应用。算法的实现思路是：先扫描根结点的所有左结点
5、并入栈；当找到一个结点的值为 x，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点；然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过；如果不是，则对栈顶结点的右子树进行后序遍历，此时应把栈顶结点的右子树的相结点放入栈中。再重复上述过程，直至遍历过树中所有结点。(1)、(2)空年在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时 top=0，因此在入栈时，先将栈顶指针加 1，因此(1)空处应填写top或其等价形式，(2)空是取当前结点的左子树的根结点，因此应填写t=t-leftChild。(3)空所在循环是处理
6、找到值为 x 的结点，那么该结点的所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，(3)空处应填写i=top。(4)空所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，这里要填写判断条件。tag=0 表示左子树，tag=1 表示右子树，因此，(4)空处应填写top0&STtop tag=1。(5)空所在语句块是处理栈顶元素的右子树没有被后序遍历情况，则将右子树入栈，因此(5) 空处应填写t=STtop ptr-rightChild 。 试题三阅读下列函数说明和 C 函数，将应填入 (n)处的字句写在答题纸的对应栏内。
7、【说明】函数 DelA_InsB(LinkedList La，LinkedList Lb，int key1，int key2，int len)的功能是：将线性表 A 中关键码为key1 的结点开始的 len 个结点，按原顺序移至线性表 B 中关键码为 key2 的结点之前，若移动成功，则返回 0；否则返回-1。线性表的存储结构为带头结点的单链表， La 为表 A 的头指针，Lb 为表 B 的头指针。单链表结点的类型定义为typedef struct node int key；struct node *next；*LinkedList；【函数】int DelA_InsB(LinkedList L
8、a，LinkdeList Lb，int key1，int key2，int len)LinkedList p，q，s ，prep， pres；int k；if(!La-next|!Lb-next|len=0)return-1；p=La-next；prep=La；while(p & & p- key != key1)/*查找表 A 中键值为 key1 的结点*/prep=p； p=p-next；if(!p)return -1；/*表 A 中不存在键值为 key1 的结点*/q=p；k=1；while(q & (1) )/*在表 A 中找出待删除的 len 个结点*/(2) ；k+；if(!q)r
9、eturn -1；/*表 A 中不存在要被删除的 len 个结点*/s=Lb-next； (3) ；while(s & s- key !=key2)/*查找表 B 中键值为 key2 的结点*/pres=s；s=s- next；if(!s)return -1；/*表 B 中不存在键值为 key2 的结点*/(4) =q-next；/*将表 A 中的 len 个结点删除*/q-next= (5) ；pres-next=p；/*将 len 个结点移至表 B*/return 0；试题三【答案】(1)knext 或 q=(*q).next(3)pres=Lb(4)prep-next 或 (*prep)
10、.next(5)s 或 pres-next 或(*pres).next【解析】(1)此处 while 循环应当循环至 k 等于 len 结束，所以应填入 knext 或 q=(*q).next。(3)此处语句为指针 pres 赋初值，使他指向 s 的上一结点。(4)修改指针 prep，使 prep 指向 q 的下一结点。(5)此处语句为修改指针 q，q 指向 s 或者 pres 的下一结点，达到将 A 中的 len 个结点删除的目的。试题四阅读以下说明和 C 代码，将应填入 (n)处的字句写在答题纸的对应栏内。【说明】将一正整数序列K1，K2，K9重新排列成一个新的序列，新序列中，比 K1 小
11、的数都在 K1 的前面(左面)，比 K1 大的数都在 K1 的后面(右面) ，最后调用 writeDat()函数的新序列输出到文件 outdat 中。在程序中已给出了 10 个序列，每个序列有 9 个正整数，并存入数组 a10 9中，分别求出这 10 个新序列。例：序列 6，8，9，1，2， 5，4，7，3经重排后成为3，4，5，2，1，6，8，9，7【函数】#include#includevoid jsValue(int a10 9)int i，j，k，n，temp；int b9 ；for(i=0； iai j) (2) =ai j ；if(temp=ai j) (3) =temp；for(
12、j=0； j#define Max 100最多元素个数templateclass SampleT AMax：存放有序数序int n：实际元素个数publicSample()默认构造函数Sample(T a ，int i)；初始化构造函数int seek(T c)；void disp()for(int i=0；iSample：Sample(T a ，int i)n=i；for(intj=0；jint Sample：seek(T c)int low=0，high=n-1，mid；while( (2) )mid=(low+high)2；if( (3) )return mid；else if( (4)
13、 )low=mid+l；else(5) ；return-1；void main()char a =acegkmpwxz；Samples(a，1。)；cout模板类。(1) 空所在处为构造函数的声明，将参数中的值赋值到类的成员变量中，所以(1)空应填入A j =a j。成员函数 seek()采用二分法查找元素下标，变量 low 和 high 分别表示查找区间的下标，如果查询到目标，则返回相应的下标，若没有查询到，则其结束的条件即(2)空的内容为 low=high。根据二分法的原理，当中间的元素恰好等于目标元素时，则返回其下标，所以(3)空应填入 Amid =c；若中间的元素小于目标元素时，则mi
14、d+1 作为新的查找区间的起始下标，所以(4)空应填入Amid c；否则 mid-1 作为新的查找区间的结束下标，所以(5)空应填入high=mid-1。试题七阅读以下说明和 Java 代码，将解答写入答题纸的对应栏内。【说明】下面的程序的功能是利用实现 Runnable 接口的方法来创建线程，并利用它来执行响应的一些操作。最后使得m 的执行结果:100，如图 3。注意：请勿改动 main()主方法和其他已有的语句内容，仅在下划线处填入适当的语句。class ClassName (1) Runnableint n；(2) tryThreaDsleep(2000)；n=100；catch( (3
15、) e)public static void main(Stringargs)tryClassName a=new ClassName()；(4) thread1. (5) ()；thread1.join()；int m=An；System.out.println(m=+m)；catch( (3) e)试题七【答案】 (1)implements(2)ClassName(3)Exception(4)ClassName thread1 = new ClassName()；(5)start【解析】此处为实现接口关键字。此处应填类 ClassName 的构造函数名，即 ClassName。此处应填异常类名 Exception。定义并初始化对象thread1。线程的启动函数。试题八阅读以下应用说明及 Visual Basic 部分程序代码，将应填入(n) 处的字句写在答题纸的对应栏内。【说明】该应用程序是用来修改文本框中的字体属性，其运行窗口如图 4 所示。窗口由 1 个标签(Labell)、1 个文本框(txtPassage)和 4 个选择框
