数据结构820记忆性题总结(By Dawnon)

1、1. 数据结构及算法的相关概念和术语（1） 数据结构及算法的概念；数据结构三要素：逻辑结构、存储结构和数据的运算。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（2） 数据的逻辑结构和存储结构；1. 数据的物理结构主要包括 顺序存储结构 和 链式存储结构 两种情况。2. 数据的逻辑结构是对数据之间关系的描述，主要有 线性结构 和 非线性结构 两大类。3. 线性结构主要包括以下几种数据结构（1） 线性表的顺序和链式结构 （2） 栈和队列 （3） 串 （4） 数组和广义表 （3） 算法的定义及特性；算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作

2、。算法特性：有穷性、确定性、可行性、输入和输出。1. 一个“好”的算法应考虑达到以下目标： 正确性 、 可读性 、 健壮性 和 效率与低存储量需求 。2. 算法是 指令的有限序列 。（4） 算法时间复杂度和空间复杂度的分析方法。O1<Olog2n<On<Onlog2n<On2<On3<O2n<On!<O(nn)2. 线性表（1） 线性表的定义线性表是具有相同数据类型的n（n0）个数据元素的有限序列。1. 数组结构的特性是 它是线性表的扩充 和 可进行随机访问 。（2） 线性表的基本操作及在顺序存储及链式存储上的实现；线性表是一种逻辑结构，顺序表和

3、链表是指存储结构。线性表的基本操作：InitList(&L)Length(L)LocateElem(L,e)GetElem(L,i)ListInsert(&L,i,e)ListDelete(&L,i,&e)PrintList(L)Empty(L)DestroyList(&L)顺序表：静态分配#define MaxSize 50typedef structElemType dataMaxSize; int length;SqList;动态分配#define InitSize 100typedef structElemType *data;int MaxSi

4、ze,length;SeqList;动态分配语句：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);单链表：typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;双链表：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DLinklist;静态链表：#define MaxSize 50typedef structElemType data;int next;SLinkLi

5、stMaxSize;1. 读取数组给定下标的数据元素的操作，称为 取值 操作；存储或修改数组给定下标的数据元素的操作，称为 赋值 操作。1、 线性表有哪两种存储结构？在这两种存储结构中元素之间的逻辑关系分别是通过什么决定的？答：有顺序和链式两种存储结构，顺序结构中元素之间的逻辑关系由物理存储位置决定，链式结构中元素之间的逻辑关系由链指针决定。2、 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时应采取哪种存储表示？为什么？答：采用顺序表。若表的总数基本稳定，且很少进行插入和删除，则顺序表可以充分发挥它的存取速度快、存储利用率高的优点。（3） 各种变形链表（循环链

6、表、双向链表、带头结点的链表等）的表示和基本操作的实现；1、 简述单链表中设置头结点的作用。答：引入头结点后，可以带来两个优点： （1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表其它位置上的操作一致，无须进行特殊处理。 （2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。2、 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？答：采用链表。如果采用顺序表，在多个表并存的情况下，使用表浮动技术在同一存储空间内定义多个

7、顺序表，初始时把整个空间均等地分配给每个表，在问题求解的过程中，一旦发现某个表有放满并溢出的情况，必须移动其它表以扩充溢出表的空间，导致不断把大片空间移来移去，不但时间耗费很大，而且操作复杂，容易出错。如果表的总数还要变化，操作起来就更困难。如果采用链表就没有这些问题，各个表自行扩充，各自操作。3、 为什么在单循环链表中设置尾指针比设置头指针更好？答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使查找链表的开始结点和终端结点都很方便。设置一个带头结点的单循环链表，其尾指针是rear，则开始结点和终端结点分别为指针rear所指结点的后继结点的后继结点和指针rear所指结点，即rear-&

