图的存储结构邻接矩阵表示法

图-存储结构-数组表⽰法（邻接矩阵）⽂字描述 ⽤两个数组分别存储顶点信息和边/弧信息。

⽰意图算法分析 构造⼀个采⽤邻接矩阵作存储结构、具有n个顶点和e条边的⽆向⽹(图)G的时间复杂度是(n*n + e*n), 其中对邻接矩阵G.arcs的初始化耗费了n*n的时间。

借助于邻接矩阵容易判定两个顶点之间是否有边/弧相连，并容易求得各个顶点的度。

对于⽆向图，顶点vi的度是邻接矩阵地i⾏(或第i列)的元素之和；对于有向图，第i⾏的元素之和为顶点vi的出度；第j列的元素之和为顶点vj的⼊度；代码实现1/*2以数组表⽰法(邻接矩阵)作为图的存储结构创建图。

3*/4 #include <stdio.h>5 #include <stdlib.h>6 #include <string.h>78#define INFINITY 100000 //最⼤值9#define MAX_VERTEX_NUM 20 //最⼤顶点数10 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向⽹，⽆向图，⽆向⽹}11 typedef int VRType;12 typedef char VertexType;13 typedef struct{14char note[10];15 }InfoType;16 typedef struct ArcCell{17 VRType adj; //顶点关系类型：1)对⽆权图，⽤1或0表⽰相邻否；2)对带权图，则为权值类型18 InfoType *info; //该弧相关信息的指针19 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];20 typedef struct{21 VertexType vexs[MAX_VERTEX_NUM]; //顶点向量22 AdjMatrix arcs; //邻接矩阵23int vexnum, arcnum; //图的当前顶点数和弧数24 GraphKind kind; //图的种类标志25 }MGraph;2627/*28若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。

一、单选题C01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A)1/2 B)1 C)2 D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A)1/2 B)1 C)2 D)4B03、有8个结点的无向图最多有条边。

A)14 B)28 C)56 D)112C04、有8个结点的无向连通图最少有条边。

A)5 B)6 C)7 D)8C05、有8个结点的有向完全图有条边。

A)14 B)28 C)56 D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A)O(n) B)O(e) C)O(n+e) D)O(n2)C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、图的深度优先遍历类似于二叉树的。

A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历D14、图的广度优先遍历类似于二叉树的。

《数据结构》期末复习题及参考答案- 第7章图//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 注意：做复习题时，请结合阅读教材，钻研教材，参考课件////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、以下数据结构中，哪种具有非线性结构？A．栈B．队列C．双向链表D．十字链表2、下面关于图的存储的叙述中正确的是（）。

A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。

C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。

D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历4、图的广度优先遍历算法类似于树的（）。

A. 中根遍历B. 先根遍历C. 后根遍历D. 按层次遍历5、设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．06、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A．n-1 B．n C．n+1 D．nlogn；7、一个含有n个顶点的非连通图，则（）：A．它的边一定不大于n-1 B．它的边一定不大于nC．它的边一定小于n-1 D．它的边一定大于08、要连通具有n个顶点的有向图，至少需要（）条边。

第1章绪论1、填空题1.常见的数据结构有集合，_线性__结构，__树形___结构，__图形__结构等四种。

2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。

3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。

2、选择题1. 算法的计算量的大小称为计算的（B）。

A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C）A．问题的规模 B. 待处理数据的初态 C. A和B D. 以上都不对3.计算机算法指的是（1）（c），它必须具备（2）（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4. 下面关于算法说法错误的是（D）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的3、应用题1、给出以下算法的时间复杂度.void fun(int n){int i=1,k=100;while(i<n){k=k+1;i=i+2;}}时间复杂度为____O（n）_____。

2、给出以下算法的时间复杂度.void fun2(int n){int i=1,k=100;while(i<n){i=i*10;k=k+1;}}时间复杂度为____O（log n）___________。

第2章线性表1、填空题1. 线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。

2.顺序表采用__随机___访问机制对数据元素进行访问。

3.若在单链表结点p的后面插入一个新的结点s，则其操作序列为:①____s->next=p->next_____________；②____p->next=s___________________；4.在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。

