1、软件水平考试（初级）程序员下午（应用技术）模拟试卷 34及答案与解析 1 阅读下列算法说明和算法，将应填入 (n)处的语句写在对应栏内。 1. 【说明】 实现连通图 G的深度优先遍历 (从顶点 v出发 )的非递归过程。 【算法】 第一步：首先访问连通图 G的指定起始顶点 v； 第二步：从 V出发，访问一个与 v(1)p，再从顶点 P出发，访问与 p(2)顶点 q，然后从 q出发，重复上述过程，直到找不到存在 (3)的邻接顶点为止。 第三步：回退到尚有 (4)顶点，从该顶点出发，重复第二、三步，直到所 有被访问过的顶点的邻接点都已被访问为止。 因此，在这个算法中应设一个栈保存被 (5)的顶点，以
2、便回溯查找被访问过顶点的未被访问过的邻接点。 2 阅读以下函数说明和 C语言函数，将应填入 (n)处的字句写在对应栏内。 【说明】 实现矩阵 (3行 3列 )的转置 (即行列互换 )。 例如，输入下面的矩阵： 100 200 300 400 500 600 700 800 900 程序输出： 100 400 700 200 500 800 300 600 900 【函数】 int fun(int array33) int i,j,t; for(i=0;(1);i+) for(j=0;(2);j+) t=arrayij; (3); (4); main() int i,j; int array33
3、=100,200,300,400,500,600,700,800,900; clrscr(); for (i=0;i 3;i+) for(j=0;j 3;j+) printf(“%7d“,arrayij); printf(“n“); fun(5); printf(“Converted array:n“); for(i=0;i 3;i+) for(j=0;j 3;j+) printf(“%7d“,arrayij); printf(“n“); 3 阅读以下函数说明和 C语言函数，将应填入 (n)处的字句写在对应栏内。 【说明】 对 20个数进行排序，可以利用选择法，即从后 19个比较过程中，选择一
4、个最小的与第 一个元素交换，依次类推，即用第二个元素与后 18个进行比较，并进行交换。 【函数】 #define N 20 main() int i,j,min,tem,aN; printf(“please input twenty num:n“); for(i=0;i N;i) printf(“a%d=“,i); scanf(“%d“, printf(“n“); for(i=0;i N;i) printf(“,“,ai); printf(“n“); for(i=0;(1);i) min=(2); for(j=(3);j N;j+) if(4) min=j; tem=ai; (5); amin
5、=tem; printf(“After sorted n“); for(i=0;i N;i+) printf(“,“,ai); 4 阅读以下函数说明和 C语言函数，将应填入 (n)处的字句写在对应栏内。 【说明】 已知某数列的前两项为 2和 3，其后继项根据当前最后两项的乘积按下列规则生成： (1)若乘积为一位数，则该乘积即为数列的后继项； (2)若乘积为二位数，则 该乘积的十位数和个位数依次作为数列的两个后继项。 本程序输出该数列的前 n项以及它们的和。其中，函数 sum(n,pa)返回数列的前 n项之和，并将生成的前 n项存放于首指针为 pa的数组中。程序中规定输入的 n值必须大于 2并且
6、不超过给定的常数值 MAXNUM。 例如：若输入 n值为 10，则程序输出如下内容： sum(10)=44 2 3 6 1 8 8 6 4 2 4 #include stdio.h #define MAXNUM 100 int sum(int n,int *pa) int count,total,temp; *pa=2; (1)=3; total=5; count=2; while(count+ n) temp+=*(pa-1)*pa; if(temp 10) total+=temp; *(+pa)=temp; else (2)=temp/10; total+=*pa; if(count n)
7、 count+;pa+; (3)=temp%10; total+=*pa; (4); main() int n,*p,*q,numMAXNUM; do printf(“Input N=?(2 N %d):“,MAXNUM+1); scanf(“%d“, while(5); printf(“nsum(%d)=%dn“,n,sum(n,num); for(p=num,q= (6) ;p q;p+)printf(“%4d“,*p); printf(“n“); 5 阅读以下说明，以及用 C+在开发过程中所编写的程序代码，将应填入 (n)处的字句写在对应栏内。 【说明】 在下面程序横线处填上适当的字句，
8、 3个 (2)空填的是一样的。使其输出结果为： x=5 x=6 y=7 x=8 z=9 【程序】 #include iostream.h class X1 int x; (1); X1(int xx=0)x=xx; (2) void Output() cout “x=“ x end; ; (3) Y1:public X1 int y; public: Y1(int xx=0,int yy=0);X1(xx)y=yy; (2) void Output() (4) Output(); cout “y=“ y endl; ; class Z1:public X1 int z: (5); Z1(int
9、 xx=0,int zz=0):X1(xx)(z=zz; (2) void Output() X1 Output(); cout “z=“ z endl; ; void main() X1 a(5);Y1 b(6,7);Z1 c(8,9); X1*p3= For(int i=0;i 3;i+) pi- Output();cout endl; 6 阅读以下说明， Java代码将应填入 (n)处的字句写在对应栏内。 【说明】 链表和栈对象的共同特征是：在数据上执行的操作与在每个对象中实体存储的基本类型无关。例如，一个栈存储实体后，只要保证最后存储的项最先用，最先存储的项最后用，则栈的操作可以从链表
10、的操作中派生得到。程序 6-1实现了链表的操作，程序 6-2实现了栈操作。 import java.io.*; class Node /定义结点 private String m_content; private Node m_next; Node(String str) m_content=str; m_next=null; Node(String str,Node next) m_content=str; m_next=next; String getData() /获取结点数据域 return m_content; void setNext(Node next /设置下一个结点值 m_n
11、ext=next; Node getNext() /返回下一个结点 return m_next; ) 【程序 6-1】 class List Node Head; List() Head=null; void insert(String str) /将数据 str的结点插入在整个链表前面 if(Head=null) Head=new Node(str); else (1) void append(String str) /将数据 str的结点插入在整个链表尾部 Node tempnode=Head; it(tempnode=null) Heed=new Node(str); else whit
12、e(tempnode.getNext()!=null) (2) (3) String get() /移出链表第一个结点，并返回该结点的数据域 Srting temp=new String(); if(Head=null) System.out.println(“Errow! from empty list!“) System.exit(0); else temp=Head.getData(); (4) return temp; 【程序 6-2】 class Stack extends List void push(String str) /进栈 (5) String pop() /出栈 ret
13、urn get(); 软件水平考试（初级）程序员下午（应用技术）模拟试卷 34答案与解析 1 【正确答案】 (1)邻接的顶点 (2)邻接的且未被访问的 (3)未访问过 (4)未被访问过的邻接点的 (5)访问过 【试题解析】 本题考查连通图的深度优先遍历算法的非递归过程。 在做题前，我们首先来了解一下图的遍历。和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。 连通图的深度优先遍历可定义如下：首先访问出发点 v，并将其标记为已访问过；然后依次从 v出发搜索 v的每个邻接点 w。若 w未曾访问过，则以 w为新的出发点继续进行深度优先遍历，直至图中所有
14、和源点 v有路径相通的顶点 (亦称为从源点可达的顶点 )均已被访问为止。其关键是每次遍历都是往下直到最后再往回搜索，找到还未被访问过的邻接点的顶点，然后从该顶点出发，对它及下面的顶点进行深度 优先遍历。下面来具体分析其算法。 第 (1)空在第二步中，在访问起始顶点 v后应该访问的结点，那么这个结点肯定是与起始顶点 v邻接的顶点，因此此空答案为 “邻接的顶点 ”。 第 (2)空是在访问 p顶点后应该访问的顶点，接下来应该也是访问与 p顶点邻接的顶点，但这个时候 p顶点的邻接顶点中有已经被访问过了的顶点，因此在访问前还需判断此顶点是否被访问过了，所以此空答案为 “邻接的且未被访问的 ”。 第 (3
15、)空也在第二步中，结合前后的内容，可以知道此空是要判断是否还可以找到与当前访问顶点邻接而未被访问的顶点，根据上 面分析，如果找不到，才往回搜索，因此此空答案为 “未访问过 ”。 第 (4)空是回退过程中要注意的地方，一般回退到还未被访问过的邻接点的顶点，接着访问这个未被访问过的邻接点。因此此空答案为 “未被访问过的邻接点的 ”。 第 (5)空是存放在栈中的内容，栈具有后进先出的特点，根据上面对深度优先遍历的分析可以知道，在回退的过程中需要用到被访问过的顶点，而且回退的过程是按遍历的顶点的顺序回退的，越后被访问的顶点越先被回退，因此此空答案是“访问过 ”。 2 【正确答案】 (1)i 3 (2)
16、j i (3)arrayij=arrayji (4)arrayji=t (5)array 【试题解析】 本题考查用 C语言实现矩阵的转置。 题目要求程序实现矩阵 (3行 3列 )的转置，其关键是将当前行列对应的元素与其对应的列行元素互换。题目中给出了具体的矩阵元素和结构，下面来具体分析程序。 第 (1)空很明显是循环语句的判断条件，是上界条件，这个二重循环的作用是进行数组中元素的互换，而从题目中给出的已知条件可以判断出，这个数组是一个三维的数组，而在程序中下标是从 0开始的，那么其 上界应该是不大于 3，因此这个空的答案分别是 i 3。 第 (2)空也是循环的判断上界，在上面我们已经分析出了这
17、个二重循环的作用是进行数组中元素的互换，而元素互换的过程是将当前行列对应的元素与其对应的列行元素互换，元素的下标都要在能互换的下标范围内，那么第二重循环的上界应该是第一重循环变量的当前值，因此此空答案为 j i。 第 (3)空在这个二重循环体中，从程序中不难发现，用一个临时变量 f来存放要置换的值，接下来就是此空，那么应该是将其中一个值放到其转置后的位置，再结合上面分析，可以得出此空答案为 arrayij=arrayji。 第 (4)空是紧接着上一空而来的，在上面的程序中已经将当前位置中的值保存到了临时变量 t中，且把其对应的转置位置的元素值放到了这个位置，那么接下来应该是将临时变量中的值放到
18、转置位置，因此此空答案为 arrayji=t。 第 (5)空很明显是函数的参数，这个函数就是功能函数 fun()，用来实现矩阵的转置，根据程序中函数的定义，它只有一个参数，这个参数是要被处理的数组。在主函数中，需要被处理的数组是 array，这里我们需要注意在数组作为函数的形参时，一般是通 过传递其地址来实现参数传递的，因此此空答案为 array。 3 【正确答案】 (1)i N-1 (2)i (3)i+1 (4)amin aj (5)ai=amin 【试题解析】 本题考查 C语言中的排序算法。 题目要求对 20个数进行排序，并告诉我们利用选择法，即从后 19个比较过程中，选择一个最小的与第一
19、个元素交换，依此类推，即用第二个元素与后 18个进行比较，并进行交换。它的每次排序的过程都是从元素中选取最小的一个排在当前排序序列的最前面，需要注意的是，程序中用数 组的下标来协助完成排序。下面来具体分析程序。 第 (1)空是循环的判断条件，而这个循环是一个二重循环的第一重，从程序中不难分析出，这个二重循环的作用是完成排序的过程，且这个排序的元素存放在数组 a中，元素的个数为 N个，而数组的下标是从 0开始的，根据题目的意思，最多到最后一个元素的时候就不需要再排序了，它就是最大的元素。那么循环的上界应该是不大于 N-1，因此此空答案为 i N-1。 第 (2)空是给变量 min赋一个值，根据题
20、目要求，这个变量中存放的是当前排序序列中最小的元素的数组下标，而在开始排序之前，这 里存放的是当前排序序列的第一个元素，每次参加排序的序列的第一个元素下标就是 i，因此此空答案为i。 第 (3)空是给第二重循环的循环变量 j赋一个初值，这重循环的作用是从当前位置后面的元素中选一个最小的元素排在当前位置的后一个位置，那么循环应该是从当前位置的后一个位置开始，因此此空答案为 i+1。 第 (4)空是条件判断语句的判断条件，很明显，这个条件判断语句的作用是判断当前数组 min中的值 (最小元素 )与当前位置元素的大小关系，如果小则继续与下一个元素比较，如果大则把数组中当前位置的元素的下标存放到 mi
21、n中，从 min=j可以看出，应该是大，因此此空答案为 amin aj。 第 (5)空也在循环中，从程序中不难看出是用来调换序列中元素的位置，上面的程序是将 ai的值存放到临时变量 tem中， ai中存放的元素应该是参加排序的序列中最小的元素值，而数组中下标 min指明了序列中最小元素在数组中的位置，此空的任务就是将最小的元素放到数组的 i位置，因此此空答案为 ai=amin。 4 【正确答案】 (1)*+pa (2)*+pa (3)*pa (4)return(total) (5)n 3|n MAXNUM (6)p+n 【试题解析】 本题考查用 C语言对数列的操作。 通过程序说明部分的描述及实
22、例，可以清楚地了解程序功能。由于真正的处理函数是 sum()，而主函数只是输入数据，调用 sum()，以及输出结果，所以我们可以先分析 sum()。 int sum(im n,int*pa) int cotmt,total,temp; *pa=2; (1)=3; 程序说明部分已经提到数列的前两个元素为 2和 3。 *pa存储了第一个元素 “2”，很显然 “3”应存在 *(pa+1)中。又因为后面有语句 “temp+=*(pa-1)*pa;”，这说明在求乘积时， pa是指向要运算数的后者，例如要求 2*3， pa指向 3，用 *(pa-1)表示2。所以 (1)空应填 *(+pa)，而不能用 *(
23、pa+1)。 total=5;count=2; while(count+ n) temp+=*(pa-1)*pa; 这里是求两数列元素的乘积。 if(temp 10) total+=temp; *(+pa)=temp; else (2)=temp/10; 对应程序说明，当乘积小于 10时，直接把乘积作为数列的后继项；当乘积大于等于 10时，把该乘积的十位数字和个位数字依次作为数列的两个后继项。这时应当把大于等于 10的数 (因为最大的数为 9*9=81，所以都为两位数 )分解为单个的数字， “temp/10”求出的是十位数字，所以存入当前数列元素的后继项，即 (2)空应填*(+pa)。 tot
24、al+=*pa; 统计当前数列和。 if(count n) 如果当前数列元素个数没有达到指定 值 n，则把乘积的个位数 (temp%10)作为数列的后继项；如果当前数列元素个数已经达到指定值 n，则可以退出循环，返回主函数了。 count+;pa+; (3)=temp%10; 由于前面已经有 “pa+”，所以 (3)空应填 *pa。 total+=*pa; (4); 又因为主函数有 “printf(“nsum(%d)=%dn“,n,sum(n,num,)； ”，说明函数 sum()返回了数列和。因此， (4)空应填 return(total)。 当分析完函数 sum()的功能后，我们再来看 m
25、ain()，就显得十分简单了。 do printf(“Input N=?(2 N %d):“,MAXNUM+1); scanf(“%d“, while(5); 上面是输入 n的值， n要保证是合法值才能继续下面的工作，所以当输入 n不合法时，应重新输入 n值。因此， (5)空应填 n 3|n MAXNUM。 printf(“nsum(%d)=%dn“,n,sum(n,num); for(p=num,q=(6);p q;p+)printf(“%4d“,*p); 此 for循环用于输出数列，循环终止条件是 “p q”，又因为 num是数列首指针且 n为数列长度，所以 (6)空应填 p+n。 5 【
26、正确答案】 (1)public (2)virtual (3)class (4)X1 (5)public 【试题解析】 本题考查了 C+类的定义、成员变量的声明、类继承以及虚函数的一些基本知识。 我们对比三个类的定义就可以发现 ，在类 x1和 z1的定义中缺少类的成员属性声明，而类一般将成员变量声明为公有的、私有的或受保护的三种类型中的一种，在类的定义中，我们一般将类的构造函数放在公有的属性下面，在题目中只能选择公有的属性了，因此，第 (1)空和第 (5)空中应该填 public。 对三个类的定义进行仔细观察后，我们同样可以发现，每个类中都定义了一个同名函数 Output()，而且在后两个类的函
27、数体中调用了函数 Output()，由此，我们应该想到虚函数。虚函数的作用是允许在派生类中重新定义与基类同名的函数，并且可以通过基类指针或引用来访 问基类和派生类中的同名函数。因此，第 (2)空应该填 virtual。 第 (3)空就简单了，考查类的定义，应该填类的标识符 class。 从程序中我们可以看到，类 Y1和 Z1都以公有的方式继承类 X1。从输出的结果来分析，类 Y1和 Z1都输出了两个数，但单从类 Z1的函数来看，只能输出一个变量的值 Z，因此，可以发现在类 Z1中应该和类 Y1一样，都调用了类 X1的函数 Output()，因此，第 (4)空的答案为 X1 。 6 【正确答案】
28、 (1)Head=new Node(str， Head); (2)tempnode=tempnode.getNext(); (3)tempnode.setNext(new Node(str,tempnode.getNext(); (4)Head=Head.getNext()； (5)insert(str); 【试题解析】 本题考查链表和栈的基本特征在 Java中的实现。 在对链表进行表头插入时，首先要判断该链表是否为空，如果为空，直接插入结点；如果非空，在插入结点时把该结点的指针域改成能指向下一个结点的地址。在队尾插入时，同样要判断该链表是否为空，如果为空，直接插入结点 ；如果非空，在插入结点
29、时把上一个结点的指针域改成能指向该结点的地址。 下面来具体分析代码，首先定义了一个结点类，类中有两个不同的构造函数和三个函数，分别用于获取结点数据域，设置下一个结点值和返回下一个结点值。第 (1)空是函数 insert()里面的代码，函数要实现的功能是将数据 str的结点插入在整个链表前面。结合整个函数看，此空处要实现的功能是在非空链表的前面插入结点，需要指针域来存放下一个结点的地址，而下一个结点的地址就是 Head，因此，此处应该填 Head=new Node(str,Head)。 第 (2)空和第 (3)空一起考虑，它们都是函数 append()里面的内容。函数要实现的功能是将数据 str
30、的结点插入在整个链表尾部。这两空要实现的功能是在非空链表的尾部插入结点。这需要调用返回下一个结点值函数和设置下一个结点值函数，因此，第 (2)空和第 (3)空的答案分别为 tempnode=tempnode.getNext()和tempnode.setNext(new Node(str,tempnode.getNext()。 第 (4)空是函数 get()里面的内容，此函数的功能是移出链表第一个结点， 并返回该结点的数据域，从整个函数来看，此空处的功能是让链表的地址 Head指向下一个结点。因此，答案为 Head=Head.getNext()。 第 (5)空就比较简单了，要实现的功能就是让数据进栈，而进栈操作是在栈顶进行插入的，因此，只要调用函数 insert()即可，其参数是 str，此空答案为insert(str)。
