初级程序员 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对应公式中的x_n，x2对应公式中的x_n+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;
};

【C代码】

【解析】

本题考查C程序流程控制和指针的应用。

函数createList()中首先创造链表的第一个结点。

然后通过循环来创建其余n-1个结点。

显然，创建第一个结点后，该结点是表尾结点，因此空（1）处应填入“tail”，来设置表尾指针。

通过运算p->next=p，形成只有1个结点的单循环链表，如下图所示。

对于for循环中创建的每一个结点（p所指），首先通过运算p->key=a[i]设置其数据域的值，因此空（2）处应填入“p->key”或其等效形式，如下图（a）所示，

然后设置新结点的指针域（p->next），使其指向第一个结点（tail->next所指），即p->next=tail->next，如下图（b）所示，

再将结点链接进入链表，即tail->next=p，如下图（c）所示，最后更新表尾指针，即tail=p。因此空（3）处应填入“p->next”。

函数display(NodePtr tail)输出链表中结点数据域的值，参数为表尾指针。

当链表为空时，该函数可以直接结束，因此空（4）处通过tail指针进行判断，应填入“tail==NULL”或其等效形式。

该函数中通过变量p遍历链表中的结点，因此空（5）处需要修改p，使其指向下一个结点，应填入“p->next”。

【答案】

（1）tail

（2）p->key 或 (*p).key 或等效形式

（3）p->next 或 (*p).next 或等效形式

（4）!tail 或 tail==NULL 或等效形式

（5）p->next 或 (*p).next 或等效形式

#include<stdio.h>
#include<malloc.h>

typedef struct Node* NodePtr;
struct Node {
	int key;
	NodePtr next;
};

NodePtr createList(int a[], int n) //根据数组a的前n个元素创建单循环链表
{ 
	NodePtr tail = NULL, p;
	if (n < 1) return NULL;
	p = (NodePtr)malloc(sizeof(struct Node)); //创建第一个结点
	if (!p) return tail;

	p->key = a[0];
	p->next = p;
    tail = p;

	for (int i = 1; i < n; i++) //创建剩余的 n -1 个结点
	{ 
		p = (NodePtr)malloc(sizeof(struct Node));
		if (!p) break;
		p->key = a[i]; //或 (*p).key 或等效形式
		p->next = tail->next; //或 (*p).next 或等效形式
		tail->next = p;
		tail = p;
	}

	return tail;
}

void display(NodePtr tail) //从表头元素开始依次输出单循环链表中结点数据域的值
{
	if (!tail) return; //或 tail == NULL 或等效形式
	NodePtr p = tail->next;
	do {
		printf("%d\t", p->key);
		p = p->next; //或 (*p).next 或等效形式
	} while (p != tail->next);
}

int main() {
	int a[] = { 25,12,39 };
	NodePtr tail;
	tail = createList(a, 3);
	display(tail); //输出 25 12 39
	return 0;
}

第5题

案例题：

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

【说明】

在线购物系统需要提供订单打印功能，相关类及关系如图5-1所示，其中类Order能够完成打印订单内容的功能，

类HeadDecorator与FootDecorator分别完成打印订单的抬头和脚注的功能。

【Java代码】

【答案】

（1）extends

（2）this.order

（3）super(order);

（4）super(order);

（5）super.printOrder();

（6）extends

（7）this.order

【解析】

本题考查Java语言程序设计的能力，涉及类、对象、方法的定义和相关操作。

要求考生根据给出的案例和代码说明，阅读并完成程序填空。

本题目中涉及打印订单内容、打印抬头和打印脚注。根据说明进行设计，题目给出了类图（图5-1类图所示）。

图中类Order有PrintOrder和Decorator两个子类。Decorator与Order之间是聚合关系。

Decorator有两个子类，HeadDecorator和FootDecorator，分别实现打印抬头和打印脚注的功能。

Java语言中，子类继承父类采用关键字extends实现。Order类中定义printOrder()方法，实现打印“订单内容”。

Decorator中定义有Order类型成员order，即：

private Order order;

并且定义带参数构造器：

    public Decorator(Order order) {
        this.order=order;
    }

其中对order进行初始化。

Java中，一个类有显式定义带参数构造器，那么编译器就不会自动生成缺省的构造器，而子类构造器中首先调用父类的构造器，缺省的情况下调用父类的缺省无参数构造器，带参数构造器需要显示调用，形式为super(参数)。

对象的属性若为引用类型，自动初始化为null，所以需要在构造器中对order加以显式初始化。

其构造器接收order，参数名称与对象的属性名均为order，需要用this关键字来引用当前对象或类实例，可以用点取属性或行为，即：

this.order=order;

Decorator覆盖父类的printOrder()方法。在printOrder()方法中，order不为空引用时，用order.printOrder()调用Order的printOrder()方法，实现打印“订单内容”；

而若order为空时，则不进行调用，即没有打印订单内容。

