东北大学数据结构考研复习ppt课件.ppt

《东北大学数据结构考研复习ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构考研复习10大纲解读1考研真题0大纲解读1.考查目标（1）理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。（2）在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。（3）能够选择合适的数据结构和方法进行问题求解；具备采用C或JAVA语言设计与实现算法的能力。0大纲解读2.基本要求（1）三基问题基本概念、基本结构、基本操作（2）基本原理及应用技术基本应用、经典算法（3）综合应用问题求解、算法设计0大纲解读3.考查内容（1）线性表（2）栈、队列和数组（3）树与二叉树（4）图（5）查找（6）内部排序0大纲解读一、线性表（1）线性

2、表的定义和基本操作（2）线性表的存储结构实现顺序表链表（3）线性表的应用如：集合运算、多项式求解0大纲解读二、栈、队列和数组（1）栈和队列的基本概念（2）栈和队列的存储结构实现顺序栈、顺序队列、循环队列链栈、链队列（3）栈和队列的应用如：表达式求值、递归、迷宫问题（4）特殊矩阵的压缩存储0大纲解读三、树与二叉树（1）树与二叉树的基本概念（2）二叉树的基本性质与存储结构（3）二叉树的遍历（4）线索二叉树的基本概念和构造（5）树与森林的存储结构0大纲解读（6）树、森林与二叉树的转换（7）树与森林的遍历（8）树的应用二叉排序树、平衡二叉树、哈夫曼树和哈夫曼编码0大纲解读四、图（1）图的定

3、义和基本概念（2）图的存储结构及基本操作-邻接矩阵、邻接表、逆邻接表、十字链表（3）图的遍历-深度优先、广度优先（4）图的应用-最小生成树、最短路径、拓扑排序、关键路径0大纲解读五、查找（1）查找的基本概念（2）顺序查找（3）折半查找（4）B-树及其基本操作、B+树概念（5）散列（哈希）表（6）查找算法的分析及应用0大纲解读六、内部排序（1）排序的基本概念（2）传统排序-插入排序（直接、折半）、交换（冒泡）、简单选择（3）优化排序-希尔排序、快速排序、堆排序、二路归并排序（4）基数排序（5）排序算法的比较及应用0大纲解读6、复习方法（1）了解课程内容体系（2）循序渐进（3）典型算法

4、（4）综合应用（5）实验能力-辅助提高手段（6）练习与测试0大纲解读课程内容体系（1）数据结构基本概念逻辑结构-存储结构-基本操作（2）数据结构基本应用基本结构-常用结构-复杂结构（3）数据结构算法应用线形结构-树形结构-图形结构0大纲解读循序渐进简单数组-顺序表-单链表-字符串-二叉树-图简单基本操作-复杂基本操作简单应用-高级应用-综合应用经典算法线性表经典算法1、集合求并2、一元多项式求和栈和队列经典算法3、表达式求值4、简单背包问题0大纲解读5、杨辉三角形6、子集划分问题树形结构经典算法7、哈夫曼树8、堆排序树图形结构经典算法9、最小生成树10、拓扑排序0大纲解读11、关键

5、路径12、最短路径查找和排序经典算法13、折半查找14、希尔排序15、快速排序16、二路归并排序17、基数排序0大纲解读0大纲解读综合应用迷宫问题背包问题任务分配拓扑集合划分全局最优问题……0大纲解读考试题型单选题应用题0大纲解读单选题在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作A.s->next=q->next;q->next=s;B.s->next=p;p->next=sC.q->next=s;s->next=p;D.p->next=s;s->next=q;0大纲解读单选题假设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不

6、可能是A．A，B，C，DB．D，C，B，AC.A，C，D，BD.D，A，B，C0大纲解读单选题在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的平衡因子为-2，左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是A．LL型B．LR型C．RL型D．RR型0大纲解读单选题有向无权图G用邻接矩阵A存储，则顶点i的入度等于A中A.第i行1的元素之和B.第i列1的元素之和C.第i行0的元素个数D.第i列0的元素个数0大纲解读应用题1设一哈希表长为13，采用线性探测法解决冲突，哈希函数H(key)=key%13,请画出在空表中依次插入关键字25，20

7、，36，15，41，52，29，72，67后的哈希表，并求在等概率情况下查找成功时的平均查找长度。0大纲解读应用题2设无向图G=(V,E)，其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组（V1,V2,W）表示，V1、V2为关联的顶点，W为权值。要求写出图G中从顶点1到其余各点的最短路径的求解过程。要求列出最短路径上的各顶点，并计算路径长度。0大纲