(总分：100.00，做题时间：90分钟)
一、单项选择题(总题数：15，分数：30.00)
1.一个算法的时间耗费的数量级称为该算法的___
分数：2.00）
a.效率。b.难度。
c.可实现性。
d.时间复杂度√
解析：[考点] 算法的时间复杂度的概念
解析] 一个算法的时间耗费的数量级称为该算法的时间复杂度。
2.顺序表便于___
分数：2.00）
a.插入结点。
b.删除结点。
c.按值查找结点。
d.按序号查找结点√
解析：[考点] 顺序表的特征
解析] 顺序表便于按序号查找结点。
3.设带头结点的单循环链表的头指针为head，指针变量p指向尾结点的条件是___
分数：2.00）
解析：[考点] 指针变量p指向尾结点的判定条件
解析] 单循环链表的指针变量p指向尾结点的判定条件是p-＞next==head。
4.设以数组a[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为___
分数：2.00）
a.(rear-front+m)%m√
c.(front-rear+m)%m
d.(rear-front)%m
解析：[考点] 队列中元素个数的计算
解析] 队列中元素的个数为(rear-front+m)%m
5.下列关于顺序栈的叙述中，正确的是___
分数：2.00）
a.入栈操作需要判断栈满，出栈操作需要判断栈空√
b.入栈操作不需要判断栈满，出栈操作需要判断栈空。
c.入栈操作需要判断栈满，出栈操作不需要判断栈空。
d.入栈操作不需要判断栈满，出栈操作不需要判断栈空。
解析：[考点] 顺序栈的性质的判断
解析] 入栈操作需要判断栈满，出栈操作需要判断栈空。
是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a 0，0 的存储地址为1，每个元素占一个存储单元，则a 7，5 的地址为___
分数：2.00）
a.25b.26
c.33d.34√
解析：[考点] 对称矩阵的元素的地址的计算
解析] 若对称矩阵采用下三角压缩存储，根据其地址的计算公式，可得到所求元素的地址。
7.树的后序遍历等价于该树对应二叉树的___
分数：2.00）
a.层次遍历。
b.前序遍历。
c.中序遍历√
d.后序遍历。
解析：[考点] 树的遍历与二叉树遍历的关系
解析] 树的后序遍历等价于该树对应的二叉树的中序遍历。
8.使用二叉线索树的目的是便于___
分数：2.00）
a.二叉树中结点的插入与删除。
b.在二叉树中查找双亲。
c.确定二叉树的高度。
d.查找一个结点的前驱和后继√
解析：[考点] 二叉线索树的使用目的
解析] 二叉线索树的使用目的是便于查找一个结点的前趋和后继。
9.设无向图的顶点个数为n，则该图边的数目最多为___
分数：2.00）
d..n2解析：[考点] 无向图的边数的问题
解析] 无向图的边数最多为n(n-1)/2。
10.可进行拓扑排序的图只能是___
分数：2.00）
a.有向图。
b.无向图。
c.有向无环图√
d.无向连通图。
解析：[考点] 拓扑排序的图的要求
解析] 可进行拓扑排序的图只能是有向无环图。
11.下列排序方法中稳定的是___
分数：2.00）
a.直接插入排序√
b.直接选择排序。
c.堆排序。
d.快速排序。
解析：[考点] 排序方法稳定性的判断
解析] 直接插入排序是稳定的，直接选择排序、堆排序以及快速排序是不稳定的。
12.下列序列不为堆的是___
分数：2.00）
a.75，45，65，30，15，25
b.75，65，45，30，25，15
c.75，65，30，15，25，45√
d.75，45，65，25，30，15
解析：[考点] 堆的判断
解析] 根据堆的概念，可判断出75，65，30，15，25，45不为堆。
13.对线性表进行二分查找时，要求线性表必须是___
分数：2.00）
a.顺序存储。
b.链式存储。
c.顺序存储且按关键字有序排列√
d.链式存储且按关键字有序排列。
解析：[考点] 二分查找对线性表的要求
解析] 对线性表进行二分查找时，要求线性表必须是顺序存储且按关键字有序排列。
14.分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是___
分数：2.00）
a.(4，1，2，3，5)√
b.(4，2，3，1，5)
c.(4，5，2，1，3)
d.(4，2，1，5，3)
解析：[考点] 二叉排序树的生成
解析] 根据二叉排序树的生成方法，不同的序列是a选项。
15.下列关于m阶b树的叙述中，错误的是___
分数：2.00）
a.每个结点至多有m个关键字√
b.每个结点至多有m棵子树。
c.插入关键字时，通过结点**使树高增加。
d.删除关键字时通过结点合并使树高降低。
解析：[考点] b树的特征的判断
解析] m阶b树中，若树非空，则根结点至少有一个关键字，最多有m-1个关键字。
二、填空题(总题数：10，分数：20.00)
16.数据元素之间的逻辑关系称为数据的 1结构。
分数：2.00）
解析：逻辑 [考点] 数据的逻辑结构的概念
解析] 数据元素之间的逻辑关系称为数据的逻辑结构。
17.**性表中，表的长度定义为 1。
分数：2.00）
解析：数据元素的个数 [考点] 线性表中表的长度的计算
解析] **性表中，表的长度定义为数据元素的个数。
18.用s表示入栈操作，x表示出栈操作，若元素入栈的顺序为，为了得到的出栈顺序，相应的s和x的操作序列为 1。
分数：2.00）
解析：sxssxsxx [考点] 栈的操作
解析] 若元素入栈的顺序为，为了得到的出栈顺序，相应的s和x的操作序列为sxssxsxx。
19.在二叉树中，带权路径长度最短的树称为 1。
分数：2.00）
解析：哈夫曼树 [考点] 哈夫曼树的概念
解析] 在二叉树中，带权路径长度最短的树称为哈夫曼树。
20.已知广义表g，head(g)与tail(g)的深度分别为4和6，则g的深度是 1。
分数：2.00）
解析：6 [考点] 广义表的深度
解析] 若表尾深度大于表头深度，那么线性表的深度为表尾的深度。
21.一组字符(a，b，c，d)在文**现的次数分别为(7，6，3，5)，字符"d"的哈夫曼编码的长度为 1。
分数：2.00）
解析：2 [考点] 哈夫曼编码
解析] 先构造出相应的哈夫曼树，然后进行编码。
22.在一个具有n个顶点的无向图中，要连通全部顶点至少需要 1条边。
分数：2.00）
解析：n-1 [考点] 连通无向图的边数的问题
解析] 在一个具有n个顶点的无向图中，要连通全部顶点至少需要n-1条边。
23.直接选择排序算法的时间复杂度是 1。
分数：2.00）
解析：o(n 2 ) 考点] 直接选择排序算法的时间复杂度
解析] 直接选择排序算法的时间复杂度是o(n 2 )。
24.对于长度为81的表，若采用分块查找，每块的最佳长度为 1。
分数：2.00）
解析：9 [考点] 分块查找
解析] 对于长度为81的表，若采用分块查找，每块的最佳长度为9。
25.用二叉链表保存有n个结点的二叉树，则结点中有 1个空指针域。
分数：2.00）
解析：n+1 [考点] 二叉链表中空指针域的个数
解析] 用二叉链表保存有n个结点的二叉树，则结点中有n+1个空指针域。
三、解答题(总题数：4，分数：20.00)
26.假设q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一个位置，队头指针指向队头元素)，初始状态写出依次执行下列操作后头、尾指针的当前值。
a，b，c，d，e，f入队，a，b，c，d出队；(1)
g，h，i，j，k，1入队，e，f，g，h出队；(2)
m，n，o，p入队，i，j，k，l，m出队；(3)
分数：5.00）
正确答案：()
解析： 考点] 循环队列的操作。
27.已知一个无向图如下图所示，以①为起点，用普里姆(prim)算法求其最小生成树，画出最小生成树的构造过程。
分数：5.00）
正确答案：()
解析：最小生成树的生成过程如下：
[考点] prim算法求最小生成树的过程。
用归并排序法对序列(98，36，-9，0，47，23，1，8)进行排序，问：（分数：5.00）
1).一共需要几趟归并可完成排序。（分数：2.50）
正确答案：()
解析：需要3趟。
2).写出第一趟归并后数据的排列次序。（分数：2.50）
正确答案：()
解析：(36，98，9，0，23，47，1，8)[考点] 归并排序法的应用。
一组记录关键字(55，76，44，32，64，82，20，16，43)，用散列函数h(key)=key%11将记录散列到散列表ht___中去，用线性探测法解决冲突。（分数：5.00）
2019数据结构模拟真题
即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。命运如同手中的掌纹，无论多曲折，终掌握在自己手中。末样卷参 一 是非题 每题1分共10分 1.线性表的链式存储结构优于顺序存储结构。f 2.栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。f 3 字符串是数据对象特定的线...
经典数据结构题
目录。第一部分选择题 2 第二部分填空题 19 第三部分应用题 24 1.数据的四种基本逻辑结构是指 a 数组 链表 树 图形结构b 线性表 链表 栈 广义表。c 线性结构 链表 树 图形结构 d 集合 线性结构 树 图形结构。2.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用 表示。a ...
数据结构常用算法数据结构算法
void union list la,list lb union void mergelist list la,list lb,list lc else while i la len while j lb len mergelist status initlist sq sqlist l elemt...