HeadDecorator类和FootDecorator类中均定义带Order类型参数的构造器。

在Java中，构造器中自动调用父类中的缺省无参数构造器，而Decorator中只定义了带参数构造器，因此，需要显式调用父类Decorator中的构造器，形式为：super(参数)，即super(order)，对Decorator中私有成员order进行初始化。

HeadDecorator覆盖父类printOrder()方法。在printOrder()方法中，先打印“订单抬头”，再使用super.printOrder()调用父类的printOrder()方法打印“订单内容”。

FootDecorator覆盖父类的printOrder()方法。在printOrder()方法中，先使用super.printOrder()调用父类的printOrder()方法打印“订单内容”，再打印“订单脚注”。

在PrintOrder类中，实现整体订单的打印逻辑。其中定义Order成员变量order，构造器PrintOrder(Order order)中对order进行初始化，因为参数名称也是order，所以需要采用this.order区分对象的属性。

在printOrder()方法中，实现的主要逻辑为打印“订单内容”的基础上，加上打印“订单抬头”和“订单脚注”。

此时，order对象不为null时只可以打印“订单内容”，再执行如下语句：

FootDecorator foot = new FootDecorator(order);

实现在打印“订单内容”的基础上，加上打印“订单抬头”，再执行如下语句：

HeadDecorator head = new HeadDecorator(foot);

实现在打印“订单内容”和“订单抬头”的基础上，加上打印“订单脚注”。 此时，head.printOrder()调用执行printOrder()方法即可打印出：

订单抬头！
订单内容！
订单脚注！

若order对象为null时，则只打印出“订单抬头”和“订单脚注”。

入口方法main()定义在PrintOrder类中。

在main()方法中，先创建Order类的对象order，并作为参数传递给PrintOrder的构造器进行对象的创建，名称为print，之后print.printOrder()即调用PrintOrder中的printOrder()方法，执行主要打印逻辑。即：

        Order order = new Order();
        PrintOrder print= new PrintOrder(order);
        print.printOrder();

综上所述，空（1）和空（6）表示继承Order类，即extends；

空（2）需要表示Decorator对象的order属性，即this.order；

空（3）和空（4）需要显式调用父类的Decorator的带参数构造器，参数为order，即super(order)；

空（5）处调用父类对象的printOrder()方法，即super.printOrder()；

空（7）需要表示PrintOrder对象的order属性，即this.order。

【代码】

class Order{
    public void printOrder(){
        System.out.println("订单内容");
    }
}

class Decorator extends Order {
    private Order order;

    public Decorator(Order order) {this.order=order;}

    public void printOrder(){
        if (order != null)
            order.printOrder();
    }
}

class HeadDecorator extends Decorator {

    public HeadDecorator(Order order){
        super(order);
    }

    public void printOrder(){
        System.out.println("订单抬头！");
        super.printOrder();
    }
}

class FootDecorator extends Decorator {
    public FootDecorator(Order order) { super(order);}
    public void printOrder(){
        super.printOrder();
        System.out.println("订单脚注！");
    }
}

class PrintOrder extends Order {
    private Order order;

    public PrintOrder(Order order){this.order=order;}

    public void printOrder(){
        FootDecorator foot = new FootDecorator(order);
        HeadDecorator head = new HeadDecorator(foot);
        head.printOrder();
        System.out.println("----------------------------");
        FootDecorator foot1 = new FootDecorator(null);
        HeadDecorator head1 = new HeadDecorator(foot1);
        head1.printOrder();
    }

    public static void main(String[] args) {
        Order order = new Order();
        PrintOrder print= new PrintOrder(order);
        print.printOrder();
    }
}

第6题

案例题

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

【说明】

在线购物系统需要提供订单打印功能，相关类及关系如图6-1所示，其中类Order能够完成打印订单内容的功能，类HeadDecorator与FootDecorator分别完成打印订单的抬头和脚注的功能。

下面的C++代码应实现上述设计，其执行结果如下：

订单抬头！
订单内容！
订单脚注！
------------------------
订单抬头！
订单脚注！

【C++代码】

【解析】

本题考查C++语言程序设计的能力，设计类、对象、函数的定义和相关操作。

要求考生根据给出的案例和代码说明，阅读并完成程序填空。

本题目中涉及打印订单内容、打印抬头和打印脚注。

根据说明进行设计，题目给出了类图（图6-1类图所示）。

图中类Order有PrintOrder和Decorator两个子类。

Decorator与Order之间为聚合关系。

Decorator有两个子类HeadDecorator和FootDecorator，分别实现打印抬头和打印脚注的功能。

C++语言中，子类继承父类使用冒号（:）加父类实现。Order类中定义虚函数virtual void printOrder()方法，实现打印“订单内容”。

Decorator中定义私有Order成员，即：

private: Order* order;

并且定义带参数构造器：

public :
	Decorator(Order* order) {
		this->order = order;
	}