数据结构课程设计报告设计题目：图的邻接矩阵存储结构院系计算机学院年级x 级学生xxxx学号xxxxxxxxxx指导教师xxxxxxxxx起止时间10-6/10-102013年10月10日目录1 需求分析 (3)2 概要设计 (4)2.1 ADT描述 (4)2.2程序模块结构 (5)2.3各功能模块 (6)3详细设计 (7)3.1类的定义 (7)3.2 初始化 (8)3.3 图的构建操作 (8)3.4 输出操作 (9)3.5 get操作 (9)3.6 插入操作 (10)3.7 删除操作 (10)3.8 求顶点的度操作 (11)3.10 判断连通操作 (12)3.11 主函数 (13)4 调试分析 (16)4.1调试问题 (16)4.2 算法时间复杂度 (16)5用户手册 (16)5.1 主界面 (16)5.2 创建图 (17)5.3插入节点 (17)5.4 深度优先遍历 (17)5.5 求各顶点的度 (18)5.6 输出图 (18)5.7 判断是否连通 (19)5.8 求边的权值 (19)5.9 插入边 (19)5.10 删除边 (20)结论 (20)参考文献 (20)摘要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。

本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。

首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。

其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。

然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。

再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。

然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。

邻接矩阵的基本操作
首先，创建邻接矩阵是指根据图的节点和边的信息构建邻接矩阵。

通常情况下，我们可以使用二维数组来表示邻接矩阵，数组的行和列分别对应图中的节点，而数组中的元素则表示节点之间的连接关系。

如果节点i和节点j之间有边相连，则邻接矩阵中第i行第j列的元素为1，否则为0。

其次，查询邻接关系是指根据邻接矩阵来确定图中节点之间的连接关系。

通过访问邻接矩阵中的特定元素，我们可以判断两个节点之间是否存在边相连，从而确定它们的邻接关系。

另外，添加节点和删除节点也是邻接矩阵的基本操作之一。

当需要向图中添加新节点时，我们可以扩展邻接矩阵的行和列，并根据新的节点信息来更新邻接矩阵。

而当需要删除节点时，我们可以删除邻接矩阵中与该节点相关的行和列，同时调整其他节点的索引以保持邻接矩阵的正确性。

除了上述基本操作外，邻接矩阵还可以进行其他操作，如修改边的权重、遍历邻接矩阵以获取特定信息等。

总之，邻接矩阵是一种非常实用的图表示方法，在实际应用中有着广泛的用途。

通过合
理地运用邻接矩阵的基本操作，我们可以对图进行高效地管理和分析。

第一部分：数据结构——线性结构(顺序表、链表、栈、队列、数组、串)考点：1、时间复杂度2、数据的逻辑结构与存储结构相关知识——分类、与存储结构之间的关系3、顺序表的知识——特点4、链表的知识——编程求单链表中结点的个数、插入、删除。

5、栈与队列知识——特点、循环队列、基本术语、链队列6、数组与矩阵——求元素的地址、稀疏矩阵行优先存储:下标从1开始:Loc(A i,j) = Loc(A1,1)+[(i-1)*n+j-1]*b下标从0开始:Loc(A i,j) = Loc(A0,0)+(i*n+j)*b 列优先存储:下标从1开始:Loc(A i,j) = Loc(A1,1)+[(j-1)*m+i-1]*b下标从0开始:Loc(A i,j) = Loc(A0,0)+(j*m+i)*b1. 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___________个数据元素；删除第i个位置上的数据元素需要移动表中___________个元素。

2.数据的逻辑结构通常有集合、线性结构、_________ 和 _________ 四类结构。

3.若进栈序列为a、b、c ，且进栈和出栈可以穿插进行，则可能出现_________个不同的出栈序列。

4.在栈结构中，允许插入的一端称为 _________；在队列结构中，允许删除的一端称为 _________。

5. 下列程序段的时间复杂度为_____________s=0;for(i=1;i<n;i++)for(j=1;j<n;j++)s+=i*j;6. 假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件（）A、head= =NULLB、head->next= =NULLC、head!=NULLD、head->next= =head7. 栈是一种操作受限的线性结构，其操作的主要特点是（）A、先进先出B、后进先出C、进优于出D、出优于进8. 假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

