数据结构 试题
前言
这里是 数据结构 系列文章，主要介绍计算机二级考试中的涉及到数据结构的知识点 /
数据结构在计算机科学中处处都有存在，例如编译系统要使用栈、散列表、语法树等；操作系统要使用队列、存储管理表、目录树等等。
关于作者：
- 小白（Libra），计算机兴趣爱好者，Java，C，Hadoop，MySQL
- Email : hewei20031009@163.com
- GitHub : https://github.com/Regel-zack
转载请注明出处
题目
冒泡排序在最坏情况下的比较次数是
- n(n+1)/2
- nlogn
- n(n-1)/2
- n/2
某二叉树有5个度为2的节点，则该二叉树中的叶子节点数是
- 10
- 8
- 6
- 4
对于循环队列，下列叙述中正确的是
- 队头指针是固定不变的
- 队头指针一定大于队尾指针
- 队头指针一定小于队尾指针
- 队头指针可以大于队尾指针，也可以小于队尾指针
某二叉树中有n个度为2的结点，则该二叉树中的叶子节点数为
- n+1
- n-1
- 2n
- n/2
- 支持子程序调用的数据结构是
- 栈
- 树
- 队列
- 二叉树
解析
- 冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。
- 假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。
- 在任意一颗二叉树中，度为0的节点，总是比度为2的节点多一个。
- 所谓循环队列，就是将队列空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
- 在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。
- 循环队列主要有两种基本运算：入队运算与退队运算，每进行一次入队运算，队尾指针就进一。
- 每进行一次退队运算，排头指针就进一。
- 当rear或front的值等于队列的长度+1时，就将rear或front的值置为1。一般情况下，rear大于front，因为入队的元素肯定比出队的元素多。特殊的情况是rear到达数组的上限后又从数组的低端开始，此时，rear是小于front的。
- 在任意一颗二叉树中，度为0的节点，总是比度为2的节点多一个。
- 栈是一种只能在一端进行插入或删除的线性表。在主程序调用子程序时，要首先保存主程序当前的状态，然后去执行子程序，最终把子程序的执行结果返回到主程序调用子程序时的位置，继续往下执行，这种调用符合栈的“先进后出”的功能。
图表复盘
| 题目数量 | 错误数量 | 错误率 |
|---|---|---|
| 20 | 5 | 25% |
| 20 | 6 | 30% |
| 40 | 11 | 27.5% |
第一行为今日的错误数量占比分析 /
第二行开始是前几日的错误数量占比分析 /
最后一行是总的错误数量占比分析
今日知识点分布图
| 涉及知识点 | 出现次数 | 占比 |
|---|---|---|
| 排序算法 | 1 | 20% |
| 二叉树 | 2 | 40% |
| 队列 | 1 | 20% |
| 栈 | 1 | 20% |
总知识点分布图
| 涉及知识点 | 出现次数 | 占比 |
|---|---|---|
| 排序算法 | 4 | 36% |
| 二叉树 | 3 | 27% |
| 队列 | 1 | 9% |
| 栈 | 2 | 18% |
| 链表 | 1 | 9% |
| 算法分析 | 1 | 9% |
精度取自小数点后两位
小结
分为两部分。
先看今日的，今日出现最多的是二叉树，其余各占20%，当然了，这跟不了解二叉树的性质有关，而之前一日占比最大的排序算法在今天仍然是错误了，其主要原因可能因为，八大排序算法都会被归为排序算法中，其范围大，自然错其中一个也就会增加数量了。
其次是总的，从排名上来看，仍然是排序算法占据榜首，其次是二叉树，虽然仅仅只有40道题目的样本，但大概反映了情况，100道题会是一个意义比较大的样本数量，期待吧。
