1、初级程序员下午试题-28 及答案解析(总分:90.00,做题时间:90 分钟)一、试题一(总题数:1,分数:15.00)说明信息处理过程中经常需要将图片或汉字点阵作旋转处理。一个矩阵以顺时针方向旋转 90后可以形成另一个矩阵,如下图所示。流程图 a描述了对 n*n矩阵的某种处理。流程图 b是将矩阵 A顺时针旋转 90形成矩阵 B的具体算法。(分数:15.00)(1).问题 1请写出以下 3*3单位矩阵沿顺时针方向旋转 90后所形成的矩阵。(分数:5.00)_(2).问题 2如果以下 3*3矩阵沿顺时针方向旋转 90后所形成的矩阵就是原来的矩阵。(分数:5.00)_(3).问题 3在上述流程图
2、a和 b所示的算法中:(1) 矩阵 A第 i行第 j列的元素 A(i,j)被复制到矩阵 B中的哪个位置?(2) A(i,j)后来又被复制到矩阵 C中的哪个位置?(3) 填补流程图 b中的空缺。 (分数:5.00)_二、试题二(总题数:1,分数:15.00)1.说明 1函数 int factors(int n)的功能是判断整数 n(n=2)是否为完全数。如果 n是完全数,则函数返回 0,否则返回-1。所谓“完全数”是指整数 n的所有因子(不包括 n)之和等于 n自身。例如,28 的因子为1,2,4,7,14,而 28=1+2+4+7+14,因此 28是“完全数”。C函数 1int factors
3、(int n)int i,s;for(i=1,s=0;i=n/2;i+)if(n%i=0) (1) ;if( (2) )return 0;rerurn-1;说明 2函数 int maxint(int a,int k)的功能是用递归方法求指定数组中前 k个元素的最大值,并作为函数值返回。C函数 2int maxint(int a,int k)int t;if( (3) ) return (4) ;t=maxint(a+1, (5) );return(a0t)?a0:t;(分数:15.00)_三、试题三(总题数:1,分数:15.00)2.说明已知一棵二叉树用二叉链表存储,t 指向根节点,P 指向树
4、中任一节点。下列算法为输出从 t到 P之问路径上的节点。C程序#define MaxSize 1000typedef struct node TelemType data ;struct node *ichiid,*rchiid;BiNode,*BiTree;void Path(BiTree t,BiNode *P)BiTree *stackMaxsize,*stacklMaxsize,*q;int tagMaxsize,top=0,topl;q=t;/*通过先序遍历发现 P*/dowhile(q!=NULL q!=p)/*扫描左孩子,_日相应的节点不为 P*/(1) ;stacktop=q;
5、tagtop=0;(2) ;if(top0)if(stacktop=P) break; /*找到 P,栈底到栈顶为 t到 P*/if(tagtop=1)top-;else q=stacktop;q=q-rchiid;tagtop=1;(3) ;top-;topl=0;while(top0) q=stacktop; /*反向打印准备*/topl+;(4) ;top-;while( (5) ) /*打印栈的内容*/q=stackltopljprintf(q-data);topl-;(分数:15.00)填空项 1:_四、试题四(总题数:1,分数:15.00)3.说明设一个环上有编号为 0n-1 的
6、n粒颜色不尽相同的珠子(每粒珠子颜色用字母表示,n 粒珠子的颜色由输入的字符串表示)。从环上的某两粒珠子问剪开,则环上珠子形成一个序列然后按以下规则从序列中取走珠子:首先从序列左端取走所有连续的同色珠子;然后从序列右端在剩下的珠子中取走所有连续的同色珠子,两者之和为该剪开处可取走珠子的粒数。在不同位置剪开,能取走的珠子也不尽相同。本程序所求的是在环上哪个位置剪开,按上述规则可取走的珠子粒数最多。程序中用数组存储字符串。例如,10 粒珠子颜色对应字符串为 aaabbbadcc,在 0号珠子前剪开,序列为 aaabbbadcc,从左端取走 3粒a色珠子,从右端取走 2粒 c色珠子,共取走 5粒珠子
7、。若在 3号珠子前剪开,即 bbbadccaaa,共取走 6粒珠子。C函数int count(char *s,int start,int end)int i,c=0,color:sstart,step=(startend)?-1:1;for(i=Start;si=color;i+=step)if(step0 return c;void main()char t,s120;int i,k,c,len,maxc,cut=0;printf(“请输入环上代表不同颜色珠子字符串:“);scanf(“%s”,s);len=strlen(s);for(i=maxc=0; ilen;i+)( /*尝试不同的剪
8、开方式*/c=count(s,0,len-1);if(clen) c+=count( (3) );if(cmaxc) cut=i;maxc=c;)/*数组 s的元素循环向左移动一个位置*/t=s0;for(j=1;jlen;j+) (4) ;(5) ;printf(“在第%d 号珠子前面剪开,可以取走%d 个珠子n“,cut,maxc);(分数:15.00)填空项 1:_五、试题五(总题数:1,分数:15.00)4.说明下而程序实现十进制向其他进制的转换。C+程序#include“ioStreamh“#include“mathh“#include coniohtypedef struct no
9、deint data;node *next;Node;class Transformpublic: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(d0)(1) ;d=d/i;p=new Node;if(!n)P-data=m;(2) j(3) ;n+;elsep-data=m;(4) ;(5) ;void Transform:print()Node *P;while(top!=NULL)p=to
10、p;if(P-data9)coutdata+55:elsecoutdata;top=p-next;delete P;(分数:15.00)填空项 1:_六、试题六(总题数:1,分数:15.00)5.说明下面程序实现十进制向其他进制的转换。Java程序C1ass Nodeint data;Node next;class Transformprivate Node top;publiC void print()Node P;while(top !=null)P=top;if(P.data9)System.out.print(char)(p.data+55);elseSystem.out.print(
11、p.data);top=P.next;public void Trans(int d,int i)(/d为数字;i 为进制int m;(1) n=false;Node P;while(d0)(2) ;d=d/i;P=flew Node();if( (3) )P.data=m;(4) ;top=P;n=true;elsep.data=m;(5) ;toP=P;(分数:15.00)填空项 1:_初级程序员下午试题-28 答案解析(总分:90.00,做题时间:90 分钟)一、试题一(总题数:1,分数:15.00)说明信息处理过程中经常需要将图片或汉字点阵作旋转处理。一个矩阵以顺时针方向旋转 90后可
12、以形成另一个矩阵,如下图所示。流程图 a描述了对 n*n矩阵的某种处理。流程图 b是将矩阵 A顺时针旋转 90形成矩阵 B的具体算法。(分数:15.00)(1).问题 1请写出以下 3*3单位矩阵沿顺时针方向旋转 90后所形成的矩阵。(分数:5.00)_正确答案:(*)解析:(2).问题 2如果以下 3*3矩阵沿顺时针方向旋转 90后所形成的矩阵就是原来的矩阵。(分数:5.00)_正确答案:(*)解析:(3).问题 3在上述流程图 a和 b所示的算法中:(1) 矩阵 A第 i行第 j列的元素 A(i,j)被复制到矩阵 B中的哪个位置?(2) A(i,j)后来又被复制到矩阵 C中的哪个位置?(3
13、) 填补流程图 b中的空缺。 (分数:5.00)_正确答案:(B(j,n-i+I) (2) C(n-i+1,n-j+1) (3) A(n-j+1,i)解析:解析 对于问题 1很容易得到矩阵沿顺时针方向旋转 90后所形成的矩阵为*对于问题 2根据顺时针方向旋转 90保持矩阵不变,可以逐步推断出一些元素的值:*对于问题 3根据上述流程图中的算法,不难发现,矩阵 A第 i行第 i列的元素 A(i,j)被复制到 B的第n-i+1列第 j行,即 B(j,n-i+1)。A(i,j)后来又被复制到矩阵 C中的第 n-i+1行第 n-j+1列,即 C(n-i+1,n-j+1)。流程图 b中,循环开始后,应该是
14、将 A(n-j+1,i)赋给 B(i,j)。二、试题二(总题数:1,分数:15.00)1.说明 1函数 int factors(int n)的功能是判断整数 n(n=2)是否为完全数。如果 n是完全数,则函数返回 0,否则返回-1。所谓“完全数”是指整数 n的所有因子(不包括 n)之和等于 n自身。例如,28 的因子为1,2,4,7,14,而 28=1+2+4+7+14,因此 28是“完全数”。C函数 1int factors(int n)int i,s;for(i=1,s=0;i=n/2;i+)if(n%i=0) (1) ;if( (2) )return 0;rerurn-1;说明 2函数
15、int maxint(int a,int k)的功能是用递归方法求指定数组中前 k个元素的最大值,并作为函数值返回。C函数 2int maxint(int a,int k)int t;if( (3) ) return (4) ;t=maxint(a+1, (5) );return(a0t)?a0:t;(分数:15.00)_正确答案:(s+=i (2) n=s (3) k=1 或 k-1=0 (4) a0或*a 或 ak-1 (5) k-1或-k)解析:解析 对于函数 1,是判断整数 n(n=2)是否为完全数。首先用 for循环求该整数的所有因子之和,所以(1)填“s+=i”。若其和等于整数本身
16、,则为完全数,返回值为 0,则(2)填“n=s”;否则返回值为-1。对于函数 2,是用递归方法找出数组中的最大元素。该递归的出口条件为 k=1,即(3)填“k=1”或“k-1=0”;只有一个数时,它本身就是最大的,(4)填“a0”或“*a”或“ak-1”;对于多个数的情况,在剩下的 k-1个元素中找到最大的,并与首元素值比较,返回最大的一个,所以(5)填“k-1”或“-k”。三、试题三(总题数:1,分数:15.00)2.说明已知一棵二叉树用二叉链表存储,t 指向根节点,P 指向树中任一节点。下列算法为输出从 t到 P之问路径上的节点。C程序#define MaxSize 1000typedef
17、 struct node TelemType data ;struct node *ichiid,*rchiid;BiNode,*BiTree;void Path(BiTree t,BiNode *P)BiTree *stackMaxsize,*stacklMaxsize,*q;int tagMaxsize,top=0,topl;q=t;/*通过先序遍历发现 P*/dowhile(q!=NULL q!=p)/*扫描左孩子,_日相应的节点不为 P*/(1) ;stacktop=q;tagtop=0;(2) ;if(top0)if(stacktop=P) break; /*找到 P,栈底到栈顶为
18、t到 P*/if(tagtop=1)top-;else q=stacktop;q=q-rchiid;tagtop=1;(3) ;top-;topl=0;while(top0) q=stacktop; /*反向打印准备*/topl+;(4) ;top-;while( (5) ) /*打印栈的内容*/q=stackltopljprintf(q-data);topl-;(分数:15.00)填空项 1:_ (正确答案:(1)top+ (2) q=q-lchild (3) while(top0) (4) stackltopl=q (5) topl0)解析:解析 本题本质上是对二叉树的先序遍历进行考核,但
19、不是简单地进行先序遍历,而是仅遍历从根节点到给定的节点 p为止。本题采用非递归算法来实现,其主要思想是:初始化栈;根节点进栈,栈不空则循环执行以下步骤直到发现节点 p;当前节点不为空且不为 P进栈;栈顶为 p,则结束,否则转;若右子树访问过,则栈顶的右孩子为当前节点,转。扫描左孩子,当相应的节点不为 P时进栈,所以(1)填“top+”,(2)填“q=q-lchild”。在栈不为空时则一直在 do while循环中查找,因此(3)填“while(top0)”。在进行反向打印准备时,读取stacktop的信息放到 stackltopl中,即(4)填“stackltop1=q”。打印栈中所有内容,所
20、以(5)填“topl0”。四、试题四(总题数:1,分数:15.00)3.说明设一个环上有编号为 0n-1 的 n粒颜色不尽相同的珠子(每粒珠子颜色用字母表示,n 粒珠子的颜色由输入的字符串表示)。从环上的某两粒珠子问剪开,则环上珠子形成一个序列然后按以下规则从序列中取走珠子:首先从序列左端取走所有连续的同色珠子;然后从序列右端在剩下的珠子中取走所有连续的同色珠子,两者之和为该剪开处可取走珠子的粒数。在不同位置剪开,能取走的珠子也不尽相同。本程序所求的是在环上哪个位置剪开,按上述规则可取走的珠子粒数最多。程序中用数组存储字符串。例如,10 粒珠子颜色对应字符串为 aaabbbadcc,在 0号珠
21、子前剪开,序列为 aaabbbadcc,从左端取走 3粒a色珠子,从右端取走 2粒 c色珠子,共取走 5粒珠子。若在 3号珠子前剪开,即 bbbadccaaa,共取走 6粒珠子。C函数int count(char *s,int start,int end)int i,c=0,color:sstart,step=(startend)?-1:1;for(i=Start;si=color;i+=step)if(step0 return c;void main()char t,s120;int i,k,c,len,maxc,cut=0;printf(“请输入环上代表不同颜色珠子字符串:“);scanf
22、(“%s”,s);len=strlen(s);for(i=maxc=0; ilen;i+)( /*尝试不同的剪开方式*/c=count(s,0,len-1);if(clen) c+=count( (3) );if(cmaxc) cut=i;maxc=c;)/*数组 s的元素循环向左移动一个位置*/t=s0;for(j=1;jlen;j+) (4) ;(5) ;printf(“在第%d 号珠子前面剪开,可以取走%d 个珠子n“,cut,maxc);(分数:15.00)填空项 1:_ (正确答案:(1)step0 private:Node *top;void Transform:Trans(int
23、 d,int i)int m,n=0;Node *P;while(d0)(1) ;d=d/i;p=new Node;if(!n)P-data=m;(2) j(3) ;n+;elsep-data=m;(4) ;(5) ;void Transform:print()Node *P;while(top!=NULL)p=top;if(P-data9)coutdata+55:elsecoutdata;top=p-next;delete P;(分数:15.00)填空项 1:_ (正确答案:(1)m=d%i (2) top=p (3) top-next=NULL (4) p-next=top (5) top
24、=p)解析:解析 本题考查 C+编程,主要考查了链表的使用。所有的问题只出在函数 Trans中,它的功能是完成将十进制数 d转换为任意进制 i的数,并存在数组中。函数中首先定义了一个指向链表节点的指针,然后开始进行转换,进制转换应该是一个很常见的问题,就是不断地求模运算,所以(1)处应填入“m=d%i”。然后,我们要把求模的结果保存到链表节点中,并使链表首指针指向该节点,节点中指向下一个节点的指针设为空,所以(2)处应填入 top=p,(3)处应填入 top-next=NULL。由于求模运算是从低位到高位逐位求出的,所以在进行完第二次求模运算后,应该将第二次运算的结果放到链表首位,所以(4)处
25、应填入 p-next=top,(5)处应填入 top=p。六、试题六(总题数:1,分数:15.00)5.说明下面程序实现十进制向其他进制的转换。Java程序C1ass Nodeint data;Node next;class Transformprivate Node top;publiC void print()Node P;while(top !=null)P=top;if(P.data9)System.out.print(char)(p.data+55);elseSystem.out.print(p.data);top=P.next;public void Trans(int d,int
26、 i)(/d为数字;i 为进制int m;(1) n=false;Node P;while(d0)(2) ;d=d/i;P=flew Node();if( (3) )P.data=m;(4) ;top=P;n=true;elsep.data=m;(5) ;toP=P;(分数:15.00)填空项 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”。