数据结构2011年统考真题，数据结构2013年统考真题

1 .【顺序表】

以逐次记忆方式记忆包含n个元素的线性列表时，其运算速度最快的操作是【 】。

a .访问第I个元素( 1in )

b .删除第I个元素( 1in )

c .在第I个元素( 1in )之后插入新元素

d .查找与特定值匹配的元素

【答案】a

【解析】线形表( a1，a2，…，an )，如下图所示采用顺序存储方式，因为逻辑上邻接的要素的物理位置也邻接，所以按顺序访问要素的速度很快。

访问第I个元素( 1in )的元素可以在计算a1的存储位置之后进行对存储器的随机访问操作。 用loc(AI )表示线性表的最初要素的存储位置，用l表示各要素所占的存储单元的个数的话，loc(AI )计算如下。

LOC(AI ) LOC(AI ) ) i-1 ) XL

分析其他运算时，如果不在表的末尾插入或删除，则需要移动其他元素，很费时间。 要找到与特定值匹配的元素，需要与表中的多个元素进行比较，比随机访问第I个元素所需的时间更长。

2 .【链表】

线性表采用单链表时的特征为【 】。

a .插入和删除不需要移动的元素

b .可以随机访问表中的任何元素

c .需要提前估计存储空间的需求量

d .节点占用地址的连续存储空间

【答案】a

【解析】当链表存储时，各个元素表示为一个节点，节点中的指针字段表示后续元素所在的节点，访问元素时只需从第一个指针开始依次查找元素，根据需要动态要在单链表中插入和删除元素，只需修改逻辑上相关元素所在节点的指针字段，而无需移动元素。

3 .【堆栈、队列概念】

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

a .堆栈和队列都是线性的数据结构

b .堆栈和队列都不允许在端口以外的位置插入和删除元素

c .数组最初通过空堆栈后，元素的数组顺序保持不变

d .最初通过空队列后，元素的排列顺序不变

【答案】c

【分析】暂存器和队列是运算受到限制的线性表格，暂存器的特征是先入先出，也就是只能在末尾插入或删除要素。 队列的特征是先进先出，即只能在表的末尾插入元素，然后在标题中删除元素。 因此，即使最初通过空队列，元素的排列顺序也不会改变。 使用堆栈时，只要堆栈不为空，就可以执行堆栈操作，因此如果一个序列首次通过空堆栈，元素的排列顺序可能会发生变化。

4 .【堆栈的算法】

对于最初为空的堆栈，如果该堆栈序列是abc，则该堆栈序列可以具有【 】类型。

A. 3

B. 4

C. 5

D. 6

【答案】c

【解析】堆栈系列为abc时，输出堆栈系列可以为abc、acb、bac、bca、cba，用I表示与堆栈、o相对应的输出堆栈。 原则上，各要素每次栈、出栈； 一次堆栈操作的条件是堆栈不为空，且

可以把堆栈的顶级元素从堆栈中拿出来。

如果堆栈序列是abc，则对应的操作序列为IOIOIO。

如果堆栈序列为acb，则对应的操作序列为IOIIOO。

如果堆栈序列是bac，则对应的操作序列为IIOOIO。

如果堆栈序列为bca，则对应的操作序列为IIOIOO。

如果堆栈序列是cba，则对应的操作序列为IIIOOO。

堆栈的有效操作序列中，在所有前缀部分中，堆栈操作的次数都在堆栈操作的次数以下。

5 .【串的算法】

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

A. 3

B. 5

C. 6

D. 9

【答案】c

【解析】由正规式( ab|c )表示的正规集合为{ab，c}，由正规式(0|1|2)表示的正规集合为{ 0，1，2 }，由{ab，c}和{ 0，1，2 }进行连接运算的正规集合为{ ab0，1，2 }

6 .【串的算法】

有字符串S=\’software \’，其长度为3的子字符串的数量为【 】。

A. 8

B. 7

C. 6

D. 5

【答案】c

【解析】对于字符串S=\’software \’，长度为3的子列共计6个，即“sof”、“oft”、“ftw”、“twa”、“war”、“are”。

