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”。
