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

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

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

A、8

B、7

C、6

D、5

答案解析

C

【解析】

对于字符串S= 'software'，其长度为3的子串有“sof”“oft”“ftw”“twa”“war”“are”，共6个。

讨论

数据结构与算法

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

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

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

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

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

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

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

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

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

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

串

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

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

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

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

已知字符串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。

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

对于n个元素的关键码序列{k1,k2,…,kn}，当且仅当满足下列关系时称其为堆。或以下关键码序列中，【】不是堆。

在单 CPU 计算机系统中，完成相同功能的递归程序比非递归程序【】

线性表采用单循环链表存储的主要特点是【】

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

串的算法

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

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

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

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

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

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

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

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码ki时，其前面的 i-1 个关键码已排好序，因此令k与 ki-1、ki-2、…，依次比较，最多到 k1为止，找到插入位置并移动相关元素后将ki插入有序子序列的适当位置，完成本趟(即第 i-1 趟)排序。以下关于直接插入排序的叙述中，正确的是【】。

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

对二叉树中的结点如下编号：树根结点编号为1，根的左孩子结点编号为2、右孩子结点编号为3，以此类推，对于编号为i的结点，其左孩子编号为2i、右孩子编号为2i+1。例如，下图所示二又树中有6个结点，结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么，当结点数为n(n>0)的【】时，其最后一个结点编号为2n-1。