7 .【模式匹配】

包括字符串s和p，字符串的模式匹配是确定【 】。

A. P在s中首次出现的位置

B. S和p是否相连

C. S和p是否互换

D. S和p是一样的吗

【答案】a

【解析】字符串的模式匹配是指模式字符串在主字符串内的定位运算，即模式字符串在主字符串内首次出现的位置。

8 .【数组的定义与实现】

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

a .插入和删除

b .读取和修改

c .插入和检索

d .修正和删除

【答案】b

【分析】定义数组后，元素的增减变化消失，因此通常对数组执行的两个基本操作是读取和修改。 也就是说，给定一组下标，读取或修改相应数据元素的值。

9 .【特殊矩阵】

特殊矩阵是非零元素有序分布的矩阵，在以下特殊矩阵的描述中，正确的是【 】。

a .特殊矩阵适合采用双向链表进行压缩存储

b .特殊矩阵适合采用单向循环链表进行压缩存储

c .特殊矩阵的所有非零元素都可以压缩存储在一维数组中

d .特殊矩阵的所有零元素可以压缩存储在一维数组中

【答案】c

【解析】矩阵时，压缩存储器是指对具有相同值的多个要素只分配1个存储单元，对零要素不分配存储单元。 如果矩阵的零元素规则分布，则可将非零元素压缩和存储在一维阵列中，以建立矩阵中每个非零元素的位置与一维阵列中的位置之间的对应关系。

10 .【二叉树】

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

a .单链接列表

b .二叉树

c .散列表

d .循环队列

【答案】b

【解析】单链表是一个有关存储结构的术语，常用于线性表的链式存储。 通过在节点上设置指针字段来表示具有当前元素的直接继承(或直接前驱)元素的节点，表示元素之间的顺序关系或逻辑关系。

散列表是存储结构，也是搜索结构。 以记录的关键字为自变量计算一个称为哈希函数的函数，获取该记录的存储地址，从而实现快速存储和检索。

循环队列是使用顺序存储结构实现的队列。 在序列队列中，元素入队时，仅修改队列末尾的指针，以减少运算复杂度； 元素离开团队时，只修改团队领导者的指针。 由于序列队列的存储空间是预置的，队列指针有上限值，当队列指针到达其上时，只需修改队列指针就不能实现新元素的入队操作。 此时，将序列队列称为循环结构，可以在维持队列操作的容易性的状态下对循环队列进行虚拟化。

11 .【二叉树】

如果已知某二叉树的先行扫描序列为ABCD，后行扫描序列为CDBA，则该二叉树为【 】。

A.

B.

C.

D.

【答案】a

【分析】先遍历非空二叉树的过程是先访问根节点，再先遍历左子树，最后先遍历右子树。 标题中的四个二叉树的前导扫描序列分别为ABCD、ABCD、ABCD、ACBD。

反向遍历非空二叉树的过程是按顺序遍历左子树，再按顺序遍历右子树，最后访问根节点。 问题的四个二叉树后面的扫描序列分别是CDBA、BDCA、DCBA、DBCA。

12 .【完全二叉树】

完全二叉树的特点是叶节点分布在最后两段，除最后一段外其他段的节点数达到最大值时，25个节点的完全二叉树的高度，即层数为【 】。

A. 3

B. 4

C. 5

D. 6

【答案】c

【分析】当深度为k的二叉树具有2k-1个节点时，将其称为满二叉树。 二叉树每层的节点数达到最大值。 二叉树中的节点可以连续编号，约定编号从根节点开始从上到下，从左到右依次编号。 一种深度为k，具有n个节点的二叉树，只有当每个节点在深度为k的满二叉树中与编号为1~n的节点一一对应时，才称为完全二叉树。 高度3的二叉树如下图( a )所示，具有6个节点的完全二叉树如下图) b )所示，下图) c )不是完全二叉树。

由上图可知，在完全二叉树中，除了最后一层的节点数不足之外，剩下的层的节点数达到了最大值。 如果完全二叉树有25个节点，其前4级节点数为15(1248 )，第5级有10个节点)即25-10 )，最多没有超过该层16个节点的上限，所以该二叉树的高度为5。

