2018年中国农业大学821数据结构考试大纲

1、 PAGE PAGE 5一、考查目标821 数据结构考试大纲本操作的实现。掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题求解。二、考试形式和试卷结构试卷满分及考试时间试卷满分 150 分，考试时间 180 分钟。答题方式答题方式为笔试、闭卷。试卷内容与题型结构单选题10 题每小题2 分共 20 分填空题10 题每小题2 分共 20 分简答题5 题每小题5 分共 25 分综合题3 题每小题15 分共 45 分算法题三、考查内容4 题每小题10 分共 40 分概念基本概念和术语数据数据结构抽象数据类型算法的描述和分析算法、算法的时间复杂度和空间

2、复杂度概念算法描述和算法分析的方法，对于一般算法能分析出时间复杂度线性表线性表的概念线性表的逻辑结构线性表的存储结构：顺序表，单链表，双链表，循环链表线性表的实现顺序存储结构：查找、插入、删除等主要操作及其平均时间性能分析链式存储结构：查找、插入、删除等主要操作及其平均时间性能分析栈、队列栈和队列的概念栈和队列的逻辑结构栈和队列的存储结构：顺序栈，循环队列，链式栈，链式队列栈和队列的实现顺序存储结构：入栈、出栈、入队、出队等主要操作及其平均时间性能分析链式存储结构：入栈、出栈、入队、出队等主要操作及其平均时间性能分析数组和广义表数组和广义表的概念数组和广义表的逻辑结构数组的存储结构：特殊矩阵压

3、缩存储、稀疏矩阵压缩存储（三元组表）广义表的存储结构：链式存储数组和广义表的实现数组顺序存储结构：一般数组顺序存储的地址计算方法广义表链式存储结构：非空广义表的求表头和表尾运算树和二叉树树和二叉树的概念树和二叉树的逻辑结构树和二叉树的存储结构：树的孩子兄弟二叉链表、二叉树的二叉链表树和二叉树的遍历：树的三种遍历、二叉树的三种遍历树和二叉树的转换树和二叉树的实现二叉树的递归遍历Huffman树Huffman编码图图的概念图的逻辑结构图的存储结构：邻接矩阵、邻接表图的遍历：深度优先搜索、广度优先搜索图的实现最小（代价） Kruskal方法最短路径：Dijkstra 方法拓扑排序关键路径查找查找的概

4、念查找表、查找分类、查找结构查找算法效率的评判标准：平均查找长度静态表及其查找顺序查找折半查找动态表及其查找二叉排序树平衡二叉树哈希表及其查找哈希函数处理冲突方法哈希查找各种查找算法的分析排序排序的概念排序方法稳定性、排序分类排序算法效率的评判标准插入排序简单插入排序希尔排序交换排序冒泡排序快速排序选择排序简单选择排序堆排序归并排序二路归并排序分治归并排序各种排序算法的比较四、题型举例选择题在单链表中成功查找一个元素的等概率下的平均搜索长度是。A. n 2填空题B.n/2C.(n+1)/2D. n+1深度为5 的二叉树至多有个结点。简答题请比较顺序表和单链表在存储空间和数据访问方面的特点。综合

5、题已知一棵二叉树的先序遍历的结果是ABDECF，中序遍历的结果是DEBAFC，请画出这棵二叉树，并写出该二叉树的后序遍历结果。算法题分析下面算法功能，以及时间复杂度。#define List_Size typedef structElemType elemList_Size; intlength; SqList;void ex(SqList la, SqList lb,SqList&lc)i=0;j=0;k=0;while(ila.length & jlb.length) if(la.elemi=lb.elemj)elselc.elemk+=lb.elemj+;while(ila.length)while(jlb.length) / ex的类型定义，并分别编写队列初始化、入队、出队算法。五、参考教材数据结构，严蔚敏编著，清华大学出版社数据结构，彭 波主编，北京邮电大学出版社QQ 552325756 821 数据结构初试