25-26-1-计算导论与程序设计-期末（计算机学院-网络空间安全学院-未来学院）

一、选择题（每题2分，共20分）

对于数组 int a[10]，数组名 a 可看作以下那种指针定义 ( )

int * a;

const int * a;

int * const a;

const int * const a;

关于 C 语言结构体和枚举，以下叙述中正确的是 ( )

结构体所占的内存字节数，通常小于或等于结构体中所有成员所占字节数的总和。

枚举抽象的是一组有意义的整数，使用枚举类型值可以增加程序的可读性。

指向结构体的指针所占内存大小，通常要大于指向整型的指针所占内存大小。

相同类型结构体变量之间可以互相赋值和作相等判断。

下列能正确且安全进行字符串赋值操作的语句有几个 ( )
1. char str[6]={'T', 'u', 'r', 'i', 'n', 'g'};
2. char str[6]="Turing";
3. char *str="Turing";
4. char str[7]; str="Turing";

1

2

3

4

C 语言环境下，以下叙述中错误有几个 ( )
1. 函数调用会在栈中创建活动记录，因此子函数内定义的动态数组会在函数调用结束后和活动记录一起被释放。
2. 函数内部定义的动态数组和普通静态数组在不同的存储区分配空间。
3. C 语言函数只有值传递，所以子函数无法通过参数传递改变主函数中实际变量的值。
4. 函数的返回值类型由 return 语句中的表达式类型决定。

1

2

3

4

定义三维数组 int a[7][8][10]，则 a[5][6][7] 与 a[4][3][2] 之间相差 ( ) 个元素

135

115

540

460

以下关于递归的说法中错误的是 ( )

递归算法最外层结构一定是一个选择结构。

递归算法体现了“自顶向下，逐步细化”的思想，能用递归方法解决的问题也可以用迭代方法解决。

递归的书写通常比迭代简洁，但执行效率通常比迭代低。

递归算法比较符合人的思维方式，是一个从初始条件出发逐次调用本身的求解过程。

对于指针 int * q，假定语句 printf("%p", q) 的打印结果为 2345FC。如果内存按照每个字节（Byte）对应一个地址，则该机器 CPU 最小寻址空间为多少字节? ( )

24B

32B

64KB

16MB

下面关于计算机系统的说法中正确的是 ( )

指令和 CPU 无关，不同类型的计算机可以执行相同的指令系统。

数据可以用二进制、八进制或十六进制形式存储在内存中，但指令不能。

正在运行的程序和需要的数据存放在主存，CPU 直接与主存相连，目的是让 CPU 能够快速访问程序和数据。

指令在内存中都有地址，CPU 一定是按照指令地址顺序依次执行的。

使用“冒泡排序”算法对数组 a[]={1, 9, 6, 3, 4} 进行升序排序，元素之间“交换”的次数为 $m$ ；对排序后的数组 a 进行“二分查找”元素 7，元素之间“比较”的次数为 $n$ 。则 $m$ 和 $n$ 分别为 ( )

5, 2

5, 3

10, 3

10, 5

对于一个 5 行 6 列的整数矩阵，可以使用一个二维数组 int a[5][6] 进行存储，也可以使用一个指针数组 int * b[5] 进行存储（数组的每个元素指向一个长度为 6 的动态数组）。假定 a 和 b 存储了同一个矩阵内容，则下面说法错误的是 ( )

*(a[2]+3) 等于 b[2][3]

*(*(a+3)+4) 等于 b[3][4]

&a[1][4]-&a[1][1] 等于 &b[1][4]-&b[1][1]

&a[3][5]-&a[2][3] 等于 &b[3][5]-&b[2][3]

二、函数题（每题100分，共300分）

6-1 字符去重

任意给定一个字符串 str（长度大于 0 且小于 100），该字符串只包含小写字母“a—z”。请你写一个函数把 str 中重复的字符去掉。

输入格式：

只有一行，为一个长度大于 0 且小于 100 且只包含小写字母“a—z”的字符串。代表待去重字符串。测试用例保证合法。

输出格式：

共两行，第一行为一个整数，为被删除字符的个数；第二行为一个字符串，为去重后的字符串。

函数接口定义：

int deduplicate(char *str);

