百色职业学院2018——2019学年第二学期清考试卷
计算机 系 应用技术、软件开发 专业 《数据结构》清考卷
命题教师： 农铮 考试日期： 2019年 5 月 日
考试班级： 高职16计算机应用技术班、高职16软件开发技术班 考生姓名：
试题序号
第一题
第二题
第三题
总分
试题满分
30
20
50
100
试题得分
单项选择题（每题 2 分，共30分）
1.数据结构的研究内容不涉及（ ）。
A.数据如何组织 B.数据如何存储
C.数据的运算如何实现 D.采用何种语言描述算法
2.算法的执行时间一般与（ ）无关。
A.问题的规模 B.计算机的档次
C.编译语言的种类和版本 D.算法设计者的水平
3.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（ ）。
A.i>0 B.i≤n C.1≤i≤n D.1≤i≤n+1
4.一般情况下，链表中所占用的存储单元地址是（ ）。
A.无序的 B.连续的 C.不连续的 D.索引
5.所谓稀疏矩阵是指（ ）的矩阵。
A.零元素较多且分布无规律 B.非零元素较少
C.元素较少 D.不适合采用二维数组表示
6.将10阶三对角矩阵中的所有非零元素按照行序方式依次存放于一维数组中，矩阵的第7行第8列的元素在该一维数组中（ ）。
A.是第22个数组元素 B.是第21个数组元素
C.是第20个数组元素 D.不存在
7.堆栈和队列的共同之处在于它们具有相同的（ ）
A.逻辑特性 B.物理特性 C.运算方法 D. 元素类型
8.若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是（ ）。
A.2,4,3,1,5 B.2,3,1,5,4 C.3,1,4,2,5 D.3,1,2,5,4
9.广义表A=((),(a),(b,(c,d)))的长度为（ B ）
A.2 B.3 C.4 D.5
10．广义表A=((),(a),(b,(c,d)))的深度为（ ）
A.2 B.3 C.4 D.5
11．”二叉树为空”意味着二叉树（ ）
A.由一些未赋值的空结点组成 B.树结点无子树
C.不存在 D.没有结点
12.对一棵二叉排序树进行（ ）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。
A.前序 B.中序 C.后序 D.按层次
13．有向图的邻接表的第i个链表中的边结点数是第i个顶点的（ ）
A.度数 B.出度 C.入度 D.边数
14．若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个（ ）图。
A.非连通 B. 连通 C. 强连通 D. 完全
15.通过拓扑排序能够得到拓扑序列的图一定是（ ）。
A.连通图 B.带权连通图 C.无回路的图 D.无回路的有向图
填空题（每题 2 分，共20分）
1.长度为n的线性表采用顺序存储结构，插入或删除一个元素的时间复杂度为 。
2.已知具有4行6列的矩阵A采用行序为主序方式存储，每个元素占用3个存储单元，该数组一共占用了 个存储单元。
3.任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的 。
4.已知二叉树的前序遍历序列为ABDCEFG,中序遍历序列为DBCAFEG,其后序遍历序列为 。
5.若具有n个结点的非空二叉树有n0个叶子结点，则该二叉树有 个 度为2的结点， 个度为1的结点。
6.一个具有n个顶点的有向图最多有 条边。
7.具有n个顶点的连通图的生成树一定有 条边。
8.索引文件包括 和 两个部分。
9.若一个待散列存储的线性表为K=（18,25,63,50,42,32,9,45），散列函数为H(k)=k MOD 9,则与元素18发生冲突的元素有 个。
10. 若在n个记录中查找其中任意一个记录，至少要比较2次，则所采用的查找方法可能是 。
解答题（共50分）
已知叶子节点的权值分别为A（20）、B（8）、C（18）、D（26）、E（3）、
F（9），请利用这些节点构造哈夫曼树。(8分)
2. 分别写出如图所示的树的中序遍历序列与后序遍历序列。(8分)
3. 将如图所示的树林转换为一棵二叉树。(8分)
4.已知一带权连通图如图所示，请首先写出其邻接矩阵结构，然后再按Prim算法求出其所有可能的最小生成树。(8分)
5.对给定AOE网如下图所示，请完成
（1）分别求出各活动的最早开始时间与最晚开始时间。(6分)
（2）求出所有关键路径。(6分)
（3）该工程完成的最短时间是多少？(6分)
第 PAGE4 页/共 NUMPAGES4页
1
2
3
4
8
7
9
10
6
5