二叉树基本操作实现 && 树和二叉树&& 二叉树进阶oj && 堆的基本概念 && 优先级队列的使用

第 1 题单选题

题目名称

3.在用树表示的目录结构中从根目录到任何数据文件有 通道

题目内容

A .唯一一条

B .二条

C .三条

D .不一定

第 2 题单选题

题目名称

4.在一颗度为3的树中度为3的结点有2个度为2的结点有1个度为1的结点有2个则叶子结点有 个

题目内容

A .4

B .5

C .6

D .7

第 3 题单选题

题目名称

5.一颗拥有1000个结点的树度为4则它的最小深度是

题目内容

A .5

B .6

C .7

D .8

第 4 题单选题

题目名称

6.下列关于二叉树的叙述错误的是   

题目内容

A .二叉树指的是深度为 2 的树

B .一个 n 个结点的二叉树将拥有 n-1 条边

C .一颗深度为 h 的满二叉树拥有 2^h-1 个结点根结点深度为1

D .二叉树有二叉链和三叉链两种表示方式

第 5 题单选题

题目名称

7.一颗完全二叉树有1001个结点其叶子结点的个数是

题目内容

A .251

B .500

C .501

D .不能确定

第 6 题单选题

题目名称

15.设某种二叉树有如下特点每个结点要么是叶子结点要么有2棵子树。假如一棵这样的二叉树中有mm>0个叶子结点那么该二叉树上的结点总数为

题目内容

A .2m+1

B .2(m-1)

C .2m-1

D .2m

第 7 题单选题

题目名称

16.设根结点的深度为1则一个拥有n个结点的二叉树的深度一定在   区间内

题目内容

A .[log(n + 1)n]

B .[lognn]

C .[log(n + 1)n - 1]

D .[log(n + 1)n + 1]

第 8 题单选题

题目名称

14.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反则该二叉树一定满足

题目内容

A .所有的结点均无左孩子

B .所有的结点均无右孩子

C .只有一个叶子结点

D .至多只有一个结点

第 9 题编程题

题目名称

判断一棵二叉树是否为平衡二叉树

题目内容

判断一棵二叉树是否为平衡二叉树

第 10 题编程题

题目名称

另一棵树的子树

题目内容

另一棵树的子树

第 11 题编程题

题目名称

对称二叉树

题目内容

对称二叉树

第 12 题编程题

题目名称

检查两棵树是否相同

题目内容

检查两棵树是否相同

第 13 题编程题

题目名称

反转二叉树

题目内容

反转二叉树

第 14 题编程题

题目名称

实现二叉树的基本操作

题目内容

public class BinaryTree {

    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }


    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {

    }

    // 前序遍历
    public void preOrder(TreeNode root) {
    }

    // 中序遍历
    void inOrder(TreeNode root) {
    }

    // 后序遍历
    void postOrder(TreeNode root) {
    }

    public static int nodeSize;

    /**
     * 获取树中节点的个数遍历思路
     */
    void size(TreeNode root) {
    }

    /**
     * 获取节点的个数子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
    }


    /*
     获取叶子节点的个数遍历思路
     */
    public static int leafSize = 0;

    void getLeafNodeCount1(TreeNode root) {
    }

    /*
     获取叶子节点的个数子问题
     */
    int getLeafNodeCount2(TreeNode root) {
    }

    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
    }

    /*
     获取二叉树的高度
     时间复杂度O(N)
     */
    int getHeight(TreeNode root) {
       
    }


    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        
        return null;
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        
    }


    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        return true;
    }
}

第 1 题单选题

题目名称

8.在一颗完全二叉树中某一个结点没有其左孩子则该结点一定

题目内容

A .是根结点

B .是叶结点

C .是分支结点

D .在倒数第二层

第 2 题单选题

题目名称

9.设一棵二叉树中有3个叶子结点有8个度为1的结点则该二叉树中总的结点数为 个

题目内容

A .11

B .12​

C .13

D .14

第 3 题单选题

题目名称

1.下列关于树的叙述正确的是

题目内容

A .树中可以有环

B .树的度是指所有结点中度最小的结点的度

