初级程序员 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);

}

【解析】

本题考查考生对C程序基本结构、函数定义及调用和运算逻辑的理解和应用。

根据空（1）所在语句的注释，明确是对函数 usrSort 进行调用。usrSort的原型声明为“void usrSort(int n, int a[])”，第一个参数表示需要排序的参数个数，第二个参数表示对哪个数组进行排序，题目中，需要对含有10个元素的数组进行排序，因此空（1）应填入“usrSort(10, a)”或其等效形式。注意：第二个参数需要传入的数组（数组首地址），用数组名或下标为0的数组元素取地址都可以。

空（2）所在语句是调用 memset 对申请的存储区域进行初始化。根据注释，要求将 temp_arr 指向的内存区域清零，根据声明 memset 时的定义，void* memset(void *p, int ch, size_t n);，此处需要对 temp_arr 所指向的空间区域的元素值都设置为0，根据声明 memset 时的形参要求，结合调用 malloc 的实参值 N*sizeof(int)，可知函数调用为 memset(temp_arr, 0, N*sizeof(int))。

空（3）所在的循环语句遍历数组a[]中的所有元素，将元素a[i]作为temp_arr的下标，从而使得temp_arr[a[i]]表示了a[i]表示的值在数组a中出现的次数。

例如：数组a中函数元素1，则需要temp_arr[1]的值+1，数组a中函数元素5，则需要temp_arr[5]的值+1。

空（4）、（5）主要是通过temp_arr中的元素取值情况来对数组a中元素进行重排，假设temp_arr[0]=3，则表示0元素出现了3次。

首先用cnt保留元素出现的次数，可知空（4）处应设置cnt的初始值，为“temp_arr[i]”。

当cnt>0时，表示元素i出现的次数大于等于1次，需要进行循环填入，每在数组中放入1个i元素后，cnt自减（表明还需要放置的次数要减1），而k需要自增（表明元素放置位置要往后一个），以给出下一个i要放入的数组位置，因此空（5）处应填入“k++”或其等效形式。

【答案】

（1）usrSort(10, a)或等效形式，a可替换为&a，&a[0]

（2）temp_arr, 0, N*sizeof(int)或等效形式，其中N可替换为101，sizeof(int)可替换为4。

（3）a[i]或*(a+i)或等效形式

（4）cnt=temp[i]或cnt=*(temp_arr+i)或等效形式

（5）k++或++k或k=k+1或k+=1或等效形式

第4题

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

函数strCompress(char *s)对小写英文字母串进行压缩，其基本思路是：如果串长小于3则不压缩，否则对连续出现的同一字符，用该字符及其个数来表示。

例如，字符串“abbbcdddddddeeed”压缩后表示为“ab3cd7e3d”。

如图4-1所示，在计算连续出现的同一字符个数时，借助字符指针s和计数变量k表示串中的字符，当s所指字符与其后的第k个字符不同时，一个重复字符串的压缩参数即可确定。

【C代码】

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

void strCompress(char*);

int main()
{
	char test[] = "abbbcdddddddeeed";
	printf("%s\n", test);
	__（1）__ //调用strCompress实现test中字符串的压缩
    printf("%s\n", test);
	return 0;
}

void strCompress(char* str)
{
	int i;
	char* p, tstr[11]; //在tstr中以字符串方式表示同一字符连续出现的次数
	char* s = str, * buf; //借助buf暂存压缩后的字符串
	if (strlen(str) < 3)
		return;

	buf = (char*)malloc(strlen(str) * sizeof(char) + 1);

	if (!buf)
		return;

	for (i = 0; *s;){
		int k = 1; //用k累计当前字符的连续出现次数
		buf[__（2）__] = *s; //先将当前字符写入buf[]

		if (s[1] && *s == *(s + 1)) {
			k++;
			while (__（3）__)k++;

			sprintf(tstr, "%d", k); //将k的值转换为数字串暂存在tstr中

			//将暂存在tstr中的数字字符逐个写入buf[]
			p = tstr;
			while (*p)
				buf[i++] = __（4）__;
		}

		s += k; //跳过连续出现的同一字符，使s指向下一个不同的字符
	}

	__（5）__ = '\0'; //设置字符串结尾
	strcpy(str, buf); //将暂存在buf中的压缩字符串复制给原串
	free(buf);

}