其中 str 是用户传入的参数，为指向待去重字符串的指针。函数需返回删除字符的个数。函数的功能为如果在 str 中某个字符出现了两次或两次以上，则只保留从前向后数第一个出现的字符，且保留下来的字符要保持原有顺序。注意：去重后的字符串仍保存在原来的数组中。

裁判测试程序样例：

#include<stdio.h>

#define        MAXLEN        100

int deduplicate(char *str);

int main()
{
    char    str[MAXLEN];
    int        count;

    scanf("%s" , str);
    count = deduplicate(str);
    printf("%d\n%s\n" , count , str);

    return 0;
}

/* 请在这里填写答案 */

输入样例：

bupttpubuppttt

输出样例：

10
bupt

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

6-2 21点变种一

21 点又名黑杰克（Blackjack），起源于法国，已流传到世界各地，有着悠久的历史。随着互联网的发展，二十一点开始走向网络时代。该游戏由 2 到 6 个人玩，使用除大小王之外的 52 张牌，游戏者的目标是使手中的牌的点数之和不超过 21 点且尽量大。

大家手中扑克点数的计算规则是：2 至 9 牌，按其原点数计算；K、Q、J 和 10 牌都算作 10 点；A 牌（ace）既可算作 1 点也可算作 11 点，由玩家自己决定。当玩家停牌时，点数一律视为最大而尽量不爆（所谓爆了，就是超过 21 点），如 A+9 为 20，A+4+8 为 13，A+3+A 视为 15。

现有一种变种的 21 点，该变种增加新规则如下：一手牌中一定存在某种花色的张数最多，如果该花色的张数超过 3 张，则计算总牌点儿时需加 5；如果该花色没有超过 3 张但超过了 2 张，则计算总牌点儿时需加 2。产生加点儿后一手牌的点数仍然遵循最大且不爆。现请你写一段程序来计算变种规则下一手牌的点数。

输入格式：

共两行，第一行为一个整数 $n(1<n<10)$ ，代表这手牌的张数；第二行是一个长度为 $2\times n$ 字符串，代表 $n$ 张牌。每张牌都是由一个大写字母一个数字组成（大写字母在前），大写字母代表花色（其中 A 代表黑桃、B 代表红桃、C 代表梅花、D 代表方块），数字代表牌面（其中 1 代表 A 牌，2 到 9 依次代表 2 至 9 牌，K、Q、J 和 10 牌均用 0 表示）。测试用例保证合法。

输出格式：

只有一行，为一个整数，代表输入的这手牌的点数。

此题你需要实现两个函数。

函数接口定义一：

CARD * create(int n) ;

其中 n 是用户传入的参数，该函数创建一个长度为 n 的 CARD 类型（见裁判测试程序样例）的动态数组。如果申请内存成功，则函数须返回动态数组第一个元素的地址。否则返回 NULL。

函数接口定义二：

int    getPoints(CARD * deck , int size) ;

其中 deck 和 size 都是用户传入的参数。deck 为指向存储一手牌的数组的指针；size 为数组中元素的个数。函数须返回这手牌的点数。注意，点数是有可能超过 21 点的，此时 A 牌一定按 1 点算。

裁判测试程序样例：

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

#define        SUITS            4        //花色数量
#define        EXTRA_POINTS_2    5        //同色加分2
#define        EXTRA_POINTS_1    2        //同色加分1
#define        THRESHOLD_2        3        //加分门槛2
#define        THRESHOLD_1        2        //加分门槛1

struct card
{
    char    face;
    char    suit;
};

typedef struct card CARD ;

CARD * create(int n) ;
int    getPoints(CARD * deck , int size) ;

int main()
{
    int        i , n;
    CARD    *deck;

    scanf("%d" , &n) ;
    deck = create(n) ;
    if ( deck == NULL )
        return -1 ; //这里的return是因为没有获得内存而直接结束程序。
    getchar();
    for ( i = 0 ; i < n ; i++ )
        scanf("%c%c" ,  &deck[i].suit , &deck[i].face) ;
    printf("%d\n" ,  getPoints(deck , n)) ;

    free(deck);
    return 0;
}


/* 请在这里填写答案 */

输入样例：

3
A1B3C1

输出样例：

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

6-3 新计票方式一