8、gt;next->next和rear，查找时间均为O(1)。若用头指针来表示该链表，则查找开始结点为O(1)，终端结点为O（n）。（4） 递归过程的特点及实现方法；1、 简述递归过程的关键点。答：（1）反复用与原问题相似但更简单的新问题来表示较复杂的原问题，直到问题可解。 （2）不能产生自己调用自己的无穷序列，即必须有递归调用出口。2、 描述堆栈和递归的关系。答：递归过程是一种调用自身的函数，在调用的过程中存在转入子程序的过程。在每次转入子程序前需要保护现场，则将相应参数和中间结果压入系统堆栈，而在子程序返回的时候，需要恢复现场，则将之前压栈的数据从系统堆栈弹出，因此，递归过程存在隐含的

9、堆栈操作，而且子程序的调用过程满足堆栈先进后出的特性。（5） 栈和队列的基本概念；栈和队列的顺序存储结构、链式储存结构及其存储特点；栈是限定仅在一端进行插入或删除操作的线性表，允许进行插入或删除的一端称为栈顶，另一端称为栈底。当n个编号元素以某种顺序进栈，并且可在任意时刻出栈，所获得的编号元素排列的数目N恰好满足Catalan函数的计算，即N=1n+1C2nn栈的基本操作：InitStack(&S)StackEmpty(S)Push(&S,x)Pop(&S,&x)GetTop(S,&x)ClearStack(&S)顺序栈：#define MaxS

10、ize 50typedef structElemType dataMaxSize;int top;SqStack;栈顶指针：S.top，初始时设置S.top = -1栈顶元素：S.dataS.top进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1栈空条件：S.top = -1栈满条件：S.top = MaxSize 1栈长：S.top + 1链栈：typedef struct SNodeElemType data;struct SNode *next;SNode,*LiStack;队列是一种仅允许在表的一端进行插入，而在表的另一端进行删除

11、的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列的基本操作：InitQueue(&Q)QueueEmpty(Q)EnQueue(&Q,x)DeQueue(&Q,&x)GetHead(Q,&x)顺序队列：#define MaxSize 50typedef structElemType dataMaxSize;int front,rear;SqQueue;初始条件：Q.front = Q.rear = 0队空条件：Q.front = Q.rear进队操作：队不满时，+ Q.rear；Q.dataQ.rear = x；出队操作：队不空时，+ Q.

12、front；x = Q.dataQ.front；链式队列：typedef struct QNode/链式队列结点ElemType data;struct QNode *next;QNode;typedef struct/链式队列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计数器法：队满条件：

14、Q.size = MaxSize队空条件：Q.size = 0标志位法：队满条件：tag = 1队空条件：tag = 0若因插入导致Q.front = Q.rear，置tag = 1，若因删除导致Q.front = Q.rear，置tag=0。1. 判定循环队列的满与空，有三种方法，它们是 计数器法 ， 标志位法 和 牺牲一个存储单元法 。（8） 特殊矩阵的压缩储存； 1、 对数组Am×n，它主要有哪两种顺序存储结构？在这两种存储方式中元素aij的存储地址loc(i,j)的值是多少？（注：每个元素占一个存储单元，loc(1,1)=1）答：按行优先存储，loc(i,j)=(i-1)*n

15、+j。 按列优先存储，loc(i,j)=(j-1)*m+i。2、 稀疏矩阵的三元组表的说明中，nu,mu,tu,data存放什么内容？答：nu存稀疏矩阵行数，mu存稀疏矩阵列数，tu存非零元个数，data存放非零元素。3. 广义表的基本概念、存储结构和基本操作1. 广义表难以用 顺序 存储结构，适合编写递归算法的广义表的存储结构是 表头表尾链 。2. 对广义表进行操作，结果总是表的基本操作是 取表尾 操作。4. 树和二叉树（1） 树与森林的基本概念1、 树的路径长度与树的带权路径长度有什么区别？答：树的路径长度是根到每一个结点的路径长度之和；树的带权路径长度为树中所有叶结点的权值与路径长度的乘

