数据结构复习整理

1、功能：建立空的线性表L;2 销毁操作DetroyList(&L)功能：回收为线性表L动态分配的存储空间；3 置空操作ClearList(&L)功能：L中已存在，重新将其置成空表；4 判空操作ListEmpty(L)功能：判断线性表L是否为空表，若为空表返回TRUE否则返回FALSE5 求表长操作ListLength(L)功能：返回线性表L的表长；6 取元素操作：GetElem(L,i,&e)功能：将线性表L中第i个元素赋值给e;7 查找操作LocateElem(L,e,compare()功能：在线性表L中查找与元素e满足compare。的第1个元素，返回该元素在表中的序

2、号(或位置)，若表中不存在这样的元素，则返回0;8 查找前驱PriorElem(L,cur_e,&pre_e)功能：若cur_e是L中的数据元素且不是第一个，则用pre_e返回它的前驱，否则失败，pre_e无定义。9 查找后继NextElem(L,cur_e,&next_e)功能：若cur_e是L中的数据元素且不是最后一个，则用next_e返回它的后继，否则失败，next_e无定义。10 插入操作Listinsert(&L,i,e)功能：在线性表L的第i个元素之前插入1个新元素e;11 删除操作ListDelete(&L,i,&e)功能：删除线性表L的第

3、i个元素，并用e返回；12 遍历操作ListTraverse(L,visit()功能：依次对线性表L的每个元素调用函数visit()。若visit()失败，则返回ERROR否则返回OK;顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序(没有规定元素进栈顺序),平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时

4、在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。作为一般规律，当线性表中元素个数变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表

5、顺序结构，链表比较方便插入和删除操作。对线性表的基本操作栈是限定仅能在表尾一端进行插入、删除操作的线性表能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。1、栈是限定仅能在表尾一端进行插入、删除操作的线性表2、栈的元素具有后进先出的特点3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针出藏腾愿栈的特点后进先出第个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素栈的示意图最后一个出栈的元素为栈底元素队列是限定仅能在表头进行删除，表尾进行插入的线性表。能进行插入的一端称为队尾，能进行删除的一端

6、称为队头。称插入操作为入队，删除操作为出队。队列的示意图第一个入队的元素在队头最后一个入队的元素在队尾wM第一个出队的元素为队头元素J-丁丁”最后一个出队的元素为队尾元素三、队列的应用1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；3）离散事件的模拟一一模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程。1、队列是限定仅能在表尾一端进行插入，表头一端进行删除的线性表；2、队列中的元素具有先进先出的特点；3、队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示；4、入队操作要修改队尾指针，出队操作要修改队头指针。数组的概念数量固定，数据类型相

7、同的（变量）元素组合在一起。使用一个名称代表它。这个名称就是数组名。如果要访问其中某个元素（变量），可以使用元素的索引值（下标）来访问它。在C语言中，数组元素的索引值从0开始。数组的存储两种形式：既可以是顺序存储，也可以采用链式结构。稀疏矩阵含有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵如何设计递归函数？一、分治法（DivideandConquer）（又称分割求解法）二、后置递归法（Postponingthework）三、回溯法（Backtracking）递归函数一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：2.必须有一

8、个终止条件。树的表不1）图木表不2）二兀组表本3）文氏图表示4）广义表表示5）凹入表示法（类似书的目录）树的基本术语树的结点：包含一个数据元素的内容及若干指向子树的分支。孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如B是E的双亲。兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。堂兄结点：同一层上结点；如G与E、FH、I、J互为堂兄。祖先结点：某一结点的祖先是从根到该结点所经分支上的所有结点；如H的祖先为A、Do子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、CD、E、F、G、H、I、Jo结点的度

9、：结点子树的个数；如叶子结点：也叫终端结点，是度为分枝结点：度不为0的结点；如D的度为3。0的结点；如E、F、G、H、I、JoA、B、CDo结点：数据元素+若干指向子树的分支结点的度：分支的个数树的度：树中所有结点的度的最大值叶子结点：度为零的结点分支结点：度大于零的结点结点的层次：假设根结点的层次为1,第l层的结点的子树根结点的层次为1+1树的深度：树中叶子结点所在的最大层次二叉树一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉

10、树中编号为1至n的结点对应遍历的基本概念遍历：按某种搜索路径访问二叉树中的每个结点，且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据等。遍历是各种数据结构最基本的操作，许多其它的操作可以在遍历基础上实现。遍历对线性结构来说很容易解决，但二叉树每个结点都可能有两棵子树，因而需要寻找一种规律，使得二叉树上的结点能线性排列。二叉树的遍历二叉树的遍历，就是按某种次序访问二叉树中的结点，要求每个结点访问一次且仅访问一次。二叉树由根、左子树、右子树三部分组成。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树。令：L:遍历左子树D:访问根结点R:遍历右子树有

11、六种遍历方法：基本：DLRLDRLRD镜象：DRL,RDL,RLD例：先序遍历、中序遍历、-,+,a,*,b,-,c,d,/,e,fa，+,b,*,c,-,d,-,e,/,fa，b，c，d，-,*,+，e，f,/,-DLRLDRLRD,分别根据访问根结点的次序称为：先序约定先左后右，有三种遍历方法:遍历、中序遍历和后序遍历。最优二叉树(赫夫曼树)先序遍历序列:中序遍历序列:后序遍历序列:哈夫曼树：假设有n个权彳t(wi,w2,，W,构造有n个叶子结点的二叉树，每个叶子结点有一个Wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。图(Graph)图G是由两个集合V(G)和E(G即成的，记为

12、G=(V,E)其中：V(G)是顶点的非空有限集E(G谑边的有限集合，边是顶点的无序对或有序对。图的分类有向图无向图有向图一一有向图G是由两个集合V(G)和E(G即成的。其中：V(G)是顶点的非空有限集。E(G谑有向边(也称弧)(的有限集合，弧是顶点的有序对，记为<v,w>,v,w是顶点，v为弧尾，w为弧头。无向图一一无向图G是由两个集合V(G)和E(G即成的。其中：V(G)是顶点的非空有限集。E(G)是边的有限集合，边是顶点的无序对，记为(v,w)=(w,v)。?图的基本术语1邻接点及关联边邻接点：边的两个顶点关联边：若边e=(v,u),则称顶点v、u关连边e2顶点的度、入度、出度

13、顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n,边数为e图的所有顶点的度数和=2*e(每条边对图的所有顶点的度数和贡献”2度)(v,w)或(w,v),并且1、数据结构在计算机内存中的表示是指A.数据的存储结构B.数据元素的结构C.数据的逻辑结构D.数据元素之间的关系答案：A2、在数据结构中，与所使用的计算机无关的是A.数据的存储结构B.逻辑和物理结构C.数据的逻辑结构D.数据的物理结构答案：C3、对于给定的n个元素，可以构造出的逻辑结构有、四种。答案：集合线性结构树结构图结构1、线性表

14、的顺序存储结构是通过何种方式表示元素之间的关系。A.保存后继元素地址B.元素的存储顺序C.保存左、右孩子地址D.后继元素的数组下标B当对一个线性表经常进行的是读取操作，而很少进行插入和删除操作时，则采用存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用存储结构为宜。顺序链式3、若线性表最常用的操作是存取第i个元素及其前趋和后继元素的值，为节省时间应采用的存储方式是。答案：顺序表4、在p所指向的结点后插入由q指向的新结点的语句序列是。A) p->next=q;q->next=p->next;B) q=p->next;p->next=q;C) q->ne

15、xt=p->next;p->next=q;q->next=p;D)p=p->next;答案：C5、若长度为n的线性表采用顺序存储结构，在其第i个位置之前插入一个新元素的算法的时间复杂度为。(iwiwn+1)A)O(n)B)O(1)C)O(n2)D)O(log2n)答案：A6、若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储结构算法的时间效率最高的是。A)单链表C)双向链表B)给出表尾指针的单循环链表D)给出表尾指针双向循环链表答案：D?编程题1编写一算法，实现单链表的原地置逆。即利用原来的结点将线性表L=(a1,a2,an变换为：L=

16、(an,a2,a1)?编程题2将两个非递减有序的有序单链表la和lb归并为非递增的有序表。TypedefstructintLNodestructLnodedata;/数据域next;/指针域LNode,*LinkList;LinkListla,lb;/单链表的头指针请用la和lb中的结点合并生成一个新的非递增的有序单链表lc。合并完成后，la和lb为空链表。?编程题3设一带头结点的双向循环链表表示的线性表：L=(a1,a2,an请写出一个时间复杂度为O(n)的算法，将L改造为：L=(a1,a2,an,a2,a1)1、已知一堆栈的进栈序列为：1234,则下列哪个序列为不可能的出栈序列：A)123

17、4B)4321C)2143D)4123答案：D2、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？A)1和5B)2和4C)4和2D)5和1答案：B3、写出循环队列队空、队满的判断方法及条件(一种)。答案：方法：少用一个存储单元判满条件(Q.rear+1)%Q.queuesize=Q.front判空条件Q.rear=Q.front4、若将一个双端队列顺序表示在一维数组Vm中，两个端点设为endl和end2，并组织成一个循环队列。试写出双端队列所用指针endl和end2的初始化条件及队空