新学期伊始，班级将启动班长选举工作。与往年不同，本次选举采用全新方式，具体规则如下：假设班里共有 $n$ 个同学，每张票只能选一个人；每个人可以投 0 到 $n$ 张票，但不能把票投给重复的人；每个同学投的票都有一个权值，这个权值就是该同学所获得的选票的张数；某位同学的最终分数是所有给他投了票的同学的权值的和，分数最高的当选班长。现请你写一段程序来计算一下每位同学的最终分数。

输入格式：

第一行为一个整数 $n(1<n<=100)$ ，代表同学的总数；这些同学的编号为 0 到 $n-1$ 。后边 $n$ 行，每行代表一位同学获得的选票的情况；其中第 1 行代表 0 号同学的情况，第 2 行代表 1 号同学的情况，依此类推，第 $n$ 行代表 $n-1$ 号同学的情况；每行的格式均为若干用空格分隔的整数，其中第一个整数 $m$ 代表该同学获得的选票的张数，后边 $m$ 个整数为给他投票的同学的编号。测试用例保证合法。

输出格式：

共 $2\times n$ 行，每行一个整数。前 $n$ 行依次为 0 到 $n-1$ 号同学获得的票数，后 $n$ 行依次为 0 到 $n-1$ 号同学的分数。

此题你需要写两个函数来完成。

函数接口定义一：

void points(int *votes , int **students , int num);

其中 votes、students 和 num 都是用户传入的参数。num 是学生的总数；votes 是指向保存所有投票数据的一维 int 型数组的指针；students 指向一个一维 int * 型数组的指针。函数没有返回值。函数的功能是将保存在 votes 所指向数组中的每位同学的信息的首地址保存到 students 所指向的指针数组中。votes 所指向保存所有投票数据的一维 int 型数组的数据格式见裁判测试程序样例。

函数接口定义二：

void count( int **students , int * ranks , int num);

其中 students、ranks 和 num 都是用户传入的参数。num 是学生的总数；students 是指向保存每位同学的信息的首地址的指针数组的指针；ranks 是指向保存每位同学最终的分数数组的指针。函数没有返回值。函数的功能是将每位同学的最终得分依据编号保存在 ranks 所指向的一维 int * 型数组中。

裁判测试程序样例：

#include<stdio.h>

#define        MAX_NUMBER        100        //学生的最多数量

void points(int *votes , int **students , int num);
void count( int **students , int * ranks , int num);

int main()
{
    int        num , numOfVotes , i , j , k = 0;
    int        *students[MAX_NUMBER];        //保存每个学生信息数组首地址的整型指针数组
    int        votes[MAX_NUMBER * (MAX_NUMBER + 1)];    //保存全部数据的整型数组
    int        ranks[MAX_NUMBER];// 保存每个学生的分数值的数组

    //以下代码为输入数据的读入过程。
    //其本质就是将所有num个同学的数据依次保存在一个一维数组votes中。
    scanf("%d" , &num) ;
    for (i = 0 ; i < num ; i++){
        scanf("%d" , &numOfVotes) ;    //读入每个学生获得的选票的张数
        votes[k++] = numOfVotes;
        for(j = 0 ; j < numOfVotes ; j++ , k++){
            scanf("%d" , &votes[k]) ;        //读入每个学生的具体投票人
        }
    }

    points(votes , students , num);
    for (i = 0 ; i < num ; i++)        //依次输出每个学生获得的选票的张数
        printf("%d\n" , students[i][0]) ;
        //函数points执行过后，students中的指针应该指向每个同学的数据的首地址
        //所以其第0个单元即为该同学获得的选票的张数

    count(students , ranks , num);
    for (i = 0 ; i < num ; i++) //依次输出每个学生的分数值
        printf("%d\n" , ranks[i]) ;

    return 0;
}

/* 请在这里填写答案 */

输入样例：

5
5 0 1 2 3 4
4 1 2 3 4
2 0 1
3 2 3 4
3 1 2 3

输出样例：

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

三、编程题（每题100分，共300分）

7-1 订单总价

双十二购物狂欢节是每年 12 月 12 日由淘宝、京东、苏宁易购等电商平台发起的网购促销活动，又称淘宝双十二、京东双十二或苏宁易购双十二，作为双十一购物节的补充，旨在挖掘年底消费潜力。该活动始于 2011 年，最初由淘宝发起，后京东、苏宁等平台跟进。

