初级程序员 2020年 下半年 下午
第1题
下面流程图所示算法的功能是：在一个二进制位串中，求出连续的“1”构成的所有子串的最大长度M。
例如，对于二进制位串0100111011110，M=4。
该算法中，将长度为n的二进制位串的各位数字，按照从左到右的顺序依次存放在数组A[1..n]。
在对各个二进制位扫描的过程中，变量L动态地记录连续“1”的个数。
答案：
（1）0
（2）L+1或等效形式
（3）0→L或等效形式
（4）L>M或L≥M或等效形式
（5）M
解析：
本流程图采用的算法是对二进制位串从左到右进行逐位判断，并累计连续遇到数字1的个数L，再以动态地得到当前L的最大值M。
初始时，L和M都应该是0，故初值为0，因此，流程图的空（1）处应填0。
接着开始对i=1，2，...，n循环，一次判断二进制数位A[i]是否为1。
如果A[i]=1，就应该将L增1，即执行L+1→L，因此流程图的空（2）处应填L+1；
如果A[i]=0，则应该将数字1的累计长度L清0，重新开始累计，因此，流程图的空（3）处应填0→L。
当遇到数字L进行累计后，应将L与现行的擂台值M进行比较。
如果L>M，则显然应该以新的L值代替原来的M值，即执行L→M；
如果L<M，则不能更新M值；
如果L=M，则可以更新也可以不更新M值，对计算结果没有影响。
为此，流程图的空（4）处可填L>M或L≥M（填前者更好），而空（5）处应填M。
第2题
阅读以下说明和C代码，填补C代码中的空缺，将解答写在答题纸的对应栏内。
【说明】
答案：
（1）fabs(x)<=1e-6
（2）x2
（3）x/(x1*x1)
（4）(x2-x1)/x1
（5）x+=0.1
解析：
本题考查C程序基本运算和流程控制的应用。
函数cubeRoot(x)根据给定的公式计算x的立方根。
根据精度要求，绝对值小于1e-6的数，其立方根为0，因此，空（1）处填入“fabs(x)<=1e-6”或其等效形式。
分析函数cubeRoot中的代码，可知x1对应公式中的xn，x2对应公式中的xn+1，每次循环时，需要将x2传给x1，再计算出新的x2，因此空（2）处应填入“x2”，
空（3）处应填入“x/(x1*x1)”。
在满足精度要求时结束循环，即空（4）处应填入“(x2-x1)/x1”。
根据题干部分的说明，显然空（5）处应填入“x+=0.1”或其等效形式。
#include<stdio.h>
#include<math.h>
/*
*
*/
double cubeRoot(double x) {
double x1, x2 = x;
printf("x1=%f, x2=%f", x1, x2);
if (fabs(x) <= 1e-6) return 0.0;
do {
x1 = x;
x2 = (2.0 * x1 + x / x1 * x1);
} while ( fabs( (x2 - x1) / x1 ) >= 1e-6 );
return x2;
}
int main()
{
double x;
for (x = -8.0; x <= 8.0; (x += 0.1))
printf("cube_root(%.1f)=%.4f\n", x, cubeRoot(x));
return 0;
}
另：现在“double x1, x2 = x;”这种语法编译会报错：
应该是应用了不同的C语言标准的原因。
“double x1, x2 = x;”中，x1的默认初始值应该是0.000000。
第3题
阅读以下说明和C代码，填补C代码中的空缺，将解答写在答题纸的对应栏内。
【说明】
下面程序中，函数 convertion(char *p) 的功能是通过调用本程序中定义的函数，将p所指示字符串中的字母和数字字符按如下约定处理：
（1）大写字母转换为小写字母；
（2）小写字母转换为大写字母；
（3）数字字符转换为其伙伴字符（当两个十进制数字相加为9时，这两个十进制数字对应的数字字符互为伙伴字符）。
例如，字符‘2’的伙伴字符为‘7’，‘8’的伙伴字符为‘1’、‘0’的伙伴字符为‘9’等。
【C代码】
【解析】：
观察代码中定义的函数，isUpper(char c)、isLower(char c)、isDigit(char c) 的形参为传值方式的字符型参数，
调用这些函数时实参为字符变量或常量。
toUpper(char *c)、toLower(char *c)、cDigit(char *c)、convertion(char *p) 的形参为字符指针类型，
调用调用这些函数时实参应为指向字符的指针（字符变量的地址）。
根据题干部分的描述，求解数字字符的伙伴字符时，需要进行算术运算，
用9减去数字字符对应的数值（即数字字符-'0'），得到的值再加上'0'从而再次转换为数字字符，因此空（1）处应填入“*c-'0'”或其等效形式。
函数convertion(char *p)根据题干描述的要求对字符进行转换，满足空（2）所给的条件时需要调用toLower(p)将字符转换为小写字母，
因此空（2）处应判断字符是否为大写字母，应填入“isUpper(*p)”或其等效形式。
满足空（3）所给的条件时需要调用toUpper(p)将字符转换为大写字母，因此空（3）处应判断字符是否为小写字母，应填入“isLower(*p)”或其等效形式。
满足空（4）所给的条件时需要调用cDigit(p)将数字字符转换为其伙伴字符，因此空（4）处应判断字符是否为数字字符，应填入“isDigit(*p)”或其等效形式。
在while循环中还需要对指针变量p进行递增，处理完p指向的当前字符后再指向下一字符，因此空（5）处应填入“p++”或其等效形式。
【答案】：
（1）*c-'0'或c[0]-'0'或*c-48或c[0]-48或等效形式
（2）isUpper(*p)或isUpper(p[0])
（3）isLower(*p)或isLower(p[0])
（4）isDigit(*p)或isDigit(p[0])
（5）p++或++p或p=p+1或p+=1或等效形式
#include<stdio.h>
int isUpper(char c) { //判断c表示的字符是否为大写字符
return (c >= 'A' && c <= 'Z');
}
int isLower(char c) { //判断c表示的字符是否为小写字母
return (c > 'a' && c <= 'z');
}
int isDigit(char c) { //判断c表示的字符是否为数字字符
return (c>='0' && c<= '9');
}
void toUpper(char *c) { //将c指向的小写字母转换为大写字母
*c = *c - 'a' + 'A';
}
void toLower(char* c) { //将c指向的大写字母转换为小写字母
*c = *c - 'A' + 'a';
}
void cDigit(char* c) { //将c指向的数字字符转换为其伙伴字符
*c = 9 - (*c - '0') + '0'; //或c[0]-'0'或*c-48或等效形式
}
void convertion(char *p) {
while (*p) {
if (isUpper(*p)) { //或 isUpper(p[0])
toLower(p);
}
else if (isLower(*p)) { //或isLower(p[0])
toUpper(p);
}
else if (isDigit(*p)) { //isDigit(p[0])
cDigit(p);
}
p++; //或++p或p=p+1或p+=1或等效形式
}
}
int main() {
char str[81] = "Aidf3F4";
printf("%s\n", str); //输出为Aidf3F4
convertion(str);
printf("%s\n", str); //输出为aIDF6f5
return 0;
}
第4题
阅读以下说明和C代码，填补C代码中的空缺，将解答写在答题纸的对应栏内。
【说明】
函数 createList(int a[], int n) 根据数组a的前n个元素创建对应的单循环链表，并返回链表的尾结点指针。
例如，根据数组int a[]={25,12,39}创建的单循环链表如图4-1所示。
函数display(NodePtr tail)的功能是从表头元素开始，依次输出单循环链表中结点数据域的值。 链表的结点类型定义如下：
typedef struct Node* NodePtr;
struct Node {
int key;
NodePtr next;
};