特别说明
本书根据历年考研大纲要求并结合历年考研真题对该题型进行了整理编写，涵盖了这一考研科目该题型常考试题及重点试题并给出了参考答案，针对性强，考研复习首选资料。
版权声明
青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。
因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。
重要提示
本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。
一、2021年重庆大学计算机学院917计算机学科专业基础综合考研核心题库之数据结构算法设计题精编
1．设树上每个结点所包含的数据元素为一个字母，并且以孩子兄弟表示法为树的存储结构，试写一个按图所示的凹入表示式显示一棵树的算法。
【答案】具体算法如下。
2．已知递归函数F(m)(其中DIV为整除)：
(1)写出求F(m)的递归算法。
(2)写出求F(m)的非递归算法
【答案】
3．设有n个待排序元素存放在中，设计一个算法，对其进行二路归并排序，并分析算法的时间复杂度和空间复杂度。
【答案】二路归并排序算法如下。
对长度为n的文件，需进行log 2n趟二路归并，每趟归并的时间为，故其时间复杂度无论是在最好情况下还是在最坏情况下均是。由于二路归并排序需要一个辅助向量来暂存两
有序子序列归并的结果，故其辅助空间复杂度为。
4．对于一个使用邻接表存储的带权有向图G,试利用深度优先搜索方法，对该图中所有顶点进行拓扑排序。若邻接表的数据类型定义为Graph,则算法的首部为：
若函数返回trne，表示拓扑排序成功，图中不存在环;若函数返回false,则图中存在环，拓扑排序不成功。在这个算法中嵌套调用一个递归的深度优先搜索算法为：
在遍历图的同时进行拓扑排序，其中vtxnum是顶点号。
(1)给出该图的邻接表定义；
(2)定义在算法中使用的全局辅助数组；
(3)写出拓扑排序的算法。
【答案】(1)
(2)在算法中使用的全局辅助数组为：
若，则表示顶点i已被访问过;否则表示顶点i未被访问过。
若，表示对顶点i的DFS搜索已结束；否则表示对顶点i的DFS搜索未结束。
(3)函数和过程dfs的定义如下：