数据结构面试常见问题总结怎么写_前端数据结构与算法面试题

数据结构面试常见问题总结怎么写_前端数据结构与算法面试题数据结构面试常见问题总结写在前面本文记录了一些数据结构面试常见问题,本意用于考研复试,以下面试题为网上整理的问题以及自己加入的一些问题,答案仅供参考!Q:数据结构三要素A:逻辑结构、物理结构、数据运算Q:数组与链表有什么区别?A:数组静态分配内存,链表动态分配内存数组在内存中连续,链表不连续数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n)数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)Q:线性表的存储结构?A:顺序存储(内

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

数据结构面试常见问题总结

写在前面

本文记录了一些数据结构面试常见问题,本意用于考研复试,以下面试题为网上整理的问题以及自己加入的一些问题,答案仅供参考!


Q:数据结构三要素

A:逻辑结构、物理结构、数据运算

Q:数组与链表有什么区别?

A:

  • 数组静态分配内存,链表动态分配内存
  • 数组在内存中连续,链表不连续
  • 数组利用下标定位,时间复杂度为 O (1),链表定位元素时间复杂度 O (n)
  • 数组插入或删除元素的时间复杂度 O (n),链表的时间复杂度 O (1)

Q: 线性表的存储结构?

A:顺序存储(内存连续)、链式存储(内存不连续)

Q:头指针和头结点的区别?

A:

  • 头指针:是指向第一个节点存储位置的指针
  • 头结点:是放在第一个元素节点之前,便于在第一个元素节点之前进行插入和删除的操作

Q:栈和队列的区别

A:栈和队列都是操作受限的线性表

  • 栈:只能在栈尾入栈、出栈,是先进后出
  • 队列:队尾进,队首出,是先进先出

Q:度为 2 的树与二叉树有什么区别

A:

  1. 度为 2 的树至少有 3 个结点,而二叉树可以为空
  2. 二叉树有左右子树之分

Q:唯一确定一棵二叉树

A:中序 + 先序/后序/层序

Q:二叉排序树

A:若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;它的左、右子树也分别为二叉排序树。

Q: 最小生成树有几种方法?

A:

  • Prim(普里姆)算法:在图中取任意顶点 v 作为起始顶点,并加入集合 V;之后遍历与 V 中顶点相邻的边,选择权值最小且顶点未加入集合 V 的边,把其加入集合 V,直到集合 V 包含所有顶点结束
    时间复杂度:O (N2)
  • Kruskal(克鲁斯卡尔)算法:在含有 n 个顶点的图中始终选择权值最小且不会产生回路的边,一直进行此步骤直到选择 n-1 条边为止
    时间复杂度:O(e*loge),e 为边数

Q:图的存储方式有哪些?每一种方式优缺点

A:邻接矩阵、邻接表、十字链表、邻接多重表

  • 无向图:邻接矩阵、邻接表、邻接多重表

  • 有向图:邻接矩阵、邻接表、十字链表

    • 邻接矩阵:适合稠密图,确定边数总数花费时间代价大,边较少时造成空间浪费
    • 邻接表:适合稀疏图,节省空间,容易找出邻边,确定两个顶点间是否存在边花费时间代价大

Q:树的存储结构

A:双亲表示法、孩子表示法、孩子兄弟表示法

Q: 图的遍历和树的遍历有哪些

A:

  • 图的遍历:广度优先遍历(BFS)、深度优先遍历(DFS)
  • 树的遍历:先根遍历、后根遍历

Q: 图的遍历与树的遍历有什么区别?

A:图的遍历可能会出现循环遍历的情况,要设置标记数组。而树的遍历则不会出现这种情况。其次,图可能存在不连通的情况,而树不存在,所以图的遍历要对所有的顶点都循环一遍。

Q:解决哈希冲突的方法

A:

  1. 线性探测法
  2. 平方探测法
  3. 伪随机探测法
  4. 拉链法

Q:什么是稳定的算法?

A:不乱动已经排序好的数字,这样算法稳定一些

  • 稳定的排序算法:冒泡排序、插入排序、归并排序、基数排序
  • 不稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

Q:快排的操作流程

A:选取一个基准,一趟排序确定两个区间,一个区间全部比基准值小,另一个区间全部比基准值大,接着再选取一个基准值来进行排序,以此类推,最后得到一个有序的数列

Q:关键路径和关键活动

A:关键路径是项目中时间最长的活动顺序,决定着可能的项目最短工期,可能有 1 条或多条

Q:关键路径是用什么数据结构实现的

A:有向无环图

Q:排序算法的介绍

A:

  • 冒泡排序:从左到右依次比较相邻的两个元素,如果前一个元素比较大,就把前一个元素和后一个交换位置,重复地进行直到没有再需要交换
  • 选择排序:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕
  • 插入排序:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
  • 希尔排序:将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
  • 归并排序:在排序的过程中,把原来的数组变成左右两个数组,然后分别进行排序,当左右的子数组排序完毕之后,再合并这两个子数组形成一个新的排序数组
  • 快速排序:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序
  • 堆排序:把整个数组变成一个最大堆,然后每次从堆顶取出最大的元素,这样依次取出的最大元素就形成了一个排序的数组
  • 基数排序:按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位

排序算法

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193063.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • raid 5 raid 10_u盘损坏了还能恢复吗

    raid 5 raid 10_u盘损坏了还能恢复吗介绍:RAID0技术把多块物理硬盘设备(至少两块)通过硬件或软件的方式串联在一起,组成一个大的卷组,并将数据依次写入到各个物理硬盘中。这样一来,在最理想的状态下,硬盘设备的读写性能会提升数倍

  • STN:空间变换网络(Spatial Transformer Network)「建议收藏」

    STN:空间变换网络(Spatial Transformer Network)「建议收藏」空间变换网络(SpatialTransformerNetwork)空间变换网络(SpatialTransformerNetwork)空间变换器(SpatialTransformers)本文的惨开文献为:《SpatialTransformerNetworks》卷积神经网络定义了一个异常强大的模型类,但在计算和参数有效的方式下仍然受限于对输入数据的空间不…

    2022年10月19日
  • 《JavaScript 模式》读书笔记(8)— DOM和浏览器模式2

    四、长期运行脚本可能会注意到有时候浏览器会提示某个脚本已经运行了很长时间,是否应该停止该脚本。实际上无论要处理多么复杂的任务,都不希望应用程序发生上述事情。而且,如果该脚本的工作十分繁重,那么浏览器

  • go语言环境搭建_如何搭建语言培训平台

    go语言环境搭建_如何搭建语言培训平台因为项目的原因,要用到go语言,所以自学了一下。要想学习一门语言,首先必须搭建 语言的环境,go也一样,我这边是采用源码安装的。1. 下载安装包,如果觉得翻墙麻烦,可以直接在Golang中国社区下载安装包 http://www.golangtc.com/download2.假设我们在包解压到 /home/work/dev/package/go目录下, 

    2022年10月12日
  • 内核杂谈——关于platform device 创建

    内核杂谈——关于platform device 创建当拿到driver,不能用起来的时候需要去检查device了。虽说device和bus通常都是系统中带的,但也不要想当然的认为这个系统是帮你建好的。通常busdevicedriver三者中,bus基本不用干预,device干预的少,driver干预的多。从设备树中生成device从设备树中识别device的入口为arch_initcall_sync(of_platform_default_populate_init);staticint__initof_platform_defa

  • 学习算法 – 优先级队列二叉堆实现

    学习算法 – 优先级队列二叉堆实现

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号