当前位置：首页 > news >正文

【C语言16天强化训练】从基础入门到进阶：Day 15

news 2025/8/30 7:10:53

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题、洛谷刷题、C/C++基础知识知识强化补充、C/C++干货分享&学习过程记录

🍉学习方向：C/C++方向学习者

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

前言：距离我们学完C语言已经过去一段时间了，在学习了初阶的数据结构之后，博主还要更新的内容就是【C语言16天强化训练】，之前博主更新过一个【C语言刷题12天IO强训】的专栏，那个只是从入门到进阶的IO模式真题的训练。【C语言16天强化训练】既有IO型，也有接口型。和前面一样，今天依然是训练五道选择题和两道编程算法题，希望大家能够有所收获！

一、五道选择题

1.1 题目1

1.2 题目2

1.3 题目3

1.4 题目4

1.5 题目5

二、两道算法题

2.1 寻找奇数

2.1.1 题目理解

2.1.2 思路

2.1.3 异或思路的两种C语言实现方式

2.1.3.1 方式1

2.1.3.2 方式2

2.1.4 C++实现

2.2 寻找峰值

2.2.1 题目理解

2.2.2 思路

2.2.3 C语言实现的不同方式

2.2.3.1 方式1

2.2.3.2 方式2

2.2.3.3 方式3

2.2.3.4 方式4

2.2.4 C++实现

结尾

一、五道选择题

1.1 题目1

题干：有如下代码，则 *(p[0]+1) 所代表的数组元素是（）

int a[3][2] = {1, 2, 3, 4, 5, 6}, *p[3];
p[0] = a[1];

A. a[0][1] B: a[1][0] C. a[1][1] D. a[1][2]

解析：正确答案就是C选项。

p是一个指针数组，p[0] = a[1];此处a[1]是二维数组的第二行的数组名，数组名表示首元素的地址，a[1]是a[1][0]的地址，所以p[0]中存储的是第2行第1个元素的地址，p[0]+1就是第二行第2个元素的地址，*(p[0]+1)就是第二行第二个元素了。所以C正确。

1.2 题目2

题干：关于指针下列说法正确的是（）【多选】

A. 任何指针都可以转化为void* B. void *可以转化为任何指针

C. 指针的大小为8个字节 D. 指针虽然高效、灵活但可能不安全

解析：正确答案就是ABD选项。

C选项，指针占几个字节要看平台，64位环境下8个字节，32位环境下4个字节。

1.3 题目3

题干：以下 scanf 函数调用选项中，错误的是（）

struct T
{char name[20];int age;int sex;
} a[5], *pa=a;

A. scanf("%s",a[0].name); B. scanf("%d", &pa[0].age);

C. scanf("%d",&(pa->age)); D. scanf("%d", pa->age);

解析：正确答案就是D选项。

该题考察的是通过scanf函数的调用对结构体数据类型进行初始化。scanf("输入控制符", 输入参数);功能：将从键盘输入的字符转化为“输入控制符”所规定格式的数据，然后存入以输入参数的值为地址的变量中。scanf输入时要通过地址找空间， B、C用了&是正确的。name属于字符数组的数组名，相当于数组的首地址，A正确。单独的pa->age可用于输出语句获取值的形式，用在scanf中的时候需要&操作符，D错误。

1.4 题目4

题干：如下函数 fun 计算 prod=1*2*3*…*n ，并返回计算结果值。但当 n>12 时，返回值不正确。要找出该程序的错误，正确的调试方法是（）

int fun(int n)
{int prod = 1 , i = 0;for(i = 1;i <= n;i++){prod *= i;} return prod;
}

A. 监视变量prod的值，在prod *= i;行处设置断点，然后单步运行，直到发现错误原因

B. 监视变量prod的值，在return prod;行处设置断点，程序中断后，即可发现错误原因

C. 在prod=1;处设置断点，然后在函数调用堆栈中即可发现错误原因

D. 监视变量i的值，在for (i=1; i<=n; i++)行处设置断点，然后单步运行，直到发现错误原因

解析：正确答案就是A选项。

依题目已知情况，当n<=12时结果是正确的，说明是随着参数的变大计算过程中哪里出了问题，故而要在prod *= i;处设断点，查看原因。错误原因是数据过大时整型溢出。

1.5 题目5

题干：下列给定程序中，函数 fun 的功能是：把形参a所指数组中的奇数按原顺序依次存放到a[0]、a[1]、a[2]…中，把偶数从数组中删除，奇数个数通过函数值返回。例如，若a所指数组中的数据最初排列为： 9,1,4,2,3,6,5,8,7 ，删除偶数后，a所指数组中的数据为： 9,1,3,5,7 ，返回值为5。请在程序的下画线处填入正确的内容并将下画线删除，使程序得出正确的结果（）

