软件水平考试
对于下面的有向图，其邻接矩阵是一个（请作答此空）的矩阵。采用邻接链表存储时，顶点0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为（ ）。 A.3×4 B.4×3 C.6×6 D.7×7
题目
B.4×3
C.6×6
D.7×7
相似问题和答案
第1题：
●试题四
阅读下列程序说明，将在空缺处填入正确的内容。
【程序说明】
定义一个多边形结构：struct polygon实现以下内容： (1) 建立该结构的链表：create函数是创建链表，每输入一个结点的数据，就把该结点加入到链表当中，它返回创建的链表的头指针。 (2) 显示链表的各个结点数据：结点数据包括：多边形顶点数、各顶点的纵横坐标、当多边形顶点数为0时，链表创建结束。 (3) 编写一个函数disp，删除链表中的所有结点。需要注意的是：要先释放结点数据内存，再删除结点，如果在释放结点数据内存单元之前删除结点，则无法找到结点数据内存单元的地址，也就无法释放数据的内存单元。
【程序】
#include"iostream.h"
#include"iomanip.h"
struct polygon
{
int n；
int *x；
int *y；
polygon *next；
}；
void Push(polygon*& head，int n)
{
polygon*newNode=new polygon；
newNode=new polygon；
newNode－>next= (1) ；
newNode－>x=new int[n]；newNode－>y=new int[n]；newNode－>n= (2) ；
for(int i=0；i<= (3) ；i++){
cout<<"请输入多边形各顶点x、y坐标，坐标值之间用空格分隔："；
cin>>newNode->x[i]>>newNode->y[i]；}
(4) =head；// 在head前不需要额外的*
head=newNode；
}
polygon *create()
{
polygon*head=NULL；
polygon*tail；
int n；
cout<<"请输入多边形顶点的个数(顶点个数为0时结束)："；
cin>>n；
if(n==0)return (5) ；
Push(head， (6) ；
tail=head；
cout<<"请输入多边形顶点的个数(顶点个数为0时结束)："；
cin>>n；
while(n!=0)
{
Push(tail－>next， (7) ；//在tail－>next增加结点
tail=tail－>next；//advance tail to point to last node
cout<<"请输入多边形顶点的个数(顶点个数为0时结束)："；
cin>>n；
}
return head；
}
void disp(polygon*head)
{
int i，No=1；
cout<<setw (10) <<"x"<<setw (6) <<"y"<<endl；
while(head!=NULL)
{
cout<<"第"<<No<<"结点："<<endl;
for(i=0；i<=head－>n－１；i++)
cout<<setw (10) <<head－>x[i]<<setw (6) <<head－>y[i]<<endl；
(8) ；
head= (9) ;
}//Match while statement
}
void del(polygon*head)
{
polygon*p；
while(head!=NULL)
{
p= (10) ；
head=head－>next；
delete p－>x；
delete P－>y；
deletep；
}//Match while statement
}
void main()
{
polygon*head；
head=create()；
disp(head)；
del(head)；
}
●试题四
【答案】(1)NULL(2)n(3)n-1(4)newNode->next(5)head
(6)n(7)n(8)No++(9)head->next(10)head
【解析】如果掌握了链表的创建、遍历和删除的方法，解决本题应该并不困难。要显示链表各结点的数据，就是要把各结点找到，然后把该结点的每一个x、y坐标打印出来。不过，与普通的链表也有不同的地方：就是该链表的结点数据是指针。要在链表结点中存入数据，必须先动态分配存储数据的内存单元；要删除链表中的各个结点，必须先释放结点数据的内存单元，否则会造成内存泄露。
第2题：
A、 2*n
B、 2*e
C、 n
D、 e
第3题：
A.n
B.n*e
C.e
D.2*e
第4题：
采用邻接链表存储时，顶点0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为（）。
A.0
B.1
C.2
D.3
第5题：
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。
若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。
(6)O(n+e) (7)O(n2) 解析：邻接表：对有n个顶点和e条弧的有向图而言，在拓扑排序中，若有向图无环，则每个顶点进出队列各一次，共执行e次，搜索算法时间复杂度是由n和e共同决定的，所以总的时间复杂度为O(n+e)。
当用邻接矩阵：对于每个顶点，查找相邻边的时间复杂度是O(n)，一共有n个顶点，所以总的时间复杂度是O(n2)。
第6题：
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]
邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是：对于图G中的每个顶点 vi，将所有邻接于vi的顶点vj连成一个单链表，这个单链表就称为顶点vi的邻接表，其中表头称作顶点表结点VertexNode，其余结点称作边表结点EdgeNode。将所有的顶点表结点放到数组中，就构成了图的邻接表AdjList。邻接表表示的形式描述如下： define MaxVerNum 100 /*最大顶点数为100*/
typedef struct node{ /*边表结点*/
int adjvex; /*邻接点域*/
struct node *next; /*指向下一个边表结点的指针域*/ }EdgeNode;
typedef struct vnode{ /*顶点表结点*/
int vertex; /*顶点域*/
EdgeNode *firstedge; /*边表头指针*/
}VertexNode;
typedef VertexNode AdjList[MaxVerNum]; /*AdjList是邻接表类型*/
typedef struct{
AdjList adjlist; /*邻接表*/
int n; /*顶点数*/
}ALGraph; /*ALGraph是以邻接表方式存储的图类型*/
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。
下面的函数利用递归算法，对以邻接表形式存储的图进行深度优先搜索：设初始状态是图中所有顶点未曾被访问，算法从某顶点v出发，访问此顶点，然后依次从v的邻接点出发进行搜索，直至所有与v相连的顶点都被访问；若图中尚有顶点未被访问，则选取这样的一个点作起始点，重复上述过程，直至对图的搜索完成。程序中的整型数组visited[]的作用是标记顶点i是否已被访问。
[函数]
void DFSTraverseAL(ALGraph *G)/*深度优先搜索以邻接表存储的图G*/
{ int i;
for(i=0;i＜(1);i++) visited[i]=0;
for(i=0;i＜(1);i++)if((2)) DFSAL(G,i);
}
void DFSAL(ALGraph *G,int i) /*从Vi出发对邻接表存储的图G进行搜索*/
{ EdgeNode *p;
(3);
p=(4);
while(p!=NULL) /*依次搜索Vi的邻接点Vj*/
{ if(! visited[(5)]) DFSAL(G,(5));
p=p-＞next; /*找Vi的下一个邻接点*/
}
}
(1) G-＞n (2) ! visited[i] (3) visited[i]=1 (4) G-＞adjlist[i].firstedge (5) p-＞adjvex 解析：(1)此处循环是访问标志向量的初始化，应遍历 G的全体点，共计G→n个；
(2)若Vi未被访问，则从Vi开始搜索；
(3)标记Vi已访问；
(4)为递归搜索Vi的邻接点，需先取出Vi边表的头指针；
(5)若Vi的邻接点p-＞adjvex尚未被访问，则从它出发进行纵深搜索。
第7题：
对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为(20)，所有边链表中边结点的总数为(21)。
A．n
B．n+1
C．n-1
D．n+e
解析：此题考的是无向图。
第8题：
A
0 2 4 3 1 5 6
B0 1 3 5 6 4 2
C
0 4 2 3 1 6 5
D
0 1 3 4 2 5 6
第9题：
下面关于图的存储的叙述中正确的是()。
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
B.用邻接表法存储图，占用的存储空间大小与图中边数和顶点个数都有关
C.用邻接矩阵法存储图，占用的存储空间大小与图中顶点个数和边数无关
D.用邻接矩阵存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
第10题：
B7
C8
D9
