1、软件水平考试（初级）程序员下午（应用技术）模拟试卷 44及答案与解析 1 下面的流程图，用来完成求字符串 t在 s中最右边出现的位置。其思路是：做一个循环，以 s的每一位作为字符串的开头和 t比较，如果两字符串的首字母是相同的，则继续比下去，如果一直到 t的最后一个字符也相同，则说明在 s中找到了一个字符串 t；如果还没比较到 t的最后一个字符，就已经出现字符串不等的情况，则放弃此次比较，开始新一轮的比较。当在 s中找到一个字符串 t时，不应停止寻找 (因为要求的是求 t在 s中最右边出现位置 )，应先记录这个位置 pos，然后开始新一 轮的寻找，若还存在相同的字符串，则更新位置的记录，直到循
2、环结束，输出最近一次保存的位置。如果 s为空或不包含 t，则返回 -1。 注：返回值用 pos表示。 问题 将流程图的 (1) (5)处补充完整。 2 说明 1 函数 void convelt(chal *a,int n)是用递归方法将一个正整数 n按逆序存放到一个字符数组 a中，例如， n=123，在 a中的存放为 3、 2、 1。 C函数 1 void convert(char *a， int n) int i; if(i=n/10)!=0; convert( (1) ， i)； *a= (2) ; 说明 2 函数 int index(char *s， char *t)检查字符串 s中是否
3、包含字符串 t，若包含，则返回 t在 s中的开始位置 (下标值 )，否则返回 -1。 C函数 2 int index(char *s， char *t) int i， j=0； k=0； for(i=0； si!： 0； i+) ( for( (3) ； (tk!=0) if( (5) ) return(i)； return(-1)； 3 函数 Node *difference(A,B)用于求两个集合之差 C=A-B，即当且仅当 e是 A中的一个元素，但不是 B中的元素时， e是 C中的元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之间按递增排列。执行C=A-
4、B之后，表示集合 A和 B的链表不变，若结果集合 C非空，则表示其链表 根据元素之值按递增排列。函数 append()用于在链表中添加节点。 C函数 typedef struct node int element; struct node *link； Node； Node *A， *B， *C； Node *append(last， e) Node *last； int e； last- link=(Node *)malloc(sizeof(Node)； last- link- element=e； return(last- link)； Node *difference(A,B) Node
5、 *A， *B； Node *c， *last； C=last=(Node *)malloc(sizeof(Node)； while( (1) ) if(A- element B- element) last=append(last， A- element); A=A- link： else if( (2) ) A： A- link； B： B- link; elSe (3) ； while( (4) ) last=append(last， A- element)； A=A- link： (5) ; last=c； c=c- link; free(last)； return(c); 4 为参加
6、网球比赛的选手安排比赛日程。 设有 n(n=2k)位选手参加网球 循环赛，循环赛共进行 n-1天，每位选手要与其他n-1位选手赛一场，且每位选手每天赛一场，不轮空。试按此要求为比赛安排日程。 设 n位选手被顺序编号为 1,2,n 。比赛的日程表是一个 n行 n-1列的表， i行 j列的内容是第 i号选手第 j天的比赛对手。用分治法设计日程表，就是从其中一半选手 (2m-1位 )的比赛曰程，导出全体 (2m位 )选手的比赛日程。从只有 2位选手的比赛日程出发，反复这个过程，直到为 n位选手安排好比赛日程为止。 C函数 #include stdio.h #define MAXN 64 int aM
7、AxN+1MAXN； void main() int twoml， twom， il,j,m,k； printf(“指定 n(n=2的 k次幂 )位选手，清输入 k。 n“)； scanf(“%d“， a11=2; /*预设 2位选手的比赛日程 */ a21=1； m=1;twoml=1; while(m k) (1) ； twoml+=twoml; /*为 2m位选手安排比赛日程 */ (2) ； /*填日程表的左下角 */ for(il=twoml+l； il =twom； i1+) for(j=1； j =twoml-1; j+) ai1J=ai1-twomlj+twoml； (3) ；
8、 for(i1=2;i1 =twom； i1+)ai1twoml=ai1-1twom1+l; for(j=twoml+1； j twom； j+) for(i1=1； i1 twoml;i1+) ai1j=ai1+1j-1； (4) ; /*填日程表的右下角 */ for(j=twoml； j twom;j+) for(ii=i； i1 =twoml;i1+) (5) ； for(i1=1;i1 =twom;i1+) for(j=1； J twom;j+) printf(“%4d“， ai1J); printf(“n“); printf(“n“); 5 下而程序实现十进制向其他进制的转换。 C
9、+程序 #include“ioStream h“ #include“math h“ #include conio h typedef struct node int data； node *next； Node； class Transform public： void Trans(int d， int i)； /d为数字； i为进制 void print(); private： Node *top； ； void Transform:Trans(int d,int i) int m， n=0； Node *P； while(d 0) (1) ; d=d/i； p=new Node； if(!
10、n) P- data=m； (2) j (3) ; n+; else p- data=m； (4) ； (5) ； void Transform:print() Node *P; while(top!=NULL) p=top； if(P- data 9) cout data+55： else cout data； top=p- next； delete P; 6 下面程序实现十进制向其他进制的转换。 Java程序 C1ass Node int data； Node next； class Transform private Node top； publiC void print() Node
11、P； while(top !=null) P=top； if(P.data 9) System.out.print(char)(p.data+55)； else System.out.print(p.data); top=P.next; public void Trans(int d,int i)(/d为数字 ;i为进制 int m； (1) n=false; Node P; while(d 0) (2) ; d=d/i; P=flew Node()； if( (3) ) P.data=m； (4) ; top=P； n=true； else p.data=m； (5) ； toP=P； 软件
12、水平考试（初级）程序员下午（应用技术）模拟试卷 44答案与解析 1 【正确答案】 (1) pos=-1 (2) si!=0 (3) sj=tk (4) k 0 (5) pos=i； 2 【正确答案】 (1) A+1 (2) n%10+0 (3) j=i， k=0 (4) tk=sj (5) tk=0或 !tk 【试题解析】 函数 1采用递归方法将一个正整数 n按逆序存放到一个字符数组 a中，递归调用为 convert(a+1,i)，所以 (1)“a+1”。按逆序输出字符保存在数组 a中为 *a=n%10+0，即 (2)填 “n%10+ 0”。 函数 2检查字符串 s中是否含有字符串 t是在 f
13、or循环中实现的。空 (3)应填“j=i， k=0”。如果两个字符串中含有相同的字符，则字符串 s和字符串 t都指向下一个字符，循环继续，直到字符串 t结束。所以空 (4)应填 “tk=sj”，空 (5)应填“tk=0”或 “!tk”。 3 【正确答案】 (1) B- link (2) A- element=B- element (3) B=B- link (4) A link!=NULL (5) last- link=NULL 【试题解析】 本题用链表表示集合，通过比较链表的元素值判断集合的元素之间的关系。第一个 while循环的条件是链表 B指针不指向空，即空 (1)应填 “B-link”
14、。由于 A， B两集合都是按递增排列的，则 如果 A中的元素小于 B中的元素， A中元素直接放入集合 C中，集合 A指向其下一个元素；如果 A中的元素等于 B中的元素，集合 A， B分别指向下一个元素，即空 (21填 “A- element=B-element”；如果 A中的元素大于 B中的元素，集合 B指向其下一个元素，即空 (3)填 “B=B- link”。第二个循环的条件是链表 A指针不指向空时，将 A中元素直接加入到 C中，即空 (4)填 “A- link!=NULL”。将链表 C最后节点指针指向空，即空 (51填 “last- link=NULL”。 4 【正确答案】 (1) m+
15、(2) twom+=2*twom1 (3) A1twoml=twom1+1 (4) Atwom1j=a1j-1 (5) Aai1jj=i1 【试题解析】 分别有 2位、 4位、 8位选手参加比赛时的日程表。若 1 4号选手之间的比赛日程填在日程表的左上角 (4行 3列 )， 5 8号选手之间的比赛日程可填在日程表的左下角 (4行 3列 )，而左下角的内容可由左上角对应项加上数 4得到。至此剩下的右上角 (4行 4列 )是为编号小的 1 4号选手与编号大的 5 8号选手之间的 比赛安排日程。程序的思路是：由 2位选手的比赛日程得到 4位选手的比赛日程；依次得到 8位选手的比赛日程。 5 【正确答
16、案】 (1)m=d%i (2) top=p (3) top- next=NULL (4) p- next=top (5) top=p 【试题解析】 本题考查 C+编程，主要考查了链表的使用。 所有的问题只出在函数 Trans中，它的功能是完成将十进制数 d转换为任意进制i的数，并存在数组中。函数中首先定义了一个指向链表节点的指针，然后开始进行转换，进制转换应该是一个很常见的问 题，就是不断地求模运算，所以 (1)处应填入 “m=d%i” 。然后，我们要把求模的结果保存到链表节点中，并使链表首指针指向该节点，节点中指向下一个节点的指针设为空，所以 (2)处应填入 top=p， (3)处应填入 t
17、op- next=NULL。由于求模运算是从低位到高位逐位求出的，所以在进行完第二次求模运算后，应该将第二次运算的结果放到链表首位，所以 (4)处应填入 p- next=top， (5)处应填入 top=p。 6 【正确答案】 (1)boolean (2) m=d%i (3) ln (4) top- next=null (5) p-next=top 【试题解析】 本题考查 Java编程，主要考查了链表的使用。 所有的问题只出在函数 Trans中，它的功能是完成将十进制数 d转换为任意进制i的数，并存在数组中。变量 n被赋值为 false，说明 n是布尔型变量， Java中布尔型变量关键字为 boolean。故 (1)应填 “boolean”。函数中首先定义了一个指向链表节点的指针 (实为链栈 )，然后开始进行转换，进制转换应该是一个很常见的问题，就是不断地求模运算，所以 (2)处应填入 “m=d%i” 。然 后，我们要把求模的结果保存到链栈中。对于链栈，第一个节点比较特殊，需要特殊处理，从 if块中的语句 “n=tme”可知，此处正是处理第一个节点的特殊情况，故 (3)应填 “!n”， (4)处应填入 “top- next=null”。这里采用的链栈，所以 (5)处应填入 “p- next=top”。