双十二期间的小伙伴们的状态是超级分裂的：开购物车眼冒金光，加购手速赛抢票，凑满减精过会计，满脑子 “不买血亏”！想象快递堆山的快乐能笑到咧嘴，可结账时瞬间破防。现在就有一份双十二的订单，请你写一段程序来计算一下该订单的总价。

输入格式：

共三行，第一行为一个整数 $n(0<n<100)$ ，代表订单中共 $n$ 种商品。第二行与第三行均为 $n$ 个用空格分隔的正整数，其中第二行的正整数代表订单中每种商品的数量，第三行的正整数与第二行的正整数依次对应，代表每种商品的单价。测试用例保证合法，且包括总价在内的所有整数均可以用 int 存储。

输出格式：

只有一行，为一个整数，代表订单总价。

输入样例：

5
5 5 9 1 30
1 5 8 7 10

输出样例：

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

栈限制 8192 KB

7-2 最大池化

最大池化（max-pooling）即取局部接受域中值最大的点。通俗点儿说其实就是从一堆数里挑最大的那个数。是一种用来“压缩数据、保留关键信息”的简单操作，常常用在图像识别这类需要处理大量数据的场景里。最大池化的具体步骤就是首先把要处理的数据划分成一个个互不重叠的小区域（这个小区域一般叫“池化窗口”）；然后对每个小区域里的所有数字，找出最大的那个数；最后用这个最大值代替原来的小区域，把所有区域的最大值按顺序排列，就得到了池化后的结果。如下图所示：

左边是原始矩阵，右边就是用 $2\times 2$ 大小的池化窗口进行最大池化后得到的矩阵。现就按此规则请你写一段程序来实现最大池化。

输入格式：

第一行为一个整数 $n$ （为大于 0 且小于等于 100 的偶数），代表输入矩阵（一定为方阵）的阶。后边是 $n$ 行，为 $n\times n$ 个整数矩阵，整数间均以一个空格分隔。测试用例保证合法，且所有整数均可以用 int 存储。

输出格式：

共 $n/2$ 行，每行 $n/2$ 个数，每行的每个数均用一个空格分隔。注意行末为换行符，没有空格。代表池化后的结果。

输入样例：

6
1 1 2 4 5 1
5 6 7 8 0 7
3 2 1 0 4 1
1 2 3 4 3 2
8 6 5 3 3 1
1 0 2 1 2 0

输出样例：

6 8 7
3 4 4
8 5 3

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

栈限制 8192 KB

四、主观题

8-1 简答1（8分）

针对 ENIAC 计算机，冯.诺依曼为什么要提出“存储程序”的思想？冯.诺依曼机体系结构有什么特点？

8-2 简答2（7分）

C 语言中 void * p 表示的是“无类型指针”，即 p 所指向的数据类型无法确定。对于无类型指针是否能执行 p++ 操作？给出理由；请解释为什么用于动态数组分配的 malloc 函数返回的也是一个无类型指针。

8-3 简答3（15分）

用户与 AI 的一次对话信息包括如下组成部分：对话编号（整数）、对话名称（字符串，长度不超过 50 个字符）、对话时间（整数）、用户提问列表（由用户所有提问构成，每个提问对应一个字符串，长度由提问内容确定）、AI 回答列表（由 AI 所有回答构成，每个回答对应一个字符串，长度由回答内容确定）。

问题：

请设计一个对话信息的结构体 CHAT，要求包含对话编号（id）、对话名称（name）、对话时间（time）、用户提问列表（questionList）、AI 回答列表（answerList）。要求通过 C 语言的 typedef 语法格式，给出 CHAT 的完整定义。
假定计算机专业共有 10 个班，每个班有 30 名学生，每个学生每天与 AI 的对话次数不确定。使用二维数组存储所有学生一天的对话记录信息，请给出该二维数组 dayRecord 的定义；设有指向该二维数组的指针 p=dayRecord，请给出 p 的定义。
已知函数 getChatNum 的功能为：得到计算机专业所有学生一天中的全部对话次数总和，没有返回值。假定将第 (2) 问中的 dayRecord 作为参数传递给函数，函数调用完后可以得到计算机专业学生一天中的全部对话次数总和（不使用全局变量）。请给出 getChatNum 的函数原型，并说明每个函数参数的含义。

注：答题时先写出每个问题的编号。