1.采用邻接矩阵（邻接表）存储，构造无向图（网）输入：顶点数、边数、顶点信息、边信息输出：图的顶点，图的边邻接矩阵（数组表示法）处理方法：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。

假设图G＝(V,E)有n个顶点，则邻接矩阵是一个n×n 的方阵，定义为：如果(vi,vj)属于边集，则edges[i][j]=1，否则edges[i][j]=0。

邻接表存储的处理方法：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

程序代码：#include<iostream>using namespace std;#define MAX_VERTEX_NUM 20 //最大顶点个数#define OK 1typedef int Status;//图的数组（邻接矩阵）存储表示typedef struct ArcCell { // 弧的定义int adj; // VRType是顶点关系类型。

// 对无权图，用1或0表示相邻否；// 对带权图，则为权值类型。

int *info; // 该弧相关信息的指针} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct { // 图的定义char vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs; // 邻接矩阵int vexnum, arcnum; // 图的当前顶点数、弧数} MGraph;int LocateV ex(MGraph G, char v){int a;for (int i = 0; i <= G.vexnum; i++){if (G.vexs[i] == v)a= i;}return a;}Status CreateUDN(MGraph &G) { //采用邻接矩阵表示法，构造无向网Gint i, j, k, w;char v1, v2;cout <<"输入顶点数，边数："<< endl;cin >> G.vexnum >> G.arcnum;//IncInfo为0,表示各弧无信息cout <<"各顶点分别为："<< endl;for (i = 0; i<G.vexnum; i++)cin >> G.vexs[i]; //构造顶点向量for (i = 0; i<G.vexnum; i++) //初始化邻接矩阵for (j = 0; j<G.vexnum; j++){G.arcs[i][j].adj =NULL;}cout <<"顶点信息、边信息："<< endl;for (k = 0; k<G.arcnum; k++) { //构造邻接矩阵cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值i = LocateV ex(G, v1); j = LocateV ex(G, v2);G.arcs[i][j].adj = w;G.arcs[j][i] = G.arcs[i][j];} return OK;} //CreateUDN (p162 算法7.2)Status printf1(MGraph G){cout <<"该图的顶点分别为：";for (int i = 0; i<G.vexnum; i++)cout << G.vexs[i] <<"";return OK;}Status printf2(MGraph G){cout <<"该图的边为：";for (int i = 1; i<G.vexnum; i++) //初始化邻接矩阵for (int j = 0; j<i; j++){if (G.arcs[i][j].adj !=NULL)cout << G.vexs[j]<< G.vexs[i] <<"," ;}return OK;}int main(){MGraph G;CreateUDN(G);printf1(G);cout << endl;printf2(G);cout << endl;system("pause");return 0;}。

第6章 图【例6-1】回答下列问题：（1）具有n 个顶点的连通图至少有多少条边（2）具有n 个顶点的强连通图至少有多少条边这样的图应该是什么形状 （3）具有n 个顶点的有向无环图最多有多少条边 解：（1）具有n 个顶点的连通图至少有n-1条边。

这是一个与生成树相关的问题。

生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集，任何一个生成树都具有n-1边。

因此，具有n 个顶点的连通图至少有n-1条边。

（2）具有n 个顶点的强连通图至少有n 条边，这样的图是一个由n 个顶点构成的环。

强连通图是相对于有向图而言的。

由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2×n/2=n 。

（3）具有n 个顶点的有向无环图最多有n ×(n —1)/2条边。

这是一个拓扑排序相关的问题。

—个有向无环图至少可以排出一个拓扑序列，不妨设这n 个顶点排成的拓扑序列为v1，v2，v3，…，vn ，那么在这个序列中，每个顶点vi 只可能与排在它后面的顶点之间存在着以vi 为弧尾的弧，最多有n-i 条，因此在整个图中最多有(n-1)+(n-2)+ … +2+1=n ×(n-1)/2条边。

2．图的存储结构常用的存储结构有邻接矩阵和邻接表。

（1）邻接矩阵表示法设G ＝(V ，E)是有n(n ≥1)个顶点的图。

