2020福大计算机863数据结构与程序设计真题整理

皮卡丘砍木桩 · 发表于 2019-12-23 00:06

2020年的考研终于落幕了，我今年报考的是福大计算机专硕（今年都叫电子信息了，底下有三个方向，计算机技术、软件工程、人工智能）回想起来这一年还是蛮多感慨的，平时也经常来逛考研帮，感谢考研帮上的学长学姐，特别是那个昵称盘小兔的学姐，19年的分享帖子写的很好，而且只要有给他留言都会得到回复。今天就趁着刚考完，知识点还热乎，我就大概回忆一下真题，给后面考研的21学弟学妹们有一个大概的方向。
   今年总体来说英语是中规中矩，然后政治依然是应验了那句话-政治考多少分不是取决于你多努力，而且取决于肖秀荣的发挥。今年政治是真的绝了，肖老爷子的4套卷命中了很多。就是数学有点坑爹，今年的数学其难无比，考完数学整个人心态都蹦了，差点就不去参加专业课考试了，还好最后坚持下去了。
  言归正传，说说专业课吧。今年很多学校后面临时改考408计算机专业基础综合，也就是统考那个。福大依然还是自主命题，考的是863数据结构和程序设计。主要就是C++和数据结构（算法我觉得也算属于数据结构）。福大16年以及之前的真题有考选择题，17、*、19连续三年都是大题，今年又是破天荒的考了选择题。大概分值分布如下：10道选择题，一题3分，然后合计是30分。程序设计题（C++），3道阅读程序题12分，3道程序填空题*分，然后合计是30分。数据结构考的题目是6道应用题，合计是60分。最后就是3道算法题了，1道10分，合计是30分。这就是150分卷子的真题分布。
   总体来说，今年福大的专业课题目难度有点低，前面有60-70分的送分题。前面10道选择题，因为内容比较多，记得不是很清楚。但是除了2道比较难一点，其余的都算简单。主要是考数据结构和C++的一些基本知识，印象中有：问函数中变量的范围，受限双端队列，连通图，线索二叉树，指针的声明这些。
  C++程序阅读和填空主要是考察了构造函数、析构函数的概念，还有就是逆序输出和二分查找这样的题。

   数据结构应用题，大概记得如下：
1、给出一段堆排序操作的代码，让你证明把完全二叉树调整为一个二叉堆为什么时间复杂度为O(n)。（白皮书出现过，以前也有这个类似的题目）
2、哈夫曼树的构造，要求写出详细构造过程，并计算节省了多少位编码。（求散列的编码和正常差多少，白皮书上面出现过）。
3、给出一个中缀表达式，要求用栈转化成后缀表达式，（白皮书原题）
4、一棵近似满二叉树若第6层(第一层高度算1)有8个叶子节点，问该树最多含有多少个节点.
5、给出parent[e]的意义:若e点为所在树的根，那么parent[e]就是该树的节点总数的相反数。若e点不是所在树的根节点，则paren[e]为e点所在树的根结点。（白皮书上练习过得题目，主要就是考察并查集了。考试之前叶神有提起过几次，所以印象比较深）
6、 A*L树，如果*节点是分支节点，若把*删除以后新形成了一棵A*L树B,问若把*点再加入B中，是否会变成A。若会请证明，不会请举反例。（白皮书和最后六套卷练习几次），还有一个就是问无相连通图变成最小生成树，无向图的最小边一定在生成树中。

算法题：
1、皮卡丘砍木桩，喜欢从短的到长的砍，木桩按照重量从小到大排序，每次排序时只能对相邻的木桩进行交换，求最少交换次数。（冒泡排序改进问题吧，王晓东课件和书本说过）
2、有n个股票经纪，彼此之间有的可以互相通信，有的无法通信，其中任何两个人通信所需的时间不同。求选取哪一个经纪人可以保证其与其余任意一个经纪人通信耗时最短。（单源路径最短问题）
3、在X轴上水平放置着 N 个条形图，这 N 个条形图就组成了一个柱状图，每个条形图都是一个矩形，每个矩形*相同的宽度，均为1单位长度，但是它们的高度并不相同。计算柱状图中以X轴为底边的最大矩形的面积（王晓东老师课本原原本本的题目，一字不改）
   总的来说，今年福大计算机专业课难度不高，大家考完都还是比较激动，我们那个考场有几个提前半个小时就交卷了。这个倒是出乎以前对福大专业课的认识。
  最后说下对专业课这块的复习心得吧，主要复习用书
1、王晓东数据结构（C语言描述）修订版或者今年新出了一个第四版
2、钱能的C++程序设计清华大学出版社但是我后面还是听学长学姐的使用的是谭浩强老师的C++程序设计，感觉还过得去。
3、辅助用书强烈推荐福大计算机白皮书了，这个也是去年考上的学长学姐极力推荐的。今年用起来感觉很赞，特别是今年福大计算机的真题很多都出自白皮书的原题或者类似题，我都怀疑命题老师是不是看着白皮书出题的。
最后祝自己能够取得一个好成绩，顺利进入福大复试吧。也祝愿21的学弟学妹们，考研加油，考研顺利！

来自Android客户端