int fun(int a[], int n)
{int i, j;j = 0;for(i = 0; i < n; i++)if (a[i]%2== _________ ){a[j]=a[i];_________;} return _________;
}

A. 0 j++ j B. 1 j++ j+1 C. 0 j++ j+1 D. 1 j++ j

解析：正确答案就是D选项。

代码实现的思路应该是arr[i]是奇数的时候要存储起来，所以第一个空是1，最开始j是0，每次找到一个奇数就存储到arr[j]的位置，那接下里j需要+1，所以得第二个空是j++，当循环停止的时候，j其实就是奇数的个数。所以最后返回j，第三个空是j。所以选D。

选择题答案如下：

1.1 C

1.2 ABD

1.3 D

1.4 A

1.5 D

校对一下，大家都做对了吗？

二、两道算法题

2.1 寻找奇数

牛客网链接：REAL204 寻找奇数

题目描述：

2.1.1 题目理解

给定一个正整数序列，其中只有一个数值出现了奇数次，其他所有数值都出现了偶数次，要求找出这个出现奇数次的数值。

2.1.2 思路

异或：二进制比特位相同则0，不同则1。

两个相同的数字异或得到的是0，基于这个思路，这道题对数组中的所有数据进行逐一异或就可以解决得到奇数次的数字，因为偶数次的数字都被异或成为0了，最后单独保留了奇数次的数字。

2.1.3 异或思路的两种C语言实现方式

这道题是IO型的，下面是C语言的模版（如果是IO型就可以不用管它们了）——

2.1.3.1 方式1

代码演示：

#include <stdio.h>
int main()
{int n;while (~scanf("%d", &n)) {int num = 0, tmp = 0;//对每个数字进行异或，出现偶数次的就会异或为0了，而奇数次刚好剩下的就是对应数字for (int i = 0; i < n; i++) {scanf("%d", &tmp);num ^= tmp;}printf("%d\n", num);} return 0;
}

时间复杂度：O(n)；

空间复杂度：O(1)。

2.1.3.2 方式2

代码演示：

//C语言——异或
#include <stdio.h>int main()
{int n;scanf("%d", &n);int result = 0;for (int i = 0; i < n; i++){int num;scanf("%d", &num);result ^= num;}printf("%d\n", result);return 0;
}

时间复杂度：O(n)；

空间复杂度：O(1)。

2.1.4 C++实现

我们学习了C++之后也可以尝试用C++来实现一下，看看自己前段时间C++学得怎么样——

代码演示：

//C++实现
#include <iostream>
using namespace std;int main()
{int n;cin >> n;int result = 0;for (int i = 0; i < n; i++){int num;cin >> num;result ^= num;}cout << result << endl;return 0;
}

时间复杂度：O(n)，空间复杂度：O(1)。

我们目前要写出来C++的写法是非常考验前面C++的学习情况好不好的，大家可以尝试去写一写，优先掌握C语言的写法，博主还没有介绍C++的算法题，之后会涉及的，敬请期待！

2.2 寻找峰值

牛客网链接：NC107 寻找峰值

题目描述：

2.2.1 题目理解

题目要求：需要在数组中找到任意一个峰值索引，要求时间复杂度 O(logN)。

在给定的数组中找到任意一个峰值元素的索引。峰值元素是指其值严格大于左右相邻元素（假设数组边界外的元素为负无穷）。由于数组可能包含多个峰值，返回任意一个即可。并且要求使用 O(logN) 的时间复杂度。

2.2.2 思路

使用二分查找：

（1）如果中间元素大于右侧元素，说明峰值在左侧（包括中间）；

（2）否则峰值在右侧。

由于题目要求 O(logN) 的时间复杂度，我们考虑使用二分查找。虽然数组不是完全有序的，但我们可以利用峰值的特点：如果中间元素大于其下一个元素，则峰值可能在左半部分（包括中间元素本身）；否则，峰值可能在右半部分。这是因为如果nums[mid] > nums[mid+1]，那么左边必然存在一个峰值（因为最左边是负无穷），同理右边也是如此。

2.2.3 C语言实现的不同方式

这道题是接口型的，下面是C语言的模版（如果是IO型就可以不用管它们了）——

2.2.3.1 方式1

其实这里是两种写法，但是大差不差，基本上差不多，所以就归类到同一种实现方式里面。

代码演示：

//C语言实现——自测示例1有误，2通过
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型*/
int findPeakElement(int* nums, int numsLen) {int left = 0, right = numsLen - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > nums[mid + 1]){right = mid; // 峰值在左半部分，包括mid}else{left = mid + 1; // 峰值在右半部分}}return left;
}//C语言实现——自测示例1有误，2通过——和上面的实现本质上一样
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型*/
int findPeakElement(int* nums, int numsLen) {int left = 0, right = numsLen - 1;while (left < right) {int mid = left + (right - left) / 2;// 如果mid比右边小，说明峰值在右边if (nums[mid] < nums[mid + 1]) {left = mid + 1;}// 否则峰值在左边（包括mid本身）else {right = mid;}}return left;
}

时间复杂度：O(logn)；

空间复杂度：O(1)。

2.2.3.2 方式2

代码演示：

//C语言实现——最简洁——通过示例2
int findPeakElement(int* nums, int numsLen) {int left = 0;int right = numsLen - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[mid + 1]) {right = mid;}else {left = mid + 1;}}return left;
}

