数据结构（二） - 题目详情 - tarjanoj

ID: 37

客观题

难度: 2

上传者:

对于有 $n$ 个顶点、 $m$ 条边的无向连通图（ $m>n$ ）,需要删掉（）条边才能使其成为一棵树。 {{ select(1) }}

$n-1$
$m-n$
$m-n-1$
$m-n+1$

如果一二叉树只有根节点，那么这棵二叉树高度为 $1$ ，请问高度为 $5$ 的完全二叉树有多少种不同的形态？（） {{ select(2) }}

$16$
$15$
$17$
$32$

以 $a$ 为起点，对右边的无向图进行深度优先遍历，则 $b、 c、 d、 e$ 四个点中有可能作为最后一个遍历到的点的个数为（）。

{{ select(3) }}

$1$
$2$
$3$
$4$

有 $10$ 个顶点的无向图至少应该有（）条边才能确保是一个连通图。 {{ select(4) }}

$9$
$10$ $
$11$
$12$

独根树的高度为 $1$ 。具有 $61$ 个结点的完全二叉树的高度为（）。

{{ select(5) }}

$7$
$8$
$5$
$6$

一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 $1$ ，若某结点的下标为 $i$ ，则其左孩子位于下标 $2i$ 处、右孩子位于下标( $2i+1$ )处），则图中所有结点的最大下标为（）。

{{ select(6) }}

$6$
$10$
$12$
$15$

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（）。 {{ select(7) }}

ABCDEFGHIJ
ABDEGHJCFI
ABDEGJHCFI
ABDEGHJFIC

根节点深度为 $0$ ，一棵深度为 $h$ 的满 $k(k>1)$ 叉树，即最后一层无任何子节点外，每一层上的所有节点都有 $k$ 个子节点的树，一共有（）个节点。 {{ select(8) }}

$\frac{k^{h-1}-1}{k-1}$
$k^{h-1}$
$k^h$
$\frac{k^{h-1}}{k-1}$

由四个没有区别的点构成的简单无向连通图的个数是（）。 {{ select(9) }}

$6$
$7$
$8$
$9$

设 G 是有 $n$ 个结点、 $m$ 条边（ $n\leq m$ ）的连通图，必须删去 G 的（）条边，才能使得 G 变成一棵树。 {{ select(10) }}

$m – n + 1$
$m - n$
$m + n + 1$
$n – m + 1$

设简单无向图 G 有 $16$ 条边且每个顶点的度数都是 $2$ ，则图 G 有()个顶点。 {{ select(11) }}

$10$
$12$
$8$
$16$

$6$ 个顶点的连通图的最小生成树，其边数为( )。 {{ select(12) }}

$6$
$5$
$7$
$4$

前序遍历序列与中序遍历序列相同的二叉树为( )。 {{ select(13) }}

根结点无左子树
根结点无右子树
只有根结点的二叉树或非叶子结点只有左子树的二叉树
只有根结点的二叉树或非叶子结点只有右子树的二叉树

一棵具有 $5$ 层的满二叉树中节点数为（） {{ select(14) }}

$31$
$32$
$33$
$16$

有向图中每个顶点的度等于该顶点的（） {{ select(15) }}

入度
出度
入度与出度之和
入度与出度之差

已知一棵二叉树有 $10$ 个节点，则其中至多有（）个节点有 $2$ 个子节点。 {{ select(16) }}

$4$
$5$
$6$
$7$

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 $4$ 个顶点、 $6$ 条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。

{{ select(17) }}

$1$
$2$
$3$
$4$

二叉树的（）第一个访问的节点是根节点。 {{ select(18) }}

先序遍历
中序遍历
后序遍历
以上都是

如果一棵二叉树的中序遍历是 $BAC$ ，那么它的先序遍历不可能是（）。 {{ select(19) }}

ABC
CBA
ACB
BAC