初级程序员 2019年 下半年 下午

第1题

阅读以下说明和流程图，填写流程图中的空缺，将解答填入答题纸的对应栏内。

【说明】

某系统中有N个等长的数据记录，其主键值为随机排序且互不相等的正整数编号，表示为K(0)，K(1)，...，K(N-1)。

现采用杂凑法将各数据记录存入区域S(0)，S(1)，S(2)，……，S(M-1)中（M≥N），以加快按主键值检索的效率（初始时各区域都是空的）。

下面流程图中，选用适当的质数P（N≤P≤M），对每个主键值先计算出它除以P的余数j。

如果区域S(j)已占用，则考查下一个区域S(j+1)，……，直到发现某个区域为空时，则将该主键值相应的数据记录存入该区域（注意，S(M-1)的下一个区域是S(0)）。

为了标记每个区域是否已占用，采用了M个标记位F(0)，F(1)，……，F(M-1)。

初始时所有的标记位都为0，每当一个区域被占用时，将相应的标记位置1。

例如，设6个记录的主键值分别为31、15、20、35、18、10，取质数P=7，用上述杂凑法将这些记录存入区域S(0)~S(7)后，各区域中记录的主键值依次为35、15、空、31、18、10、20、空。

【流程图】

注1：“循环开始”框内给出循环控制变量的初值、终值和增值（默认为1），格式为：循环控制变量=初值，终值[，增值]

注2：函数int(x)为取x的整数部分，即不超过x的最大整数。

【解析】

本题旨在考查程序设计（算法流程图设计）的能力。

杂凑法是大数据处理时常用的数据存储检索方法，其检索效率很高。

本流程图中，将依靠循环i=0，1，……，N-1，依次将主键值为K(i)的记录存入适当的区域S(j)中。

首先，需要求出K(i)除以质数P的余数j，采用的方法是计算K(i)-P*int(K(i)/P)。

例如，对于P=7，31/7的商的整数部分为4，所以31除以7的余数为31-7×4=3。因此流程图中空（1）应填写K(i)/P或其等效形式。

然后判断区域S(j)的标志位F(j)是否为0，即空（2）应填写0。

如果F(j)=0则表示区域S(j)为空，可以将K(i)直接存入区域S(j)中，并将F(j)置1表示已被占用，即空（3）应填写1→F(j)。

如果F(j)非0，则表示S(j)已占用，需要考虑下一个区域是否为空。也就是说，需要将j增1，即空（4）应填写j+1→j。

如果j增1后已超越最后一个区域，则需要考虑返回区域S(0)。也就是说，当j=M时，需要执行0→j，即空（5）应填写0→j。

【答案】

（1）K(i)/P或等效形式

（2）0

（3）1→F(j)或F(j)=1或等效形式

（4）j+1→j或j=j+1或j++或等效形式

（5）0→j或j=0或等效形式

第2题

【C代码1】

#include<stdio.h>

int main()
{
	int num = 5;
	printf("%d\n", ++num);
	printf("%d\n", num++);
	printf("%d\n", num--);
	printf("%d\n", num);
	return 0;
}

【C代码2】

void func(char ch)
{
	while (ch < 'f')
	{
		printf("%c:%d\n", ch, ch);
		ch += 2;
	}
}

【C代码3】

#define CHARS 5
const int ROWS = 5;

void test()
{
	int row;
	char ch;
	for (row = 0; row < ROWS; row++) {
		for (ch = 'B' + row; ch < ('B' + CHARS); ch++)
			putchar(ch);
		printf("\n");
	}
}

【问题1】

请给出C代码1运行后的输出结果。

【问题2】

已知字符'a'的ASCⅡ码值为十进制数97，请给出调用C代码2中函数func('a')后的输出结果。

【问题3】

请给出调用C代码3中函数test()后的输出结果。

【解析1】

第一行是先加、回写，后打印6；

第二行是先打印6，再加、回写变成7；