时间复杂度：O(logn)；

空间复杂度：O(1)。

2.2.3.3 方式3

代码演示：

//C语言实现——自测示例1有误，2通过——和上面的实现本质上一样
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型*/
int findPeakElement(int* nums, int numsLen) {// 处理只有一个元素的情况if (numsLen == 1) return 0;// 检查第一个元素是否是峰值（大于右边，左边是-∞）if (nums[0] > nums[1]) return 0;// 检查最后一个元素是否是峰值（大于左边，右边是-∞）if (nums[numsLen - 1] > nums[numsLen - 2]) return numsLen - 1;// 二分查找内部峰值int left = 1, right = numsLen - 2;while (left <= right) {int mid = left + (right - left) / 2;// 找到峰值if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {return mid;}// 如果处于上升趋势，峰值在右侧if (nums[mid] < nums[mid + 1]) {left = mid + 1;}// 如果处于下降趋势，峰值在左侧else {right = mid - 1;}}return -1; // 理论上不会执行到这里
}

时间复杂度：O(logn)；

空间复杂度：O(1)。

2.2.3.4 方式4

暴力破解：

遍历数组，从[1，n-1]号位置开始，哪个位置的数据大于上一个数据和下一个数据即可。

更优思想：二分思想

中间比右边大，认为从右往左半边递增，则把 right 不断向左靠拢 right=mid ，注意不能是 mid-1 ，因为这个位置有可能就是峰值点。

直到遇到中间比右边小了，意味着数据开始递降了，则 left 向右偏移， left=mid+1 ; 而一旦 mid+1 位置大于了right ，意味着刚好这个 mid+1 位置，是一个左半边-右往左递降，右半边-右往左递增的点，就是一个峰值点。

这个方式我们从示例来看——

int arr[] = {3, 5, 4, 4, 3, 2, 1} , 这个数组中两边边界都是非峰值点int left = 0, right = 6;

left=0,right=6,mid=3: arr[3]=4 > arr[4]=3, 则right = mid = 3; //从右往左是递增的left=0,right=3,mid=1: arr[1]=5 > arr[2]=4, 则right = mid = 1; //从右往左是递增的left=0,right=1,mid=0: arr[0]=3 < arr[1]=5, 则left = mid + 1 = 1; //从右往左开始递降了left > right 退出循环，返回left，也就是1号下标位置。

代码演示：

//C语言——示例2
int findPeakElement(int* nums, int numsLen) {//边界情况处理，1个元素前后都是负无穷 以及 0号位置大于1号位置，-1位置负无穷的情况if (numsLen == 1 || nums[0] > nums[1]) return 0;//末尾位置数据大于上一个位置数据，而nums[numsLen]负无穷的情况if (nums[numsLen - 1] > nums[numsLen - 2]) return numsLen - 1;int left = 0, right = numsLen - 1, mid;while (left < right) {mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1])//中间比右边小，意味着右边肯定有个峰值left = mid + 1;else //否则在左边包括当前位置肯定有个峰值right = mid;} return left;
}

时间复杂度：O(logn)；

空间复杂度：O(1)。

这道题是特殊输入，只要两个示例有一个通过，你手动输入能够通过的那个示例，就能过了，博主发现：C语言无论如何都只有一个示例——而且都是示例2——能够通过，其他示例都通不过，C++的实现倒是有两全其美的实现方式，但C语言博主做不到，所以博主C语言的每一种实现都会展示在【代码演示】，大家帮博主想想，有没有两全其美的实现方式？

2.2.4 C++实现

我们学习了C++之后也可以尝试用C++来实现一下，看看自己前段时间C++学得怎么样——

代码演示：

//C++实现——全部通过
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param nums int整型vector* @return int整型*/int findPeakElement(vector<int>& nums) {int n = nums.size();if (n == 1) return 0;// 检查边界情况if (nums[0] > nums[1]) return 0;if (nums[n - 1] > nums[n - 2]) return n - 1;// 二分查找内部峰值int left = 1, right = n - 2;while (left <= right) {int mid = left + (right - left) / 2;// 检查mid是否是峰值if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {return mid;}// 根据趋势决定搜索方向if (nums[mid] < nums[mid + 1]) {left = mid + 1;}else {right = mid - 1;}}return -1;}
};