《数据结构》试卷
姓名：学号：专业：层次
/p>
一、填空题（共20分，每空1分）
（一）一个队列的入列序列是d，c，b，a，则队列的输出序列是1。
（二）一个字符串中2称为该串的子串。
（三）线性表、栈和队列都是3结构。可以在线性表的4位置插入元素和删除元素；对于栈只能在5插入或删除元素，其运算遵循6的原则；对于队列只能在7插入元素，在8删除元素，其运算遵循9的原则。
（四）树的带权路径长度是树中所有10结点的带权路径长度之和。
（五）已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是11。
（六）数据的逻辑结构分为：集合结构、12、树形结构、种，其中14和15合称非线性结构。
（七）深度为m的二叉树最大结点数为16。
（八）从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动17个元素。
（九）有向图中某结点的度是其18和19之和。
（十）对图的遍历，一般使用两种算法，它们分别是：广度优先搜索遍历算法和
20。
二、选择题（共20分，每小题2分）
（一）在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）
A、数据的处理方法
B、数据元素的类型
C、数据元素之间的关系 D、数据的存储方法
（二）线性表中哪些元素只有一个直接前驱和一个直接后继（）
A、首元素B、中间元素C、尾元素D、所有元素
（三）算法分析的目的是（）
A、找出数据结构的合理性
B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进
D、分析算法的易读性和文档性
（四）队列是限定在（）进行插入操作的线性表。
A、端点B、队头C、队尾D、中间
（五）链表不具备的特点是（）
A、可随机访问任一结点
B、插入删除不需要移动元素
C、不必事先估计存储空间
D、所需空间与其长度成正比
（六）在一颗二叉树的第5层的结点数最多为（）
A、8B、15C、16D、31
（七）在一个图中，所有边数之和等于所有的顶点度数的（）
A、1/2B、1C、2D、4
（八）一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）
A、edcba
B、decba
C、dceab
D、abcde
（九）一个队列的入队序列是1，2，3，4，则队列的输出序列是（）
A、4，3，2，1
B、1，2，3，4
C、1，4，3，2
D、3，2，4，1
（十）下列排序方法中，不属于内排序方法的是（）
A、插入排序法B、选择排序法
C、拓扑排序法D、归并排序法
三、判断题（每题2分，共10分）
（一）线性表中每个元素都有一个直接前驱和一个直接后继。（）
（二）对任何数据结构链式存储结构一定优于顺序存储结构。（）
（三）在决定选取何种存储结构时，一般不考虑各结点的值如何。（）
（四）线性表就是顺序存储的表。（）
（五）循环链表不是线性表。（）
四、简答题（每题5分，共20分）
（一）线性表
（二）队列
（三）子串的序号
（四）结点的度
五、计算题（每题10分，共30分）
（一）有5个带权结点，其权值分别为3，9，6，2，5试以它们为叶子结点生成一棵哈夫曼树（5分），求出该树的带权路径长度（3分）和树的高度（2分）。
（二）已知一颗二叉树，如图所示：求其先序、中序、后序遍历的结果。（10分）
三
课程考核试卷答案
计算机科学与技术物联网工程专接本专业（类）本科
考核科目数据结构课程类别必修课考核类型考试考核方式闭卷卷别A
注：1.学生务必将答案写在答题纸上，写在本试卷上的无效。
2.学生答卷用字，不得书写繁体字、异体字、二简字或错别字（因教学需要除外）
3.学生答卷结构层次序数，第一层为“一、”，第二层为“（一）”，第三层为“1.”，第四层为“（1）”。
一、填空题（每空1分，共20分）
（一）（1）dcba（二）（2）任意个连续字符构成的部分（三）（3）线性（4）任意（5）栈顶（6）后进先出（7）队尾（8）队头（9）先进先出（四）（10）叶子（五）（11）cedba（六）（12）线性结构（13）图形结构或网状（14）树形结构（15）图形结构或网状（七）（16）2m-1（八）（17）n-i（九）（18）出度（或入度）（19）入度（或出度）（十）（20）深度优先搜索遍历算法
二、选择题（每题2分，共20分）
三、判断题（每题2分，共10分）
（一）×（二）×（三）√（四）×（五）×
四、简答题（每题5分，共20分）
（一）线性表：线性表：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的所有结点具有相同的数据类型。(5分)
（二）队列：是运算受限的线性表。是一种先进先出的线性表。只允许在表的一端进行插入，而在另一端进行删除。(5分)
（三）子串的序号：将子串在主串中首次出现时的该子串的首字符对应在主串中的序号，称为子串在主串中的序号（或位置）。(5分)
（四）结点的度：结点所拥有的子树的棵数称为结点的度。（5分）
五、计算题（每题10分，共30分）
（一）
（5分）WPL=2×3+3×3+5×2+6×2+9×2=55
该树的带权路径长度为55（3分），树的高度是4（2分）。
（二）答：先序遍历序列：ABDEGHCF（2分）
中序遍历序列：DBGEHACF（4分）
后序遍历序列：DGHEBFCA（4分）
（三）已知如图所示的有向图，请给出：
（1）每个顶点的入度和出度（5分）
（2）邻接表（5分）
