数据结构介绍2018年4月真题及答案分析（02142）
数据结构概论2018年4月真题与答案分析（02142），本文为上年的数据结构概论真题论文自考，包括答案和详细分析。
一、选择题（这个大题有15个小题，每个小题2分，共30分）每个小题列出的四个选项中只有一个符合要求标题，请发送 选择并涂黑答题卡上的相应代码。不正确、过度或未上漆不计分。
1.数据的逻辑结构分为四种，其中结构最复杂的是()
A. 收藏
B. 线性结构
C. 树形结构
D. 图结构
2.下面的程序是矩阵转置算法MM的实现过程，其时间复杂度为()const int n = 3;void MM(int A[n][n]){ int i, j,温度；for(i = 0; 我
AO(1)
BO(log2n)
一氧化碳(n2)
溶解氧(2n)
3. 设序列表的表长为n，然后删除一个元素，最坏情况下元素移动的次数为()
安-2
BN-1
cn
D.n+1
4.以头结点的双向循环链表L为空的条件为()
AL->下一个 == L->之前
BL->先前 == NULL
C.(L->next = = L)&&(L->prior = = L)
D.(L->next = = L)&&(L->prior =NULL)
5.执行推送操作。元素x入栈前需要执行的操作是()
A. 判断堆栈是否已满。如果堆栈未满，则将顶部值加 1
B.判断栈是否为空，如果栈不为空，则栈顶值加1
C.判断栈是否已满，如果栈未满数据结构导论，则栈顶值减1
D.判断栈是否为空，如果栈不为空，则栈顶值减1
6.关于队列，下列说法正确的是（）
A. 队列中的元素数量可以是无限的
B. 队列中元素的类型可以不同
C. 队列是非线性序列
D.队列的特点是先进先出
7.假设循环队列的元素存放在一维数组Q[30]中。当队列不为空时，front表示队列头节点的前一个位置，rear表示队列尾节点。如果队列的元素个数为10，front的值为25，则rear应该指向的元素为()
水[4]
BQ[5]
重庆[14]
DQ[15]
8.二叉树第i个(i≥1)层的节点数最多为()
A.2i-1
双1
C.2*i
D.2*(i-1)
9.关于二叉链表，以下说法是正确的()
A、二叉链表是二叉树唯一的链接存储结构
B. 对二叉链表的访问可以从任意节点开始
C.每个二叉链表不需要有指向根节点的指针
D、二叉链表的节点结构包含一个数据域和两个指针域
10.假设初始森林中有n棵二叉树，每棵树只有一个孤立节点。将森林构造成一棵哈夫曼树，那么最终哈夫曼树的节点数为 ()
安-1
氮化硼
C.2n-1
D.2n
11.无向图中的最大连通子图为()
A. 连接组件
B. 生成树
C. 强连通分量
D. 强连通图
12.当图用邻接表表示时，图的深度优先搜索遍历算法的时间复杂度为()
AO(n)
BO(n+e)
一氧化碳(n2)
做(n3)
13.静态查表和动态查表的根本区别是()
A. 它们有不同的逻辑结构
B. 应用于它的操作不同
C. 包含的数据元素类型不同
D.存储实现方式不同
14.在哈希函数H(k)=k MOD m中，一般情况下m应该取()
A.奇数
B.偶数
C. 质数
D. 足够大的数量
15.以下四种排序算法中，需要辅助存储最多的是()
A. 堆排序
B. 快速排序
C. 直接选择排序
D. 合并排序
二、填空题（这个大题有13个小题，每个空题2分，共26分）
11.如果线性表中的节点数不为零，除了起始节点没有直接前任外，其他节点只有____个直接前任。
12.单链表中每个节点在内存中的存储位置是_________连续的。
13.栈初始化操作的目的是_________。
14.假设E和O分别代表push和pop操作，那么对输入序列a、b、c、d、e进行一系列操作EEOEEOEOOO后，得到的输出序列为_______。
15.二叉树的任意一个结点都有两棵子树，这两棵子树之间存在_________关系。
16.一棵树_________中所有节点的最大值称为树的高度。
17.一棵高度为h(h≥2)的完全二叉树至少有_____个叶子。
18.图的广度优先搜索遍历类似于_________遍历树的过程。
19.稀疏矩阵可以使用_________方法进行压缩和存储。
110.拓扑排序的前提是AOV网络中不允许_________。
111.数据元素的键值与_________之间建立的对应关系称为散列函数。
112.静态查找表是具有相同特征的数据元素集合的逻辑结构数据结构导论，但不包括插入和_________操作。
113.假设表中元素初始状态为键值升序，使用堆排序、快速排序、冒泡排序和归并排序进行升序排序，_______排序方法是最
三、应用题（共5个小题，每个小题6分，共30分）
21.将图29所示的二叉树转化为对应的树或森林。
22.假设一条消息由5个字母a、b、c、d、e组成，每个字母在消息中出现的次数是7、9、5、6、12，试试这5个字母Alphabet设计霍夫曼树并编写相应的霍夫曼代码。（新建二叉树时，要求新二叉树的左子树根的权重小于或等于右子树根的权重。）
23.第31题展示了一个有向图，尝试给出该图的邻接表表示以及对图进行拓扑排序的各种可能的拓扑序列。
24.设哈希表的长度为11，哈希函数H(key) = key mod 11（mod为余数运算），给定的key值序列为：(3, 12 , 13, 27, 34 , 22, 38, 25). 尝试画出使用线性检测方法解决冲突时构建的哈希表，找到搜索成功的情况下的平均搜索长度等概率。
25.有一个key-value序列如第33题的表所示，现在使用快速排序算法根据最左边的key值进行排序。请给出第一次快速排序后 57、72、88 三个元素的位置。问题 33 表格
四、算法设计题（这个大题有2个小题，每个小题7分，共14分）
31.假设单链表的类型定义如下： typedef struct node{ DataType data; struct node *next;}Node, *LinkList; 设计算法 InitiateLinkList() 来初始化单链表。
32.已知静态查表顺序存储结构的类型定义如下： const int Maxsize = 20;typedef struct{ KeyType key; //关键字…//其他字段}TableElem;typedef struct{ TableElem elem[Maxsize +1]; int n;}SqTable; 设计并实现一个有序表二分查找算法SearchBin(SqTable T, KeyType key)（假设有序表按键值从小到大排序）。
