数据结构复习题：图单选题1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_____倍。

A,1/2 B,1C,2 D,42、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_____。

A,n B, n+1 C,n-1 D,n+e3、具有n个顶点的无向完全图，边的总数为_____条。

A,n-1 B,n C,n+1 D,n*(n-1)/24、在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于_____ 。

A,i+j B,i-j C,1D,05、在n个结点的线索二叉树中,线索的数目为______.A,n-1 B,n C,n+1 D,2n6、在二叉排序中,凡是新插入的结点,都是没有______的.A孩子B关键字C平衡因子D赋值7、深度为5的二叉树至多有_______个结点.A,16 B,32 C,31 D,108、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为_________。

A,s B,s-1 C,s+1 D,n9、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为_________。

A,s B,s-1 C,s+1 D,2s10、在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为_________。

A,n B,e C,n+e D,2e11、在一个具有n个顶点的无向完全图中，所含的边数的_________。

A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/212、在一个具有n个顶点的有向完全图中，所含的边数为_________。

A,n B,n(n-1) C,n(n-1)/2 D,n(n+1)/213、在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为_________。

A,k B,k+1 C,k+2 D,2k14、对于一个具有n个顶点的无向连通图，它留念的连通分量的个数为_________。

A,0 B,1C,n D,n+115、若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用_________次深度优先于搜索遍历的算法。

A,k B,1C,k-1 D,k+116、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为_________。

A,n B,n*e C,e D, 2*e17、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为_________。

A,n B,n*e C,e D,2*e18、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为_________A,n B,2n C,e D,2e19、在一个无权图的邻接表表示中，每个边结点至少包含_________域。

A,１B,２C,３D,４20、对于一个有向图，若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为_________A,k1 B,k2 C,k1-k2 D,k1+k221、对于一个有向图，若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为_________。

A,k1 B,k2 C,k1-k2 D,k1+k222、对于一个无向图，下面_________说法是正确的。

A,每个顶点的入度等于出度B,每个顶点的度等于其入度出度之和C,每个顶点的入度为０D,每个顶点的出度为０23、在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_________。

A,出边数B入边数C度数D度数减１24、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为_________。

A: A,B,C,F,D,E B: A,C,F,D,E,B C: A,B,D,C,F,E D: A,B,D,F,E,C25、若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为_________。

A, 1,2,5,4,3B,1,2,3,4,5 C,1,2,5,3,4 D,1,4,3,2,526、若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为_________。

A,1,2,3,4,5 B,1,2,4,3,5 C,1,2,4,5,3 D,1,4,2,5,329、在n个顶点的有向无环无权图的邻接矩阵中至少有_________个零元素。

A,n B,n(n-1)2 C,n(n+1)2 D,n(n-1)判断题1、有回路的图不能进行拓扑排序。

T数据结构算法题1,设计一个将邻接表转换为邻接矩阵的算法.void ListToMat(ALGraph *G,MGraph &g){ int i,j,n=G->n;ArcNode *p;for (i=0;i<n;i++){ p=G->adjlist[i].firstarc;while (p!=NULL){ g.edges[i][p->adjvex]=1;p=p->nextarc;}}g.vexnum=n;g.arcnum=G->e;}填空题1、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__________，对于有向图来说等于该顶点的__________。

度数|出度数2、已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的顶点序列为__________，按广度优先搜索遍历得到的顶点序列为__________。

A B C D E F┏0 1 1 0 1 0┓A┃1 0 1 0 1 1┃B┃1 1 0 1 0 0┃C┃0 0 1 0 0 1┃D┃1 1 0 0 0 1┃E┗0 1 0 1 1 0┛F ABCDFE|ABCEFD3、对二叉排序树进行______遍历,可以得到按关键字从小到大排列的结点序列中序4、任何一棵子树的结点个数减边数等于______,总边数等于各结点_____之和.1|出度、扇出5、己知一棵完全二叉树中共有562个结点，则该树中共有______个叶子结点. 2816、在一个具有n个顶点的无向完全图中，包括有____________条边，在一个具有n个顶点的有向完全图中，包含有____________条件。

n(n-1)2 | n(n-2)7、已知一个连通图的边集为{(1,2)3,(1,3)6,(1,4)8,(2,3)4,(2,5)10,(3,5)12,(4,5)2}，则度为３的顶点个数有____________个。

48、一个有向图的顶点集为{a,b,c,d,e,f},边集为{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},则出度为０的顶点个数为____________，入度为１的顶点个数为____________。

2|49、在一个连通图中存在着____________个连通分量110、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为____________＊____________。

N|N11、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点的个数分别为____________和____________。

e |2e12、在有向图的邻接和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有____________和____________结点。

出边|入边13、一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)},从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。

a,c,d,e,b| a,c,e,d,b14、根据图的存储结构进行某种次序的遍历，从某顶点出发得到的顶点序列是____________的唯一问答题1、无向图G如下图：B E/ \ / \A D G\ / \ /C F试给出(1)该图的邻接矩阵。

(2)该图的邻接表。

(3)从A出发的“深度优先”遍历序列。

(4)从A出发的“广度优先”遍历序列。

解答：(1) 图G的邻接矩阵┏０１１００００┓┃１００１０００┃┃１００１０００┃A＝┃０１１０１１０┃┃０００１００１┃┃０００１００１┃┗００００１１０┛(2)邻接表如见：┌─┬─┐┌─┬─┐┌─┬─┐１│Ａ│┼→─┤Ｂ│┼→─┤Ｃ│＾│├─┼─┤├─┼─┤├─┼─┤２│Ｂ│┼→─┤Ａ│┼→─┤Ｄ│＾│├─┼─┤├─┼─┤├─┼─┤３│Ｃ│┼→─┤Ａ│┼→─┤Ｄ│＾│├─┼─┤├─┼─┤├─┼─┤┌─┬─┐┌─┬─┐４│Ｄ│┼→─┤Ｂ│┼→─┤Ｃ│┼→┤Ｅ│＾├→─┤Ｆ│＾│2、用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否有关?答：设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。

3、对于稠密图和稀疏图,就存储空间而言,采用邻接矩阵和邻接表哪个更好些? 答：稠密图采用邻接矩阵好，稀疏图采用邻接表好。

4、请回答下列关于图的一些问题:(1) 有n个顶点的有向强连通图最多有多少条边?这样的图应该是什么形状?(2) 有n个顶点的有向强连通图最少有多少条边?这样的图应该是什么形状?(3) 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?答：（1）最多有n(n-1)条边（2）最少有n条边（3）106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）5、对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何判别下列有关问题?(1) 图中有多少条边?(2) 任意两个顶点i和j是否有边相连?(3) 任意一个顶点的度是多少?答：无向图采用邻接表时，⑴边表中的结点个数之和除以2。

⑵第i个边表中是否含有结点j。

⑶该顶点所对应的边表中所含结点个数。

6、己知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树.答：二叉树及线索二叉树（略）。

先序序列为：abcdefghij7、下列整数序列由选序遍历一棵二叉排序树得到:50,40,30,45,65,55,70,80.试构造一棵这样的二叉排序树.答：5040 6530 45 55 7080。