11级数据结构复习提纲

数据结构复习提要一、绪论要求理解的概念包括：数据，数据对象，数据元素或数据成员，数据元素或数据成员的结构关系类型，数据结构，数据类型，数据抽象，抽象数据类型，数据结构的逻辑结构与存储结构算法特性及其复杂性要求明确算法的时间复杂度的计算，能分析：简单递归时间复杂性分析，线性程序，书上典型算法时间复杂性分析二、线性表线性表的逻辑结构特征；线性表的两种存储方式表示和实现。1) 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系；顺序表的基本操作：插入，删除，查找和合并，算法时间复杂度分析；2) 链表如何反映线性表中元素之间的逻辑关系；链表中头指针和头结点的使用；3) 单链表，双(向)链表，循环链表链接方式上的区别；单链表的基本操作：创建链表，插入，删除，查找，单链表倒置，一元多项式的表示和运算。4) 顺序表与链表的比较；二者各自的优缺点，怎样选择哪种存储方式才能取时空较优性能；5) 教材要求掌握的算法2.2,2.32.42.52.6.2.72.82.92.102.112.12三、栈和队列1 栈的逻辑结构，存储结构及其相关算法栈的逻辑结构的特点，栈和线性表异同；2)栈的基本操作：包括顺序栈和链栈的初始化，入栈，出栈，判定栈为空与满;栈的应用；2 队列的逻辑结构，存储结构及其相关算法1）队列的逻辑结构的特点，队列和线性表异同2）队列基本操作：顺序队列（主要是循环队列）和链对列的入队，出队，判定队为空，循环队列满和空对的条件，循环队列长度。3）循环队列产生假溢出的原因是什么，怎么解决；栈和队列的特点是什么，什么情况下使用栈或队列？3 算法;P47poppushinitstackP31算法3.1P62队列的基本操作P64-65循环队列基本操作五、树和二叉树1树的逻辑结构2树的定义和树的不同表示，1 树常见基本概念和含义，如树的深度，树的度，孩子，分枝等二叉树的定义和树的区别，二叉树的性质1,2,3,4,5;2 区别完全二叉树和满二叉树，线索二叉树。二叉树的存储表示。3 二叉树的三种遍历和线索化（先，中，后序）。4 二叉树的重建。【先序+中序，后序+中序（确定二叉树）】最优二叉树的定义与构造，huffman构造与编码算法（前缀编码）5 要求掌握算法:6.16.26.36.46.56.66.7。六、图1图的概念：图的逻辑结构特征，图的常见定义和相关术语;2图存储形式，矩阵，邻接表，十字链表，多重邻接表3图遍历算法：DFS,BFS4图的生成树与最小生成树算法：生成树的概念，最小生成树概念，最小生成树算法:prim算法，kruskal算法AOE网的关键路径：事件的最早发生时间，最晚发生时间；活动的最早发生时间与最迟发生时间，整个工程的完工时间；关键活动等6理解图的最短路径算法：dijkstra算法，floyd算法7算法7.47.57.6,7.9其他内容：包括作业和课堂练习题考试题型：单项选择，填空题，解答题，算法设计附录：试题类型一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1. 非空的循环单链表head的尾节点(由p所指向)满足【】Ap-next=NULLB.p=NULLC.p-next=headD.p=head在一个链队中，假设f和1?分别为队首和队尾指针，贝删除一个节点的运算是A.r=f-next；B.r=r-next；C.f=f-next；D.f=r-next；3某二叉树的后序遍历序列为DABEC,中序遍历序列为DEBAC,则前序序列遍历为【】AACBEDBDECABCDEABCDCEDBA4、采用邻接表存储的图的深度优先遍历类似于二叉树的A.先序遍历Bo中序遍历C.后序遍历Do层次遍历5、若进栈序列为1,2,3,4，假定进栈和出栈可以穿插进行，则可能的出栈序列是()(A) 2,4,1,3(B)3,1,4,2(C)3,4,1,2(D)1,2,3,46、引入线索二叉树的目的是()加快查找结点的前驱或后继的速度为了能在二叉树中方便的进行插入与删除(B) :为了能方便的找到双亲使二叉树的遍历结果唯一7、连通图G中有n个顶点,G的生成树是()连通子图.(A)包含G的所有顶点(B)包含G的所有边(C)不必包含G的所有顶点(D)必须包含G的所有顶点和所有的边8、下面关于求关键路径的说法不正确的是()a. 求关键路径是以拓扑排序为基础的b. 个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同c.个事件的最迟开始时间同以该事件为尾的弧的活动最迟开始时间相同与该活动的持续时间的和d.关键活动一定在关键路径上二、填空题1在有n个节点的顺序表中做插入、删除运算，平均时间复杂度为。2、在非空队列里，头指针始终指向,尾指针始终指向。5一个节点的子树的个数称为这个节点的。6、对于二叉树来说，第i层上最多有个节点。7若m叉树中A有3个兄弟，节点B是A的双亲，则节点B的度是datak+=A.datai+;elseC-datak+=B.dataj+;C-datak+=A.datai+;C-datak+=B.dataj+;C-last=k-l;12、在一棵二叉树中，度为0的结点个数为n0,度为2的个数为n2,则n0=_13在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构-线索链表三，解答题1假.定用于通信的电文仅由8个字母cl,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码，并给出该电文的总码数2如图所示AOE是某个工程的计划图，各个顶点表示事件，边表示活动，边上的权值表示各活动所需要的时间计算出事件v6的最早发生时间和最晚发生时间.1 求该AOE图的关键路径并且计算工程完成所需要的最短时间.3如图所示的二叉树1 该二叉树的深度是多少”共有多少个分支.2 画出该二叉树的中序线索化树.，结点A,B,E,F的直接前驱分别是甚么四，算法设计1有一个单链表，其头指针为head编写一个函数计算数据域为x的节点的个数2向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行3写出用单链表储存的一个元多项式求n(n=l)次导数的算法.4写出顺序栈的出栈算法5.以二叉链表为存储结构，写出二叉树中序遍历算法。49.O(n2)10n-l4 写出循环队列入队算法选择和填空答案：一单选题：CCDDDAAC二填空；1O(n)2队头，队尾元素的下一个位置.5.度。6。27.11while(i=A.last);while(j=B.last);12n2+l13N+l