数据结构复习提纲

复习提纲第一章数据结构概述基本概念与术语数据：数据是用来描述现实世界的文字，字符，图像，声音，以及能够输入到计算机中并能被计算机处理的符号。数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。（补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。）数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（1） 数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：集合：数据中的数据元素之间除了“同属于一个集合“的关系以夕卜，没有其他关系。线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。（2） 数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构：顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。5.时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1)线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n)平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++时间复杂度的大小比较：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)算法与程序：1、 输入：有零个或多个输入2、 输出：有一个或多个输出3、 有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。(程序与算法的区别在于，程序不需要有有穷性)4、 确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。没有歧义。5、 可行性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。算法设计的准则：1、 正确性(达到预期效果，满足问题需求)2、 健壮性(能处理合法数据，也能对不合法的数据作出反应，不会产生不可预期的后果)3、 可读性(要求算法易于理解，便于分析)4、 可修改可扩展性5、 高效率(较好的时空性能)1、 名词解释：数据结构、二元组数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。二元组就是一种用来表示某个数据对象以及各个元素之间关系的有限集合。2、 根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。3、 常见的数据存储结构一般有两种类型，它们分别是顺序存储结构、链式存储结构4、 以下说法中，正确的是(D)数据元素是数据这个集合中的个体数据元素均由数据项组成数据项是数据的基本单位数据元素是数据的最小单位以下有关抽象数据类型的描述中，正确的是(B抽象数据类型是一个值的集合抽象数据类型是数据的逻辑结构及操作的组合抽象数据类型的操作可以没有操作结果抽象数据类型只能够用C语言来描述在一般情况下，一个算法的时间复杂度是问题规模的函数7.常见时间复杂度有：常数阶O(1)、线性阶O(n)、对数阶O(log2n)、平方阶。(”2)、指数阶0(25)。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。第二章线性表顺序表结构线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。2.单链表链表结点结构线性表中的数据元素可以用任意的一组存储单元来存储，用指针表示逻辑关系逻辑相邻的两元素的存储空间可以是不连续的。结点遍历链表操作算法：初始化、插入、输出、删除1、 线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。2、 在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的操作语句为P->next=q->next;free(q);3、 在长度为N的顺序表仲，插入一个新元素平均需要移动表中N/2个元素，删除一个元素平均需要移动(N-1)/2个元素。4、 若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用数序表存储结构最节省运算时间。5、 已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336,则顺序表的首地址为300

6、设有一带头结点单链表L,请编写该单链表的初始化，插入、输出和删除函数。(函数名自定义)结点定义：typedefintdatatype; 〃结点数据类型，假设为inttypedefstructnode{ 〃结点结构datatypedata;structnode*next;}Lnode,*pointer;〃结点类型，结点指针类型typedefpointerlklist;〃单链表类型，即头指针类型初始化函数：lklistinitlist(){pointerhead;head=newnode;head->next=NULL;returnhead;}插入函数：intinsert(lklisthead,datatypex,inti){pointerq,s;q=get(head,i-1);//找第i-1个点if(q==NULL) 〃无第/T点，即/<1或i>n+1时{cout<<”非法插入位置!\n”;return0;}s=newnode; 〃生成新结点s->data=x;s->next=q->next;〃新点的后继是原第i个点q->next=s; 〃原第i-1个点的后继是新点return1; 〃插入成功}删除函数：intdelete(lklisthead,inti){pointerp,q;q=get(head,i-1); 〃找待删点的直接前趋if(q==NULL||q->next==NULL)//即i<1或i>n时{cout<<”非法删除位置!\n”;return0;}〃保存待删点地址〃修改前趋的后继指针〃释放结点〃删除成〃保存待删点地址〃修改前趋的后继指针〃释放结点〃删除成q->next=p->next;deletep;return1;不带头结点的单链表head为空的判定条件是(A)head=NULLB.head->next=NULLC.head->next=headD.head!=NULL带头结点的单链表head为空的判定条件是(B)A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)A.s->next=p;p->next=s; B.s->next=p->next;p->next=s;C.s->next=p->next;p=s; D.p->next=s;s->next=p;在一个单链表中，若删除p所指结点的后续结点，则执行(A)p->next=p->next->next;p=p->next;p->next=p->next->next;p->next=p->nextp=p->next->next从一个具有n个结点的有序单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较(B)个结点。A.nB.n/2C.(n-1)/2 D.O(nlog2n)给定有n个元素的向量，建立一个有序单链表的时间复杂度(BA.O(1)B.O(n) C.O(n2) D.O(ng2n)在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)A.O(1)B.O(n) C.O(n2) D.O(ng2n)在一个单链表中删除q所指结点时，应执行如下操作：q=p->next;p->next=(p->next->next);free(q);//这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。在一个单链表中p所指结点之后插入一个s所指结点时，应执行：s->next=(p->next)p->next=(s)操作。对于一个具有n个节点的单链表，在已知所指结点后插入一个新结点的时间复杂度是(O)；在给定值为x的结点后插入一个新结点的时间复杂度是(O(n))。问答题线性表可用顺序表或链表存储。试问：⑴两种存储表示各有哪些主要优缺点?顺序表的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半（或近一半）元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。（2）若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。第三章栈和队列栈（1） 栈的结构与定义（2） 顺序栈操作算法：入栈、出栈、判断栈空等（3） 链栈的结构与定义队列（1） 队列的定义1、 一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（BA.BCDAE B.EDACB C.BCADE D.AEDCB2、 栈的顺序表示中，用TOP表示栈顶元素，那么栈空的条件是（DA.TOP==STACKSIZEB.TOP==1C.TOP==0D.TOP==-13、 允许在一端插入，在另一端删除的线性表称为队列。插入的一端为表头，删除的一端为表尾。4、 栈的特点是先进后出，队列的特点是先进先出。5、 对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是O（1）。6、 已知链栈Q，编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输出。（要求判断栈空、出栈、入栈用函数实现）考点1：队列的编程：考点2：栈的编程：出队与取队头元素的区别：出队就是删除对头的数据元素，取队头元素是获取对头的数据元素值，不需要删除。链栈与顺序栈相比，比较明显的优点是：(D1插入操作比较容易 B.删除操作比较容易C.不会出现栈空的情况 D.不会出现栈满的情况第六章树和二叉树树树的概念及术语树：n(〃30)个结点的有限集合。当n=0时，称为空树；任意一棵非空树满足以下条件：⑴有且仅有一个特定的称为根的结点；⑵当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,...,Tm，其中每个集合又是一棵树，并称为这个根结点的壬树。结点的度：结点所拥有的子树的个数。树的度：树中所有结点的度的最大值。叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。孩子、双亲树中某结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟： 具有同一个双亲的孩子结点互称为兄弟。路径：如果树的结点序列n1,n2,…,nk有如下关系:结点ni是ni+1的双亲(1<=i<k)，则把n1,n2,...,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度： 树中所有结点的最大层数，也称高度。层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树树通常有前序(根)遍历、后序(根)遍历和层序(次)遍历三种方式(树，不是二叉树，没中序遍历。二叉树二叉树的定义：二叉树是n(n30)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。(满二叉树的特点:叶子只能出现在最下一层;只有度为0和度为2的结点。)完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i(1</<n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。(完全二叉树的特点：1.在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。深度为k的完全二叉树在k-1层上一定是满二叉树。)二叉树的性质：性质1：二叉树的第i层上最多有2/-1个结点(i31)。，性质2：一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。深度为k且具有2k-1个结点的二叉树一定是满二叉树性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0=n2+1。(一个结点的度就是指它放出的射线)，性质4：具有n个结点的完全二叉树的深度为log2n+1。性质5：对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为/(1WiWn)的结点(简称为结点i)，有：如果/・>1，则结点/•的双亲结点的序号为i/2；如果i=1，则结点/•是根结点，无双亲结点。如果2iWn，则结点/•的左孩子的序号为2i；如果2i>n，则结点/•无左孩子。如果2/+1Wn，则结点/•的右孩子的序号为2/+1；如果2/+1>n，则结点i无右孩子。二叉树的遍历前序遍历中序遍历后序遍历森林(1)森林的遍历：先序遍历森林和中序森林先序遍历：若森林不空，则访问森林中第一棵树的根结点；

先序遍历森林中第一棵树的子树森林；先序遍历森林中（除第一棵树之外）其余树构成的森林。（约定：依次从左至右对森林中的每一棵树进行先根遍历。）后序遍历：若森林不空，则后序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；后序遍历森林中（除第一棵树之外）其余树构成的森林。（约定：依次从左至右对森林中的每一棵树进行后根遍历。）（2）森林：m（m30）棵互不相交的树的集合。二叉搜索树（1）二叉搜索树的定义及构建：哈夫曼树（1） 哈夫曼树的基本概念：哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。（2） 哈夫曼树的特点：权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.（3） 哈夫曼树的构造算法思想及构造过程（7森林与哈夫曼编码1、 已知一棵完全二叉树有47个结点，则该二叉树有（）个叶子结点。A.6B.12C.24 D.482、 已知遍历一棵二叉树的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵AB树（C）

AB3、如下图所示的一棵二叉树进行遍历，得到的遍历序列是CADREFB，则该遍历序列是哪种遍历（3、如下图所示的一棵二叉树进行遍历，得到的遍历序列是CADREFB，则该遍历序列是哪种遍历（B）的结果。A.前序遍历B.中序遍历 C.后序遍历D.层次遍历4、 完全二叉树必须满足的条件为：:一棵具有n个结点的二叉树，它的结构与满二叉树的前n个结点的的结构相同。5、 哈夫曼树不存在度为1的结点。6、有5个带权结点，其权值分别为2,5,3,7,11，根据哈夫曼算法构建该树，并计算该树的带权路径长度。（构建哈夫曼树，很简单，从小开始，计算相加，然后把所有叶子结点乘以等级数字然后相加。也即是：带权路径长度=叶结点的权值*路径长度）8、写出前序和后序遍历下面森林得到的序列，并将森林转化成二叉树前序：abdjcefhi后序：djbaechif前序遍历和中序遍历结果相同的二叉树是（D）。A根结点无左孩子的二叉树 B根结点无右孩子的二叉树C所有结点只有左子树的二叉树D所有结点只有右子树的二叉树用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]~A[n]中，结点A[i]若有左子树，则左子树的根结点是(D)。AA[2i-1]BA[2i+1]CA[i/2]DA[2i]对任何一棵二叉树T,如果其终端结点的个数为n0,度为2的结点个数为门2,则(C)。A.n0=n2-1B.n0=n2C.n0=n2+1D.没有规律对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h,则其左分支下的子孙的最大层次为(C)。A.h B.h+1C.h或h+1D任意假定一棵度为3的树的结点个数为50,则它的最小深度为—如最大深度为_5d。A3 B4 C5 D6试找出分别满足下列条件的所有二叉树：⑴前序序列和中序序列相同：只有右子树⑵中序序列和后序序列相同：只有左子树⑶前序序列和后序序列相同：只有根，空二叉树8二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法(A)(A)正确(B)错误由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法(B)(A)正确(B)错误已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac，它的前序遍历序列是(D)。(A)acbed(B)decab(C)deabc(D)cedba某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(D)。(A)bdgcefha(B)gdbecfha(C)bdgaechf(D)gdbehfca在一非空二叉树的中序遍历序列中，根结点的右边(C)(A)只有右子树上的所有结点 (B)只有右子树上的部分结点(C)只有左子树上的部分结点 (D)只有左子树上的所有结点15.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序(B)(A)不发生改变 (B)发生改变(C)不能确定(D)以上都不对第七章图图的基本概念：图的基本术语及推论邻接矩阵：邻接矩阵的定义图的遍历深度优先遍历广度优先遍历1、 对于上图所示的有向图，其深度优先搜索遍历序列为ADFCEB，广度优先搜索遍历序列为ABCDEF，其拓扑排序序列为A(去掉A发出的射线)B(去掉B发出的射线)EDFC。2、 一个具有N个顶点的完全无向图的边数为1/2N(N-1)；一个具有N个顶点的完全有向图的弧数为N(N-1)。3、 在有向图中，总入度、总出度和总边数相等。在无向图中，总度数是总边数的两倍。4、 一个有16个顶点的无向图，至少应该有15(n-1)条边才能确保它是连通图。5、 给出下面所示有向图的邻接矩阵。第九章排序1.直接排序：直接插入、直接选择算法思想直接插入排序法：依次将待排序数据元素按其关键字的大小插入到有序区的适当位置上，这就是直接插入排序法。Eg:(25，6，23，11，67，45)25，6，23，11，67，456,25，23，11，67，4523,25,11，67，45(在有序区内进行比较排序)直接选择排序法：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。Eg:(70,89,3,8,25,18)先固定第一个元素，然后从剩下的元素中选出最小的，与固定元素比较，交换(3,89,70,8,25,18)(3,8,70,89,25,18)冒泡排序:算法思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。Eg（98,25,70,36,13,85）首先，我们假设是升序排序，98先出来与25比，若大于25,交换继续比较，直到遇见比它大的数字或者到了最后，停下。详细参考书本P295笔记3.快速排序：算法思想首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。快速排序比较难以理解，（31， 68，45， 90， 23， 39， 54， 12， 87， 7631<76,指向31的左指针不用移动；指向76的右指针移动87，12。当到了12之后，因为31>12，交换，（12，68，45， 90， 23， 39， 54， 31， 87， 76）68与31按照前面的，交换！堆排序：堆的定义首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，然后又将它从堆中移走，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。（大根堆：越往上越大；小根堆：越往下越大）按照给出的数据的顺序由上往下建一个堆；根据题目要求，看是要大根堆还是小根堆；从最下面的支点开始调整；1、 排序方法的稳定性是指（BA.排序算法能在规定的时间内完成排序 B.排序算法能得到确定的结果C.排序算法不允许有相同关键字的数据元素D.以上都不对2、 在对一组关键字序列｛70，55，100，15，33，65，50，40，95｝进行直接插入排序时，把65插入到有序序列需要比较（B）次。A.2B.4C.6D.83、 若有关键字序列｛42,70,50,33,40,80｝，则利用快速排序的方法，以第一个关键字为基准元素得到的一次划分结果为（A）。（指着第一个原始元素的那个指针成为不动指针，又叫做伴随指针，另一个指针叫做比较指针）A.40,33,42,50,70,80 B.40,33,80,42,50,70C.40,33,42,80,50,70 D.33,40,42,50,70,804、 以下排序方法中，排序过程中的比较次数与排序方法无关的是（A）A.直接选择排序B.快速排序法 C.堆排序 D.直接插入排序5、 以下（B）排序方法是不稳定的排序方法A.冒泡 B.堆 C.直接插入 D.二路归并以下各种排序方法中，最好情况下时间复杂度为O（n）的是（D）。A.归并排序B.快速排序 C.堆排序D.直接插入排序和冒泡排序在待排序序列局部有序时，效率最高的排序方法是（C）。A.直接选择排序B.快速排序C.直接插入排序和冒泡排序 D.归并排序已知