数据结构 试题
前言
这里是 数据结构 系列文章，主要介绍计算机二级考试中的涉及到数据结构的知识点 /
数据结构在计算机科学中处处都有存在，例如编译系统要使用栈、散列表、语法树等；操作系统要使用队列、存储管理表、目录树等等。
关于作者：
- 小白（Libra），计算机兴趣爱好者，Java，C，Hadoop，MySQL
- GitHub : https://github.com/Regel-zack
转载请注明出处
题目
在单链表中，增加头结点的目的是
- 方便运算的实现
- 使单链表中至少有一个节点
- 表示表节点中首节点的位置
- 说明单链表是线性表的链式存储实现
算法分析的目的是
- 找出数据结构的合理性
- 找出算法中输入和输出之间的关系
- 分析算法的易懂性和可靠性
- 分析算法的效率以求改进
对于长度为n的线性表，在最坏情况下，各排序算法所对应的比较次数中正确的是
- 冒泡排序为n/2
- 冒泡排序为n
- 快速排序为n
- 快速排序为n(n-1)/2
已知数据表A中每个元素距离其最终位置不远，为节省时间，应采用的算法是
- 堆排序
- 直接插入排序
- 快速排序
- 直接选择排序
下列关于栈的描述中，错误的是
- 栈是先进后出的线性表
- 栈只能顺序存储
- 栈具有记忆功能
- 对栈的插入与删除操作中，不需要改变栈底指针
- 试述二叉树中前序遍历，中序遍历，后序遍历的顺序
解析
头节点不仅表示了表中首节点的位置，而且根据单链表（包含头节点）的结构，只要掌握了表头，就能够访问整个链表，因此增加头节点目的是为了便于运算的实现。
算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后和n/2遍的从后往前扫描，需要比较次数为n(n-1)/2。快速排序的最坏情况比较次数也是n(n-1)/2。
当数据表中每个元素距离其最终位置不远，意味着数据表中元素基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少。
栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又被称为先进后出表(FILO-First In LastOut)。线性表可以顺序存储，也可以链式存储，栈是线性表，因此也可以采用链式存储结构。
- 根据先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为3种：前序遍历、中序遍历和后序遍历。
- 前序遍历指，先访问根结点，再遍历左子树，最后遍历右子数，并且在遍历左、右子树的时候，仍然按先访问根结点，再遍历左子树，最后遍历右子数的顺序。
- 中序遍历指，先遍历左子树，再访问根结点，最后遍历右子数，并且在遍历左、右子树的时候，仍然按先遍历左子树，再访问根结点，最后遍历右子数的顺序。
后序遍历指，先遍历左子树，再遍历右子数，最后访问根结点，并且在遍历左、右子树的时候，仍然是按先遍历左子树，再遍历右子树，最后访问根结点的顺序。
图表复盘
| 题目数量 | 错误数量 | 错误率 |
|---|---|---|
| 20 | 6 | 30% |
| 涉及知识点 | 出现次数 | 占比 |
|---|---|---|
| 链表 | 1 | 14% |
| 算法分析 | 1 | 14% |
| 排序算法 | 3 | 42% |
| 栈 | 1 | 14% |
| 二叉树 | 1 | 14% |
精度自小数点后两位
小结
目前来看，排序算法频率较为突出，占比最大，其他例如链表、栈也各占14%，二叉树虽只有14%，但涉及到的点确实更为复杂，考了前中后序遍历。
但也不排除有样本数量过少，分析不够准确的点
