2018年4月自考02142数据结构导论试题及答案含解析

数据结构导论年月真题

0214220184

1、【单选题】数据的逻辑结构分为四种，其中结构最复杂的是

集合

线性结构

A:

树形结构

B:

图结构

C:

答D:案：D

解析：图结构中任意两个数据元素间均可相关联。

2、【单选题】下面程序是矩阵转置算法MM的实现过程，其时间复杂度为

O(1)

O(log2n)

A:

O(n2)

B:

O(2n)

C:

答D:案：C

解析：算法中循环体的执行次数为0+1+2+3+---+(n-1)=n(n-1)/2，所以，算法的时间复杂

度为O(n2)。

3、【单选题】设顺序表的表长为n，则删除一个元素在最坏情况下元素移动次数为

n-2

n-1

A:

n

B:

n+1

C:

答D:案：B

解析：删除第1个元素时，需要移动的元素最多，其后面的n-1个元素都需要移动。

4、【单选题】执行进栈操作，在元素x进栈前需要进行的操作是

判断栈是否满，若栈未满，top值加1

判断栈是否空，若栈未空，top值加1

A:

判断栈是否满，若栈未满，top值减1

B:

判断栈是否空，若栈未空，top值减1

C:

答D:案：A

解析：在元素x进栈前需要进行的操作首先判断栈是否满，若栈未满，top值加1。

5、【单选题】关于队列，下列叙述正确的是

队列的元素个数可以无穷大

队列中元素的类型可以不同

A:

队列是一个非线性的序列

B:

队列的特点是先进先出

C:

答D:案：D

解析：队列的特点是先进先出，栈的特点是先进后出。

6、【单选题】设循环队列的元素存放在一维数组Q[30]中，队列非空时，front指示队列首

结点的前一个位置，rear指示队列尾结点。如果队列中元素的个数为10，front的值为25，

则rear应指向的元素是

Q[4]

Q[5]

A:

Q[14]

B:

Q[15]

C:

答D:案：B

解析：循环队列的元素的个数：当rear大于front时，元素的个数=rear-front；当

front大于rear时，元素的个数=M（数组长度）-(front-rear)。本题元素的个数=30-

(25-rear)=10，所以rear的值为5。

7、【单选题】二叉树第i(i≥1)层上的结点数最多为

2i-1

i-1

A:

2*i

B:

2*(i-1)

C:

答D:案：A

解析：二叉树第i(i≥1)层上的结点数最多为2i-1。

8、【单选题】关于二叉链表，下列叙述正确的是

二叉链表是二叉树唯一的链式存储结构

对二叉链表的访问可以从任意结点开始

A:

每个二叉链表不需要有一个指向根节点的指针

B:

二叉链表的结点结构包含一个数据域和两个指针域

C:

答D:案：D

解析：二叉链表是二叉树常用的链式存储结构，但不是唯一。对二叉链表的访问从根结点

开始，线索二叉树有一个指向根结点的指针；二叉链表的结点结构包含一个数据域和两个

指针域，选项D是正确的。

9、【单选题】假设初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点。将该森林

构造成哈夫曼树，则最终求得的哈夫曼树的结点数为

n-1

n

A:

2n-1

B:

2n

C:

D:

答案：C

解析：哈夫曼树的特点：（1）在哈夫曼树中，权值越大的叶子离根结点越近。（2）若有

n0个权值，需要进行n0-1次合并，构造成为哈夫曼树。（3）哈夫曼树没有度为1的结

点。（4）由n0个权值构成的哈夫曼树，叶结点数为n0，度为2的结点数为n0-1，结点

总数为n0\+n2=n0\+n0-1=2n0-1。（5）给定一组权值，构造出的哈夫曼树的形态可能

不唯一，但它们的带权路径长度都一样。

10、【单选题】无向图中的极大连通子图是

连通分量

生成树

A:

强连通分量

B:

强连通图

C:

答D:案：A

解析：连通分量：无向图中的极大连通子图。生成树：对于具有n个顶点的连通图，包含

了该图的全部n个顶点，仅包含它的n-1条边的一个极小连通子图被称为生成树。生成树

本身也是连通的，而且不具有回路。一个连通图的生成树不一定是唯一的。有向图中任意

两个顶点之间都有连通，就称该有向图是强连通图。一个有向图的极大强连通子图，称为

该有向图的强连通分量。

11、【单选题】在用邻接表表示图时，对图进行深度优先搜索遍历的算法的时间复杂度为

O(n)

O(n+e)

A:

O(n2)

B:

O(n3)

C:

答D:案：B

解析：在用邻接表表示图时，对图进行深度优先搜索遍历的算法的时间复杂度为O(n+e)。

12、【单选题】静态查找表与动态查找表二者的根本差别在于

它们的逻辑结构不同

施加在其上的操作不同

A:

所包含的数据元素类型不同

B:

存储实现不同

C:

答D:案：B

解析：静态查找表与动态查找表二者的根本差别在于施加在其上的操作不同，静态查找表

主要完成的操作是查询，动态查找表除了进行查询，也方便进行插入和删除操作。

13、【单选题】在散列函数H(k)=kMODm中，一般来讲，m应取

奇数

偶数

A:

素数

B:

充分大的数

C:

答D:案：C

解析：m一般取小于等于散列表容量的最大素数。

14、【单选题】在下述四种排序算法中，所需辅助存储量最多的是

堆排序

快速排序

A:

直接选择排序

B:

归并排序

C:

答D:案：D

解析：归并排序所需要的辅助存储量最多，为O(n)；快速排序所需辅助存储量最多的是

O(log2n)，其他两种排序所需要的辅助存储量为O(1)。

15、【问答题】线性表中如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点

有且仅有__________个直接前驱。

答案：1

16、【问答题】单链表各个结点在内存中的存储位置并连续。

答案：不一定

17、【问答题】栈初始化运算的目的是。

答案：构造一个空栈

18、【问答题】假设以E和O分别表示进栈和出栈操作，则对输入序列a，b，c，d，e进行

一系列操作EEOEEOEOOO之后，得到的输出序列为。

答案：BDECA

19、【问答题】二叉树的任一结点都有两棵子树，并且这两棵子树之间有关系。

答案：次序

20、【问答题】一棵树中所有结点的最大值称为该树的高度。

答案：层次数

21、【问答题】高度为h(h≥2)的完全二叉树至少有个叶子结点。

答案：2H-1

22、【问答题】图的广度优先搜索遍历类似于树的按遍历的过程。

答案：层次

23、【问答题】稀疏矩阵可以采用法进行压缩存储。

答案：三元组表示

24、【问答题】完成拓扑排序的前提条件是AOV网中不允许出现。

答案：回路

25、【问答题】数据元素的键值和之间建立的对应关系称为散列函数。

答案：存储位置

26、【问答题】静态查找表是以具有相同特性的数据元素集合为逻辑结构，但不包括插入和

运算。

答案：删除

27、【问答题】设表中元素的初始状态是按键值递增有序的，分别用堆排序、快速排序、冒

泡排序和归并排序方法