day22—选择题
文章目录
1.下列数据结构具有记忆功能的是（C）
A 队列
B 循环队列
C 栈
D 顺序表
思路：记忆功能：如浏览器的回退，文本编辑器的撤销功能都是属于记忆功能；栈是先进后出，最先进去的数肯定是最后出来的，所以说有记忆功能
2.循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（A）
A 队空：end1 == end2；队满：end1==(end2+1) mod M
B 队空：end1 == end2；队满：end2==(end1+1) mod (M-1)
C 队空：end2==(end1+1) mod M；队满：end1==(end2+1) mod M
D 队空：end1==(end2+1) mod M；队满：end2==(end1+1) mod (M-1)
思路：对于循环队列来说，我们需要浪费一个空间用来判断队列是否已满；数组的长度是M，能存储的元素个数就是M-1，最终判断是否已满就是mod M
3.对递归程序的优化的一般的手段为（A）
A 尾递归优化
B 循环优化
C 堆栈优化
D 停止值优化
思路：对递归程序的优化，一般是采用尾递归优化
4.将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点加入队。以上操作可以实现哪种遍历（D）
A 前序遍历
B 中序遍历
C 后序遍历
D 层序遍历
思路：用到队列的只有层序遍历；其他的遍历用到的都是栈
补充一个知识：hash表的插入的时间复杂度是O(1)
5.将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是（D）
A 2n
B 2n-1
C n-1
D n
思路：两个有序的子区间的个数都为n，最好的情况就是第二个子区间都比第一个区间大，只需要比较n次
6.下列排序法中，每经过一次元素的交换会产生新的逆序的是（A ）
A 快速排序
B 冒泡排序
C 简单插入排序
D 简单选择排序
思路：数组的逆序指的是每当一次元素交换后，当前元素之后还有比当前元素还小的元素，就构成了数组的逆序；简单插入排序和简单选择排序会减少逆序；冒泡排序是交换相邻的两个元素，不一定会产生新的逆序；快速排序一定会产生新的逆序