试题三

阅读下列函数说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。

[函数3说明]

函数ELEM *proc(FILE *fp)从文件fp中逐个读入职工的工号及其完成的产品数量，对相同工号的产品数量计入该职工完成的产品总数，并且按照产品总数降序排列，若多个职工完成的产品总数相同，则按工号升序排列。

函数中建立了一个有序链表，来存储每个职工的工号和完成产品总数等数据，其结点类型为：

typedef struct ELE{

int no; /*职工工号*/

int num; /*完成的产品总数*/

struct ELE *next;

}ELEM;

[函数3]

ELEM *proc(FILE *fp)

{ int m，n;

ELEM *u,*v,*p,*base;

base = NULL; /*base是链表的首指针*/

while(fscanf(fp，"%d%d",&n，&m) == 2){

/*链表中是否存在工号为n的结点*/

for(v = base;v != NULL && v->no != n; __(1)___);

if(v != NULL) {/*若链表中已有工号为n的结点v，则将其从链表中脱钩*/

if(__(2)__ base = v->next;

else u->next = v->next;

v->num += m; /*累加工号为n的职工完成的产品数量*/

}

else { /*创建一个工号为n的结点*/

v = (ELEM *)malloc(sizeof(ELEM));

v->no = n; v->num = m;

}

/* 寻找结点v的插入位置*/

p = base;

while(p != NULL)

if(v->num > p->num || v->num == p->num && ___(3)___) break;

else {u = p; p = p->next; }

/* 将结点v插入链表*/

if(p == base) __(4)__;

else u->next = v;

__(5)__;

}

return base;

}

试题四

阅读下列函数说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。

[函数4说明]

函数void rcr(int a[]，int n,int k)的功能是：将数组a中的元素a[0]～a[n-1]循环向右平移k个位置。

为了达到总移动次数不超过n的要求，每个元素都必须只经过一次移动到达目标位置。在函数rcr中用如下算法实现：首先备份a[0]的值，然后计算应移动到a[0]的元素的下标p，并将a[p]的值移至a[0];接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p];依次类推，直到将a[0]的备份值移到正确位置。

若此时移动到位的元素个数已经为n，则结束;否则，再备份a[1]的值，然后计算应移动到a[1]的元素的下标p，并将a[p]的值移至a[1];接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p];依次类推，直到将a[1]的备份值移到正确位置。

若此时移动到位的元素个数已经为n，则结束;否则，从a[2]开始，重复上述过程，直至将所有的元素都移动到目标位置时为止。

例如，数组a中的6个元素如下图(a)所示，循环向右平移2个位置后元素的排列情况如图(b)所示。

412538476576 657641253847

a[0]a[1]a[2]a[3]a[4]a[5] a[0]a[1]a[2]a[3]a[4]a[5]

(a) (b)

[函数4]

void rcr(int a[]，int n，int k)

{ int i，j，t，temp，count;

count = 0; /*记录移动元素的次数*/

k = k % n;

if(__(1)__){ /*若k是n的倍数，则元素无须移动;否则，每个元素都要移动*/

i = 0;

while(count < n) {

j = i; t = i;

temp = a[i]; /*备份a[i]的值*/

/* 移动相关元素，直到计算出a[i]应移动到的目标位置*/

while((j = __(2)__) != i){

a[t] = a[j];

t = __(3)___;

count++;

}

__(4)___ = temp; count++;

__(5)___;

}

}

}

答案解析