初级程序员下午试题-91

1、初级程序员下午试题-91(总分：90.00，做题时间：90分钟)一、试题一(总题数：1,分数：15.00)1. 阅读以下说明和流程图，回答问题将解答填入对应栏。说明下面的流程图，用来完成计算一组数组中的中值，其方法是：将数组中的一个值与其他值比较，并计算大于等于被比较数的数值的个数，以及小于等于被比较数的数值的个数，如果两数都大于n/2，则已经找到了中值，否则继续之前的步骤。注：流程中循环开始的说明按照“循环变量：循环初值，循环终值，增量”格式描述；*问题将流程图的(1)(5)处补充完整。(分数：15.00 )填空项 1: (正确答案：j=-1 ; (2) xj!=xi; (3) count_

2、lowe 叶+;(4) count_lower < (n/2.0)|count higher(n/2.0)； (5) xj;)解析：解析本题目考查流程图。算法描述在题目中已经详细给岀，通过阅读题目可知j用来定位数组中一个被比较的数，i用来循环遍历数组中所有的数。j应该从第0个数开始，又由于要执行一步j=j+1，所以(1)中应填入“j= -1”，counUlighe叶+说明遍历的数比被比较的数大，即(2)中应填入“ xj!=xi ”相应的，(3)中就应填入“count_lowe叶+ ”，题目说明中已经指出，当 count_lower和count_higher 都大于n/2时，就说明找到 了

3、中值，所以(4)应当填入“ count_lower <(n/2.0)count_higher(n/2.0)"，最后，如果循环结束，则xi就应该是中值，(5)中应填入“ xj ”。二、试题二(总题数：1，分数：15.00)2. 阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。说明1L为一个带头结点的循环链表。函数LinkList deletenode(LinkList L,int c)的功能是删除L中数据域data的值大于C的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返 回值。C函数1LinkList deletenode(Lin

