资源描述
1821 数据结构考试大纲一、考查目标1理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3能够选择合适的数据结构和方法进行问题求解。二、考试形式和试卷结构1试卷满分及考试时间试卷满分 150 分，考试时间 180 分钟。2答题方式答题方式为笔试、闭卷。3试卷内容与题型结构单选题 10 题 每小题 2 分 共 20 分填空题 10 题 每小题 2 分 共 20 分简答题 5 题 每小题 5 分 共 25 分综合题 3 题 每小题 15 分 共 45 分算法题 4 题 每小题 10 分 共 40 分三、考查内容1概念（1）基本概念和术语 数据 数据结构 抽象数据类型（2）算法的描述和分析 算法、算法的时间复杂度和空间复杂度概念 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度2线性表（1）线性表的概念2 线性表的逻辑结构 线性表的存储结构：顺序表，单链表，双链表，循环链表（2）线性表的实现 顺序存储结构：查找、插入、删除等主要操作及其平均时间性能分析 链式存储结构：查找、插入、删除等主要操作及其平均时间性能分析3栈、队列（1）栈和队列的概念 栈和队列的逻辑结构 栈和队列的存储结构：顺序栈，循环队列，链式栈，链式队列（2）栈和队列的实现 顺序存储结构：入栈、出栈、入队、出队等主要操作及其平均时间性能分析 链式存储结构：入栈、出栈、入队、出队等主要操作及其平均时间性能分析4数组和广义表（1）数组和广义表的概念 数组和广义表的逻辑结构 数组的存储结构：特殊矩阵压缩存储、稀疏矩阵压缩存储（三元组表） 广义表的存储结构：链式存储（2）数组和广义表的实现 数组顺序存储结构：一般数组顺序存储的地址计算方法 广义表链式存储结构：非空广义表的求表头和表尾运算5树和二叉树（1）树和二叉树的概念 树和二叉树的逻辑结构 树和二叉树的存储结构：树的孩子兄弟二叉链表、二叉树的二叉链表 树和二叉树的遍历：树的三种遍历、二叉树的三种遍历 树和二叉树的转换（2）树和二叉树的实现 二叉树的递归遍历 Huffman 树 Huffman 编码36图（1）图的概念 图的逻辑结构 图的存储结构：邻接矩阵、邻接表 图的遍历：深度优先搜索、广度优先搜索（2）图的实现 最小（代价）生成树：Prim 和 Kruskal 方法 最短路径：Dijkstra 方法 拓扑排序 关键路径7查找（1）查找的概念 查找表、查找分类、查找结构 查找算法效率的评判标准：平均查找长度（2）静态表及其查找 顺序查找 折半查找（3）动态表及其查找 二叉排序树 平衡二叉树（4）哈希表及其查找 哈希函数 处理冲突方法 哈希查找（5）各种查找算法的分析8排序（1）排序的概念 排序方法稳定性、排序分类 排序算法效率的评判标准（2）插入排序4 简单插入排序 希尔排序（3）交换排序 冒泡排序 快速排序（4）选择排序 简单选择排序 堆排序（5）归并排序 二路归并排序 分治归并排序（6）各种排序算法的比较四、题型举例1选择题在单链表中成功查找一个元素的等概率下的平均搜索长度是 。A. n B. n/2 C. (n+1)/2 D. n+12填空题深度为 5 的二叉树至多有 个结点。3简答题请比较顺序表和单链表在存储空间和数据访问方面的特点。4综合题已知一棵二叉树的先序遍历的结果是 ABDECF，中序遍历的结果是 DEBAFC，请画出这棵二叉树，并写出该二叉树的后序遍历结果。5算法题分析下面算法功能，以及时间复杂度。#define List_Size 100typedef struct ElemType elemList_Size; int length; 5 SqList;void ex(SqList la, SqList lb, SqList j=0; k=0;while(ila.length else lc.elemk+=lb.elemj+;while(ila.length) lc.elemk+=la.elemi+;while(jlb.length) lc.elemk+=lb.elemj+; / ex(2) 用循环单链表实现队列，要求该队列只使用一个指向队尾指针。请写出结点和队列的类型定义，并分别编写队列初始化、入队、出队算法。五、参考教材(1) 数据结构，严蔚敏编著，清华大学出版社(2) 数据结构，彭 波主编，北京邮电大学出版社
展开阅读全文