数据结构复习指导_2014

1数据结构复习大纲第1章概论2基本术语：程序、数据结构、算法、数据逻辑结构、数据存储结构、抽象数据类型。算法：4个特性（通用性、有效性、确定性、有穷性）算法分析：算法分析的相关概念；渐进分析方法以及3个符号（O，Ω，）的含义；最差、最佳与平均情况的意义3逻辑结构：线性结构、树形结构和图形结构存储结构：顺序方法、链接方法、索引方法、散列方法4将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。A.O(n)B.O(1)C.O(m)D.O(m+n)5•数据的逻辑结构主要描述元素之间的逻辑关系，它独立于数据的_______________。•数据结构的基本存储方式有_____、_____、_____与_____。•算法分析的主要内容是分析算法的_______。第2章线性表6清楚线性表定义、理解类定义及抽象数据类型中定义的各个基本操作含义存储形式：顺序存储结构与链式存储结构顺序存储结构的特点：1.逻辑结构与物理结构一致；2.属于随机存取方式缺点：插入\删除元素需要移动，平均约一半的元素，限制了长度变化链式存储结构的特点：1.逻辑结构与物理结构不一致；2.属于顺序存取方式顺序表和有序表7顺序表：线性表采用顺序存储结构表示(向量)有序表：内容按从小到大排列的线性表算法：（时间复杂性）在有序表中插入/删除一个元素使其仍有序在给定位置插入/删除一个元素链表—单向、循环、双向8不特殊说明，均带头结点算法：（时间复杂性）在有序表中插入/删除结点给定元素位置，插入/删除相应结点注意：对循环链表操作时，尾部的判断双向链表的插入/删除结点删除结点一定要释放空间线性表实现方法的比较（教材2.4）9有序的顺序表与无序的顺序表相比，其操作优势是（）。A.删除快B.插入快C.生成快D.查找快10线性表的链式存储结构主要包括_______、_______、_______三种形式。线性表的顺序存储是通过_________来表示数据元素之间的逻辑关系，而链式存储结构是通过_________表示数据元素之间的逻辑关系。单链表带头结点的目的是__________________。11若对线性表进行的主要操作是按照下标存取，且很少插入和删除，则应该采用的存储结构是；若需要频繁地对线性表进行插入和删除时，则应该采用的存储结构是。给定一个含有n个元素的一维数组，建立一个有序单链表的时间复杂度是。第3章栈与队列12栈与队列的定义、抽象数据类型定义及基本操作。栈的应用：*会跟踪递归函数执行过程*深度（纵向）周游*表达式（掌握后缀表达式计算中栈的应用）队列的应用：按层周游注意：熟悉ADT的操作形式，会直接调用抽象数据类型中定义的操作栈的典型题13判回文、判表达式括号是否匹配（思路）给定一个中缀表达式，按照教材给出的算法转换为后缀表达式（掌握）给定后缀表达式，按照教材上给出的算法跟踪计算后缀表达式的过程（掌握）14假设入栈顺序为1234，则下列不可能出现的出栈序列为：4321342112343412给定一个序列ssxxssxxxxsxsxxxssss,s代表入栈，x代表出栈，这是合法的操作序列吗？15栈和队列的共同点是。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点仅允许在一端进行插入删除的线性表称为。16若已知一个栈的入栈序列是1,2,…,n.其出栈序列为p1,p2,…,pn。若p1=n，则pi为（）。A.iB.n-iC.n-i+1D.不确定17给定表达式23+(34*45)/(5+6+7)（1）将其转换成后缀表达式（2）跟踪后缀表达式的计算过程后缀表达式：233445*56+7+/[phone]+7+/[phone]+/[phone]/+2385+10818设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为()。A.SQ.front=SQ.front+1B.SQ.front=(SQ.front+1)%(m–1)C.SQ.front=(SQ.front–1)%mD.SQ.front=(SQ.front+1)%m19012345678k0k1k2k3k4rearfrontk5k6k7队满:(rear+1)%n==front第4章字符串(了解）20基本概念存储结构（顺序、标准类）基本操作的含义第5章二叉树21基本概念定义、性质、存储结构（相应的类定义）满二叉树、完全二叉树及扩充二叉树抽象数据类型定义中的基本操作含义深度周游（递归与非递归），广度周游二叉搜索树插入、删除（改进）与检索算法。必须能够跟踪执行过程。堆概念、建堆与调整堆的相关算法（过程）Huffman树及Huffman编码与算法有关的典型例题22已知一棵二叉树的前序和中序（后序和中序）遍历序列，构造对应的二叉树通过二叉树，获得对应的树与森林的相关信息深度周游与广度周游二叉树二叉搜索树与堆的相关算法要能够根据给定实例写出执行过程例：二叉树的先序序列“abcdefg”由二叉树的先序和中序序列建树或森林二叉树的中序序列“cbdaegf”二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列25某棵二叉树的前序序列为ABDEFC，中序序列为DBFEAC，则该二叉树对应的森林按层遍历的结果为___________。设一棵完全二叉树有128个结点，则该完全二叉树的叶子结点数目为64。设a、b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。A.a在b右方B.a是b的祖先C.a在b左方D.a是b的子孙26给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中的改进算法）。给定关键码序列，判断是否为最大值堆或最小值堆，如果不是，调整成堆。给定关键码序列，建初堆。二叉搜索树的删除与插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。删除过程分为如下情况：被删除的结点是叶子被删除的结点只有左子树或只有右子树被删除的结点有左、右子树50308020908540358832（1）被删除的结点是叶子结点被删关键字=2088其双亲结点中相应指针域的值改为“空”50308020908540358832（2）被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。被删关键字=4080若p有左右子树，则在左子树里找中序周游的最后一个结点r，将r的右指针置成指向p的右子树的根，用结点p的左子树的根去代替被删除的结点p。50308020908540358832308020908540358832pr被删关键字=50（3）被删除的结点既有左子树，也有右子树50308020908540358832（3）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字=5032建“初堆”的基本方法：从堆中最后一个有孩子的结点开始利用调整。40554973816436122798（40,55,49,73,12,27,98,81,64,36)1236817349988173559849406436122733插入新元素templateclassTboolMinHeapT::Insert(constT&newNode){//向堆中插入新元素newNodeif(CurrentSize==MaxSize)//堆空间已经满returnFALSE;heapArray[CurrentSize]=newNode;SiftUp(CurrentSize);//向上调整CurrentSize++;returnTRUE;}34移出最小值T&MinHeapT::RemoveMin(){if(CurrentSize==0){coutCan'tDelete;exit(1);}else{swap(0,--CurrentSize);//交换堆顶和堆尾的元素if(CurrentSize1)SiftDown(0);returnheapArray[CurrentSize];}}35删除元素templateclassTboolMinHeapT::Remove(intpos,T&node){if((pos0)||(pos=CurrentSize))returnfalse;node=heapArray[pos];heapArray[pos]=heapArray[--CurrentSize];if(heapArray[parent(pos)]heapArray[pos])SiftUp(pos);elseSiftDown(pos);returntrue;}36由五个分别带权值为9，2，5，7，14的叶子结点构成Huffman树，写出该树的带权的路径长度WLP，及计算步骤。37树的带权的路径长度树中所有叶子结点的带权路径长度之和Huffman树设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树—结点到根的路径长度——权值—其中：kknkkklwlwwpl1Huffman树构建389例如:已知权值W={5,6,2,9,7}56275276976713952739671395279527166713290000111100011011011140前缀编码ABACCDAA0；B110；C10；D111特点：任何编码均不是其他编码的前缀发送编码：0110010101110译码无二义性，如：1011001110010CABD000111Huffman编码第6章树41树与森林：定义、抽象数据类型定义以及基本操作含义树与森林的链式存储结构（教材6.2）树与森林的顺序存储结构（教材6.3）树、森林遍历，与二叉树之间的关系，相互转换树的深度优先周游与广度优先周游树的链式存储421.子结点表表示法2.左子结点/右兄弟结点表示法3.动态结点表示法4.动态“左子/右兄”二叉链表表示法5.父指针表示法43ADFBCGHEIJKLA\A\A\B0A\C0A\A\A\A\A\G2A\D1A\E1\A\F2\A\H2\A\I3\A\J3\A\A\A\K6\A\L6\01234567891011索引值父子12\34\5689\1011\7\子结点表示法静态左子/右兄表示法44HBGACDIJEFA\A/\A\B0A\C0A\A\A\A\A\G/\A\D0\A\E2A\F2\A\H6A\I6\A\J7\0123456789左子值父右兄AA\AAAAAAA\A\A\AA\A\45ADFBCGHEIJKLE0A\A\A\F0A\H0A\I0A\J0A\K0A\A\A\L0A\A2A\B2A\G2A\D2A\C33.动态结点表示法4.动态“左子/右兄”二叉链表表示法46DABCEFG^|B|^|C|^|D|^|E|^^|F|^|G|^^|A|^5.父指针表示法47树的最简单表示方法是对每个结点只保存一个指针域指向其父结点，这种实现被称为父指针(parentpointer)表示法如果两个结点到达同一根结点，它们一定在同一棵树中。如果找到的根结点是不同的，两个结点就不在同一棵树中父指针数组表示法48父结点索引标记结点索引树的顺序存储491.带右链的先根次序表示法2.带双标记位的先根次序表示法1.带右链的先根次序表示法50在带右链的先根次序表示中，结点按先根次序顺序存储在一片连续的存储单元中。每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为:info是结点的数据，rlink是右指针，指向结点的下一个兄弟ltag是一个左标记，当结点没有子结点，即对应的二叉树中结点没有左子结点时，ltag