13 .【图中的存储】

某个权重图g的邻接表已知如下，其中表节点的结构如下。

在以下关于该图的记述中，正确的是【 】。

a .图g为强连通图

b .图g有14条弧线

c .顶点b的出度为3

d .顶点b的入度为3

【答案】d

【解析】从问题图中可以看出，由于顶点a、b、c、d、e的编号为1~5，所以顶点a的邻接表中的两个节点有从顶点a到顶点b的弧，权重为5，有从顶点a到顶点d的弧，权重为8，进一步调查顶点b

在有向图中，如果各顶点对之间存在路径的话，就是强连通图。 上图不是强连通图。 例如，从顶点c到b有路径，反之则没有路径。 在有向图中，顶点的入度是以该顶点为终点的有向边的数量，顶点的出度是以该顶点为起点的有向边的数量。 对于顶点b，其出度为1，入度为3。

14 .【图中的存储】

在下图中，使用相邻矩阵存储时，矩阵中非零元素的数量为【 】。

A. 7

B. 8

C. 14

D. 16

【答案】b

【解析】关于有向图，其邻接矩阵中的非零要素的数量表示图表中的有向弧的数量，由于问题中的图表有8条弧，所以矩阵中的非0要素的数量为8。 如下图所示。

15 .【图的遍历】

对于下图，从顶点1开始进行深度优先遍历时，得不到的遍历顺序为【 】

A. 1234567

B. 1523467

C. 1234675

D. 1267435

【答案】a

【解析】对表示问题的图从顶点1开始进行深度优先的扫描，访问1后，接下来可以访问顶点2和顶点5两者。

如果先访问顶点2，则接下来可以访问顶点3或6，此时得到的已访问的顶点的顺序是123或26。 如果选择先访问顶点3，则接下来访问顶点4，得到访问过的顶点的顺序1234，由于不存在从顶点4前进的路径，所以需要追溯到顶点3之后再追溯到顶点2。 因为在顶点2处存在尚未访问的相邻顶点6，所以下一次访问的顶点为6，然后为顶点7，从而得到被访问顶点的扫描序列123467。 最后追溯到顶点1，通过访问顶点5，完成对所有顶点的访问，得到深度优先遍历序列1234675。 访问顶点2后，然后选择访问顶点6，可以获得导线测量序列1263475或1267435。

访问顶点1，然后选择访问顶点5以获得深度优先遍历序列1523467或1526347或1526734。

因此，得不到的深度优先扫描序列为1234567。

16 .【规则表检索】

在由13个要素构成的秩序表data[1.13]中，通过对折检索(即二分检索，计算时向下舍入)寻找值等于data[8]的要素时，前后)等要素进行了比较。

A. data[7]、data[6]和data[8]

B. data[7]、data[8]

C. data[7]、data[10]和data[8]

d.data [7] data [ 10 ] data [9] data [8]

【答案】c

在二分搜索即对半搜索过程中，将位于中间位置的记录的关键字与预定值进行比较，当相等时，搜索成功； 否则，缩小范围，直到在新搜索区间的中间位置记录的关键字等于预定值，或者搜索区间没有元素(表示搜索失败)。

由13个要素组成的秩序表data1.13] )中进行二分检索的过程如下图所示(计算中间要素的位置时向下舍入，节点中的数字是要素的下标或编号)，在根据该过程中，在检索要素data(7)、data(7)时

17 .【二叉排序树】

某些二叉树变成了，新元素45应该作为【 】插入到此二叉树中。

A. 11左边的树

B. 17右边的子树

C. 61左边的树

D. 27右边的子树

【答案】c

【分析】根据二叉树的定义，新元素大于根节点的关键码时插入根节点的右部分树，新元素小于根节点的关键码时插入根节点的左部分树。 45大于23，并将其插入节点31右边部分树中，45大于31，小于91，小于61，最后作为61左边的部分树添加到该二叉树中。

数据结构与算法——题库