1、目录第一部分历年考研真题汇编2012年南京财经大学信息工程学院826数据结构考研真题第二部分兄弟院校真题汇编2011年厦门大学845数据结构考研真题2009年厦门大学845数据结构考研真题2008年厦门大学845数据结构考研真题2006年厦门大学496数据结构考研真题第一部分历年考研真题汇编2012年南京财经大学信息工程学院826数据结构考研真题科目代码：826科目名称：数据结构注意： 认真阅读答题纸上的注意事项； 所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效； 本试题纸须随答题纸一起装入试题袋中交回！一、回答下列问题：（1）具有n个结点的有向图和无向图分别最多有多少条边？（10分）
2、（2）设G是一个非连通图，共有28条边，问图G至少有多少个顶点？（10分）（3）若一棵二叉树共有1001个结点，且没有1度的结点，则叶子结点的个数是多少？（5分）（4）在一棵有124个叶子结点的完全二叉树中，最多有多少个结点？（5分）（5）一个具有1025个结点的二叉树，高度为多少？（10分）二、设有一个栈，元素进栈的次序为A、B、C、D、E，问能否得到下列出栈序列？若能，请写出操作序列(设PUSH为进栈操作，POP为出栈操作)；若不能，请写出原因。（1）C、E、A、B、D （5分）（2）C、B、A、D、E （10分）三、已知一个无向图G如下图所示。（1）给出从顶点1开始进行的深度优先遍历和广
3、度优先遍历。（10分）（2）给出图G的邻接矩阵。 （5分）（3）给出图G的邻接表。 （5分）四、（1）以数据集2,5,7,9,13作为二叉树中叶子结点权值构造一棵赫夫曼树。（5分）（2）计算上述赫夫曼树的带权路径长度。（5分）（3）构造该赫夫曼树的哈夫曼更多考研资料 v/q:344647 公众号/小程序：顺通考试资料编码。（5分）五、判断以下两个序列是否为堆，如果不是，按照堆排序思想把它调整为堆，并图示建堆过程。（1）3,9,5,8,4,17,21,6 （10分）（2）1,2,8,4,3,9,10,5 （10分）六、假设有向图G采用邻接表存储，设计算法实现下列要求：求出图G中每个顶点的入度。（10分）求出图G中每个顶点的出度。（10分）要求先用文字叙述算法的思想，然后用类C，或类C+，或类java语言描述算法的具体步骤。对给定的一个序号j（1jn），在无序记录A1An中找到按关键字从小到大排在第j位上的记录。 （20分）要求：1、利用快速排序的划分思想设计算法实现上述查找；2、先用文字叙述算法的思想，然后用类C，或类C+，或类java语言描述算法的具体步骤。第二部分兄弟院校真题汇编2011年厦门大学845数据结构考研真题2009年厦门大学845数据结构考研真题2008年厦门大学845数据结构考研真题2006年厦门大学496数据结构考研真题