第三行是先打印7，再减、回写变成6；

第四行打印6；

6
6
7
6

【解析2】

第一次：'a' < 'f'，执行，输出：a:97，然后加2变成'c'

第二次：'c' < 'f'，执行，输出：c:99，然后加2变成'e'

第三次：'e' < 'f'，执行，输出：e:101，然后加2变成'g'

第四次：'g' < 'f' 不成立，结束循环。

a:97
c:99
e:101

【解析3】

第一趟，外层循环，row是0，ROWS是5，0<5，成立，进入内层循环

内层循环，row是0，'B'+row还是'B'，ch是'B'，CHARS是5，'B'+5是'G'，依次打印BCDEF

换行

row++变成1；

第二趟，外层循环，row是1，ROWS是5，1<5，成立，进入内层循环

内层循环，row是1，'B'+row是'C'，ch是'C'，CHARS是5，'B'+5还是'G'，依次打印CDEF

换行

row++变成2；

第三趟，外层循环，row是2，ROWS是5，2<5，成立，进入内层循环

内层循环，row是2，'B'+row是'D'，ch是'D'，CHARS是5，'B'+5仍是'G'，依次打印DEF

换行

row++变成3；

第四趟，外层循环，row是3，ROWS是5，3<5，成立，进入内层循环

内层循环，row是3，'B'+row是'E'，ch是'E'，CHARS是5，'B'+5仍是'G'，依次打印EF

换行

row++变成4；

第五趟，外层循环，row是4，ROWS是5，4<5，成立，进入内层循环

内层循环，row是4，'B'+row是'F'，ch是'F'，CHARS是5，'B'+5仍是'G'，依次打印F

换行

row++变成5；

第五趟，外层循环，row是5，ROWS是5，5<5，不成立，循环结束。

BCDEF
CDEF
DEF
EF
F

第3题

阅读以下说明和C代码，填写程序中的空缺，将解答写入答题纸的对应栏内。

【说明】

规定整型数组a中的元素取值范围为[0,N),函数usrSort(int n, int a[])对非负整型数组a[]的前n个元素进行计数排序。

排序时，用temp_arr[i]表示i在数组a中出现的次数，因此可以从0开始按顺序统计每个非负整数在a中的出现次数，

然后对这些非负整数按照从小到大的顺序，结合其出现次数依次排列。

例如，对含有10个元素{0,8,5,2,0,1,4,2,0,1}的数组a[]排序时，先计算出有3个0、2个1、2个2、1个4、1个5和1个8，然后可确定排序后a的内容为{0,0,0,1,1,2,2,4,5,8}。

下面代码中用到的memset函数的原型如下，其功能是将p所指内存区的n个字节都设置为ch的值。

void* memset(void *p, int ch, size_t n);

【C代码】

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define N 101

void printArr(int a[], int n);
void usrSort(int n, int a[]);

int main()
{
	int a[10] = { 0,8,5,2,0,1,4,2,0,1 };

	printArr(a, sizeof(a) / sizeof(int));

	_____（1）_____;          //调用usrSort()对数组a进行升序排序

	printArr(a, sizeof(a) / sizeof(int))

	return 0;

}


void printArr(int a[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d", a[i]);
	printf("\n");
}

void usrSort(int n, int a[])
{
	int i, k;
	int* temp_arr;	//用temp_arr[i]表示i在a中出现的次数
	temp_arr = (int*)malloc(N * sizeof(int));
	if (!temp_arr)return;
	//将所申请并由temp_arr指向的内存区域清零
	memset(_____（2）______);
	for (i = 0; i < n; i++)
		temp_arr[____（3）_____]++;
	k = 0;

	for (i = 0; i < N; i++) {
		int cnt;         //cnt表示i在数组a中的出现次数
		______（4）______;

		while (cnt > 0) {
			a[k] = i;	//将i放入数组a的适当位置
			_____（5）_____;
			cnt--;

		}
	}

	free(temp_arr);

}