2024年4月30日发(作者：)

数据结构导论自考题模拟14

(总分：100.00，做题时间：90分钟)

一、单项选择题(总题数：15，分数：30.00)

1.算法指的是______

（分数：2.00）

A.计算机程序

B.解决问题的计算方法

C.排序算法

D.解决问题的有限运算序列 √

解析：[考点] 算法的定义

[解析] 算法是为了某一特定问题而制定的求解步骤的一种描述，它是有限的指令序列。它的特性有零个或

多个输入，一个或多个输出，确定性，有穷性，有效性。

2.下面程序段的时间复杂度是______

for(i=0;i＜n;i++)

for(j=1;j＜m;j++)

A[i][j]=0;

（分数：2.00）

A.O(m*n) √

B.O(m+n+1)

C.O(m+n)

D.O(n)

解析：[考点] 时间复杂度的计算

[解析] 第一重循环n，嵌套循环m，时间复杂度为mn。

3.队和栈的主要区别是______

（分数：2.00）

A.逻辑结构不同

B.限定插入和删除的位置不同 √

C.所包含的运算个数不同

D.存储结构不同

解析：[考点] 栈和队列的区别

[解析] 栈后进先出，队列先进先出。

4.设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是______

s-＞next=p-＞next;p-＞next=s;

t=p-＞data;p-＞data=s-＞data;s-＞data=t;

（分数：2.00）

A.结点*p与结点*s的数据域互换

B.在p所指结点的元素之前插入元素

C.在p所指结点的元素之后插入元素

D.在结点*p之前插入结点*s √

解析：[考点] 链表的插入

[解析] 根据指针的修改，确定选项D正确。

5.队列用链接方式存储，在进行删除运算时______

（分数：2.00）

A.头、尾指针可能都要修改 √

B.仅修改头指针

C.仅修改尾指针

D.头、尾指针都要修改

解析：[考点] 队列用链接方式存储时的删除运算

[解析] 队列用链接方式存储，在进行删除运算时，头尾指针可能都要修改。

6.根据定义，树的叶子结点其度数______

（分数：2.00）

A.必大于0

B.必等于1

C.必等于0 √

D.必等于2

解析：[考点] 树的叶子结点的度

[解析] 树的叶子结点的度是0。

7.二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，

则元素A[9][7]的地址为______

（分数：2.00）

A.432

B.429 √

C.435

D.438

解析：[考点] 数组元素地址是运算

[解析] 对于，n×n的数组采取列优先存储时，Loc[i,j]=Loc[0,0]+(j×m+i)*k=150+(7×12+9)×3=429。

8.下图所示二叉树的中序遍历序列是______

（分数：2.00）

f

g

e √

c

解析：[考点] 二叉树的中序遍历

[解析] 二叉树的中序遍历顺序是、左子树、根、右子树。

9.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为______









A.e

B.2e

C.n-e

D.n-2e

2

2

（分数：2.00）

A.

B.

C.

D. √

解析：[考点] 无向图的邻接矩阵存储

[解析] 无向图邻接矩阵的对称性，0元素的个数为n -2e。

10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为______

2

（分数：2.00）

√

解析：[考点] 图的广度优先遍历

[解析] 图的广度优先遍历算法。

11.对n个关键字的序列进行快速排序，平均情况下的时间复杂度为______

（分数：2.00）

A.O(nlog2n) √

B.O(log2n)

C.O(n)

D.O(1)

解析：[考点] 快速排序的空间复杂度

[解析] 快速排序的3个步骤：找到序列中用于划分序列的元素；用元素划分序列；对划分后的两个序列重

复1，2两个步骤指导序列无法再划分。所以对于n个元素其排序时间为：

T(n)=2*T(n/2)+n(表示将长度为n的序列划分为两个子序列，每个子序列需要T(n/2)的时间，而划分序列

需要n的时间)；而T(1)=1(表示长度为1的序列无法划分子序列，只需要1的时间即可)；

T(n)=2^log

2

n+log

2

n*n，n被不断二分最终只能二分logn次(最优的情况，每次选取的元素都均分序

列))=n+nlog

2

n。

因此T(n)=O(nlog

2

n)。

12.利用散列技术实现动态查找表的基本出发点是______

（分数：2.00）

A.查找过程中不再需要比较操作

B.增加查找过程中的比较次数

C.减少查找过程中的比较次数 √

D.节省存储空间

解析：[考点] 用散列技术实现动态查找的基本出发点

[解析] 用散列技术实现动态查找的基本出发点是减少查找过程中的比较次数。

13.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，

则该排序方法称为______

（分数：2.00）

A.堆排序

B.归并排序

C.冒泡排序

D.插入排序 √

解析：[考点] 插入排序算法

[解析] 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当

位置，则该排序方法称为插入排序。

14.排序趟数与序列的原始状态有关的排序方法是______

（分数：2.00）

A.插入排序法

B.冒泡排序法 √

C.二路归并排序法

D.选择排序法

解析：[考点] 冒泡排序算法

[解析] 排序趟数与序列的原始状态有关的排序方法是冒泡排序，交换类的排序，其趟数与元素的原始状态

有关。直接插入排序、选择排序，排序的趟数不变，为m-1。基数排序的排序的趟数为d。

15.下列排序方法中，属于不稳定的排序方法是______

（分数：2.00）

A.选择排序 √

B.冒泡排序法

C.基数排序法

D.直接插入排序法

解析：[考点] 排序算法的稳定性

[解析] (1)稳定的排序：冒泡排序；直接插入排序；归并排序；基数排序。

(2)不稳定的排序：希尔排序；选择排序；快速排序；堆排序。

二、填空题(总题数：13，分数：26.00)

16.从逻辑关系上讲，数据结构主要分为两大类，分别是 1和 2。

（分数：2.00）

解析：线性结构 非线性结构 [考点] 数据的分类

[解析] 从逻辑上讲，数据结构主要分为两类，分别是线性结构和非线性结构。

17.队列的修改是按 1的原则进行的。

（分数：2.00）

解析：先进先出 [考点] 队列的修改原则

[解析] 队列的修改是按先进先出的原则进行的。

18.栈下溢是指在 1时进行出栈操作。

（分数：2.00）

解析：栈空 [考点] 栈的操作容易出现的现象

[解析] 栈下溢是指在栈空时进行出栈操作。

19.设某非空双链表，其结点形式为

＞next=p-＞next; 1。

（分数：2.00）

解析：p-＞next-＞prior=p-＞prior [考点] 双链表的删除操作

[解析] 注意双链表的prior和next都要修改。

20.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下

一个位置，则在队列不满的情况下，队列的长度是 1。

（分数：2.00）

解析：(rear-front+m)%m [考点] 循环队列长度的求取

[解析] 循环队列长度(rear-front+m)%m。

21.已知完全二叉树T的第5层只有7个结点，则该树共有 1个叶子结点。

（分数：2.00）

解析：11 [考点] 完全二叉树的性质

[解析] 完全二叉树第5层最多应有2

2 +7/2=11。

22.n个顶点的无向图G用邻接矩阵A[n][n]存储，其中第i列的所有元素之和等于顶点V

i

的 1。

（分数：2.00）

解析：度 [考点] 用无向图邻接矩阵求取某顶点的度数

[解析] n个顶点的无向图G用邻接矩阵A[n][n]存储，其中第i列的所有元素之和等于顶点V

i

的度。

3

(5-1)

若要删除指针p所指向的结点，则需执行下述语句段：p-＞prior-

=16个结点＞7，所以此完全二叉树深度为5，叶子结点个数为：