《数据结构820记忆性题总结(ByDawnon)(共32页)376.pdf》由会员分享，可在线阅读，更多相关《数据结构820记忆性题总结(ByDawnon)(共32页)376.pdf（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.数据结构及算法(sun f)的相关概念和术语（1）数据结构及算法(sun f)的概念；数据结构(sh j ji u)三要素：逻辑结构、存储结构和数据(shj)的运算。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（2）数据的逻辑结构和存储结构；1.数据的物理结构主要包括 顺序存储结构 和 链式存储结构 两种情况。2.数据的逻辑结构是对数据之间关系的描述，主要有 线性结构 和 非线性结构 两大类。3.线性结构主要包括以下几种数据结构（1）线性表的顺序和链式结构（2）栈和队列（3）串（4）数组和广义表 （3）算法的定义及特性；算法是对特定问题求解步骤的一种描述，它是指令的有限序列，
2、其中每一条指令表示一个或多个操作。算法特性：有穷性、确定性、可行性、输入和输出。1.一个“好”的算法应考虑达到以下目标：正确性、可读性、健壮性 和 效率与低存储量需求。2.算法是 指令的有限序列。（4）算法时间复杂度和空间复杂度的分析方法。2.线性表（1）线性表的定义 线性表是具有相同数据类型的 n（n0）个数据元素的有限序列。1.数组结构的特性是 它是线性表的扩充 和 可进行随机访问。（2）线性表的基本操作及在顺序存储及链式存储上的实现；线性表是一种逻辑结构，顺序表和链表是指存储结构。线性表的基本操作：InitList(&L)Length(L)LocateElem(L,e)GetElem(L
3、,i)ListInsert(&L,i,e)ListDelete(&L,i,&e)PrintList(L)Empty(L)DestroyList(&L)顺序(shnx)表：静态(jngti)分配#define MaxSize 50 typedef struct ElemType dataMaxSize;int length;SqList;动态分配#define InitSize 100 typedef struct ElemType*data;int MaxSize,length;SeqList;动态分配语句(yj)：L.data=(ElemType*)malloc(sizeof(ElemTyp
4、e)*InitSize);单链表：typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;双链表：typedef struct DNode ElemType data;struct DNode*prior,*next;DNode,*DLinklist;静态(jngti)链表：#define MaxSize 50 typedef struct ElemType data;int next;SLinkListMaxSize;1.读取数组给定下标的数据元素的操作，称为 取值 操作；存储或修改数组给定下标的数据元素的操作
5、，称为 赋值 操作。1、线性表有哪两种存储结构？在这两种存储结构中元素之间的逻辑关系分别是通过什么决定的？答：有顺序和链式两种存储结构，顺序结构中元素之间的逻辑关系由物理存储位置决定，链式结构中元素之间的逻辑关系由链指针决定。2、若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时应采取哪种存储表示？为什么？答：采用顺序表。若表的总数基本稳定，且很少进行插入和删除，则顺序表可以充分发挥它的存取速度快、存储利用率高的优点。（3）各种变形链表（循环链表、双向链表、带头结点(ji din)的链表等）的表示和基本操作的实现；1、简述(jin sh)单链表中设置头结点的作用。
6、答：引入头结点后，可以(ky)带来两个优点：（1）由于开始结点的位置(wi zhi)被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表其它位置上的操作一致，无须进行特殊处理。（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。2、如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？答：采用链表。如果采用顺序表，在多个表并存的情况下，使用表浮动技术在同一存储空间内定义多个顺序表，初始时把整个空间均等地分配给每个表，在问题求解的过程中，一旦发
7、现某个表有放满并溢出的情况，必须移动其它表以扩充溢出表的空间，导致不断把大片空间移来移去，不但时间耗费很大，而且操作复杂，容易出错。如果表的总数还要变化，操作起来就更困难。如果采用链表就没有这些问题，各个表自行扩充，各自操作。3、为什么在单循环链表中设置尾指针比设置头指针更好？答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使查找链表的开始结点和终端结点都很方便。设置一个带头结点的单循环链表，其尾指针是 rear，则开始结点和终端结点分别为指针 rear 所指结点的后继结点的后继结点和指针rear所指结点，即 rear-next-next 和 rear，查找时间均为 O(1)。若用头指
8、针来表示该链表，则查找开始结点为 O(1)，终端结点为 O（n）。（4）递归过程的特点及实现方法；1、简述递归过程的关键点。答：（1）反复用与原问题相似但更简单的新问题来表示较复杂的原问题，直到问题可解。（2）不能产生自己调用自己的无穷序列，即必须有递归调用出口。2、描述堆栈和递归的关系。答：递归过程是一种调用自身的函数，在调用的过程中存在转入子程序的过程。在每次转入子程序前需要保护现场，则将相应参数和中间结果压入系统堆栈，而在子程序返回的时候，需要恢复现场，则将之前压栈的数据从系统堆栈弹出，因此，递归过程存在隐含的堆栈操作，而且子程序的调用过程满足堆栈先进后出的特性。（5）栈和队列的基本概念
9、；栈和队列的顺序存储结构、链式储存结构及其存储特点；栈是限定仅在一端进行插入或删除操作的线性表，允许进行插入或删除的一端称为栈顶，另一端称为栈底。当 n 个编号元素以某种顺序进栈，并且可在任意时刻出栈，所获得的编号元素排列的数目N 恰好满足 Catalan 函数的计算，即 栈的基本操作：InitStack(&S)StackEmpty(S)Push(&S,x)Pop(&S,&x)GetTop(S,&x)ClearStack(&S)顺序(shnx)栈：#define MaxSize 50 typedef struct ElemType dataMaxSize;int top;SqStack;栈顶指
10、针(zhzhn)：S.top，初始(ch sh)时设置 S.top=-1 栈顶元素(yun s)：S.dataS.top 进栈操作：栈不满时，栈顶指针先加 1，再送值到栈顶元素 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减 1 栈空条件：S.top=-1 栈满条件：S.top=MaxSize 1 栈长：S.top+1 链栈：typedef struct SNode ElemType data;struct SNode*next;SNode,*LiStack;队列是一种仅允许在表的一端进行插入，而在表的另一端进行删除的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列的基本操作：
11、InitQueue(&Q)QueueEmpty(Q)EnQueue(&Q,x)DeQueue(&Q,&x)GetHead(Q,&x)顺序队列：#define MaxSize 50 typedef struct ElemType dataMaxSize;int front,rear;SqQueue;初始条件：Q.front=Q.rear=0 队空条件：Q.front=Q.rear 进队操作：队不满时，+Q.rear；Q.dataQ.rear=x；出队操作(cozu)：队不空时，+Q.front；x=Q.dataQ.front；链式队列(duli)：typedef struct QNode /链式
12、队列(duli)结点 ElemType data;struct QNode*next;QNode;typedef struct /链式队列(duli)QNode*front,*rear;LiQueue;当 Q.front=NULL 且 Q.rear=NULL 时，链式队列为空。1、栈和队列各有什么特点，什么情况下用到栈，什么情况下用到队列？答：栈的主要特点是“后进先出”，栈的应用十分广泛，通常将递归算法转换成非递归算法时需要使用栈，栈的应用有括号匹配、算术表达式求值和迷宫问题求解等。队列的主要特点是“先进先出”，队列的应用也十分广泛，特别在操作系统资源分配和排队论中大量地使用队列，还有队列在层
13、次遍历中的应用。2、队列是一个表头和表尾，既能插入又能删除的线性表。该说法是否正确？为什么？答：不正确。队列是一个限制只能在表头删除和只能在表尾插入的线性表，上述说法只说明了队列有表头和表尾，而插入和删除位置没有具体限定。（6）栈和队列的应用（7）循环队列的判满、判空方法；牺牲一个存储单元法：队满条件：(Q.rear+1)%MaxSize=Q.front 队空条件：Q.front=Q.rear 队列中元素个数：(Q.rear Q.front+MaxSize)%MaxSize 计数器法：队满条件：Q.size=MaxSize 队空条件：Q.size=0 标志位法：队满条件：tag=1 队空条件：
14、tag=0 若因插入导致 Q.front=Q.rear，置 tag=1，若因删除导致 Q.front=Q.rear，置tag=0。1.判定循环队列的满与空，有三种方法，它们是 计数器法，标志位法 和 牺牲一个存储单元法。（8）特殊矩阵的压缩储存；1、对数组，它主要有哪两种顺序存储结构？在这两种存储方式中元素的存储地址loc(i,j)的值是多少？（注：每个元素占一个存储单元，loc(1,1)=1）答：按行优先存储，loc(i,j)=(i-1)*n+j。按列优先存储，loc(i,j)=(j-1)*m+i。2、稀疏矩阵的三元组表的说明中，nu,mu,tu,data 存放什么内容？答：nu 存稀疏(x
15、sh)矩阵行数，mu 存稀疏矩阵列数，tu 存非零元个数，data 存放非零元素。3.广义(gungy)表的基本概念、存储结构和基本操作 1.广义(gungy)表难以用 顺序(shnx)存储结构，适合编写递归算法的广义表的存储结构是 表头表尾链。2.对广义表进行操作，结果总是表的基本操作是 取表尾 操作。4.树和二叉树（1）树与森林的基本概念 1、树的路径长度与树的带权路径长度有什么区别？答：树的路径长度是根到每一个结点的路径长度之和；树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。两者的区别为：（1）计算的范围：前者涉及所有结点，后者仅考虑叶结点。（2）计算的方法：前者仅是路径
16、长度之和，后者是权值与路径长度乘积之和。2、简述树与线性表结构上的不同点。答：树中结点可有多个后继，但仅有一个前驱，而线性表中一个结点的前驱和后继均最多一个。树中元素的关系是一对多，而线性表是一对一。（2）树与森林的存储结构及遍历 树的存储结构：双亲存储结构、孩子链存储结构和孩子兄弟链存储结构。双亲存储结构：typedef struct ElemType data;int parent;PTreeMaxSize;孩子链存储结构：typedef struct TNode ElemType data;struct TNode*sonsMaxSize;TSonNode;孩子兄弟链存储结构：typed
17、ef struct TNode ElemType data;struct TNode*nextbrother;struct TNode*firstchild;TSBNode;1.遍历二叉树实质上是对一个非线性结构进行 线性化 操作。1、简述树与它的二叉树表示（孩子兄弟表示）间的关系？答：（1）根是同一结点。（2）二叉树中结点的左孩子域指向树中它的第一个孩子。（3）二叉树中结点的右孩子域指向树中它的下一个兄弟。（3）二叉树的定义及 6 大性质 6 大性质(xngzh)：（1）n0=n2+1（2）二叉树的第 i 层上最多有（i1）个结点(ji din)（3）高度(god)为 k 的二叉树最多有（k
18、1）个结点(ji din)（4）有 n 个结点的完全二叉树，各结点从上到下、从左到右一次编号（1-n），则有：如果 i!=1，则 i 结点的双亲为i/2 如果 2in，则 i 结点左孩子为 2i；否则无左孩子 如果 2i+1n，则 i 结点右孩子为 2i+1；否则无右孩子（5）具有 n 个结点的完全二叉树的高度为或+1（6）Catalan 函数：给定 n 个结点，能构成 h(n)种不同的二叉树，1、下图既可以看成是一颗二叉树，又可以看成是一个无向图，试回答两者有何差异。答：二叉树 无向图 有根、叶和层次概念 无 有左右子树之分 无 度的概念：子树个数 度的概念：与顶点连接的边数（4）二叉树的顺
19、序储存与链式储存结构 顺序存储结构：typedef ElemType SqBTreeMaxSize;链式存储结构：typedef struct BTNode ElemType data;struct BTNode*lchild,*rchild;BTNode,*BTree;（5）二叉树的先序、中序、后序三种遍历方式的关系以及实现；层序遍历的实现 先序遍历：递归算法 void PreOrder(BTree T)if(T!=NULL)visit(T);PreOrder(T-lchild);PreOrder(T-rchild);非递归算法(sun f)void PreOrder(BTree T)A C
20、 B D E Stack S;InitStack(S);/初始化栈 BTree p;if(T!=NULL)Push(S,T);/根结点(ji din)进栈 while(!IsEmpty(S)/栈不为空循环(xnhun)Pop(S,p);visit(p);if(p-rchild!=NULL)Push(S,p-rchild);/右孩子(hi zi)进栈 if(p-lchild!=NULL)Push(S,p-lchild);/左孩子进栈 中序遍历：递归算法 void InOrder(BTree T)if(T!=NULL)InOrder(T-lchild);visit(T);InOrder(T-rch
21、ild);非递归算法 void InOrder(BTree T)Stack S;InitStack(S);/初始化栈 BTree p=T;while(p!=NULL|!IsEmpty(S)/栈不为空或 p 不为空时循环 if(p!=NULL)Push(S,p);/遇到非空二叉树先左走 p=p-lchild;else Pop(S,p);/退栈，访问结点 visit(p);p=p-rchild;/向右子树走 后序(hu x)遍历：递归算法(sun f)void PostOrder(BTree T)if(T!=NULL)PostOrder(T-lchild);PostOrder(T-rchild);
22、visit(T);非递归算法(sun f)void PostOrder(BTree T)Stack S;InitStack(S);/初始化栈 BTree p=T,r=NULL;while(p!=NULL|!IsEmpty(S)/p 不为空或者(huzh)栈不为空循环 if(p!=NULL)/走到最左边 Push(S,p);p=p-lchild;else GetTop(S,p);if(p-rchild!=NULL&p-rchild!=r)/若右子树存在且未访问 p=p-rchild;/向右转 Push(S,p);p=p-lchild;/再走到最左 else/右子树不存在或已访问 Pop(S,p)
23、;visit(p);r=p;/记录最近访问过的结点 p=NULL;/访问完重置 p 指针 /else/while 该算法当访问结点 p 时，栈中结点恰好是 p 结点的所有(suyu)祖先。层次(cngc)遍历：void LevelOrder(BTree T)Queue Q;InitQueue(Q);/初始化队列(duli)BTree p;EnQueue(Q,T);while(!IsEmpty(Q)/队列(duli)不为空循环 DeQueue(Q,p);visit(p);if(p-lchild!=NULL)EnQueue(Q,p-lchild);/左子树不为空则入队 if(p-rchild!=N
24、ULL)EnQueue(Q,p-rchild);/右子树不为空则入队 1、回答满足后序序列和前序序列正好相同的二叉树的树型和正好相反的二叉树的树型各是什么？答：相同：只有一个根节点的二叉树。相反：任意结点均无左孩子的二叉树（仅有右孩子的二叉树）或任意结点均无右孩子的二叉树（仅有左孩子的二叉树）2、什么样的二叉树，对它采用任何次序的遍历，结果都相同？答：仅有根结点的二叉树或空二叉树。3、根据中序、先序、后序遍历二叉树的特点，将根结点、叶结点、叶结点或无左子树结点、叶结点或无右子树结点填入下表空白处。第一个被访问的结点 最后一个被访问的结点 先序遍历二叉树 根结点 叶结点 中序遍历二叉树 叶结点或
25、无左子树结点 叶结点或无右子树结点 后序遍历二叉树 叶结点 根结点 （6）线索二叉树的基本概念与构造方法 标志域含义：ltag=0，lchild 域指向结点的左孩子；ltag=1，lchild 域指向结点的前驱结点。rtag=0，rchild 域指向结点的右孩子；rtag=1，rchild 域指向结点的后继结点。线索二叉树存储结构：typedef struct TBTNode ElemType data;struct TBTNode*lchild,*rchild;int ltag,rtag;TBTNode,*TBTree;中序遍历线索化：void InThread(TBTree&p,TBTre
26、e&pre)if(p!=NULL)InThread(p-lchild,pre);/递归，左子树线索(xin su)化 if(p-lchild=NULL)/左子树为空，建立(jinl)前驱线索 p-lchild=pre;p-ltag=1;if(pre!=NULL&pre-rchild=NULL)pre-rchild=p;/建立前驱(qinq)结点的后继线索 pre-rtag=1;pre=p;/记录(jl)当前遍历结点 InThread(p-rchild,pre);/递归，右子树线索化 中序遍历线索化主过程：void CreateInThread(TBTree T)TBTree pre=NULL;
27、/前驱结点指针 if(T!=NULL)InTread(T,pre);pre-rchild=NULL;/处理中序遍历的最后一个结点 pre-rtag=1;求中序线索二叉树中中序序列下的第一个结点：TBTNode*FirstNode(TBTNode*p)while(p-ltag=0)p=p-lchild;/最左下结点（不是一定是叶结点）return p;求中序线索二叉树中结点 p 在中序序列下的后继结点：TBTNode*NextNode(TBTNode*p)if(p-rtag=0)return FirstNode(p-rchild);else return p-rchild;/rtag=1 直接返
28、回后继线索 中序线索二叉树的中序遍历算法：void InOrder(TBTNode*T)for(TBTNode*p=FirstNode(T);p!=NULL;p=NextNode(p)visit(p);求中序线索(xin su)二叉树中中序序列下的最后(zuhu)一个(y)结点：TBTNode*LastNode(TBTNode*p)while(p-rtag=0)p=p-rchild;/最右下结点(ji din)（不一定为叶结点）return p;求中序线索二叉树中结点 p 在中序序列下的前驱结点：TBTNode*PreNode(TBTNode*p)if(p-ltag=0)return Last
29、Node(p-lchild);else return p-lchild;/ltag=1 直接返回前驱线索 1、简述在中序线索树中，求结点 P 中元素在中序遍历中的前驱元素存储地址 Q 的主要步骤。答：（1）当 P-ltag=1，则 Q=P-lchild，结束（2）Q=P-lchild（3）当 Q-rtag=1，则结束。（4）Q=Q-rchild，转（3）2、简述在中序线索二叉树中找结点 N 的后继结点的主要思想。答：（1）若 N-rtag=1，则表示 P 的右孩子域指向后继结点，N 的后继结点为 N-rchild，结束，否则执行（2）。（2）Q=P-rchild，即转向 P 的右孩子。（3）当
30、 Q-ltag=1，则表示 Q 的左孩子域指向该结点的前驱结点，即 N 结点，所以 N 的后继结点为该结点，结束。（4）Q=Q-lchild，转（3）。（7）树与二叉树的应用：二叉排序树；二叉平衡树；哈夫曼树与哈夫曼编码 表示深度为 h 的平衡树中含有的最少结点数，则，并且有 二叉排序树的存储结构：typedef struct BTNode int key;struct BTNode*lchild,*rchild;BTNode,*BTree;查找算法：递归 BTNode*BSTSearch(BTNode*BT,int key)if(BT=NULL)return NULL;else if(BT-
31、key=key)return BT;else if(key key)return BSTSearch(BT-lchild,key);else return BSTSearch(BT-rchild,key);非递归 BTNode*BSTSearch(BTNode*BT,int key)BTNode*p=BT;while(p!=NULL&key!=p-key)if(key key)p=p-lchild;else p=p-rchild;插入(ch r)算法：int BSTInsert(BTNode*&BT,int key)if(BT=NULL)BT=(BTNode*)malloc(sizeof(BT
32、Node);BT-lchild=BT-rchild=NULL;BT-key=key;return 1;/返回 1，表示(biosh)成功 else if(key=BT-key)return 0;else if(key key)return BSTInsert(BT-lchild,key);else return BSTInsert(BT-rchild,key);构造(guzo)算法：void CreatBST(BTNode*&BT,int key,int n)int i;BT=NULL;for(i=0;i=n;+i)BSTInsert(BT,keyi);1、设 HT 为哈夫曼树，叶结点(ji
33、din)a 的路径长度 La 比叶结点 b 的路径长度 Lb 长，试证明：叶结点 b 的权值 Wb 不小于叶结点 a 的权值 Wa。证：反证法，设 Wb0 则 WPL1 不是带权路径最小的树，与 HT 为哈夫曼树矛盾，故 WbWa。2、试证明若按中序遍历给定二叉树，能得到结点有序序列，则该二叉树是二叉排序树。证：反证法，假设按中序遍历给定二叉树，得到结点有序序列，而该二叉树又不是二叉排序树。设 D 表示某结点值，L 表示该结点的左子树，R 表示该结点的右子树，MIN(X)和 MAX(X)分别表示 X 子树的最小、最大值，即存在这样的子树：使不等式MAX(L)DMIN(R)不成立，但是按中序遍历
34、给定二叉树的任意子树的顺序一定是LDR，又因得到的是结点的有序序列，所以对任意子树 MAX(L)DMIN(R)一定成立，假设矛盾。故该二叉树一定是二叉排序树。3、当查找表有既能较快查找又能适应动态变化的需求时，选用什么查找方法(fngf)最适合？并简述其理由。答：选用(xunyng)二叉排序树。当较平衡时，二叉排序树的查找(ch zho)性能接近于二分查找，插入删除元素只需修改指针，性能也好。4、已知一颗二叉排序(pi x)树 BST 和中序遍历算法 inorder，如何能得到从大到小的结点序列。答：方法一：修改中序遍历算法为 RNL，即先递归遍历右子树，输出根结点，然后递归遍历左子树。方法二
35、：将二叉排序树的所有左右子树交换，然后用中序遍历算法遍历，所输出的结点序列就是从大到小的有序序列。5.图（1）图的基本概念和术语；图不可以是空图，即顶点集不能为空，但边集可以为空。1.设图中顶点数为 n，则其生成树有 n-1 条边；若图的边数大于 n-1，则一定是 有环 图；若图的边数小于 n-1，则一定是 非连通 图。2.连通分量是无向图中的 极大 连通子图。3.要保证连通具有 10 个顶点的无向图，至少需要 37 条边。（9 个顶点构成完全图，再加一条边连通第 10 个顶点）1、对有向图和无向图，分别描述如何判定图中是否存在回路。答：对有向图，可以用拓扑排序算法来判定图中是否存在回路，当输
36、出顶点数小于顶点数时，图中存在回路，否则图中无回路。2、什么叫无向图的连通分量和生成树？答：无向图的极大连通子图称为连通分量；图的极小连通子图称为生成树。（2）图的存储结构：邻接矩阵、邻接表、逆邻接表；邻接矩阵：#define MaxSize 100 typedef char VertexType;typedef int EdgeType;typedef struct VertexType VexMaxSize;/顶点表 EdgeType edgeMaxSizeMaxSize;/边表 int vexnum,arcnum;/顶点数、边数 MGraph;邻接表：#define MaxSize 10
37、0 typedef struct ArcNode int adjvex;/该边所指向的结点位置 struct ArcNode*nextarc;/指向(zh xin)下一条边指针 ArcNode;typedef struct VNode VertexType data;/顶点(dngdin)信息 ArcNode*firstarc;/指向(zh xin)第一条边的指针 VNode;typedef struct VNode adjlistMaxSize;/邻接(ln ji)表 int vexnum,arcnum;/顶点数、边数 AGraph;1.在无权的无向图 G 的邻接矩阵 A 中，若（vj,vi
38、）属于图 G 的边集合，则对应元素Aij等于 1。1、对 n 个顶点的无向图，采用邻接表表示时，如何判别下列有关问题？（1）图中有多少条边？（2）任意两个顶点 i 和 j 是否有边相连？（3）任意一个顶点的度是多少？答：（1）图中的边数=邻接表链表结点总数的一半 （2）任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若链表中的 adjvex 域有另一顶点位置的结点，则表示有边相连。（3）任意一个顶点的度等于该顶点的链表中的结点个数。2、简述具有 n 个顶点、带权的无向图的邻接矩阵 ga.cost 的特点。答：（1）矩阵有 n 行 n 列 （2）矩阵是对称的 （3）当 vi 到 vj 有边时
39、，ga.cost(i,j)为数值，否则为。（3）遍历算法：深度优先搜索算法和广度优先搜索算法；DFS 空间复杂度：时间复杂度：邻接矩阵 邻接表 BFS 空间复杂度：时间复杂度：邻接矩阵 邻接表 DFS：邻接矩阵 bool visitedMaxSize;/访问标记组，全初始化为 false void DFS(MGraph*G,int v)visitedv=true;visit(v);int i;for(i=0;i vexnum;+i)if(G-edgevi&visitedi=false)/v 到 i 有边且未访问则递归访问 DFS(G,i);邻接表 bool visitedMaxSize;/访问
40、标记组，全初始化为 false void DFS(AGraph*G,int v)ArcNode*p;visitedv=true;visit(v);p=G-adjlistv.firstarc;/p 指向(zh xin)顶点v 的第一条边 while(p!=NULL)if(visitedp-adjvex=false)/顶点(dngdin)未访问则递归访问它 DFS(G,p-adjvex);p=p-nextarc;/p 指向顶点(dngdin)的下一条边的终点 BFS:邻接矩阵 bool visitedMaxSize;/访问(fngwn)标记组，全初始化为 false void BFS(MGraph
41、*G,int v)int i;Queue Q;InitQueue(Q);/初始化队列 visit(v);visitedv=true;/已访问 EnQueue(Q,v);/顶点 v 入队 while(!IsEmpty(Q)/队列不为空时循环 DeQueue(Q,v);/顶点出队 for(i=0;i vexnum;+i)if(G-edgevi&visitedi=false)/v 到 i 有边且未访问 visit(i);visitedi=true;EnQueue(Q,i);邻接表 bool visitedMaxSize;/访问标记组，全初始化为 false void BFS(AGraph*G,int
42、 v)ArcNode*p;Queue Q;InitQueue(Q);/初始化队列 visit(v);visitedv=true;/已访问 EnQueue(Q,v);/顶点 v 入队 while(!IsEmpty(Q)/队列不为空时循环 DeQueue(Q,v);/顶点出队 p=G-adjlistv.firstarc;/p 指向出队顶点 v 的第一条边 while(p!=NULL)if(visitedp-adjvex=false)/当前邻接顶点(dngdin)未访问，则进队 visit(p-adjvex);visitedp-adjvex=true;EnQueue(Q,p-adjvex);p=p-
43、nextarc;/p 指向(zh xin)v 的下一条边/while/while 1.对有 n 个顶点(dngdin)、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度是 O(n+e)。1、图的遍历结果所依赖(yli)的因素有哪些？答：顶点编号，存储结构和所执行的算法。（4）应用：最小生成树；最短路径，拓扑排序和关键路径。最小生成树：Prim（普里姆算法）void Prim(MGraph G,int v0,int&sum)int lowcostMaxSize,vsetMaxSize,v;int i,j,k,min;v=v0;for(i=0;i G.vexnum;+i)lowcos
44、ti=G.edgev0i;/初始化最短边 vseti=0;/初始化树集合 vsetv0=1;/将 v0 并入树中 sum=0;/树权值初始化 for(i=1;i G.vexnum;+i)min=INF;/INF 是已定义(dngy)比图中所有权值都大的常量 for(j=0;j G.vexnum;+j)if(vsetj=0&lowcostj min)/选出当前(dngqin)生成树到其余顶点 min=lowcostj;k=j;/记录树到其余(qy)顶点最短边对应点 vsetk=1;/加入(jir)树集合 v=k;sum+=min;for(j=0;j G.vexnum;+j)if(vsetj=0&
45、G.edgevj lowcostj)lowcostj=G.edgevj;/更新最短边 普里姆算法时间复杂度，适用于稠密图。Kruskal（克鲁斯卡尔算法）typedef struct int a,b;/a,b 为一条边所连的两个顶点 int w;/边的权值 Road;Road roadMaxSize;int vMaxSize;/定义并查集数组 int getRoot(int a)/在并查集中查找根结点 while(a!=va)a=va;return a;void Kruskal(MGraph G,int&sum,Road road)int i,N,E,a,b;N=G.vexnum;E=G.ar
46、cnum;sum=0;for(i=0;i N;+i)vi=i;sort(road,E);/对 road 数组中的 E 条边按其权值从小到大排序(pi x)for(i=0;i E;+i)a=getRoot(roadi.a);b=getRoot(roadi.b);if(a!=b)/不在一个(y)集合中 va=b;/合并(hbng)两颗树 sum+=roadi.w;/求生成(shn chn)树权值 克鲁斯卡尔算法时间复杂度与排序算法 sort 有关，适合于稀疏图。最短路径：Dijkstra（迪杰斯特拉算法）void Dijkstra(MGraph G,int v,int dist,int path)
47、int setMaxSize;int min,i,j,u;for(i=0;i G.vexnum;+i)/初始化 disti=G.edgevi;seti=0;if(G.edgevi INF)/INF 为已定义的常量，边权为 INF 表示两顶点无边 pathi=v;else pathi=-1;setv=1;pathv=-1;for(i=1;i=G.vexnum;+i)min=INF;for(j=0;j G.vexnum;+i)if(setj=0&distj min)/未加入(jir)源 S 且距离小于min u=j;min=distj;set u=1;/将选出的顶点(dngdin)并入最短路径中
48、for(j=0;j G.vexnum;+i)/更新源 S 与剩余(shngy)顶点距离 if(setj=0&distu+G.edgeuj distj)distj=distu+G.edgeuj;pathj=u;/for/for 迪杰斯特拉算法(sun f)时间复杂度。Floyd（弗洛伊德算法）void Floyd(MGraph G,int AMaxSize,int pathMaxSize)int i,j,k;for(i=0;i G.vexnum;+i)for(j=0;j G.vexnum;+j)Aij=G.edgeij;/初始化 pathij=-1;for(k=0;k G.vexnum;+k)/
49、经过 k 顶点 for(i=0;i G.vexnum;+i)for(j=0;j j 距离(jl)if(Aij Aik+Akj)Aij=Aik+Akj;pathij=k;弗洛伊德算法(sun f)时间复杂度。拓扑(tu p)排序：typedef struct VNode VertexType data;/顶点(dngdin)信息 int count;/新增部分，统计当前入度 ArcNode*firstarc;/指向第一条边的指针 VNode;bool TopSort(AGraph*G)int i,j,n=0;Stack S;InitStack(S);/初始化栈 ArcNode*p;for(i=0
50、;i vexnum;+i)if(G-adjlisti.count=0)Push(S,i);/入度为 0 顶点(dngdin)进栈 while(!IsEmpty(S)/栈不为空循环(xnhun)Pop(S,i);/顶点(dngdin)出栈 print(i);/输出(shch)i 顶点 +n;/统计当前顶点 p=G-adjlisti.firstarc;while(p!=NULL)j=p-adjvex;-(G-adjlistj.count);/i 顶点引出的边所指向的顶点入度减 1 if(G-adjlistj.count=0)Push(S,j);/入度为 0 的顶点入栈 p=p-nextarc;if