则G 的邻接矩阵是按如下定义的n 阶方阵：例如，图6-1中G1，Ｇ2的邻接矩阵分别表示为A1、A2，矩阵的行列号对应于图6-1中结点的序号。

由邻接矩阵的定义可知，无向图的邻接矩阵必定是对称阵；有向图的邻接矩阵不一定是对称的。

根据邻接矩阵，很容易判定任意两个顶点之间是否有边相连。

求各顶点的度也是非常容易的。

图的两种存储⽅式---邻接矩阵和邻接表图：图是⼀种数据结构，由顶点的有穷⾮空集合和顶点之间边的集合组成，表⽰为G(V,E)，V表⽰为顶点的集合，E表⽰为边的集合。

⾸先肯定是要对图进⾏存储，然后进⾏⼀系列的操作，下⾯对图的两种存储⽅式邻接矩阵和邻接表尽⾏介绍。

（⼀）、邻接矩阵存储：⽤两个数组分别进⾏存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

存储顶点：⽤⼀个连续的空间存储n个顶点。

存储顶点之间的边：将由n个顶点组成的边⽤⼀个n*n的矩阵来存储，如果两个顶点之间有边，则表⽰为1，否则表⽰为0。

下⾯⽤代码来实现邻接矩阵的存储：#define SIZE 10class Graph{public:Graph(){MaxVertices = SIZE;NumVertices = NumEdges = 0;VerticesList = new char[sizeof(char)*MaxVertices];Edge = new int*[sizeof(int*)*MaxVertices];int i,j;for(i = 0;i<MaxVertices;i++)Edge[i] = new int[sizeof(int)*MaxVertices];for(i = 0;i<MaxVertices;i++){for(j = 0;j<MaxVertices;++j)Edge[i][j] = 0;}}void ShowGraph(){int i,j;cout<<"";for(i = 0;i<NumVertices;i++)cout<<VerticesList[i]<<"";cout<<endl;for(i = 0;i<NumVertices;i++){cout<<VerticesList[i]<<"";for(j = 0;j<NumVertices;j++)cout<<Edge[i][j] <<"";cout<<endl;}cout<<endl;}int GetVertexPos(char v){int i;for(i = 0;i<NumVertices;i++){if(VerticesList[i] == v)return i;}return -1;}~Graph(){Destroy();}void Insert(char v){if(NumVertices < MaxVertices){VerticesList[NumVertices] = v;NumVertices++;}}void InsertEdge(char v1,char v2){int i,j;int p1 = GetVertexPos(v1);int p2 = GetVertexPos(v2);if(p1 == -1 || p2 == -1)return ;Edge[p1][p2] = Edge[p2][p1] = 1;NumEdges++;}void RemoveEdge(char v1,char v2){int p1 = GetVertexPos(v1);int p2 = GetVertexPos(v2);if(p1 == -1 || p2== -1)return;if(Edge[p1][p2] == 0)return;Edge[p1][p2] = Edge[p2][p1] = 0;NumEdges--;}void Destroy(){delete[] VerticesList;VerticesList = NULL;for(int i = 0;i<NumVertices;i++){delete Edge[i];Edge[i] = NULL;}delete[] Edge;Edge = NULL;MaxVertices = NumVertices = 0;}void RemoveVertex(char v){int i,j;int p = GetVertexPos(v);int reNum = 0;if(p == -1)return;for(i = p;i<NumVertices-1;i++){VerticesList[i] = VerticesList[i+1];}for(i = 0;i<NumVertices;i++){if(Edge[p][i] != 0)reNum++;}for(i = p;i<NumVertices-1;i++){for(j = 0;j<NumVertices;j++){Edge[i][j] = Edge[i+1][j];}}for(i = p;i<NumVertices;i++){for(j = 0;j<NumVertices;j++)Edge[j][i] = Edge[j][i+1];}NumVertices--;NumEdges = NumEdges - reNum;}private:int MaxVertices;int NumVertices;int NumEdges;char *VerticesList;int **Edge;};上⾯的类中的数据有定义最⼤的顶点的个数（MaxVertices），当前顶点的个数（NumVertices），当前边的个数（NumEdges），保存顶点的数组，保存边的数组。

