CSP-J Day3 分类练习：树与图｜排序算法与时间复杂度

Q1:姓名

Q2:一棵完全二叉树的节点总数是 1001，其叶子节点数为（　）。

Q3:对于任何一棵二叉树 T，设 n₀,n₁,n₂ 分别是度数为 0,1,2 的节点数，则下列正确的是（　）。

Q4:一棵非空二叉树的先序序列和后序序列正好相反，则该二叉树一定满足（　）。

Q5:下列有关二叉树的说法正确的是（　）。

Q6:一棵树度是 4，有 2 个度数为 2 的节点，有 6 个度数为 3 的节点，有 3 个度数为 4 的节点，则叶子节点有（　）个。

Q7:某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（　）。

Q8:一棵完全二叉树第六层有 9 个叶结点（根为第一层），则结点个数最多有（　）。

Q9:设根节点的高度为 1，一棵完全二叉树有 999 个结点，它的高度 h 为（　）。

Q10:设一棵完全二叉树有 700 个结点，则共有（　）个度为 2 的结点。

Q11:一棵节点数为 2021 的二叉树最多有多少叶子节点（　）。

Q12:由 3 个结点所构成的二叉树有（　）种形态。

Q13:将一棵有 50 个结点的完全二叉树从根开始每层从左到右编号（根编号为 1），则编号为 20 的结点的右孩子编号为（　）。

Q14:如果哈夫曼树有 67 个结点，则可知叶结点总数为（　）。

Q15:某二叉树中序序列为 ABCDEFG，后序序列为 BDCAFGE，则前序序列是（　）。

Q16:某二叉树的前序遍历序列是 ABCDEFG，中序遍历序列是 CBDAFGE，则其后序遍历序列是（　）。

Q17:已知一棵树的先序序列是 ABDEGCFH，中序序列是 DBGEACHF，则该树的层次遍历为（　）。

Q18:对某二叉树进行先序遍历的结果为 ABDEFC，中序遍历的结果为 DBFEAC，则后序遍历的结果是（　）。

Q19:假设在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为（　）个。

Q20:以数据集 {4,5,6,7,12,18,10} 为结点权值所构造的哈夫曼树，其带权路径长度 WPL 为（　）。

Q21:为五个使用频率不同的字符设计哈夫曼编码，下列方案中哪个不可能是哈夫曼编码？

Q22:若一棵哈夫曼树具有 887 个结点，则该二叉树的度为 2 的结点个数是（　）。

Q23:树最适合用来表示（　）。

Q24:在具有 n（n1）个结点的完全二叉树中，结点 i（2in）的左孩子结点是（　）。

Q25:若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点个数是（　）。

Q26:若一棵完全二叉树具有 665 个结点，则该二叉树的度为 2 的结点个数是（　）。

Q27:某二叉树的先序和后序序列正好相反，则该二叉树一定是（　）的二叉树。

Q28:在图的广度优先搜索中通常需要一个（　）存放需要访问的顶点。

Q29:在一个无向图中，所有顶点的度数之和等于所有边数的（　）倍。

Q30:在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 s，则所有顶点的入度数之和为（　）。

Q31:一个有 n 个顶点的无向图最多有（　）条边。

Q32:在一个具有 n 个顶点、e 条边的无向图中，所有顶点的度数之和为（　）。

Q33:在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 s，则所有顶点的度数之和为（　）。

Q34:具有 6 个顶点的无向图至少应有（　）条边才能确保是一个连通图。

Q35:在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（　）条边。

Q36:对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则顶点表数组的大小为（1），所有邻接表（边表）中的结点总数是（2）。（1）A.n B.n+1 C.n−1 D.n+e；（2）A.e/2 B.e C.2e D.n+e

Q37:图的广度优先遍历算法类似于树的（　）。

Q38:将数组 {32,74,25,53,28,43,86,47} 按从小到大排列，每次可交换任意两个元素，最少需要交换（　）次。

Q39:将数组 {8,23,4,16,77,−5,53,100} 按从小到大排列，每次可交换任意两个元素，最少需要交换（　）次。

Q40:快速排序最坏情况下的算法时间复杂度为（　）。

Q41:排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的？

Q42:基于比较的排序时间复杂度的下限是（　），其中 n 表示待排序元素个数。

Q43:同学们按从高到矮站成一排，每个同学从排尾走向排头，找到第一个比自己高的同学并站在他后面。这种站队方法类似于（　）算法。

Q44:使用冒泡排序对序列 5,4,3,2,1 升序排列，每执行一次交换减少 1 个逆序对，则共需执行（　）次操作。

Q45:（　）的平均时间复杂度为 O(n log n)，其中 n 是待排序元素个数。

Q46:下列各种排序算法中，不是以“比较”作为主要操作的算法是（　）。

Q47:将 5 个数的序列排序，不论原先顺序如何，最少都可以通过（　）次比较完成从小到大排序。

Q48:给定序列（49,38,65,97,76,13,27,49,55,4）经三趟后变为 4,13,27,38,49,49,55,65,76,97，所用方法是（　）。

Q49:下列排序算法中不稳定的是（　）。

Q50:给出 3 种排序：插入排序、冒泡排序、计数排序，它们的时间代价分别是（　）。

Q51:给出 10 个整数，需要至少进行（　）次比较操作才能保证找出最小值。

Q52:请选择一个选项

Q53:下列伪代码所描述的排序算法是（　）：for i←1 to n−1: xb←i; for j←i to n: if a[j]a[xb] then xb←j; swap(a[xb],a[i])。

Q54:插入排序的最好情况与最差情况时间复杂度分别为（　）。

Q55:以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需要的最少比较次数为（　）。

Q56:在数据压缩编码中的哈夫曼编码方法，本质上是一种（　）的策略。

Q57:假设有序表中有 1000 个元素，用二分法查找元素 x 最多需要比较（　）次。

Q58:用 5 个权值 10,12,15,20,25 构造哈夫曼树，带权路径长度是（　）。

Q59:在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于（　）。

Q60:已知完全二叉树第 4 层节点数共 8 个，则该树最多有多少个节点（　）。