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

数据结构面试常见问题总结怎么写_前端数据结构与算法面试题数据结构面试常见问题总结写在前面本文记录了一些数据结构面试常见问题,本意用于考研复试,以下面试题为网上整理的问题以及自己加入的一些问题,答案仅供参考!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)
blank

相关推荐

  • Java Calendar获取时间的月和日

    Java Calendar获取时间的月和日 Calendarcal=Calendar.getInstance(); //当前年 intyear=cal.get(Calendar.YEAR); //当前月 intmonth=(cal.get(Calendar.MONTH))+1; //当前月的第几天:即当前日 intday_of_month=cal.get(Calen

  • 用 managedQuery() 时须要注意的一个陷阱

    用 managedQuery() 时须要注意的一个陷阱

  • Android中setPositiveButton和setNegativeButton

    Android中setPositiveButton和setNegativeButtonsetPositiveButton表示设置弹框后的确定按钮,setNegativeButton表示设置弹框后的取消按钮。setPositiveButton是实现android.content.DialogInterface.OnClickListener接口后的方法普通的onclick()是view下的,完全是两个不同的实现。又在View类中也有OnClickListener()方法,而我们…

  • 解决TimeWait过多的问题

    解决TimeWait过多的问题原文链接:https://www.tiejiang.org/27040.html1、time_wait的作用:TIME_WAIT状态存在的理由:1)可靠地实现TCP全双工连接的终止在进行关闭连接四次挥手协议时,最后的ACK是由主动关闭端发出的,如果这个最终的ACK丢失,服务器将重发最终的FIN,因此客户端必须维护状态信息允许它重发最终的ACK。如果不维持这个状态信息,那么客户端将响应RST分节,服务器将此分节解释成一个错误(在java中会抛出connectionreset的SocketExc

  • jira使用教程_jira 工具

    jira使用教程_jira 工具JIRA使用教程:在Windows上安装JIRA JIRA使用教程:在Linux上安装JIRA JIRA使用教程:使用文件包安装JIRA JIRA使用教程:创建项目 JIRA使用教程:创建问题 JIRA使用教程:搜索问题 JIRA使用教程:编辑项目键 JIRA使用教程:简单问题跟踪 JIRA使用教程:创建软件开发项目 JIRA使用教程:共享搜索结果 JIRA使用教程:查看项目…

    2022年10月21日
  • 想要快速完成一个Python项目,离不开这些开源库

    想要快速完成一个Python项目,离不开这些开源库

    2021年10月28日

发表回复

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

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