理工大学2020年硕士学位研究生招生考试业务课考试大纲考试科目：数据结构代码：991考试的总体要求考查学生对数据的逻辑结构和物理结构的基本概念的掌握，对基本的数据结构和算法的掌握；考查学生利用基本数据结构和算法，使用C语言来解决实际科学和理论问题的思想和能力。

基本内容一、线性表1．线性表的概念及特点2．线性表的逻辑结构3．线性表的顺序及链式存储结构4．相关的各种基本运算二、栈和队列1．栈的概念、特点及存储结构2．栈的基本运算3．栈的应用4．队列的概念、特点及存储结构5．链队列、循环队列6．队列的应用及基本运算三、数组和广义表1．数组的顺序存储结构（二维及三维数组的元素地址计算）2．稀疏矩阵的压缩存储结构（三元组表、十字链表）四、树和二叉树1．二叉树的定义、性质及存储结构2．遍历二叉树和线索二叉树3．二叉树的应用五、图1．图的定义及存储结构（邻接矩阵表示和邻接表表示。

）2．图的遍历3．最小生成树4．拓扑排序六、查找1．静态表查找2．动态表查找（二叉排序树、平衡二叉树、B-树和B+树）3．哈希表的构造、哈希表的查找及分析、处理哈希冲突的方法七、内部排序1．插入排序、快速排序、选择排序、归并排序、基数排序等内部排序的特点与算法，各类排序方法的比较，时、空复杂度分析2．相关排序的应用考试题型：选择题（15％）、填空题（20％）、判断题（10％）、应用题（35％）、算法设计题（20％）；其中算法设计题将着重考查学生使用C语言编程解决实际问题的能力，需要有一定的实际编程基础，而不是只会解书上的习题。

《数据结构》模拟卷A一、选择题1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。

A. O(n)B. O(n/2)C. O(1)D. O(n2)2.带头结点的单链表first为空的判定条件是：（ B ）。

A. first == NULL;B. first->link == NULL;C. first->link == first;D. first != NULL;3. 从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。

在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ D ），在被调用程序中可直接操纵实际参数。

A. 空间B. 副本C. 返回地址D. 地址5. 以下数据结构中，哪一个是线性结构（ D ）。

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串6. 以下属于逻辑结构的是（ C ）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ C ）的值除以9。

A. 20B. 18C. 25D. 228.在有向图中每个顶点的度等于该顶点的（ C ）。

A. 入度B. 出度C. 入度与出度之和D. 入度与出度之差9.在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

A. 起泡排序B. 希尔排序C. 归并排序D. 快速排序10.当α的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。

A. 较慢B. 较快C. 相同D.不同二、填空题1.二维数组是一种非线性结构，其中的每一个数组元素最多有______2___个直接前驱（或直接后继）。

2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。

*问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

1、邻接矩阵表示法:设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。

G的邻接矩阵是一个他有下述性质的n阶方阵：1，若(Vi,Vj)∈E 或<Vi,Vj>∈E；A[i,j]={0，反之图5-2中有向图G1和无向图G2的邻接矩阵分别为M1和M2:M1=┌0 1 0 1 ┐│ 1 0 1 0 ││ 1 0 0 1 │└0 0 0 0 ┘M2=┌0 1 1 1 ┐│ 1 0 1 0 ││ 1 1 0 1 │└ 1 0 1 0 ┘注意无向图的邻接是一个对称矩阵，例如M2。

用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。

因此其类型定义如下：VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量AdjMatrix arcs; // 邻接矩阵int vexnum, arcnum; // 图的当前顶点数和弧(边)数GraphKind kind; // 图的种类标志若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。

此时存储结构可简单说明如下：type adjmatrix=array[1..vnum,1..vnum]of adj;利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。

对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即n nD(Vi)＝∑A[i,j]（或∑A[i,j]）j=1 i=1对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。

即n nOD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]）j=1j=1用邻接矩阵也可以表示带权图，只要令Wij, 若<Vi,Vj>或(Vi,Vj)A[i,j]＝{∞, 否则。