18、与队满条件。end1*en<12双端队列实际上就是一个双端的栈。假设：end1端顺时针进栈，end2端逆时针进栈初始化条件：end1=end2=0;队空条件：end1=end2;队满条件：(end1+1)%m=end2;1、树最适合用来表示A)B)C)D)答案：有序数据元素无序数据元素兀系之间具有分支层次关系的数据元素之间无联系的数据C2、在一非空二叉树的中序遍历序列中，根结点的右边A)B)C)D)答案：3、设只有右子树上的所有结点只有右子树上的部分结点只有左子树上的所有结点只有左子树上的部分结点An为一棵二叉树上的两个结点，在中序遍历时,n在m前的条件是A) n在C)n在答案：Cm右方

19、m左方B) n是m祖先D)n是m子孙4、试分别找出满足以下条件的所有二叉树:(2)答案：二叉树的前序二叉树的中序二叉树的前序序列与序列与序列与中序后序后序序列相同;序列相同;序列相同。(2)空树或缺左子树的单支树；空树或缺右子树的单支树；空树或只有根结点的二叉树。5、为了将遍历结果还原为惟一的二叉树，应当知道的遍历条件是A)B)C)D)答案:先序遍历和后序遍历先序遍历和层次遍历中序遍历和层次遍历中序遍历和后序遍历D6、已知二叉树的前序扩充序列如下:3*12*45*请画出对应的二叉树。答案：7、已知一棵二叉树的不同遍历结果:先序遍历结果:中序遍历结果:求该二叉树。答案：1、判断一个有向图是否有环

