初级程序员下午试题-75_真题(含答案与解析)-交互

初级程序员下午试题-75

(总分90, 做题时间90分钟) 试题一 1.

阅读以下说明和流程图，回答问题将解答填入对应栏。 [说明]

下面的流程图，用来完成计算一组数组中的中值，其方法是：将数组中的一个值与其他值比较，并计算大于等于被比较数的数值的个数，以及小于等于被比较数的数值的个数，如果两数都大于n/2，则已经找到了中值，否则继续之前的步骤。

注：流程中循环开始的说明按照“循环变量：循环初值，循环终值，增量”格式描述；

[问题]

将流程图的(1)～(5)处补充完整。

SSS_FILL 分值: 15 答案:j=-1； (2) x[j]!=x[i]； (3) count_lower++；

(4) count_lower＜(n/2.0)||count higher(n/2.0)； (5) x[j]; [解析]

本题目考查流程图。

算法描述在题目中已经详细给出，通过阅读题目可知j用来定位数组中一个被比较的数，i用来循环遍历数组中所有的数。j应该从第0个数开始，又由于要执行一步j=j+1，所以(1)中应填入“j=-1”，counUligher++说明遍历的数比被比较的数大，即(2)中应填入“x[j]!=x[i]”相应的，(3)中就应填入“count_lower++”，题目说明中已经指出，当count_lower和count_higher都大于n/2时，就说明找到了中值，所以(4)应当填入“count_lower＜

(n/2.0)][count_higher(n/2.0)”，最后，如果循环结束，则x[i]就应该是中值，(5)中应填入“x[j]”。 试题二 1.

阅读以下函数说明和C语言函数，将应填入 (n) 处的字句写在对应栏内。 [说明1]

L为一个带头结点的循环链表。函数LinkList deletenode(LinkList L,int c)的功能是删除L中数据域data的值大于C的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。 [C函数1]

LinkList deletenode(LinkList 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) ; (3) ; Lc-＞next=p; p=pre-＞next; } else{ pre=p;

p=pre-＞next; }

return Lc; }

[说明2]

递归函数dec_to_k_2(int n,int k)的功能是将十进制正整数n转换成进制数，并打印。 [C函数2]

