1、初级程序员下午试题-108 及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面的流程图说明的是图的深度遍历。它的基本思想是：以图中某一结点作为当前结点，然后进行以下过程：(1)处理或输出当前结点，并记录当前结点的查访标志。(2)若当前结点有后件结点，则取第一个后件结点。若该后件结点未被查访过，则以该后件结点为当前结点用深度遍历法进行查访。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_二、试题二(总题数：1，分数：15.00)函数 2.1说明假设两个队列共享一个循环向量空间，其类型 Queue2定义如
2、下：typedef structDateType data MaxSize;int front2，rear2;Queue2;对于 i=0或 1，fronti和 reari分别为第 i个队列的头指针和尾指针。函数 EnQueue(Queue2 *Q，int i，DateType x)的功能是实现第 i个队列的入队操作。函数 2.1int EnQueue(Queue2 *Q,int i,DateType x)/*若第 i个队列不满，则元素 x入队列，并返回 1，否则返回 0*/if (i0 | i1) return 0; if(Q-rear i =Q-front (1) ) return 0;Q-
3、data (2) =x;Q-rear i= (3) ; return 1;函数 2.2说明函数 int BtreeEquaI(BinTreeNode *T1，BinTreeNode *T2)的功能是递归判断两棵二叉数是否相等，若相等则返回 1，否则返回 0。当两棵树的结构完全相同，并且对应结点的值也相同时才被认为相等。已知二叉树中的结点类型定义为：struct BinTreeNodechar data;BinTreeNode *left,*right; 其中 data为结点值域，left 和 right分别为指向左、右子女结点的指针域。函数 2.2int BtreeEqual(BinTreeN
4、ode *T1,BinTreeNode *T2)(if (T1=NULLT2=NULL) return 1;else if ( (4) ) return 0; else if( (5) ) return 1; else return 1; （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_三、试题三(总题数：1，分数：15.00)说明这个是一个链接存储线性表的直接插入排序函数。把未排序序列中的第一个结点插到已排序序列中。排序完毕，链表中的结点按结点值由小到大链接。函数typedef struct nodechar data;struct node *li
5、nk;NODE;NODE *insert_sort (NODE *h)NODE *t，*s，*u，*v; s=h-link;h-link=NULL：while(s!=NULL)for(t=s,v=h;v!=NULL V-datat-data; (1) , (2) );s=s-link;if(V=h) (3) ;else (4) ;(5) ;return h;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、试题四(总题数：1，分数：15.00)说明将一正整数序列 K1，K2，.，K9 重新排列成一个新的序列，新序列中，比 K1小的数都在 K1的前面(
6、左面)，比 K1大的数都在 K1的后面(右面)。在程序中已给出了 10个序列，每个序列有 9个正整数，并存入数组 a109中，分别求出这 10个新序列。函数#includestdio.h#includeconio. hvoid jsValue(int a10 9)int i, j ,k.n, temp;int b9;for (i=0 ; i10 ; i+)temp=a 1 0 ;for(j=8;j=0;j-)if(tempail j) (1) =aij;if(temp=ai j) (2) =aij;if(temp=ai j) (3) =temp;for (j=0; j9; j+) ajj=bj
7、void main ()int a 109= 6, 8,9,1,2, 5,4,7,3,3，5，8，9，1，2，6，4，7，8，2，1，9，3，5，4，6，7)，3，5，1，2，9，8，6，7，4，4，7，8，9，1，2，5，3，6，4，7，3，5，1，2，6，8，9，9，1，3，5，8，6，2，4，7，2，6，1，9，8，3，5，7，4，5，3，7，9，1，8，2，6，4，7，1，3，2，5，8，9，4，6;int i，j;(4) ;for(i=0; i10; i+)for(j=0; j9; j+) printf(“%d“,ai j );if( (5) ) printf(“,“);printf
8、 (“/n“);getch () ;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_五、试题五(总题数：1，分数：15.00)说明设计一个类模板 Sample用于对一个有序数组采用二分法查找元素下标。c+程序#includeiostream. h#define Max 100 /最多元素个数templateclass Tclass SampleT A Max; /存放有序数序int n; /实际元素个数Public：Sample /默认构造函数Sample(T a ,int i); /初始化构造函数int seek(T c); void dispfor
9、 (int i=0; in; i+)coutA i“ “;coutendl; templateclass TSampleT:Sample(T a,int i)n=I;for (int j=0; jI; j+)(1) ;templateclass Tint SampleT:seek(T c)int low=0,high=n-1,mid;while( (2) )mid=(low+high)/2;if( (3) )return mid;else if ( (4) )low=mid+1; else(5) ; return-1;void main()char a=“acegkmpwxz“; Sample
10、chars(a,1.);cout“元素序列：“ ;s. disp();cout“元素g 的下标： “s. seek(g)endl;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：15.00)1.说明下面 Application程序根据 ManKind类中的 sex属性输出“Man!”或“Woman!”。程序全部写在Main.java文件中。程序中存在两个错误，分别在第 01和 14行，请将其改正或删除相应语句，并指出程序运行的输出结果。Java程序01 public class ManKind02 int sex; /默认
11、，是公有成员03 public void manOrWoman()/公有方法04 ifsex =0 /表示男人05 System.out.print “Man!”;06 else /女人07 System.out.print “Woman!“;08 09 10 11 public class Main12 public static void main(String args13 ManKind somePerson, somePerson2;14 SomePerson. sex=1;15 somePerson=new ManKind();16 SomePerson.sex=1;17 some
12、Person.manOrWoman(); 18 SomePerson2=somePerson;19 SomePerson2.sex=0：20 somePerson2 .manOrWoman();21 somePerson.manOrWoman(); 22 23 （分数：15.00）填空项 1:_初级程序员下午试题-108 答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面的流程图说明的是图的深度遍历。它的基本思想是：以图中某一结点作为当前结点，然后进行以下过程：(1)处理或输出当前结点，并记录当前结点的查访标志。(2)若当前结点有后件结点，则取
13、第一个后件结点。若该后件结点未被查访过，则以该后件结点为当前结点用深度遍历法进行查访。（分数：15.00）填空项 1:_ （正确答案：markk-1=1;）解析：填空项 1:_ （正确答案：mark(p-num)-1=0;）解析：填空项 1:_ （正确答案：dfs(head,p-num,mark);）解析：填空项 1:_ （正确答案：p=p-next;）解析：填空项 1:_ （正确答案：struct node;）解析：解析 本题目考查流程图。按题目要求，在空(1)应该填入一个标记，表示该结点已经被访问过了，即应该填入 markk-1=1。接着p指针指向当前结点的第一个后件结点，如果 p不为空，
14、则判断该后件结点是否被访问过，空(2)应该填入 mark(p-num)-1=0。如果是，那么则采用递归调用，所以空(3)应该填入 dfs(head, p-num, mark)。如果该后件结点已经被访问过了，则 p指向当前结点的下一个后件结点，所以空(4)应该填入p=p-next。空(5)考查数据结构，根据题意，gpnode 用来存储结点的值和指向的下一个结点，所以指针的类型应该为 struct node型，即空(5)应填入 struct node。二、试题二(总题数：1，分数：15.00)函数 2.1说明假设两个队列共享一个循环向量空间，其类型 Queue2定义如下：typedef struc
15、tDateType data MaxSize;int front2，rear2;Queue2;对于 i=0或 1，fronti和 reari分别为第 i个队列的头指针和尾指针。函数 EnQueue(Queue2 *Q，int i，DateType x)的功能是实现第 i个队列的入队操作。函数 2.1int EnQueue(Queue2 *Q,int i,DateType x)/*若第 i个队列不满，则元素 x入队列，并返回 1，否则返回 0*/if (i0 | i1) return 0; if(Q-rear i =Q-front (1) ) return 0;Q-data (2) =x;Q-r
16、ear i= (3) ; return 1;函数 2.2说明函数 int BtreeEquaI(BinTreeNode *T1，BinTreeNode *T2)的功能是递归判断两棵二叉数是否相等，若相等则返回 1，否则返回 0。当两棵树的结构完全相同，并且对应结点的值也相同时才被认为相等。已知二叉树中的结点类型定义为：struct BinTreeNodechar data;BinTreeNode *left,*right; 其中 data为结点值域，left 和 right分别为指向左、右子女结点的指针域。函数 2.2int BtreeEqual(BinTreeNode *T1,BinTree
17、Node *T2)(if (T1=NULLT2=NULL) return 1;else if ( (4) ) return 0; else if( (5) ) return 1; else return 1; （分数：15.00）填空项 1:_ （正确答案：(i+1)%2 或 1-i）解析：填空项 1:_ （正确答案：Q-reari）解析：填空项 1:_ （正确答案：(Q-reari+)%Maxsize）解析：填空项 1:_ （正确答案：T1=NULL| T2=NULL）解析：填空项 1:_ （正确答案：T1-data=T2-data BtreeEqual(T1-left,T2-left) B
18、treeEqual(T1-right,T2-right)）解析：解析 函数 2.1是一个循环共享队列入队的问题，当队列 0入队时，如果队列 0队尾指针与队列1头指针相等时，说明队列 0无法入队; 当队列 1入队时，如果队列 1队尾指针与队列 0队头指针相等时，说明队列 1无法入队。所以空(1)填(i+1)%2 或 1-i。在入队操作中，其操作步骤是先将元素 x插入队列 i队尾所指的位置，再将队尾加 1。即空(2)填 Q-reari，空(3)填(Q-reari+)%Maxsize。函数 2.2判断两颗二叉树是否相等。分几种情况：若两棵树均为空，则相等; 若一棵为空一棵不为空，则不等，即空(4)应
19、填 T1=HNULL|T2=NULL;若根结点值相等并且左、右子树也相等，则两棵树相等，即空(5)应填 T1-data=T2-data BtreeEqual(T1-left, T2-left) BtreeEqual(T1-right，T2-right);否则不等。三、试题三(总题数：1，分数：15.00)说明这个是一个链接存储线性表的直接插入排序函数。把未排序序列中的第一个结点插到已排序序列中。排序完毕，链表中的结点按结点值由小到大链接。函数typedef struct nodechar data;struct node *link;NODE;NODE *insert_sort (NODE *
20、h)NODE *t，*s，*u，*v; s=h-link;h-link=NULL：while(s!=NULL)for(t=s,v=h;v!=NULL V-datat-data; (1) , (2) );s=s-link;if(V=h) (3) ;else (4) ;(5) ;return h;（分数：15.00）填空项 1:_ （正确答案：u=v）解析：填空项 1:_ （正确答案：v=v-link）解析：填空项 1:_ （正确答案：h=t）解析：填空项 1:_ （正确答案：u-link=t）解析：填空项 1:_ （正确答案：t-link=v）解析：解析 本题的主要思路是：将当前的结点插入到该结
21、点前的有序单链表中，直到当前结点为空。在将当前结点插入到该结点前的有序单链表的过程中，类似顺序表的策略，从单链表的表头开始查找，直到找到该结点应插入的位置，然后完成插入任务。在当前结点不为空且其值小于该结点值时，当前结点向后移，则空(1)应填 u=v，空(2)应填 v=v-link。在当前结点为空或其值大于等于该结点值时，跳出 for循环。若当前结点就是头结点，则将头结点指向该结点，即空(3)填 h=t;否则在 u和 v指向的结点间插入该结点 t，即空(4)填 u-link=t，空(5)填 t-link=v。四、试题四(总题数：1，分数：15.00)说明将一正整数序列 K1，K2，.，K9 重
22、新排列成一个新的序列，新序列中，比 K1小的数都在 K1的前面(左面)，比 K1大的数都在 K1的后面(右面)。在程序中已给出了 10个序列，每个序列有 9个正整数，并存入数组 a109中，分别求出这 10个新序列。函数#includestdio.h#includeconio. hvoid jsValue(int a10 9)int i, j ,k.n, temp;int b9;for (i=0 ; i10 ; i+)temp=a 1 0 ;for(j=8;j=0;j-)if(tempail j) (1) =aij;if(temp=ai j) (2) =aij;if(temp=ai j) (3
23、) =temp;for (j=0; j9; j+) ajj=bjvoid main ()int a 109= 6, 8,9,1,2, 5,4,7,3,3，5，8，9，1，2，6，4，7，8，2，1，9，3，5，4，6，7)，3，5，1，2，9，8，6，7，4，4，7，8，9，1，2，5，3，6，4，7，3，5，1，2，6，8，9，9，1，3，5，8，6，2，4，7，2，6，1，9，8，3，5，7，4，5，3，7，9，1，8，2，6，4，7，1，3，2，5，8，9，4，6;int i，j;(4) ;for(i=0; i10; i+)for(j=0; j9; j+) printf(“%d“,ai
24、j );if( (5) ) printf(“,“);printf (“/n“);getch () ;（分数：15.00）填空项 1:_ （正确答案：bk-）解析：填空项 1:_ （正确答案：bn+）解析：填空项 1:_ （正确答案：bn）解析：填空项 1:_ （正确答案：jsValue(a)）解析：填空项 1:_ （正确答案：j=7）解析：解析 在主函数中先要调用函数 is Value()对数组 a进行处理，所以空(4)应填“jsValue(a)“。然后输出数组元素，同一行的元素之间用逗号分隔，所以空(5)应填入“j=7“。函数 jsValue()是将数组按题目要求进行排序。通过观察发现处理后
25、的数组中元素的顺序与原来的顺序相反并且每一行中没有与第一个数相同的数，所以是从后往前处理，也就是将每组从最后往前倒序逐个同第一个数比较，比它大的就放到临时数组 b中的最后，比它小的就放到临时数组 b中的最前面，依此类推，所以空(1)应填入“bk-”，空(2)应填入“bn+”，空(3)应填入“bn”。最后将 b数组赋给 a数组。五、试题五(总题数：1，分数：15.00)说明设计一个类模板 Sample用于对一个有序数组采用二分法查找元素下标。c+程序#includeiostream. h#define Max 100 /最多元素个数templateclass Tclass SampleT A M
26、ax; /存放有序数序int n; /实际元素个数Public：Sample /默认构造函数Sample(T a ,int i); /初始化构造函数int seek(T c); void dispfor (int i=0; in; i+)coutA i“ “;coutendl; templateclass TSampleT:Sample(T a,int i)n=I;for (int j=0; jI; j+)(1) ;templateclass Tint SampleT:seek(T c)int low=0,high=n-1,mid;while( (2) )mid=(low+high)/2;if
27、( (3) )return mid;else if ( (4) )low=mid+1; else(5) ; return-1;void main()char a=“acegkmpwxz“; Samplechars(a,1.);cout“元素序列：“ ;s. disp();cout“元素g 的下标： “s. seek(g)endl;（分数：15.00）填空项 1:_ （正确答案：Aj=ai）解析：填空项 1:_ （正确答案：low=high）解析：填空项 1:_ （正确答案：Amid=c）解析：填空项 1:_ （正确答案：Amidc）解析：填空项 1:_ （正确答案：high=mid-1）解析：
28、解析 在主函数中，首先由类模板实例化成 Samplechar模板类。空(1)所在处为构造函数的声明，将参数中的值赋值到类的成员变量中，所以空(1)应填入“Aj=aj”。成员函数 seek()采用二分法查找元素下标，变量 low和 high分别表示查找区间的下标，如果查询到目标，则返回相应的下标，若没有查询到，则其结束的条件即空(2)的内容为“low=high”。根据二分法的原理，当中间的元素恰好等于目标元素时，则返回其下标，所以空(3)应填入“Amid=c”; 若中间的元素小于目标元素时，则 mid+1作为新的查找区间的起始下标，所以空(4)应填入“Amidc”; 否则 mid-1作为新的查找
29、区间的结束下标，所以空(5)应填入“high=mid-1”。六、试题六(总题数：1，分数：15.00)1.说明下面 Application程序根据 ManKind类中的 sex属性输出“Man!”或“Woman!”。程序全部写在Main.java文件中。程序中存在两个错误，分别在第 01和 14行，请将其改正或删除相应语句，并指出程序运行的输出结果。Java程序01 public class ManKind02 int sex; /默认，是公有成员03 public void manOrWoman()/公有方法04 ifsex =0 /表示男人05 System.out.print “Man!
30、”;06 else /女人07 System.out.print “Woman!“;08 09 10 11 public class Main12 public static void main(String args13 ManKind somePerson, somePerson2;14 SomePerson. sex=1;15 somePerson=new ManKind();16 SomePerson.sex=1;17 somePerson.manOrWoman(); 18 SomePerson2=somePerson;19 SomePerson2.sex=0：20 somePerso
31、n2 .manOrWoman();21 somePerson.manOrWoman(); 22 23 （分数：15.00）填空项 1:_ （正确答案：01 行改为 class ManKind14行删除输出结果为：Man! Woman! Woman!）解析：解析 本题考察 Java编程，涉及类的声明，对象的声明、创建和使用。程序写在 Main.java文件中，根据“一个编译单元(即一个 java文件)只能有一个公有类或接口，其名字必须与文件名相同”的原则，类 ManKind不能声明为 publiC。故 01行应改为“class MainKind”。对象在声明时并未真正生成实例，需要用 new关键
32、字使其实例化方可使用。13 行仅声明了对象并未真正实例化，因此 14行的使用是错误的，应将其删除。下面来看程序输出结果。somePerson的 sex属性被赋予了 1，表示“男人”，调用方法 manOrWoman()时应该输出“Man!”。此后，将 somePerson赋给 somePerson2，根据对象的引用本质，此后修改 somePerson2的属性 sex时也修改了somePerson的 sex，亦即此时 somePerson和 somePerson2指向同一个内存单元可以说是同一个对象。将somePerson2的 sex属性赋为 0后，somePerson2 和 somePerson调用方法 manOrWoman()时均应该输出“Woman!”。
