数据结构与算法-等级考试试题(程序员软考 2017年秋图的存储)

单项选择（2017年秋程序员软考）

对于下面的有向图，采用邻接链表存储时，顶点 0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为【】。

A、0

B、1

C、2

D、3

答案解析

C

讨论

数据结构与算法

对于下面的有向图，其邻接矩阵是一个【】的矩阵。

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【】。

对关键码序列(12，24，15，56，20，87，69，9)采用散列法进行存储和查找，并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性控查法（顺地探查可用存储单元）解决冲突所构造的散列表为【】。

对关键码序列(9，12，15，20，24，29，56，69，87)进行二分查找(折半查找)，若要查找关键码15，则需依次与【】进行比较。

对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d，则合法的出栈序列为【】。

递归函数执行时，需要【】来提供支持。

表示“以字符a开头且仅由字符a、b构成的所有字符串”的正规式为【】。

下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串【】。

对于连通无向图 G，以下叙述中，错误的是【】。

折半(二分)查找法适用的线性表应该满足【】的要求。

图的存储

设某无向图的顶点个数为n，则该图最多有______条边;若将该图用邻接矩阵存储，则矩阵的行数和列数分别为______。

有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。

表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？

n个顶点的连通图用邻接矩阵表示时，该矩阵至少有__________个非零元素。

已知某带权图G的邻接表如下所示，其中表结点的结构为:以下关于该图的叙述中，正确的是【】。

对于下图，若采用邻接矩阵存储，则矩阵中的非0元素数目为【】。

某图G的邻接表如下所示。以下关于图G的叙述中，正确的是【】。

某有向图G及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中，错误的是【】。

某图G的邻接矩阵如下所示。以下关于该图的叙述中，错误的是【】

阅读以下说明和C函数，填补函数代码中的空缺(1)~(5)。队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构(称为循环队列)。设循环队列的存储空间容量为 MAXQSIZE，并在其类型定义中设置base、rear和 length三个域变量，其中，base为队列空间的首地址，rear为队尾元素的指针， length表示队列的长度。#define MAXQSIZE 100typedef struct{ QElemType *base;/*循环队列的存储空间首地址* int real;/*队尾元素索引*/ int ength;/*队列的长度*/} SqQueue;例如，容量为8的循环队列如下图所示，初始时创建的空队列如图(a)所示，经过一系列的入队、出队操作后，队列的状态如图(b)所示(队列长度为3)。下面的C函数1、C函数2和C函数3用于实现队列的创建、插入和删除操作，请完善这些代码。【C函数1】创建一个空的循环队列int InitQueue (SqQueue *Q){ /*创建容量为 MAXQSIZE的空队列，若成功则返回1;否则返回0*/ Q->base =(QElemType *)malloc( MAXQSIZE*__ (1)__); if (! Q->base) return 0： Q->length=0; Q->rear =0; return 1;}/* InitQueue*/【C函数2】元素插入循环队列。int EnQueue( SqQueue *Q， QElemType e){/*元素e入队，若成功则返回1;否则返回0*/ if( Q->length>=MAXQSIZE) return 0; Q->rear=__(2)__; Q->base [Q->rear]=e; __(3)__; return 1;}/*EnQueue*/【C函数3】元素出循环队列。int DeQueue (SqQueue *Q，QElemType *e){ /*若队列不空，则删除队头元素，由参数e带回其值并返回1;否则返回0*/ if(__(4)__)return 0; *e=Q-base[(Q->rear-Q->length+1+MAXQSIZE)%MAXQSIZE]; __(5)__; return 1;}/*DeQueue*/

图

设无向图的顶点个数为n，则该无向图最多有【】条边。

对于给定的n个元素，可以构造的逻辑结构有__________、__________、__________和__________4种。

G是一个非连通无向图，共有28条边，则该图至少有【】个顶点。

在n个结点的无向图中，若边数>n-1，则该图必是连通图。

图的遍历方式有__________和__________两种。

有 n 个顶点的有向强连通图最多有多少条边？最少有多少条边？

对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。

试列中下列图中全部可能的拓扑排序序列。

Kruskal算法的时间复杂度为__________，它对__________图比较合适。