其中对order进行初始化。

C++中，一个类有显示定义带参数构造器时，编译器就不会自动生成缺省的构造器，而子类构造器中首先调用父类的构造器，缺省的情况下调用父类的缺省不带参数构造器，带参数构造器显式调用，形式为冒号（:）加上父类的带参数构造器。

对象的属性若为引用类型，自动初始化为NULL，所以需要在构造器中对order加以显式初始化。

其构造器接收order，参数名称与对象的属性名均为order，需要用this关键字引用当前对象或类实例，可以用this->或(*this).取属性或行为，即：

this->order = order; //或 (*this).order = order;

Decorator覆盖父类的printOrder()方法。

在printOrder()方法中，实现order不为空引用时，采用order->printOrder()调用Order的printOrder()方法，实现打印“订单内容”；

而若order为空时，则不进行调用，即没有打印订单内容。

HeadDecorator类和FootDecorator类中均定义带Order类型的参数的构造器。

在C++中，构造器中自动调用父类的缺省无参构造器，而Decorator中只定义了带参数构造器，因此需要显式调用父类Decorator中的带参数构造器，形式为：构造器名(参数)，即Decorator(order)，对Decorator中私有成员order进行初始化。

HeadDecorator覆盖父类的printOrder()方法。在printOrder()方法中，先打印“订单抬头”，再使用Decorator::printOrder()调用父类的printOrder()方法打印“订单内容”。

FootDecorator覆盖父类的printOrder()方法。在printOrder()方法中，先使用Decorator::printOrder()调用父类的printOrder()方法打印“订单内容”，再打印“订单脚注”。

在PrintOrder类中，实现整体订单的打印逻辑。

其中定义Order属性变量order，构造器PrintOrder(Order order)中对order进行初始化，因为参数名称也是order，所以需要采用this->order或(*this).order区分对象的属性。

在printOrder()方法中，实现的主要逻辑为打印“订单内容”基础上，加上打印“订单抬头”和“订单脚注”。

此时，order对象不为NULL时只可以打印“订单内容”，再执行如下语句：

FootDecorator* foot = new FootDecorator(order);

实现在打印“订单内容”的基础上，加上打印“订单抬头”，再执行如下语句：

HeadDecorator* head = new HeadDecorator(foot);

实现在打印“订单内容”和“订单抬头”的基础上，加上打印“订单脚注”。 此时，head->printOrder()调用执行printOrder()方法即可打出：

订单抬头！
订单内容！
订单脚注！

若order对象为NULL时，则只打印出“订单抬头”和“订单脚注”。 入口函数main()中，先用new关键字创建Order类的对象，即对象指针order，并作为参数传递给PrintOrder的构造器进行创建PrintOrder对象，即对象指针print，之后print->printOrder()即调用PrintOrder中的printOrder()方法，执行主要打印逻辑。即：

	Order *order = new Order();
	Order *print = new PrintOrder(order);
	print->printOrder();

综上所述，空（1）和空（6）表示继承Order类，即:public Order；

空（2）需要表示Decorator对象的order属性，即this->order或(*this).order；

空（3）和空（4）需要显式调用父类Decorator的带参数构造器，参数为order，即Decorator(order)；

空（5）处调用父类对象的printOrder()方法，即 Decorator::printOrder()；

空（7）需要表示printOrder对象的order属性，即this->order或(*this).order。【答案】

（1）: public Order

（2）this->order或(*this).order

（3）Decorator(order)

（4）Decorator(order)

（5）Decorator::printOrder()

（6）: public Order

（7）this->order或(*this).order

【代码】

#include<iostream>
using namespace std;

class Order {
public:
	virtual void printOrder() {
		cout << "订单内容！" << endl;
	}
};

class Decorator : public Order {
private: Order* order;
public :
	Decorator(Order* order) {
		this->order = order;
	}

	void printOrder() {
		if (order != NULL)
			order->printOrder();
	}

};

class HeadDecorator : public Decorator {
public:
	HeadDecorator(Order* order) :Decorator(order) {}
	
	void printOrder() {
		cout << "订单抬头！" << endl;
		Decorator::printOrder();
	}
};

class FootDecorator :public Decorator {
public:
	FootDecorator(Order* order) :Decorator(order) {}

	void printOrder() {
		Decorator::printOrder();
		cout << "订单脚注！" << endl;
	}
};

class PrintOrder :public Order {
private: Order *order;

public:
	PrintOrder(Order* order) { this->order = order; }

	void printOrder() {
		FootDecorator* foot = new FootDecorator(order);
		HeadDecorator* head = new HeadDecorator(foot);
		head->printOrder();
		cout << "----------------------" << endl;
		FootDecorator foot1(NULL);
		HeadDecorator head1(&foot1);
		head1.printOrder();

	}
};

int main() {
	Order* order = new Order();
	Order* print = new PrintOrder(order);
	print->printOrder();
}