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

2020-2021学年数据结构与算法期末考试题

一、 选择题

1.

一个算法的时间复杂度用T(n)

表示

，其中n的含义是（）

A．语句条数 B．函数数量

C．循环层数 D．问题规模

2.

下列属于线性结构的是（）

A．链表 B．图

C．队列和栈 D．广义表

3.

将长度为m的单链表接在长度为n的单链表之后，其算法的时间复杂度为（）

A．O(1)

C．O(n )

B．O(m)

D．O(m+n)

4.

在 头结点的单链表中插入新结点，需要修改的指针数量为（）

A．2个

C．4个

B．3个

D．6个

5.

有一组队列为ABCDE ，A为队首元素，①输出首元素。②将首元素插到队尾。③删

除首元素④再次删除首元素。重复操作直到空队，则输出的序列为（）

A．ACECC B．ACE

C．ACECCC D．ACEC

6.

若栈采用链式存储结构，下列正确的是（）

A．需要判断栈满且需要判断栈空

B．不需要判断栈满但需要判断栈空

C．需要判断栈满但不需要判断栈空

D．不需要判断栈满且不需要判断栈空

7.

设有两个串s和t，求s在t中首次出现的位置的运算称为（）

A．连接

C．求子串

B．模式匹配

D．求串长

8.

串的主要存储表示为（）

A．散列表示 B． 索引表示 C．顺序表示 D．位表示

9.

设有一个10阶的下三角矩阵A，采用优先压缩存储方式， a

11

为第一个元素，其存储

地址为1000，一个元素占一个地址单位，则a

85

的地址为（）

A．1012 B． 1017 C．1041 D．1039

10.

设深度为k的二叉树只有度为0和度为2的节点，则此类二叉树中包含的节点数至少为

（）

第 1 页 共 5 页

A．k+1 B． 2k+1 C．2k-1 D．2k

11.

广义表 (a,(a,b)d,e.((i,j),k)) 深度为（）

A．6 B． 5 C．4 D．3

12.

已知二叉树的后续遍历列式为 dabec，中序遍历列式为 debac，则前序遍历列式（）

A．acbed B． cedba C．deabc D．decab

13.

按二叉树定义具有3个结点的二叉树有（）

A．5种 B． 4种 C．3种 D．6种

14.

对矩阵压缩存储是为另了（）

A．方便运算 B． 节省空间 C．方便存储 D．提高运算速度

15.

下列四个序列中哪个是堆（）

A．2，3，10，9，5，7，8，12，11 B． 12，11，5，2，3，10，9，8，7

C．2，3，5，9，10，7，8，12，11 D． 12，11，7，8，10，9，2，3，5

16.

有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查

找值为82的结点时， C 次比较后查找成功

A． 11 B． 5

C． 4 D． 8

17.

一个有n个顶点的无向图中，要连通全部顶点需要（）条边。

A．n B． n+1 C．n-1 D．n/2

18.

散列表的平均查找长度（）

A．既与处理方法有关也与表长度有关

B．与处理方法无关但是与表长度有关

C．与处理方法有关但是与表长度有关

D．既与处理方法无关也与表长度无关

19.

下列排序方法中，（B）是稳定的排序方法

A．直接选择排序

C．希尔排序

B．二分法插入排序

D．快速排序

20.

直接选择排序的时间复杂度为（）（n为元素个数）

A．O（n） B．O(log

2

n) C．O(nlog

2

n) D． O(n

2

)

第 2 页 共 5 页

二、

应用题

1.

写出下列稀疏矩阵对应的元素组.

0 0 1 0

1 -5 0 2

0 3 0 0

4 0 -2 0

解：

2.

一已知二叉树如图所示，写出前序、中序、后序遍历该二叉树所

得的三种遍历序列。

解：前序遍历序列为：

中序遍历序列为 ：

后序遍历序列为：

b

a

c

d e f g

h i

3.

一份电文有5个字符：a，b，c，d，e。所对应的频率分别是：4,7,5,2,9.

求对应的哈夫曼树（以左子树的根结点的权小于等于右子树的根结点

的权的次序构造）；求每个字符的哈弗曼编码。

第 3 页 共 5 页