广东创新科技职业学院期末考试试题（标明A 卷、B 或C
卷）
2018 —2019 学年第二学期考试科目：《数据结构》
(闭（开）卷 90分钟)
院系____________ 班级____________ 学号___________ 姓名
__________
一、选择题（每小题 2 分，共 40 分）
1.计算机识别、存储和加工处理的对象被统称为（）。
A ．数据
B ．数据元素
C ．数据结构
D ．数据类型
2.数据结构指的是数据之间的相互关系，即数据的组织形式。
数据结构一般包括（）三方面内容。
A ．数据的逻辑结构、数据的存储结构、数据的描述
B ．数据的逻辑结构、数据的存储结构、数据的运算
C ．数据的存储结构、数据的运算、数据的描述
D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。
A ．线性结构和非线性结构
B ．线性结构和树型结构
C ．非线性结构和集合结构
D ．线性结构和图状结构
4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。
A ．线性结构
B ．非线性结构
C ．树型结构
D ．图状结构
5. 评价一个算法时间性能的主要标准是（）。
A ．算法易于调试
B ．算法易于理解
C ．算法的稳定性和正确性
D ．算法的时间复杂度
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;i<n;i++) ………………………………..………………..密……………….……………………封…………………………………………..线
…………….…………..……………
for(j=1;j<m;j++)
A[i][j]=0;
A.O(n) B．O(m+n+1) C．O(m+n) D．O(m*n)
8．以下关于线性表叙述正确的是（）。
A．数据元素在线性表中可以是不连续的
B．线性表是一种存储结构
C．线性表是一种逻辑结构
D．对线性表做插入或删除操作可使线性表中的数据元素不连续9. 一个顺序表第一个元素的存储地址是 100，每个元素的存储长度为4，则第 5 个元素的地址是（）。
A．110 B．116 C．100 D．120
10. 带头结点的单链表的头指针为 head，判断该链表为非空的条件是（）。
A．head==NULL B．head->next==NULL
C．head!=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 B．2，3，5，6，1，4
C．3，2，5，4，1，6 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 B．2 C．3 D．4
15. 深度为 k 的完全二叉树最少有（）个结点。
A．k B．2 k-1 C．2 k -1 D．2 k
16. 若一棵二叉树中度为 l 的结点个数是 3，度为 2 的结点个数是 4，则该二叉树叶子结点的个数是（）。
A．4 B．5 C．7 D．8
17. 结点数为 20 的二叉树最小深度为（）。
A．5 B．10 C．15 D．20
18. 如图1所示二叉树的后序序列是（）。
A.HEDBJIGFCA B．HDEBJIFGCA
C．DEHBFGIJCA D．DHEBFJIGCA
19. 用5 个权值为{3，2，4，5，1}的叶子结点构造的哈夫曼树的带权路径长度是（）。
A．31 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）给出该二叉树的后序遍历序列。
2.已知有向图的邻接表如图所示，请回答下面问题
（1）给出该图的邻接矩阵
（2）从顶点A出发，写出该图的深度优先遍历序列。