结构与算法

一、单项选择题

1. 在二叉树中，度为 2 的结点个数最多为（ ）。
A. 1
B. 2
C. 3
D. 4

2. 在二叉树中，度为 0 的结点称为（ ）。
A. 叶子结点
B. 根结点
C. 空结点
D. 中间结点

3. 在二叉树中，结点的度数等于其子树的高度称为（ ）。
A. 深度
B. 高度
C. 层次
D. 宽度

4. 以下哪个排序算法的时间复杂度最小？
A. 冒泡排序
B. 插入排序
C. 快速排序
D. 选择排序

5. 在链表中，头结点指向第一个结点，尾结点的 next 指针指向（ ）。
A. NULL
B. 头结点
C. 尾结点
D. 第一个结点

6. 在栈的顺序存储结构中，栈顶指针指向（ ）。
A. 栈底
B. 栈顶元素
C. 下一个入栈元素的位置
D. 下一个出栈元素的位置

7. 以下哪个算法不属于贪心算法？
A. Dijkstra 算法
B. Prim 算法
C. Kruskal 算法
D. Floyd 算法

8. 以下哪个算法不属于动态规划算法？
A. 贪心算法
B. 最短路径算法
C. 背包问题算法
D. 最长公共子序列算法

9. 在二叉排序树中，中序遍历的结果是（ ）。
A. 从小到大排列的序列
B. 从大到小排列的序列
C. 随机排列的序列
D. 无序排列的序列

10. 以下哪个排序算法是稳定的？
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 选择排序

二、填空题

1. 在二叉树中，度为 1 的结点称为（ ）。

2. 在链表中，结点的 next 指针指向下一个结点的（ ）。

3. 在栈的链式存储结构中，栈顶指针指向（ ）。

4. 在队列的链式存储结构中，队头指针指向（ ）。

5. 在二叉排序树中，任意一个结点的左子树中所有结点的值都小于该结点的值，右子树中所有结点的值都大于该结点的值，这个性质称为（ ）。

6. 在冒泡排序中，第 i 趟排序的比较次数是（ ）。

7. 在插入排序中，最好的时间复杂度是（ ）。

8. 在选择排序中，第 i 趟排序的比较次数是（ ）。

9. 在快速排序中，最坏的时间复杂度是（ ）。

10. 在堆排序中，堆的建立时间复杂度是（ ）。

三、简答题

1. 请简述二叉树的定义及其性质。

2. 请简述链表的定义及其常见操作。

3. 请简述栈的定义及其常见操作。

4. 请简述队列的定义及其常见操作。

5. 请简述二叉排序树的定义及其性质。

6. 请简述冒泡排序的基本思想及其优化方法。

7. 请简述插入排序的基本思想及其优化方法。

8. 请简述选择排序的基本思想及其优化方法。

9. 请简述快速排序的基本思想及其优化方法。

10. 请简述堆排序的基本思想及其优化方法。