day20—选择题
文章目录
- 1.对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（C）
- 2.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）
- 3.初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为（A）
- 4. 以下哪种排序算法对(1,3,2,4,5,6,7,8,9)进行的排序最快（A）
1.对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（C）
A O(n) O(n)
B O(n) O(1)
C O(1) O(n)
D O(1) O(1)
思路：对于顺序表，它访问结点的时间复杂度为O(1）,如果在数组的第一个位置增加一个元素，它的时间复杂度就是O(N)
2.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）
A 不存在这样的二叉树
B 200
C 198
D 199
思路：二叉树的结点个数 = 叶子结点的个数 + 度为1的结点的个数 + 度为2的结点的个数；
叶子结点的个数 = 度为2的结点的个数 + 1；
二叉树的节点的度指的是结点的孩子的个数
3.初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为（A）
A 8 3 2 5 1 6 4 7
B 3 2 8 5 1 4 6 7
C 3 8 2 5 1 6 7 4
D 8 2 3 5 1 4 7 6
思路：建立小根堆的过程是根据向上调整进行排序，自底向上递归调整
中序遍历是：左根右
4. 以下哪种排序算法对(1,3,2,4,5,6,7,8,9)进行的排序最快（A）
A 冒泡
B 快排
C 归并
D 堆排
思路：冒泡排序适用于一组数据基本是有序的