2024真题还原
25 真题分析总结
今年的科目代码虽然从981变成了859，但考试范围并未发生变化，仅题型发生了改变。之前981对C++、数据结构分别进行考察，整体也分为两部分， 而859则是更加综合地考察了同学们的能力，在各类题型中都有对两门的知识的考察，从形式上来讲更加灵活，同时题目风格应用性更强。
今年题目整体难度适中， 数据结构部分 考点在平时的授课以及模拟题中均有出现，考察也相对简单；后三道题要求同学们手写C++代码， 以代码填空、代码实现以及代码判断的三种形式 考察了大家对C++的掌握情况，难度中等偏上，但题目本身应用性仍然较强，不涉及复杂的算法，更多是逻辑判断。
另外，在考点上，主要考察了一些高频且基础的考点 ，如二维数组、动态分配内存、二分查找，相对友好。虽然考察知识点较为简单，但859在题型上进行了创新，同时在题目细节上挖了一些坑，整体还是考察同学们的知识掌握是否扎实、做题习惯是否良好。
以下为真题及参考答案，下方题目难免与实际真题有所差别，仅供各位同学参考。
真题答案与解析
一、判断
- 在C++中，单独使用++i和i++自增运算符时，效果都是使变量增加1。
答案：正确。
解析：前置自增和后置自增运算都会使得该操作数增加1，区别只是返回值不同，但变量i的值都是被增加1。
- 基类中的纯虚函数，派生类必须实现，否则派生类也是抽象类。
答案：正确。
解析：抽象类的定义是包含纯虚函数的类，若派生类不实现该函数，则派生类只是继承该纯虚函数，那么该派生类也是一个包含纯虚函数的类，符合抽象类的定义。
- 快速排序算法最坏的时间复杂度是𝑂(𝑛2) , 则在平均的情况下，该算法的时间复杂度仍然是𝑂(𝑛2) 。
答案：错误。
解析：平均情况下是𝑂(𝑛𝑙𝑜𝑔𝑛)。
- Dijkstra算法可以解决任何图的单源最短路径问题。
答案：错误。
解析：对有负权边的图，Dijkstra算法不一定能解决其单源最短路径。
- 给定二叉树的前序遍历序列和中序遍历序列，可以唯一地确定一棵二叉树。
答案：正确。
解析：通过先序遍历和中序遍历序列可以划分根节点及其左右子树，从而唯一地确定一棵二叉树。
二、填空
- 长度为n的链表中，随机查找一个元素的时间复杂度为（）
答案：（𝑂(𝑛)）。
- 高度为h的完全二 叉树有（）棵。
答案：（2ℎ）。
解析：由完全二叉树的定义可知，若高度确定（注意，一般约定根节点深度为0，仅含单个节点的树高度为0），则数量取决于最后一层的节点数量。最后一层（第h层）的节点数量取值范围为1~2ℎ，因此共有2ℎ棵。
- 双端队列中有头尾指针，经过下面的操作push pop push push pop push push pop pop push pop push，最 少需要申请的数组长度为（）。
答案：（3）。
解析：要统计任意时刻队列中元素的最大数量，即为数组长度的最小值。
push【1】 pop【0】 push【1】 push【2】 pop【1】 push【2】 push【3】 pop【2】 pop 【1】push【2】 pop【1】 push【2】
队列中最多出现3个元素，因此答案为3。
- int a =2024，那 么a*=2+1后a=（）。
答案：（6072）。
- char* a[]={"Hello World!", "Abc d", "Data Structure"},则a[1] [2]=（）。
答案：（c）。
三、代码填空
主要考察的是c++创建动态二维数组以及delete操作。
#include <iostream>using namespace std;int main(){ int m, n; cin >> m >> n; int **array; array = new (1)int *[m]; for (int i = 0; i < m; i++){ (2)array[i] = new (3)int[n]; }for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ array[i][j] = i * m + j; } }for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ cout << array[i][j] << ' '; } cout << endl; }for (int i = 0; i < m; i++){ delete (4)[] array[i];//注意delete的是数组 }delete (5)[] array;return 0;}
四、查找前k个最大亮度元素
已知渲染出了一个图像，要找出其中前K大的所有像素（像素都是整数，K远小于像素的个数）
(1)用堆来实现这个问题，简述基本思想和过程(10分)
答案：通过小顶堆来解决该问题，相当于每次找K+1个元素，找出其中最小的元素删去，一共通过N-K次删除堆顶元素，即为过滤后N-K个元素，剩下的即为前K大的元素。
- 创建一个小顶堆
- 遍历图像中的像素，将其插入到堆中；之后判断若堆的规模>K，则删除堆顶元素
- 遍历结束后，堆内元素即为前K大的元素
(2)用C++代码实现，可以使用STL，采用C++11标准(20分)
答案：
#include <iostream>#include <vector>#include <queue>#include <functional>using namespace std;int main(){ int m,n,k; cin >> m >> n >> k; vector<vector<int> > img(m,vector<int>(n));//获取图像像素亮度值，图像通常为二维数组的格式输入 for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ cin >> img[i][j]; } }priority_queue<int, vector<int>, greater<int> > pq;//创建小顶堆 for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ pq.push(img[i][j]);//插入元素 if (pq.size() > k) pq.pop();//删除堆顶元素 } }while(!pq.empty()){//输出前K大的元素 cout << pq.top()<<endl; pq.pop(); }return 0;}
五、代码判断
对于下面的二分查找代码，标记了5行代码，判断是否正确。如正确，给出解释；如不正确(错误可能是溢出或逻辑问题)，说明原因并做改正。(35分)
说明：由于无法确定真题具体是何版本，所以写两个可能的版本。另外由于不确定真题中给出的错误代码，因此只给出正确的代码，大家可根据自己的回忆进行比对。
该题目的关键在于查找的区间的概念，常用的区间概念为左闭右开，对应课本为[left,right]，另外给出在[left,right]闭区间查找的版本。解题关键为遵循该区间处理边界case。
版本1：[left,right]版本
#include <iostream>#include <vector>int binarySearch(std::vector<int> &arr, int target){ int left = 0; int right = arr.size(); while (left < right)// 标记1 //因为是左闭右开区间，合法区间则必为left < right { int mid = (left + right) / 2;//标记2 //中间轴点计算 if (target == arr[mid])//标记3 //原题目可能写的是=，此处应为比较运算符== { return mid; } else if(arr[mid] < target){//标记4 //应该比较轴点的元素arr[mid]与目标值target，原题目可能是直接比较轴点下标mid和target，又或是写反了，判断条件应该是arr[mid] < target left = mid + 1; } else{ right = mid; } } return -1;}int main(){ std::vector<int> arr = {-3, 0, 2, 5, 6, 8}; int target = 5; int result = binarySearch(arr, target); if (result != -1)// 标记5 { std::cout << "Found at " << result << std::endl; } else { std::cout << "Not Found" << std::endl; } return 0;}
版本2：[left,right]版本
#include <iostream>#include <vector>int binarySearch(std::vector<int> &arr, int target){ int left = 0; int right = arr.size() - 1; while (left <= right)// 标记1 { int mid = (left + right) / 2;//标记2 if (target == arr[mid])//标记3 { return mid; } else if(arr[mid] < target){//标记4 left = mid + 1; } else{ right = mid - 1; } } return -1;}int main(){ std::vector<int> arr = {-3, 0, 2, 5, 6, 8}; int target = 5; int result = binarySearch(arr, target); if (result != -1)// 标记5 { std::cout << "Found at " << result << std::endl; } else { std::cout << "Not Found" << std::endl; } return 0;}
`
`
26备考资料与交流群
备考资料领取：> 680理论基础知识大纲> 680理论基础参考书目> 交互手绘参考书目> 专业课备考公开课> 论文资料合辑（2024年度装饰推荐论文+CHI 2024推荐论文）
～～可以联系智将菌老师获取～～
加入26考研交流群：扫码联系智将菌老师加群～
:-)课程报名&咨询通道
【25考研复试作品集班】
全国交互设计各院校专业方向均适用！
👇
长按扫码添加微信
【26考研全程班】
即将开启
¯\_(ツ)_/¯朝菌学园考研&保研成绩
了解教学质量，可重点观察机构专业属性、教学成果、课程内容大纲、师资团队等方面。教学成果非常重要，但也是虚假信息的重灾区，同学们要多咨询多辨识，防止被迷惑欺骗。1、榜单中均为在朝菌学园考研主课学习过的学员，2019年之前的榜单则是朝菌学园现任讲师曾经的学生；2、部分同学会同时出现在其他机构成绩单中，这可能是由于该同学曾在多个机构中学习，也可能是其他机构假冒成绩单，如有疑问可以咨询教务老师；3、本榜单中不包含朝菌的保研录取成绩与留学录取成绩；
朝菌团队始终非常感谢各位同学的关注与喜爱， 2020-2024年，朝菌学园的同学们在考研、保研、留学领域取得了超过100个国内外高校的交互设计专业的录取Offer！ 多数offer为国内名校、985高校及全球Top100名校，我们对2025年度的专业课程更加充满信心！
ʕ •ᴥ•ʔJOIN CLUB
凝聚前沿设计优质内容更多精彩分享请关注▼
朝菌学园ZhaoDesign
朝菌学园是一家专注前沿、未来、智能设计领域的品牌。包含人机交互设计、服务设计、用户体验设计、互动媒体装置、智能产品设计等学习方向，已经帮助数百名学员取得考研、保研与留学申请的名校录取offer
932篇原创内容
Official Account
，