面试-数据结构

  • 队列:一种线性表,只允许在表的前端进行删除操作,在表的后端进行插入操作
    —— 特点:先进后出
    —— 如何用数组实现:shift()实现出队列,push()实现入队列

  • 栈:一种线性表,只允许在表尾进行插入和删除操作。这一端称为栈顶,对应一端称为栈底
    —— 特点:后进先出
    —— 如何用数组实现:push()实现压栈,pop()实现出栈

  • 链表:一种非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针实现的。每个节点包括两个部分,存储数据的数据域和存储下一个节点地址的指针域。

    —— 分类:

    —— 单向链表:链表的连接方向是向后连接的
    —— 双向链表:链表节点中,除了存储下一个节点地址的指针,还有一个存放上一个节点地址的指针
    —— 循环链表:普通链表的最后一个节点的next存储为null,循环链表的最后一个节点的next指向头节点

    —— 特点:非连续、非顺序
    —— 如果使用构造函数实现一个链表节点:

    function Node(val) {
        this.value = val;
        this.next = null;
    }

    —— 如何将节点构成链表:

    let pHead = new Node(1);
    pHead.next = new Node(2);
  • 树:由n个有限节点组成一个具有层次结构的集合。每个节点有零个或多个子节点;没有父节点的节点称为根节点,每个非根节点只有一个父节点、

    —— 常见的树类型:

    —— 无序树:树的任意节点的子节点没有顺序关系
    —— 有序树:树的任意节点的子节点有顺序关系
    —— 二叉树(用的最多):树的任意至多包含两棵子树
    —— 满二叉树:叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点
    —— 二叉查找树(又称二叉搜索树):
        若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值; 任意节点的左、右子树也分别为二叉查找树; 
        没有键值相等的节点。

    —— 二叉树的遍历序列:

    —— 先序遍历:先访问根节点,再访问左节点,然后右节点
    —— 中序遍历:先访问左节点,再访问根节点,然后右节点
    —— 后续遍历:先访问左节点,再访问右节点,然后根节点

    —— 如何使用构造函数实现一个二叉树节点:

    function Node(val) {
        this.value = val;
        this.left = null;
        this.right = null;
    }

    —— 如何将节点构成二叉树:

    let root = new Node(1);
    let left = new Node(2);
    let right = new Node(3);
    root.left = left;
    root.right = right;

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达,可以邮件至 610193653@qq.com,谢谢啦!

文章标题:面试-数据结构

本文作者:zzzwyyy

发布时间:2019-11-28, 22:26:39

最后更新:2019-11-28, 22:27:26

原始链接:http://yoursite.com/2019/11/28/面试-数据结构/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录