动态规划·多选训练2

第 1 题（多选）

关于二叉排序树（BST），下列哪些说法是正确的？（）

{{ multiselect(1) }}

• 左子树中所有节点的值均小于根节点的值
• 中序遍历 BST 可以得到一个升序序列
• BST 的查找效率与树的高度有关
• 删除 BST 中的节点时，如果被删除节点有左右子树，可以用左子树的最大节点来替换

第 2 题（多选）

关于二叉排序树的查找，下列说法正确的有（）。

{{ multiselect(2) }}

• 平均查找长度与树的形状有关
• 最坏情况下查找效率退化为 O(n)
• 二叉排序树查找效率一定高于顺序查找
• 插入和删除操作会改变树的形状

第 3 题（多选）

下列哪些是动态规划的特点？（）

{{ multiselect(3) }}

• 最优子结构
• 贪心选择
• 重叠子问题
• 自底向上或自顶向下求解

第 4 题（多选）

下列哪些算法可以用动态规划求解？（）

{{ multiselect(4) }}

• 背包问题
• 最长公共子序列
• 最短路径（Dijkstra 算法）
• 斐波那契数列

第 5 题（多选）

下列哪些问题是典型的动态规划问题？（）

{{ multiselect(5) }}

• 爬楼梯问题
• 最长上升子序列
• 最短路径（无权图）
• 0-1 背包问题