ID: 3752

客观题

尝试: 12

已通过: 1

难度: 2

上传者:

郑学晶 (zheng)

标签>

数据结构

链表

树与树结构

树

图

C++ 阶段测试（第 54 节 ~ 第 58 节）

共 40 题，全部为单项选择题，每题 2.5 分，满分 100 分。考试时间 30 分钟。其中第 1~28 题为容易题（每题 2.5 分，共 70 分），第 29~40 题为较难题（每题 2.5 分，共 30 分）。

第 1 题

1.一棵有 n 个结点的树，它共有（）条边。 {{ select(1) }}

第 2 题

2.在一棵树中，没有子结点的结点称为（）。 {{ select(2) }}

根结点
分支结点
叶子结点
兄弟结点

第 3 题

3.树中某个结点的"度"是指（）。 {{ select(3) }}

该结点拥有的子结点个数
该结点所在层数
从根结点到该结点经过的边数
该结点所有子孙结点的个数

第 4 题

4.已知一棵树的结构为：A 的孩子是 B、C、D；B 的孩子是 E、F；C 的孩子是 G。这棵树的叶子结点共有（）个。 {{ select(4) }}

第 5 题

5.承接上题，这棵树的高度（根结点为第 1 层）是（）。 {{ select(5) }}

第 6 题

6.承接上题，结点 B 的度是（）。 {{ select(6) }}

第 7 题

7.承接上题，对这棵树进行先根遍历，得到的序列是（）。 {{ select(7) }}

A B E F C G D
A B C D E F G
E F B G C D A
A E F B G C D

第 8 题

8.承接上题，对这棵树进行后根遍历，得到的序列是（）。 {{ select(8) }}

A B E F C G D
E F B G C D A
D C G B F E A
E F G B C D A

第 9 题

9.关于二叉树，下列说法正确的是（）。 {{ select(9) }}

二叉树中每个结点都必须有 2 个子结点
二叉树就是度为 2 的树
二叉树中每个结点最多有 2 个子结点，且左右子树有顺序之分
二叉树中的叶子结点一定在同一层

第 10 题

10.深度为 5 的满二叉树共有（）个结点。 {{ select(10) }}

第 11 题

11.二叉树的第 6 层最多有（）个结点。 {{ select(11) }}

第 12 题

12.把完全二叉树的结点按层序从 1 开始编号，则编号为 i 的结点的左孩子（若存在）的编号是（）。 {{ select(12) }}

i+1
2i+1
i/2
2i

第 13 题

13.已知一棵二叉树：根为 A，A 的左孩子为 B、右孩子为 C；B 的左孩子为 D、右孩子为 E；C 的左孩子为 F（C 没有右孩子）。该二叉树的前序遍历序列是（）。 {{ select(13) }}

A B D E C F
A B C D E F
D B E A F C
D E B F C A

第 14 题

14.已知一棵二叉树：根为 A，A 的左孩子为 B、右孩子为 D；B 没有左孩子，B 的右孩子为 C。该二叉树的中序遍历序列是（）。 {{ select(14) }}

A B C D
B C A D
C B D A
B A C D

第 15 题

15.承接上题，该二叉树的后序遍历序列是（）。 {{ select(15) }}

C D B A
B C D A
A B C D
C B D A

第 16 题

16.已知一棵二叉树：根为 1，1 的左孩子为 2、右孩子为 3；2 的左孩子为 4、右孩子为 5；3 的左孩子为 6。该二叉树的层序遍历序列是（）。 {{ select(16) }}

1 2 4 5 3 6
4 5 2 6 3 1
4 2 5 1 6 3
1 2 3 4 5 6

第 17 题

17.用二叉树表示表达式 (a+b)*(c-d)，根结点应该是（）。 {{ select(17) }}

第 18 题

18.下列问题中，最适合用树结构来表示的是（）。 {{ select(18) }}

公司里部门的层级关系
求两个数的最大公约数
判断一个数是否为素数
求若干个数中的最大值

第 19 题

19.对一棵表达式树进行后序遍历，得到的序列是（）。 {{ select(19) }}

前缀表达式
中缀表达式
后缀表达式
层序序列

第 20 题

20.在用树表示的公司组织架构中，查找某位员工的直接上级，相当于在树中查找该结点的（）。 {{ select(20) }}

