分数组成(10平时+20实验+70期末)和题型(选择10分+填空10分+简答25分+算法设计25分)和往年一样,没有什么变化。
以下部分基于个人回忆,和原题目描述上可能有出入。
1.选择&填空(10+10=20分)
这部分题目不难,只考基本概念和简单的计算。与考研题相比要简单一些。做一做本校考研题的数据结构部分应该就没问题了。
2.简答题(25分,3题)
简答题共三题,主要考察查找(平衡树、散列)、堆、线性表等知识。
第一题内容是给出一个二叉搜索树的后序遍历,问能不能确定这个二叉树。
第二题分两个小问,第一个小问是根据快递的快递单号确定快递存放的货柜,方便查找,体现了什么思想?第二个小问是已知货柜号和快递单号,在取快递时,可以采用哪些策略来快速找到快递?
第三题内容是银行系统中,每个客户都对应一个权限。要求银行每次可以选取一个权限最高或者权限最低的客户来服务,问采用什么数据结构?
3.算法设计题(25分,3题)
这部分题要求自行设计数据结构,给出C/C++/Java语言代码,分析复杂度。
第一题是给出中序线索二叉树的一个结点P,设计一个算法,求它的前驱结点P$.
第二题是给出两个升序排列的数组A、B,长度分别为m、n,设计一个算法,输入一个数k,返回数组A、B中第k小的元素。
第三题是给出一个有向图G,设计一个算法,判断任意两个顶点是否连通。