《数据结构》期末考试试卷

………………………………..………………..……………….………………………………………………………………..…………….…………..…………… 广东创新科技职业学院期末考试试题（标明A卷、B或C卷）

2018 —2019 学年第 二 学期 考试科目：《数据结构》

(闭（开）卷 90分钟)

院系____________ 班 级____________ 学号___________ 姓名__________ 题号 得分 阅卷人

得 分 一 二 三 四 五 六 七 八 九 十 总分 密

一、选择题 （每小题 2 分，共 40 分）

B．数据元素

C．数据结构

D．数据类型

1.计算机识别、存储和加工处理的对象被统称为（ ）。

A．数据

2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一 般包括（ ）三方面内容。

A．数据的逻辑结构、数据的存储结构、数据的描述 B．数据的逻辑结构、数据的存储结构、数据的运算 C．数据的存储结构、数据的运算、数据的描述 D．数据的逻辑结构、数据的运算、数据的描述 3．数据的逻辑结构包括（ ）。

A．线性结构和非线性结构 C．非线性结构和集合结构

B．线性结构和树型结构 D．线性结构和图状结构

封4.（ ）的特征是：有且仅有一个开始结点和一个终端结点，且所有结 点都最多只有一个直接前驱和一个直接后继。

A．线性结构 B．非线性结构 A．算法易于调试

C．树型结构

D．图状结构

5. 评价一个算法时间性能的主要标准是（ ）。

B．算法易于理解 D．算法的时间复杂度

C．算法的稳定性和正确性

线6. 下述程序段①中各语句执行频度的和是（ ）。

s=0; ① for(i=1;i<=i;j++) s+=j; A．n-1

B．n

C．2n-1

D．2n

7. 下面程序段的时间复杂度为（ ）。

for(i=0;i1 / 4

使用班级：2018计算机应用技术 出卷老师：周均梅

for(j=1;jA[i][j]=0;

B．O(m+n+1)

C．O(m+n)

D．O(m*n)

A.O(n)

8．以下关于线性表叙述正确的是（ ）。

A．数据元素在线性表中可以是不连续的 B．线性表是一种存储结构 C．线性表是一种逻辑结构

D．对线性表做插入或删除操作可使线性表中的数据元素不连续 9. 一个顺序表第一个元素的存储地址是 100，每个元素的存储长度为 4，则 第 5 个元素的地址是（ ）。

A．110

B．116

C．100

D．120

10. 带头结点的单链表的头指针为 head，判断该链表为非空的条件是（ ）。

A．head==NULL C．head!=NULL

B．head->next==NULL D．head->next!=NULL

11. 假设元素只能按 a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个 元素为 c，则可能得到的出栈序列为（ ）。

A．cabd

B．cadb

C．cdab D．cdba

12. 已知栈的最大容量为 4。若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）。

A．5，4，3，2，1，6 C．3，2，5，4，1，6

B．2，3，5，6，1，4

D．1，4，6，5，2，3

13. 设循环队列的容量为 50（序号从 0 到 49），现经过一系列的入队和出队运算后，有 front=11，rear=29，循环队列中的元素个数是（ ）。

A．18

B．19

C．32

D．33

14. 树可以用集合{(x,y)|结点 x 是结点 y 的双亲}表示，如 T={(b,d),(a,b),(c,e), (c,g),(c,f),(a,c),(e,h) }，则树 T 的度是（ ）。

A．1 A．k

B．2

C．3

D．4 D．2 k

15. 深度为 k 的完全二叉树最少有（ ）个结点。

B．2 k-1

C．2 k -1

16. 若一棵二叉树中度为 l 的结点个数是 3，度为 2 的结点个数是 4，则该 二叉树叶子结点的个数是（ ）。

A．4 A．5

B．5 B．10

C．7 C．15

D．8 D．20

17. 结点数为 20 的二叉树最小深度为（ ）。 18. 如图1所示二叉树的后序序列是（ ）。

2 / 4

使用班级：2018计算机应用技术 出卷老师：周均梅

A.HEDBJIGFCA C．DEHBFGIJCA

长度是（ ）。

A．31

B．HDEBJIFGCA D．DHEBFJIGCA

19. 用 5 个权值为{3，2，4，5，1}的叶子结点构造的哈夫曼树的带权路径

B．33

C．35

D．37

20. 以下说法错误的是（ ）。

A．一般在哈夫曼树中，权值越大的叶子离根结点越近。 B．哈夫曼树中没有度数为 1 的分支结点。

C．若初始森林有 n 棵二叉树，最终求得的哈夫曼树共有 2n-1 个结 点。

D．若初始森林有 n 棵二叉树，进行 2n-1 次合并后才能剩下一棵最 终的哈夫曼树

得 分

二、填空题 （每小题 4 分，共 20 分）

1.图状结构数据元素之间存在 的关系。

2.在顺序表中，只要知道 ，就可在相同时间内求出任一结点的存储地址。

3.假设结点数据域数据输入顺序为 a,b,c，则用尾插法建立的单链表结点的 顺序是

4.在栈中，出栈操作的时间复杂度是

5.在一棵度为3的含有16个结点的树中，度为 2 的结点个数是 2，度为 0 的结点个数是7，则度为 1的结点个数是

得 分

三、简答题 （每小题 20 分，共 40 分）

1. 已知一棵二叉树的前序序列和中序序列分别为 ABDGHCEFI 和 GDHBAECIF。

（1）请画出此二叉树。 （2）给出该二叉树的后序遍历序列。

3 / 4

使用班级：2018计算机应用技术 出卷老师：周均梅

2.已知有向图的邻接表如图所示，请回答下面问题

（1）给出该图的邻接矩阵

（2）从顶点A出发，写出该图的深度优先遍历序列

4 / 4