dec to k 2(int n,int k) { if(n!=O){

dec to k 2( (4) ,k); printf(\"%d\(5) ); } } SSS_FILL 分值: 15 答案:pre-＞next或L-＞next (2) pre-＞neXt=p-＞next (3) p-＞next=Lc-＞next

(4) n/k (5) n%k [解析]

函数1是考察链表的删除和插入的操作。(1)空所在语句是对指针P赋初值，应填“pre-＞next”或“L-＞next”，通过下面的程序可以判断指针pre所指的结点是指针p所指结点前驱结点。(2)、(3)空所在的语句块是处理当指针p所指的结点是一个大于C的结点，则将该结点从链表L中删除，再将它插入到链表Lc中。分别填“pre-＞next=p-＞next”和“p-＞next=-Lc-＞next” 。

函数2是一个递归函数，采用除k取余法。最开始得到余数作为k进制数的最低位，最后得到的余数作为k进制数的最高位。用递归法求解时，先将n/k转换成k进制，再输出n%k。因此(4)填“n/k”，(5)填“n%k”。 试题三 1.

阅读以下函数说明和C语言函数，将应填入 (n) 处的字句写在对应栏内。 [说明]

函数int psort(int a[],int n)实现将含n个整数的数组a[]的不同元素按从小到大顺序存于数组a[]中。实现方法是从未确定的元素列中找到最小元素并将a[]的第i最小元素交换至a[i]位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。 [C函数]

int psort(int a[],int n) {int i,J,k,P;

for(i=0,k=0;i＜ (1) ;i++){ for(j=i+1, (2) ;j＜n; j++) if(a[p]＞a[j]) p=j;

if(p!=i){ t=a[p]; a[p]=a[i]; a[i]=t; }

if( (3) ) k++; else if( (4) ＜a[i]) (5) =a[i]; }

return k; }

int a[]={5,7,5,6,4,3,4,6,7}; main() {int k,n;

for(k=0;k＜(Sizeof a)/Sizeof(int);k++) printf(\"%5d\ printf (\"\\n\\n\");

n=psort(a,(sizeof(a))/sizeof(int)); for(k=0;k＜n;k++) printf(\"%5d\ printf(\"\\n\\n\"); } SSS_FILL 分值: 15 答案:n-1 (2) P=i (3) k==0 (4) a[k-1] (5) a[k++]

[解析]

本程序排序方法是从未确定的元素列中找到最小元素并将a[]的第i最小元素交换至a[i]位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。这是采用选择法对数组元素进行排序，因此空(1)填“n-1”，空(2)填“p=i”。若该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该

元素。因此，空(3)填“k==0”；而当a[k-1]＜a[i]时”，则a[k++]=a[i]；否则忽略元素a[i]。所以空(4)填“a[k-1]”空(5)填“a[k++]”。 试题四 1.

阅读以下函数说明和C语言函数，将应填入 (n) 处的字句写在对应栏内。 [说明]

这是一个求解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++) A[i]=i+1; /*初始化，执行n次*/ i= (1) /*报名起始位置*/ for(k=n;k＞1;k-){ if( (2) ) i=0;

i= (3) /*寻找出局位置*/ if(i!=k-1){ tmp=A[i];

for(j=i;J＜k-1;j++) (4) ; (5) ; } }

for(k=0;k＜n/2;k++){

tmp=A[k];A[k]=A[n-k+1];A[n-k+1]=tmp; } } SSS_FILL 分值: 15 答案:s-1 (2) i==k (3) (i+m-1)%k (4) A[j]=A[j+1] (5) A[k-1]=tmp

[解析]

JosephuS问题是一个经典的顺序表问题，所用到的数据结构就是一维数组。整个算法过程实际上就是一个从n到1的循环。当还剩下k个人的时候，首先找到出局位置，然后将出局者交换到第k-1位置。循环结束，将数组逆置，即得到出局序列。空(1)是赋报名起始位置，应填“s-1”：(2)填

“i==k”。空(3)是寻找出局位置，应填“(i+m-1)%k”。数组A的元素要循环向右移动一个位置，则(4)填“A[j]=A[j+1](5)填“A[k-1]=tmp”。 试题五 1.

阅读以下说明和C++程序，将应填入 (n) 处的字句写在对应栏内。 [说明]

下面程序实现十进制向其它进制的转换。 [C++程序]

#include\"ioStream.h\" #include\"math.h\" #include

typedef struct node { int data; node*next; }Node;

Class Transform {

DUDlic:

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(!n){

p-＞data=m; (2) ; (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; } } SSS_FILL 分值: 15 答案: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)处应填入“top-＞next=NULL”。由于求模运算是从低位到高位逐位求出的，所以在我们在进行完第二次求模运算后，应该将第二次运算的结果放到链表首位，所以(4)处应填入“P-＞next=top”，(5)处应填入“top=p”。 试题六 1.

阅读以下说明和Java程序，将应填入 (n) 处的字句写在对应栏内。 [说明]

下面程序实现十进制向其它进制的转换。 [Java程序] ClasS Node{ int data; Node next; }

class Transform{

private Node top; public void print(){

} Node 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=new Node(); if( (3) ){ p.data=m; (4) ; top=P; n=true; } else{ p.data=m; (5) ； top=P； } } }

SSS_FILL 分值: 15 答案:boolean (2) m=d%i (3) !n (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=true”可知，此处正是处理第一个结点的特殊情况，故(3)应填“!n”，(4)处应填入“top-＞next=null”。这里采用的链栈，所以(5)处应填入“p-＞next=top”。

1