兄弟结点
孩子结点
叶子结点
父结点

第 21 题

21.5 个顶点的无向完全图共有（）条边。 {{ select(21) }}

第 22 题

22.在有向图中，以某个顶点为起点的边的条数称为该顶点的（）。 {{ select(22) }}

度
入度
出度
权

第 23 题

23.用邻接矩阵存储一个无向图，该矩阵一定是（）。 {{ select(23) }}

上三角矩阵
单位矩阵
稀疏矩阵
对称矩阵

第 24 题

24.用邻接表存储一个有 n 个顶点、e 条边的无向图，表中表示边的结点总数为（）。 {{ select(24) }}

e
2e
n+e
n(n-1)/2

第 25 题

25.在一个无向图中，若任意两个顶点之间都存在路径，则称这个图是（）。 {{ select(25) }}

连通图
完全图
有向图
稀疏图

第 26 题

26.图的广度优先遍历通常借助（）来实现。 {{ select(26) }}

栈
数组
链表
队列

第 27 题

27.已知无向图有 1~6 号共 6 个顶点，边为 1-2、1-3、2-4、2-5、3-6。从顶点 1 出发进行广度优先遍历（相邻顶点按编号从小到大访问），得到的序列是（）。 {{ select(27) }}

1 2 3 4 5 6
1 2 4 5 3 6
1 3 2 6 5 4
1 2 3 5 4 6

第 28 题

28.图的深度优先遍历在访问顺序上类似于树的（）。 {{ select(28) }}

层序遍历
中序遍历
后序遍历
先序遍历

第 29 题

29.一棵树中有 5 个度为 3 的结点、3 个度为 2 的结点，其余都是叶子结点，则这棵树的叶子结点共有（）个。 {{ select(29) }}

第 30 题

30.把一棵树按"左孩子、右兄弟"的方法转换成二叉树后，原树的先根遍历序列与转换后二叉树的（）序列相同。 {{ select(30) }}

先序
中序
后序
层序

第 31 题

31.已知某二叉树的前序遍历为 A B C D E，中序遍历为 C B D A E，则它的后序遍历为（）。 {{ select(31) }}

C B D E A
C D B A E
D C B E A
C D B E A

第 32 题

32.一棵二叉树中有 10 个度为 2 的结点、5 个度为 1 的结点，则叶子结点有（）个。 {{ select(32) }}

第 33 题

33.一棵完全二叉树共有 1000 个结点，则其中叶子结点的个数是（）。 {{ select(33) }}

第 34 题

34.一棵完全二叉树共有 2025 个结点，则它的高度（层数）是（）。 {{ select(34) }}

11
10
12
2025

第 35 题

35.一棵表达式树的结构为：根为 *，左子树的根为 +，其左右孩子分别为 3 和 5；右子树的根为 -，其左右孩子分别为 10 和 4。这棵表达式树所表示式子的值是（）。 {{ select(35) }}

第 36 题

36.一个无向图中每个顶点的度都是 3，且共有 12 条边，则该图的顶点数是（）。 {{ select(36) }}

第 37 题

37.用邻接矩阵存储一个有 100 个顶点、200 条边的无向图（不含自环），矩阵中非零元素的个数是（）。 {{ select(37) }}

200
400
10000
100

第 38 题

38.已知无向图有 1~7 号共 7 个顶点，边为 1-2、1-3、2-4、3-4、4-5、5-6、3-6、6-7。从顶点 1 出发进行深度优先遍历（相邻顶点按编号从小到大访问），得到的序列是（）。 {{ select(38) }}

1 2 4 3 6 5 7
1 2 4 5 6 3 7
1 3 6 7 5 4 2
1 2 3 4 5 6 7

第 39 题

39.对一个有 6 个顶点、5 条边的无向图，从 1 号顶点出发做深度优先遍历，只访问到 4 个顶点，则该图的连通分量至少有（）个。 {{ select(39) }}

第 40 题

40.用邻接矩阵存储含 n 个顶点的图，对其进行深度优先遍历的时间复杂度是（）。 {{ select(40) }}

O(n)
O(e)
O(n+e)
O(n²)

#Z0004. C++阶段测试（第 54 节 ~ 第 58 节）

C++阶段测试（第 54 节 ~ 第 58 节）