16、积的总和。两者的区别为： （1）计算的范围：前者涉及所有结点，后者仅考虑叶结点。 （2）计算的方法：前者仅是路径长度之和，后者是权值与路径长度乘积之和。2、 简述树与线性表结构上的不同点。答：树中结点可有多个后继，但仅有一个前驱，而线性表中一个结点的前驱和后继均最多一个。树中元素的关系是一对多，而线性表是一对一。（2） 树与森林的存储结构及遍历树的存储结构：双亲存储结构、孩子链存储结构和孩子兄弟链存储结构。双亲存储结构：typedef structElemType data;int parent;PTreeMaxSize;孩子链存储结构：typedef struct TNodeElemType

17、 data;struct TNode *sonsMaxSize;TSonNode;孩子兄弟链存储结构：typedef struct TNodeElemType data;struct TNode *nextbrother;struct TNode *firstchild;TSBNode;1. 遍历二叉树实质上是对一个非线性结构进行 线性化 操作。1、 简述树与它的二叉树表示（孩子兄弟表示）间的关系？答：（1）根是同一结点。 （2）二叉树中结点的左孩子域指向树中它的第一个孩子。 （3）二叉树中结点的右孩子域指向树中它的下一个兄弟。（3） 二叉树的定义及6大性质6大性质：（1）n0 = n2 +

18、1（2）二叉树的第i层上最多有2i-1（i1）个结点（3）高度为k的二叉树最多有2k-1（k1）个结点（4）有n个结点的完全二叉树，各结点从上到下、从左到右一次编号（1-n），则有： 如果i!=1，则i结点的双亲为i/2 如果2in，则i结点左孩子为2i；否则无左孩子 如果2i+1n，则i结点右孩子为2i+1；否则无右孩子（5）具有n个结点的完全二叉树的高度为log2(n+1)或log2n+1（6）Catalan函数：给定n个结点，能构成h(n)种不同的二叉树，hn=C2nnn+11、 下图既可以看成是一颗二叉树，又可以看成是一个无向图，试回答两者有何差异。ACBDE答： 二叉树 无向图 有根

19、、叶和层次概念 无 有左右子树之分 无 度的概念：子树个数 度的概念：与顶点连接的边数（4） 二叉树的顺序储存与链式储存结构顺序存储结构：typedef ElemType SqBTreeMaxSize;链式存储结构：typedef struct BTNodeElemType data;struct BTNode *lchild,*rchild;BTNode,*BTree;（5） 二叉树的先序、中序、后序三种遍历方式的关系以及实现；层序遍历的实现先序遍历：递归算法void PreOrder(BTree T)if(T != NULL)visit(T);PreOrder(T->lchild);