4、kList L,int c)LinkList Lc,P,pre;pre=L;P= (1);Lc=(LinkList)malloc(sizeof(Listnode);Lc- > next=Lc;while(P!=L)if(p- > data > C)(2);(3KLc- > next=p;p=pre- > next;else pre=p;p=pre- > next;return Lc;说明2的功能是将十进制正整数n转换成*进制数，并打印递归函数 dec_to_k_2(int n,int k)C函数2dec to k 2(int n,int k)if(n!=O)

5、dec to k 2(,k);printf("%d", (5) );(分数:15.00 )填空项 1: (正确答案：pre- > next 或 L- > next (2) pre- > neXt=p- > next (3) p> next=Lc- > next n/k (5) n%k )解析：解析函数1是考察链表的删除和插入的操作。(1)空所在语句是对指针P赋初值，应填“ pre - >next ”或“L ->next ”，通过下面的程序可以判断指针pre所指的结点是指针p所指结点前驱结点。(2)、(3)空所在的语句块是处理当

6、指针p所指的结点是一个大于C的结点，则将该结点从链表L中删除，再将它插入到链表Lc 中。分另U填“ pre - >next=p- >next ”和 “p - >next=-Lc- >next ” 。函数2是一个递归函数，采用除 k取余法。最开始得到余数作为k进制数的最低位，最后得到的余数作为k进制数的最高位。用递归法求解时，先将n/k转换成k进制，再输出n%k因此填“n/k”，(5)填“n%k。三、试题三(总题数：1,分数：15.00)3. 阅读以下函数说明和 C语言函数，将应填入(n)处的字句写在对应栏内。说明函数int psort(int a,int n)实现将含n

7、个整数的数组a的不同元素按从小到大顺序存于数组a中。实现方法是从未确定的元素列中找到最小元素并将a的第i最小元素交换至ai位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。C函数int psort(int a,int n)int i,J,k,P;for(i=0,k=0;i< (1) ;i+)for(j=i+1,;j_ < n; j+)if(ap > aj)p=j;if(p!=i)t=ap;ap=ai;ai=t;if( (3) ) k+;else if( (4)< ai)(5) =ai;return k;int a=5,7

8、,5,6,4,3,4,6,7;main()int k,n;for(k=0;k < (Sizeof a)/Sizeof(int);k+) printf("%5d",ak);printf ("/n/n");n=psort(a,(sizeof(a)/sizeof(int); for(k=0;k < n;k+) printf("%5d",ak);printf("/n/n");(分数:15.00 )填空项 1: (正确答案:n-1 P=i (3) k=0 ak-1 (5) ak+)解析：解析本程序排序方法是从未确

9、定的元素列中找到最小元素并将a的第i最小元素交换至ai位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。这是采 用选择法对数组元素进行排序，因此空 (1)填“n1”，空填“p=i”。若该最小元素比已确定的最后一 个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。因此，空(3)填“k=0”；而当ak-1 < ai时”，则 ak+=ai;否则忽略元素 ai。所以空(4)填“ak -1 ”空(5)填“ak+ ”。四、试题四(总题数：1,分数：15.00)4. 阅读以下函数说明和 C语言函数，将应填入(n)处的字句写在对应栏内。说

10、明这是一个求解Josephus问题的函数。用整数序列1，2，3，n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。Josephus问题描述，设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他岀局，如此反复直到所有的人全部岀局为止。C函数void Josephus(int A,int n,s,m)(int i,j,k,temp;if(m=O)printf("m=0 是无效的参数!/n");return;for(i=0;i < n;i+) Ai=i+1; /*初始化，执

11、行 n 次*/i= (1)/*报名起始位置*/for(k=n;k > 1;k-)if( (2) ) i=0;i= (3)/*寻找出局位置*/if(i!=k-1) tmp=Ai;for(j=i;J < k-1;j+) (_(5);for(k=0;k < n/2;k+) tmp=Ak;Ak=An-k+1;An-k+1=tmp;(分数:15.00 )填空项 1: (正确答案：s-1 (2) i=k (3) (i+m-1)%k (4) Aj=Aj+1(5) Ak-1=tmp )解析：解析JosephuS问题是一个经典的顺序表问题，所用到的数据结构就是一维数组。整个算法过程实际上就是一

12、个从n到1的循环。当还剩下k个人的时候，首先找到岀局位置，然后将岀局者交换到第k-1位置。循环结束，将数组逆置，即得到岀局序列。空 (1)是赋报名起始位置，应填“s -1”： (2)填“ i=k ”。空 是寻 找出局位置，应填“ (i+m -1)%k'。数组A的元素要循环向右移动一个位置，则 (4)填“Aj=Aj+1(5) 填“Ak-1=tmp ”。五、试题五(总题数：1,分数：15.00)5. 阅读以下说明和C+程序，将应填入(n)处的字句写在对应栏内。说明下面程序实现十进制向其它进制的转换。C+程序#include"ioStream.h"#include&quo

13、t;math.h"#includetypedef struct nodeint data;node*next;Node;Class Tran sformDUDlic:void Trans(int d,int i); /d为数字;i 为进制void print();private:Nodetop;void Transform:Trans(int d,int i)int m,n=0;NodeP;while(d > 0)(1);d=d/i;p=new Node;if(!n)p- > data=m;(2);壯n+;else p- > data=m;；(5)； void Tr

14、ansform:print()NodeP; while(top!=NULL)p=top;if(p- > data > 9) cout << data+55; elsecout << data;top=p- > next;delete p;(分数:15.00 )填空项 1: (正确答案: m=d%i (2) top=p (3) top- > next=NULL (4) p- > next=top(5) top=p )解析：解析本题考查C+编程，主要考查了链表的使用。所有的问题只岀在函数 Trans中，它的功能是完成将十进制数d转换为任意进制i

15、的数，并存在数组中。函数中首先定义了一个指向链表结点的指针，然后开始进行转换，进制转换应该是一个很常见的问题，就 是不断的求模运算，所以(1)处应填入“ m=d%i。然后，我们要把求模的结果保存到链表结点中，并使链表首指针指向该结点，结点中指向下一个结点"的指针设为空，所以(2)处应填入“ top=p”，(3)处应填入“top- >next=NULL'。由于求模运算是从低位到高位逐位求出的，所以在我们在进行完第二次求模运算后，应该将第二次运算的结果放到链表首位，所以(4)处应填入“P - >next=top ”，(5)处应填入“ top=p ”。六、试题六(总题数

16、：1，分数：15.00)6. 阅读以下说明和Java程序，将应填入(n)处的字句写在对应栏内。说明下面程序实现十进制向其它进制的转换。Java程序ClasS Nodeint data;Node next;class Transformprivate Node top;public void print()Node p;while(top!=null)P=top;if(P.data > 9)elsetop=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=new Node();if( (3)p.data=m;；top=P;n=true;elsep.data=m;(5)；top=P ；(分数:15.00 )填空项 1: (正确答案:boolean (2) m=d%i (3) !n (4) top-> next=null (5) p> next=top )解析：解析本题考查Java编程，主要考查了链表的使用。所有的问题只岀在函数Trans中，它的功能是完成将十进制数d转换为任意进制i的数，并存在数组中。变量n被赋值为false，说明n是布尔型变量，Java中布尔型变量关键