圣才考研网小编在考试结束后及时为大家搜集整理了2020福大计算机863数据结构与程序设计真题整理，想要估分的考生不要错过哦！更多考研动态｜模拟试题｜历年真题请关注圣才考研网！
2020福大计算机863数据结构与程序设计真题整理
数据结构应用题：
1、给出一段堆排序操作的代码，让你证明把完全二叉树调整为一个二叉堆为什么时间复杂度为O(n)。（白皮书出现过，以前也有这个类似的题目）
2、哈夫曼树的构造，要求写出详细构造过程，并计算节省了多少位编码。（求散列的编码和正常差多少，白皮书上面出现过）。
3、给出一个中缀表达式，要求用栈转化成后缀表达式，（白皮书原题）
4、一棵近似满二叉树若第6层(第一层高度算1)有8个叶子节点，问该树最多含有多少个节点.
5、给出parent[e]的意义:若e点为所在树的根，那么parent[e]就是该树的节点总数的相反数。若e点不是所在树的根节点，则paren[e]为e点所在树的根结点。（白皮书上练习过得题目，主要就是考察并查集了。考试之前叶神有提起过几次，所以印象比较深）
6、AVL树，如果v节点是分支节点，若把v删除以后新形成了一棵AVL树B,问若把V点再加入B中，是否会变成A。若会请证明，不会请举反例。（白皮书和最后六套卷练习几次），还有一个就是问无相连通图变成最小生成树，无向图的最小边一定在生成树中。
算法题：
1、皮卡丘砍木桩，喜欢从短的到长的砍，木桩按照重量从小到大排序，每次排序时只能对相邻的木桩进行交换，求最少交换次数。（冒泡排序改进问题吧，王晓东课件和书本说过）
2、有n个股票经纪，彼此之间有的可以互相通信，有的无法通信，其中任何两个人通信所需的时间不同。求选取哪一个经纪人可以保证其与其余任意一个经纪人通信耗时最短。（单源路径最短问题）
3、在X轴上水平放置着N个条形图，这N个条形图就组成了一个柱状图，每个条形图都是一个矩形，每个矩形都有相同的宽度，均为1单位长度，但是它们的高度并不相同。计算柱状图中以X轴为底边的最大矩形的面积（王晓东老师课本原原本本的题目，一字不改）
Copyright©2007–2025 www.100xuexi.com All rights reserved 圣才学习网 版权所有
全国热线：400-900-8858（09:00-22:00），18001260133（09:00-22:00）
增值电信业务经营许可证 出版物经营许可证 网络文化经营许可证 广播电视节目制作经营许可证