20、PreOrder(T->rchild);非递归算法void PreOrder(BTree T)Stack S;InitStack(S);/初始化栈BTree p;if(T != NULL)Push(S,T);/根结点进栈while(!IsEmpty(S)/栈不为空循环Pop(S,p);visit(p);if(p->rchild != NULL) Push(S,p->rchild);/右孩子进栈if(p->lchild != NULL) Push(S,p->lchild);/左孩子进栈中序遍历：递归算法void InOrder(BTree T)if(T != NUL

21、L)InOrder(T->lchild);visit(T);InOrder(T->rchild);非递归算法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;elsePop(S,p);/退栈，访问结点visit(p);p = p->rchild;/向右子树走后序遍历：递归算法void PostOrder(BTree T)if(

22、T != NULL)PostOrder(T->lchild);PostOrder(T->rchild);visit(T);非递归算法void PostOrder(BTree T)Stack S;InitStack(S);/初始化栈BTree p = T,r = NULL;while(p != NULL | !IsEmpty(S)/p不为空或者栈不为空循环if(p != NULL)/走到最左边Push(S,p);p = p->lchild;elseGetTop(S,p);if(p -> rchild != NULL && p->rchild != r

23、)/若右子树存在且未访问p = p->rchild;/向右转Push(S,p);p = p->lchild;/再走到最左else/右子树不存在或已访问Pop(S,p);visit(p);r = p;/记录最近访问过的结点p = NULL;/访问完重置p指针/else/while该算法当访问结点p时，栈中结点恰好是p结点的所有祖先。层次遍历：void LevelOrder(BTree T)Queue Q;InitQueue(Q);/初始化队列BTree p;EnQueue(Q,T);while(!IsEmpty(Q)/队列不为空循环DeQueue(Q,p);visit(p);if(p

24、->lchild != NULL) EnQueue(Q,p->lchild);/左子树不为空则入队if(p->rchild != NULL) EnQueue(Q,p->rchild);/右子树不为空则入队1、 回答满足后序序列和前序序列正好相同的二叉树的树型和正好相反的二叉树的树型各是什么？答：相同：只有一个根节点的二叉树。相反：任意结点均无左孩子的二叉树（仅有右孩子的二叉树） 或任意结点均无右孩子的二叉树（仅有左孩子的二叉树）2、 什么样的二叉树，对它采用任何次序的遍历，结果都相同？答：仅有根结点的二叉树或空二叉树。3、 根据中序、先序、后序遍历二叉树的特点，将根结点

25、、叶结点、叶结点或无左子树结点、叶结点或无右子树结点填入下表空白处。第一个被访问的结点最后一个被访问的结点先序遍历二叉树根结点叶结点中序遍历二叉树叶结点或无左子树结点叶结点或无右子树结点后序遍历二叉树叶结点根结点（6） 线索二叉树的基本概念与构造方法标志域含义：ltag = 0，lchild域指向结点的左孩子；ltag = 1，lchild域指向结点的前驱结点。rtag = 0，rchild域指向结点的右孩子；rtag = 1，rchild域指向结点的后继结点。线索二叉树存储结构：typedef struct TBTNodeElemType data;struct TBTNode *lchil

26、d,*rchild;int ltag,rtag;TBTNode,*TBTree;中序遍历线索化：void InThread(TBTree &p,TBTree &pre)if(p != NULL)InThread(p->lchild,pre);/递归，左子树线索化if(p->lchild = NULL)/左子树为空，建立前驱线索p->lchild = pre;p->ltag = 1;if(pre != NULL && pre->rchild = NULL)pre->rchild = p;/建立前驱结点的后继线索pre->r

27、tag = 1;pre = p;/记录当前遍历结点InThread(p->rchild,pre);/递归，右子树线索化中序遍历线索化主过程：void CreateInThread(TBTree T)TBTree pre = NULL;/前驱结点指针if(T != NULL)InTread(T,pre);pre->rchild = NULL;/处理中序遍历的最后一个结点pre->rtag = 1;求中序线索二叉树中中序序列下的第一个结点：TBTNode *FirstNode(TBTNode *p)while(p->ltag = 0) p = p->lchild;/最

28、左下结点（不是一定是叶结点）return p;求中序线索二叉树中结点p在中序序列下的后继结点：TBTNode *NextNode(TBTNode *p)if(p->rtag = 0) return FirstNode(p->rchild);else return p->rchild;/rtag = 1直接返回后继线索中序线索二叉树的中序遍历算法：void InOrder(TBTNode *T)for(TBTNode *p = FirstNode(T);p != NULL;p = NextNode(p) visit(p);求中序线索二叉树中中序序列下的最后一个结点：TBTNod

29、e *LastNode(TBTNode *p)while(p->rtag = 0) p = p->rchild;/最右下结点（不一定为叶结点）return p;求中序线索二叉树中结点p在中序序列下的前驱结点：TBTNode *PreNode(TBTNode *p)if(p->ltag = 0) return LastNode(p->lchild);else return p->lchild;/ltag = 1直接返回前驱线索1、 简述在中序线索树中，求结点P中元素在中序遍历中的前驱元素存储地址Q的主要步骤。答：（1）当P->ltag = 1，则Q = P-&

30、gt;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）当Q->ltag = 1，则表示Q的左孩子域指向该结点的前驱结点，即N结点，所以N的后继结点为该结点，结束。（4）Q = Q->lchild，转（3）。（7） 树与二叉树的应

31、用：二叉排序树；二叉平衡树；哈夫曼树与哈夫曼编码Nh表示深度为h的平衡树中含有的最少结点数，则N0=0,N1=1,N2=2，并且有Nh=Nh-1+Nh-2+1二叉排序树的存储结构：typedef struct BTNodeint key;struct BTNode *lchild,*rchild;BTNode,*BTree;查找算法：递归BTNode *BSTSearch(BTNode *BT,int key)if(BT = NULL) return NULL;elseif(BT->key = key) return BT;else if(key < BT->key) ret

32、urn 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 < p->key) p = p->lchild;else p = p->rchild;插入算法：int BSTInsert(BTNode *&BT,int key)if(BT = NULL)BT = (BTN

33、ode*)malloc(sizeof(BTNode);BT->lchild = BT->rchild = NULL;BT->key = key;return 1;/返回1，表示成功else if(key = BT->key) return 0;else if(key < BT->key) return BSTInsert(BT->lchild,key);else return BSTInsert(BT->rchild,key);构造算法：void CreatBST(BTNode *&BT,int key,int n)int i;BT =

34、NULL;for(i = 0;i <= n;+ i)BSTInsert(BT,keyi);1、 设HT为哈夫曼树，叶结点a的路径长度La比叶结点b的路径长度Lb长，试证明：叶结点b的权值Wb不小于叶结点a的权值Wa。证：反证法，设Wb<Wa，HT的带权路径长度WPL1=Wa*La+Wb*Lb+OthersOthers为除a,b外其它叶结点的权值与路径长度乘积之和。现交换叶结点a和b，则新树NewT的带权路径长度WPL2=Wa*Lb+Wb*La+OthersWPL1-WPL2=Wa*La+Wb*Lb-(Wa*Lb+Wb*La)=Wa*(La-Lb)-Wb*(La-Lb) =(Wa-W

35、b)*(La-Lb)>0则WPL1不是带权路径最小的树，与HT为哈夫曼树矛盾，故WbWa。2、 试证明若按中序遍历给定二叉树，能得到结点有序序列，则该二叉树是二叉排序树。证：反证法，假设按中序遍历给定二叉树，得到结点有序序列，而该二叉树又不是二叉排序树。设D表示某结点值，L表示该结点的左子树，R表示该结点的右子树，MIN(X)和MAX(X)分别表示X子树的最小、最大值，即存在这样的子树：使不等式MAX(L)<D<MIN(R)不成立，但是按中序遍历给定二叉树的任意子树的顺序一定是LDR，又因得到的是结点的有序序列，所以对任意子树MAX(L)<D<MIN(R)一定成立

36、，假设矛盾。故该二叉树一定是二叉排序树。3、 当查找表有既能较快查找又能适应动态变化的需求时，选用什么查找方法最适合？并简述其理由。答：选用二叉排序树。当较平衡时，二叉排序树的查找性能接近于二分查找，插入删除元素只需修改指针，性能也好。4、 已知一颗二叉排序树BST和中序遍历算法inorder，如何能得到从大到小的结点序列。答：方法一：修改中序遍历算法为RNL，即先递归遍历右子树，输出根结点，然后递归遍历左子树。 方法二：将二叉排序树的所有左右子树交换，然后用中序遍历算法遍历，所输出的结点序列就是从大到小的有序序列。5. 图（1） 图的基本概念和术语；图不可以是空图，即顶点集不能为空，但边集可

37、以为空。1. 设图中顶点数为n，则其生成树有 n-1 条边；若图的边数大于n-1，则一定是 有环 图；若图的边数小于n-1，则一定是 非连通 图。2. 连通分量是无向图中的 极大 连通子图。3. 要保证连通具有10个顶点的无向图，至少需要 37 条边。（9个顶点构成完全图，再加一条边连通第10个顶点）1、 对有向图和无向图，分别描述如何判定图中是否存在回路。答：对有向图，可以用拓扑排序算法来判定图中是否存在回路，当输出顶点数小于顶点数时，图中存在回路，否则图中无回路。2、 什么叫无向图的连通分量和生成树？答：无向图的极大连通子图称为连通分量；图的极小连通子图称为生成树。（2） 图的存储结构：邻

38、接矩阵、邻接表、逆邻接表；邻接矩阵：#define MaxSize 100typedef char VertexType;typedef int EdgeType;typedef structVertexType VexMaxSize;/顶点表EdgeType edgeMaxSizeMaxSize;/边表int vexnum,arcnum;/顶点数、边数MGraph;邻接表：#define MaxSize 100typedef struct ArcNodeint adjvex;/该边所指向的结点位置struct ArcNode *nextarc;/指向下一条边指针ArcNode;typedef

39、 struct VNodeVertexType data;/顶点信息ArcNode *firstarc;/指向第一条边的指针VNode;typedef structVNode adjlistMaxSize;/邻接表int vexnum,arcnum;/顶点数、边数AGraph;1. 在无权的无向图G的邻接矩阵A中，若（vj,vi）属于图G的边集合，则对应元素Aij等于 1 。1、 对n个顶点的无向图，采用邻接表表示时，如何判别下列有关问题？（1）图中有多少条边？（2）任意两个顶点i和j是否有边相连？（3）任意一个顶点的度是多少？答：（1）图中的边数=邻接表链表结点总数的一半 （2）任意两顶点间

40、是否有边相连，可看其中一个顶点的邻接表，若链表中的adjvex域有另一顶点位置的结点，则表示有边相连。 （3）任意一个顶点的度等于该顶点的链表中的结点个数。2、 简述具有n个顶点、带权的无向图的邻接矩阵ga.cost的特点。答：（1）矩阵有n行n列 （2）矩阵是对称的 （3）当vi到vj有边时，ga.cost(i,j)为数值，否则为。（3） 遍历算法：深度优先搜索算法和广度优先搜索算法；DFS空间复杂度：O(v) 时间复杂度：邻接矩阵O(v2) 邻接表O(v+e)BFS空间复杂度：O(v) 时间复杂度：邻接矩阵O(v2) 邻接表O(v+e)DFS：邻接矩阵bool visitedMaxSize

41、;/访问标记组，全初始化为falsevoid DFS(MGraph *G,int v)visitedv = true;visit(v);int i;for(i = 0;i < G->vexnum;+ i)if(G->edgevi && visitedi = false) /v到i有边且未访问则递归访问DFS(G,i);邻接表bool visitedMaxSize;/访问标记组，全初始化为falsevoid DFS(AGraph *G,int v)ArcNode *p;visitedv = true;visit(v);p = G->adjlistv.fir

42、starc;/p指向顶点v的第一条边while(p != NULL)if(visitedp->adjvex = false)/顶点未访问则递归访问它DFS(G,p->adjvex);p = p->nextarc;/p指向顶点的下一条边的终点BFS:邻接矩阵bool visitedMaxSize;/访问标记组，全初始化为falsevoid BFS(MGraph *G,int v)int i;Queue Q;InitQueue(Q);/初始化队列visit(v);visitedv = true;/已访问EnQueue(Q,v);/顶点v入队while(!IsEmpty(Q)/队列

43、不为空时循环DeQueue(Q,v);/顶点出队for(i = 0;i < G->vexnum;+ i)if(G->edgevi && visitedi = false) /v到i有边且未访问visit(i);visitedi = true;EnQueue(Q,i);邻接表bool visitedMaxSize;/访问标记组，全初始化为falsevoid BFS(AGraph *G,int v)ArcNode *p;Queue Q;InitQueue(Q);/初始化队列visit(v);visitedv = true;/已访问EnQueue(Q,v);/顶点v

44、入队while(!IsEmpty(Q)/队列不为空时循环DeQueue(Q,v);/顶点出队p = G->adjlistv.firstarc;/p指向出队顶点v的第一条边while(p != NULL)if(visitedp->adjvex = false)/当前邻接顶点未访问，则进队visit(p->adjvex);visitedp->adjvex = true;EnQueue(Q,p->adjvex);p = p->nextarc;/p指向v的下一条边/while/while1. 对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度

45、是 O(n+e) 。1、 图的遍历结果所依赖的因素有哪些？答：顶点编号，存储结构和所执行的算法。（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)lowcosti = G.edgev0i;/初始化最短边vseti = 0;/初始化树集合vsetv0 = 1;/将v0并入树中sum = 0;/树权值初始化for(i

46、 = 1;i < G.vexnum;+ i)min = INF;/INF是已定义比图中所有权值都大的常量for(j = 0;j < G.vexnum;+ j)if(vsetj = 0 && lowcostj < min)/选出当前生成树到其余顶点min = lowcostj;k = j;/记录树到其余顶点最短边对应点vsetk = 1;/加入树集合v = k;sum += min;for(j = 0;j < G.vexnum;+ j)if(vsetj = 0 && G.edgevj < lowcostj)lowcostj = G.e

47、dgevj;/更新最短边普里姆算法时间复杂度O(v2)，适用于稠密图。Kruskal（克鲁斯卡尔算法）typedef structint 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.arcnum;sum = 0;for(i

48、 = 0;i < N;+ i) vi = i;sort(road,E);/对road数组中的E条边按其权值从小到大排序for(i = 0;i < E;+ i)a = getRoot(roadi.a);b = getRoot(roadi.b);if(a != b)/不在一个集合中va = b;/合并两颗树sum += roadi.w;/求生成树权值克鲁斯卡尔算法时间复杂度与排序算法sort有关，适合于稀疏图。最短路径：Dijkstra（迪杰斯特拉算法）void Dijkstra(MGraph G,int v,int dist,int path)int setMaxSize;int m

49、in,i,j,u;for(i = 0;i < G.vexnum;+ i)/初始化disti = G.edgevi;seti = 0;if(G.edgevi < INF) /INF为已定义的常量，边权为INF表示两顶点无边pathi = v;elsepathi = -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)/未加入源S且距离小于minu = j;min = distj;

50、set u = 1;/将选出的顶点并入最短路径中for(j = 0;j < G.vexnum;+ i)/更新源S与剩余顶点距离if(setj = 0 && distu + G.edgeuj < distj)distj = distu + G.edgeuj;pathj = u;/for/for迪杰斯特拉算法时间复杂度O（n2）。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.v

51、exnum;+ j)Aij = G.edgeij;/初始化pathij = -1;for(k = 0;k < G.vexnum;+ k)/经过k顶点for(i = 0;i < G.vexnum;+ i)for(j = 0;j < G.vexnum;+ j)/i->j距离if(Aij > Aik + Akj)Aij = Aik + Akj;pathij = k;弗洛伊德算法时间复杂度O（n3）。拓扑排序：typedef struct VNodeVertexType data;/顶点信息int count;/新增部分，统计当前入度ArcNode *firstarc;/指向第一条边的指针VNode;bool TopSort(AGraph *G)int i,j,n = 0;Stack S;InitStack(S);/初始化栈ArcNode *p;for(i = 0;i < G->vexnum;+ i)if(G->adjlisti.count =