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

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

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

A、bbaa

B、aabb

C、abab

D、baba

答案解析

B有限自动机(确定或非确定的)识别字符串的过程都是从初态出发，找出到达终态的一条路径，使得路径上的字符序列与所识别的字符串相同。对于bbaa，若路径为s0->s0->s0->s0->s1，则所识别的bbaa 结束时 s1不是终态;换一条路径s0->s0->s0->s1，此时不存在从 s1 出发可以识别bbaa中的最后1个a的状态转移，由于不存在其他可能的路径，所以 bbaa 不能被该自动机识别。对于aabb，若路径为s0->s0->s0->s0->s0，则字符串aabb结束时s0不是终态;换一条路径s0->s0->s1->s2->s3，所识别的 aabb 结束时 s3 是终态，所以aabb可以被该自动机...

查看完整答案

讨论

数据结构与算法

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

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

设 S 是一个长度为n的非空字符串，其中的字符各不相同，则其互异的非平凡子串(非空且不同于S本身)的个数为【】。

在C程序中有一个二维数组 A[7][8]，每个数组元素用相邻的 8 个字节存储，那么存储该数组需要的字节数为【】。

为支持函数调用及返回，常采用称为“【】”的数据结构。

对于一个初始为空的栈，其入栈序列为 1,2,3,...,n(n>3)，若出栈序列的第一个元素是1则出栈序列的第n个元素【】

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG，则该二叉树根结点的左孩子结点和右孩子结点分别是【】

采用【】算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后，其元素的排列变为{12,10,11,18,2,7,23}。

表达式可采用后缀形式表示。例如，“a+b”的后缀式为“ab+”。那么，表达式“a*(b-c)+d”的后缀表示为【】

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

图

用DFS遍历一个无环有向图，并DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是【】。

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

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

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

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

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

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

在下列两种求图的最小生成树的算法中，【】算法适合于求边稀疏的网的最小生成树。

在一个有n个顶点的无向网中，有O(n1.5*log2n)条边，则应该选用【】算法来求这个网的最小生成树，从而使计算时间较少。

对于一个具有n个结点的连通无向图，如果它有且只有一个简单回路，那么此图有__________条边。

图的应用

已知有向图G采用邻接矩阵存储，其定义如下：typedef struct{//图的定义 int numberVertices,numEgges;//图中实际的顶点数和边数 char verticesList[maxV];//顶点表 int edge[maxV][maxV];//邻接矩阵}MGraph;将图中出度大于入度的顶点称为K顶点，如图，a和b都是K顶点，设计算法 int printVertices(MGraph G)对给定任意非空有向图G，输出G中所有K顶点，并返回K顶点的个数。(1)给出算法的设计思想。(2)根据算法思想，写出C/C++描述，并注释。

已知无向连通图 G 中各边的权值均为 1，下列算法中一定能够求出图 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*/

阅读以下说明和C函数，填补代码中的空缺(1)~(6)。二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter[]， counter[i]存放第i层上的结点数，并按照层次顺序来遍历二又树中的结点，在此过程中可获得每个结点的层次值，最后从counter[]中取出最大的元素就是树的宽度。按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号(为1)进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号入队列(若左子树存在)，其次将该结点的右子树根结点及层次号入队列(若右子树存在)，然后再取队头，重复该过程直至完成遍历。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BTNode{ TElemType data; struct BTNode *left， *right;}BTNode， *BiTree;队列元素的类型定义如下：typedef struct{ BTNode *ptr; int LevelNumber;}QElemType;Get Width()函数中用到的函数原型如下所述，队列的类型名为 QUEUE：InitQueue(QUEUE *Q)：初始化一个空队列，成功时返回值为1，否则返回值0isEmpty(QUEUE Q)：判断队列是否为空，是空则为1，否则为0EnQueue( QUEUE*Q， QElemType a)：将元素a加入队列，成功返回值为1，否则返回值0DeQueue(QUEUE *Q， QElemType *)：删除队头元素，并通过参数带回其值，成功则返回值1，否则返回值0GetHeight (BiTree root)：返回值为二叉树的高度(即层次数，空二叉树的高度为0)int Getwidth(BiTree root){ QUEUE Q; QElemType a， b; int width,height= GetHeight(root); int i， *counter =(int *)calloc(height+1， sizeof (int)); if(__(1)__) return -1;/*申请空间失败*/ if(! root) return 0;/*空树的宽度为0*/ if(__(2)__) return -1;/*初始化队列失败时返回*/ a.ptr= root; a.LevelNumber=1; if(! EnQueue(&Q，a)) return -1;/*元素入队列操作失败时返回*/ while (! isEmpty(Q)){ if(__(3)__)return -1;/*出队列操作失败时返回*/ counter[b. LevelNumber]++;/*对层号为b. LevelNumber的结点计数*/ if(b.ptr->left){/*若左子树存在，则左子树根结点及其层次号入队*/ a.ptr= b.ptr->left; a.LevelNumber=__(4)__; if(!EnQueue(&Q,a)) return -1; } if(b.ptr-> right){/*若右子树存在，则右子树根结点及其层次号入队*/ a.ptr= b.ptr->right; a. LevelNumber=__(5)__; if(! EnQueue(&Q,a)) return -1; } } width= counter[1]; for(i=1; i< height +1; 1++)/*求 counter[]中的最大值*/ if(__(6)__)width= counter [i]; free(counter); return width;}

在解决计算机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，计算机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区取出数据。因此，该缓冲区的数据结构应该是【】。

含有n个元素的线性表采用顺序存储，等概率删除其中任一个元素，平均需要移动【】个元素。

序列【】可能是第一趟冒泡排序后的结果。

设数组A[1..m,1..n]的每个元素占用1个存储单元，对于数组元素A[i,j](1≤证≤m，1≤j≤n)，在按行存储方式下，其相对于数组空间首地址的偏移量为【】

设数组A[1..m,1..n]的每个元素占用1个存储单元，对于数组元素A[i,j](1≤证≤m，1≤j≤n)，在按列存储方式下，其相对于数组空间首地址的偏移量为【】。

按照逻辑关系的不同可将数据结构分为【】。