数据结构与算法-等级考试试题(程序员软考 2015年秋串的概念)

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

以下关于字符串的叙述中，正确的是【】

A、字符串属于线性的数据结构

B、长度为0字符串称为空白串

C、串的模式匹配算法用于求出给定串的所有子串

D、两个字符串比较时，较长的串比较短的串大

答案解析

A

【解析】

选项A是正确的。一个线性表是n个元素的有限序列(n≥0)。由于字符串是由字符构成的序列，因此符合线性表的定义。

选项B是错误的。长度为0字符串称为空串(即不包含字符的串)，而空白串是指由空白符号(空格、制表符等)构成的串，其长度不为0。

选项C是错误的。串的模式匹配算法是指在串中查找指定的模式串是否出现及其位置。

选项D是错误的。两个字符串比较时，按照对应字符(编码)的大小关系进行比较。

讨论

模式匹配

设有字符串S和P，串的模式匹配是指确定【】。

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

某二叉排序树如下所示，新的元素45应作为【】插入该二叉树中。

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

含有n个元素的线性表采用顺序存储方式时，对其运算速度最快的操作是【】。

设有字符串S= "software"，其长度为3的子串数目为【】。

阅读以下说明和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;}

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

已知字符串s='(X+Y)*Z'，其中，单引号不是字符串的内容，经过以下运算后，t3的值是【】。t1= SubString(s,3,1)t2=Concat('XY', t1)t3=Replace(s,SubString(s,1,5),t2)注: SubString(s,k,n)表示从串s的第k个字符开始取出长度为n的子串， Concat(s,t)表示将串t连接在s之后， Replace(s,t,r)表示用r替换串s中的子串t。

串

正规式(ab|c)(0|1|2)表示的正规集合中有【】个元素。

设有字符串S='software'，其长度为3的子串数目为【】。

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

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

正规式(ab|c)(0|1|2)表示的正规集合中有【】个元素。

线性表采用单链表存储时的特点是【】。

特殊矩阵是非零元素有规律分布的矩阵，以下关于特殊矩阵的叙述中，正确的是【】。

完全二叉树的特点是叶子结点分布在最后两层，且除最后一层之外，其他层的结点数都达到最大值，那么25个结点的完全二叉树的高度(即层数)为【】。

数组是程序语言提供的基本数据结构，对数组通常进行的两种基本操作是数组元素的【】。

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

串的概念

含有n个元素的线性表用顺序存储方式时，对其运算速度最快的操作是【】。

在数据结构中，【】是与存储结构无关的术语。

已知某二叉树的先序遍历序列为ABCD，后序遍历序列为CDBA，则该二叉树为【】。

在有13个元素构成的有序表data[1..13]中，用折半查找(即二分查找，计算时向下取整)方式查找值等于data[8]的元素时，先后与【】等元素进行了比较。

对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是【】

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成，已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。例如，某单链表如图所示，逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下：typedef struct Node{ int data， struct Node *next;}Node， *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置， headptr为头指针 LinkList p，s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

算术表达式a*(b-c)+d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

对于顺序栈和链栈，【】不是两者共有的运算特征。

以下关于栈和队列的叙述中，错误的是【】。

对于一个初始为空的栈，其入栈序列为abc时，其出栈序列可以有【】种。