20、（回路）A）求结点的度C）求关键路径的方法是B）拓扑排序D）求最短路径答案：B2、在有向图的邻接表存储结构中，顶点v在链表中出现的次数是A）顶点的v的度C）顶点v的入度答案：C3、用邻接矩阵表示图时,B）顶点v的出度D）依附于顶点v的边数若图中有100个顶点，100条边，则形成的矩阵有多少元素？有多少非零元素？答案：邻接矩阵中的元素有1002=10000个。它有100个非零元素（对于有向图）或200个非零元素（对于无向图）.二叉树的五个性质简答：?性质1:在二叉机勺第i层上至多有2i-1个结点（i>1）o?性质2:深度为k的二叉树上至多含2k-1个结点（k>1）o?性质3:对任何一

21、棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1?性质4:具有n个结点的完全二叉树的深度为Jog2nl+1。?性质5:若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：（1）若i=1,则该结点是二叉树的根，无双亲；否则i#1,编号为皿的结点为其双亲结点；（2）若2i>n,则该结点无左孩子；否则，编号为2i的结点为其左孩子结点；（3）若2i+1>n,则该结点无右孩子结点；否则，编号为2i+1的结点为其右孩子结点。什么是数据结构？Whenyouareoldandgreyandfullofsleep,Andnoddingbythefire,takedownthisbook,Andslowlyread,anddreamofthesoftlookYoureyeshadonce,andoftheirshadowsdeep;Howmanylovedyourmomentsofgladgrace,Andlovedyourbeautywithlovefalseortrue,But