C .树的深度指的是结点数最多的那一层的深度

D .树的根结点是所有结点的祖先结点

第 4 题单选题

题目名称

11.已知某二叉树的前序遍历序列为5 7 4 9 6 2 1中序遍历序列为4 7 5 6 9 1 2则其后序遍历序列为

题目内容

A .4 2 5 7 6 9 1

B .4 2 7 5 6 9 1

C .4 7 6 1 2 9 5

D .4 7 2 9 5 6 1

第 5 题单选题

题目名称

12.已知某二叉树的中序遍历序列为JGDHKBAELIMCF后序遍历序列为JGKHDBLMIEFCA则其前序遍历序列为

题目内容

A .ABDGHJKCEFILM

B .ABDGJHKCEILMF

C .ABDHKGJCEILMF

D .ABDGJHKCEIMLF

第 6 题单选题

题目名称

13.已知某二叉树的前序遍历序列为ABDEC中序遍历序列为BDEAC则该二叉树

题目内容

A .是满二叉树

B .是完全二叉树不是满二叉树

C .不是完全二叉树

D .是所有的结点都没有右子树的二叉树

第 7 题编程题

题目名称

两个节点的最近公共祖先

题目内容

两个节点的最近公共祖先

第 8 题编程题

题目名称

二叉树的层序遍历II

题目内容

二叉树的层序遍历||

第 9 题编程题

题目名称

二叉树的分层遍历

题目内容

二叉树的分层遍历

第 1 题编程题

题目名称

二叉树的后序非递归遍历

题目内容

二叉树的后序非递归遍历

第 2 题编程题

题目名称

二叉树中序非递归遍历

题目内容

二叉树中序非递归遍历

第 3 题编程题

题目名称

二叉树前序非递归遍历

题目内容

二叉树前序非递归遍历

第 4 题编程题

题目名称

中序后序还原二叉树

题目内容

中序后序还原二叉树

第 5 题编程题

题目名称

前序中序还原二叉树

题目内容

前序中序还原二叉树

第 6 题编程题

题目名称

根据二叉树创建字符串

题目内容

根据二叉树创建字符串

第 1 题单选题

题目名称

1.下列关于堆的叙述错误的是

题目内容

A .堆是一种完全二叉树

B .堆通常使用顺序表存储

C .小堆指的是左右孩子结点都比根结点小的堆

D .堆的删除是将尾部结点放到队顶后执行向下调整算法

第 2 题单选题

题目名称

2.下列关键字序列中序列 是堆。

题目内容

A .{167231239453}

B .{942331721653}

C .{165323943172}

D .{162353319472}

第 3 题单选题

题目名称

3.下列关于向下调整算法的说法正确的是

题目内容

A .构建堆的时候要对每个结点都执行一次

B .删除操作时要执行一次

C .插入操作时要执行一次

D .以上说法都不正确

第 4 题单选题

题目名称

4.在一个堆中根节点从0开始编号下标为 ii > 0 的结点的左右孩子结点及父结点的下标分别是   

题目内容

A .2 i、2 i + 1、i /2

B .2i、2i + 1、(i - 1)/2

C .2i + 1、2i + 2、(i - 1)/2

D .2i + 1、2i + 2、i/2-1

第 5 题单选题

题目名称

5.将一个顺序表利用向下调整的方式整理成堆的时间复杂度为   

题目内容

A .O(nlogn)

B .O(logn)

C .O(1)

D .O(n)

第 6 题编程题

题目名称

优先级队列(堆)的模拟实现

题目内容

public class PriorityQueue {
    public int[] elem;
    public int usedSize;

    public PriorityQueue() {
    }

    /**
     * 建堆的时间复杂度
     *
     * @param array
     */
    public void createHeap(int[] array) {
    }

    /**
     *
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度O(logn)
     */
    private void shiftDown(int root,int len) {
    }


    /**
     * 入队仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
    }

    private void shiftUp(int child) {
    }

    public boolean isFull() {
    }

    /**
     * 出队【删除】每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() {
    }

    public boolean isEmpty() {
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
    }
}

第 1 题编程题

题目名称

最小的k个数

题目内容

最小的k个数