网站制作需求,东莞微信小程序开发公司报价,网站发的文章怎么做的,网络营销的核心是什么前言
编程想要学的好#xff0c;刷题少不了#xff0c;我们不仅要多刷题#xff0c;还要刷好题#xff01;为此我开启了一个弯道超车必做好题锦集的系列#xff0c;此为树和二叉树的选择题精选集锦。该系列会不定期更新#xff0c;敬请期待#xff01; 1.已知某二叉树的…前言
编程想要学的好刷题少不了我们不仅要多刷题还要刷好题为此我开启了一个弯道超车必做好题锦集的系列此为树和二叉树的选择题精选集锦。该系列会不定期更新敬请期待 1.已知某二叉树的中序遍历序列为JGDHKBAELIMCF后序遍历序列为JGKHDBLMIEFCA则其前序遍历序列为
A.ABDGHJKCEFILM
B.ABDGJHKCEILMF
C.ABDHKGJCEILMF
D.ABDGJHKCEIMLF
答案B
解析 由后序遍历确定子树的根后序遍历从后向前看最后一个元素为根和前序遍历刚好相反从后向前看后序遍历应该是根右左根据中序遍历确定子树的左右区间 故根为: A A的左子树JGDHKB A的右子树ELIMCF A的左子树的根B A的右子树的根C B的左子树JGDHK B的右子树空 C的左子树ELIM C的右子树F B的左子树的根D C的左子树根E D的左子树的根G D的右子树的根H E的右子树的根:I 故树的结构为 2.设根结点的深度为1则一个拥有n个结点的二叉树的深度一定在 区间内
A.[log(n 1)n]
B.[lognn]
C.[log(n 1)n - 1]
D.[log(n 1)n 1] 答案A
解析 最大深度 即每次只有一个节点次数二叉树的高度为n为最高的高度 最小深度 此树为完全二叉树 如果是完全二叉树 根据二叉树性质完全二叉树的高低为 h log(n1)向上取整 故选择A 3.二叉树的( )遍历相当于广度优先遍历( )遍历相当于深度优先遍历
A.前序 中序
B.中序 前序
C.层序 后序
D.层序 前序
答案D
解析 广度优先需要把下一步所有可能的位置全部遍历完才会进行更深层次的遍历层序遍历就是一种广度优先遍历。 深度优先是先遍历完一条完整的路径从根到叶子的完整路径才会向上层折返再去遍历下一个路径前序遍历就是一种深度优先遍历。 4.如果一颗二叉树的前序遍历的结果是ABCD则满足条件的不同的二叉树有 种
A.13
B.14
C.15
D.16 答案B 解析 首先这棵二叉树的高度一定在3~4层之间: 三层 四层 如果为四层就是单边树每一层只有一个节点除过根节点其他节点都有两种选择在上层节点的左边还是右边所以2*2*2共8种 总共为14种。 4.n个节点的完全二叉树最多可以有多少层
A.n/2
B.log(n)1(向下取整)
C.n-1
D.n
解析 根据二叉树性质4对于完全二叉树节点个数为n时高度h为 h log(n1)向上取整 或者 即3.x 取4 h log(n)1向下取整 即3.x 取 3 故应该选择B 5.设一棵二叉树中有3个叶子结点有8个度为1的结点则该二叉树中总的结点数为 个
A.11
B.12
C.13
D.14
答案C
解析 设Ni表示度为i的节点个数则节点总数 N N0 N1 N2 节点个数于节点边的关系 N个节点的树有N-1个边 边与度的关系N - 1 N1 2 * N2 故N0 N1 N2 - 1 N1 2 * N2 因此得N0 N2 1 回到原题N0 3N1 8可得N2 2。 因此答案是 3 8 2 13。 6.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反则该二叉树一定满足
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.至多只有一个结点
答案C
解析 前序遍历根 左 右 后序遍历左 右 根 从二叉树 前序 和 后序遍历结果规则中可以看出如果树中每个节点只有一个孩子时遍历结果肯定是反的 比如下面这前序和中序序列所构成的树的结构: 12345 54321 故每个节点只有一个孩子即只有一个叶子节点 7.在一颗度为3的树中度为3的结点有2个度为2的结点有1个度为1的结点有2个则叶子结点有 个
A.4 B.5 C.6 D.7
答案C
解析 设度为i的节点个数为ni, 该树总共有n个节点,则nn0n1n2n3. 有n个节点的树的总边数为n-1条. 根据度的定义,总边数与度之间的关系为n-10*n01*n12*n23*n3. 联立两个方程求解,可以得到n0 n2 2n3 1, n06 8.一颗拥有1000个结点的树度为4则它的最小深度是
A.5 B.6 C.7 D.8
答案B
解析 如果这棵树每一层都是满的则它的深度最小假设它为一个四叉树高度为h则这个数的节点个数为(4^h - 1) / 3当h 5, 最大节点数为341 当h 6, 最大节点数为1365所以最小深度应该为6。 9.一颗完全二叉树有1001个结点其叶子结点的个数是
A.251 B.500 C.501 D.不能确定
答案C
解析 该题需要用到二叉树性质在任意二叉树中度为0的节点都比度为2的节点多1个即 n0 n2 1 另外在完全二叉树中如果节点总个数为奇数则没有度为1的节点如果节点总个数为偶数只有一个度为1的节点 因此n0 n1 n2 1001 节点总数为奇数没有度为1的节点 n0 0 n2 2*n0-1 1001 n0 501 以上为我个人的小分享如有问题欢迎讨论
都看到这了不如关注一下给个免费的赞
