当前位置: 首页 > news >正文

计算机基础面试(数据结构)

1. 数组和链表的区别是什么?各自的优缺点是什么?
  • 专业解答
    数组内存连续,支持随机访问,但插入删除效率低;链表内存离散,插入删除高效,但访问需遍历。

  • 初中生版
    数组像排座位,按编号找人快,但中间加人麻烦;链表像自由组队,拉人容易,但找人得挨个问。


2. 什么是哈希表?如何解决哈希冲突?
  • 专业解答
    哈希表通过键值映射实现快速存取。冲突解决方法:开放寻址法(找下一个空位)、链地址法(拉链表)。

  • 初中生版
    哈希表像快递柜:用手机号(键)算出柜子号(哈希值)。冲突时,要么找下一个空柜(开放寻址),要么同一柜子放多个包裹(链表)。


3. 二叉搜索树(BST)的性质是什么?如何实现插入和删除?
  • 专业解答
    BST左子树值 < 根 < 右子树值。插入从根开始比较;删除需分三种情况(叶子节点、单子、双子)。

  • 初中生版
    BST像猜数字:每次猜中间数,根据大小缩小范围。插入像按规则排队,删除像抽走中间人时找替补。


4. 什么是红黑树?与AVL树的区别是什么?
  • 专业解答
    红黑树是近似平衡的二叉搜索树,通过旋转和变色保持平衡,查询稍慢但插入删除更高效。AVL树严格平衡,查询快但维护成本高。

  • 初中生版
    红黑树像灵活的交通信号灯,允许轻微不平衡但调整快;AVL树像严格交警,必须完全平衡但调整麻烦。


5. 什么是堆?如何用堆实现优先队列?
  • 专业解答
    堆是完全二叉树,最大堆根节点最大,最小堆反之。优先队列通过堆的插入和提取根节点实现。

  • 初中生版
    堆像金字塔:最大堆的顶层是最大的西瓜。优先队列像急诊室,最紧急的病人(堆顶)先被处理。


6. 快速排序和归并排序的时间复杂度及稳定性分析。
  • 专业解答
    快排平均O(n log n),最坏O(n²),不稳定;归并稳定O(n log n),但需额外空间。

  • 初中生版
    快排像分班比赛:每次选班长分两队,可能选错人导致效率低;归并像合并小组,先拆到单人再两两合并,稳定但占地方。


7. 什么是动态规划?举一个典型问题(如背包问题)并说明解决思路。
  • 专业解答
    动态规划通过状态转移方程分解子问题,存储中间结果避免重复计算。背包问题:选物品使总价值最大且不超重。

  • 初中生版
    动态规划像存钱罐:每天存一点,最后算总数。背包问题像装行李,选最值钱又不超重的组合。


8. 什么是贪心算法?与动态规划的区别是什么?
  • 专业解答
    贪心每一步选局部最优,不回溯;动态规划保存所有子问题解,可能回溯。

  • 初中生版
    贪心像吃自助餐:每次拿最贵的菜;动态规划像存零花钱:每天留一点,最后买大件。


9. 广度优先搜索(BFS)和深度优先搜索(DFS)的实现方式及应用场景。
  • 专业解答
    BFS用队列,逐层遍历;DFS用栈或递归,优先深入。BFS找最短路径,DFS拓扑排序。

  • 初中生版
    BFS像水面涟漪:一圈圈扩散找最近目标;DFS像探险:一条路走到头再回头。


10. 什么是拓扑排序?如何检测有向图中的环?
  • 专业解答
    拓扑排序对DAG节点线性排序,入度为0的节点优先。环导致无法排序。

  • 初中生版
    拓扑排序像穿衣服顺序:先穿内衣再外套。如果发现“外套要穿在内衣里面”,说明有环。


11. 什么是Dijkstra算法?如何解决负权边问题?
  • 专业解答
    Dijkstra用贪心策略找单源最短路径,无法处理负权边。负权边需用Bellman-Ford或SPFA。

  • 初中生版
    Dijkstra像导航:每次都选最近的路,但遇到“倒贴钱”的路(负权)会失效,需换工具。


12. 什么是KMP算法?部分匹配表(Prefix Table)的作用是什么?
  • 专业解答
    KMP通过前缀表跳过重复匹配,时间复杂度O(n+m)。前缀表记录最长公共前后缀长度。

  • 初中生版
    KMP像聪明的找字:如果匹配失败,根据“记忆”跳过已知位置,不用从头开始。


13. 什么是并查集(Union-Find)?如何优化路径压缩?
  • 专业解答
    并查集维护集合,支持合并与查询。路径压缩将树高度降为1,提升查询效率。

  • 初中生版
    并查集像家族族谱:查两人是否同家族,路径压缩让所有人直接认族长为父。


14. 什么是LRU缓存淘汰算法?如何用双向链表+哈希表实现?
  • 专业解答
    LRU淘汰最久未使用的数据。哈希表存键值对,双向链表维护访问顺序,头尾操作O(1)。

  • 初中生版
    LRU像冰箱:最近吃的放门口,很久没吃的放里面。双向链表记录顺序,哈希表快速定位。


15. 什么是布隆过滤器?优缺点及适用场景是什么?
  • 专业解答
    布隆过滤器用位数组和多个哈希函数判断元素是否存在,空间效率高但有误判率。适用于缓存穿透场景。

  • 初中生版
    布隆过滤器像班级点名册:可能误判“某人没来”(实际来了),但绝对不误判“来了的人没来”。


16. 什么是Trie树?如何实现前缀匹配?
  • 专业解答
    Trie树(字典树)用树结构存储字符串,共享公共前缀。前缀匹配沿树路径遍历。

  • 初中生版
    Trie树像查字典:先找首字母,再逐步缩小范围,适合自动补全。


17. 什么是跳表(Skip List)?与平衡树的比较?
  • 专业解答
    跳表通过多级索引加速查找,平均O(log n)。与平衡树相比,实现简单,支持高并发。

  • 初中生版
    跳表像地铁线路图:多层站台快速跳转,比逐站找快很多。


18. 什么是回溯算法?举一个例子(如八皇后问题)说明实现思路。
  • 专业解答
    回溯通过递归尝试所有可能,剪枝无效路径。八皇后问题:逐行放置皇后,冲突则回退。

  • 初中生版
    回溯像走迷宫:走到死胡同就回头,换条路试试。


19. 什么是Manacher算法?如何实现线性时间的最长回文子串查找?
  • 专业解答
    Manacher算法预处理字符串,利用对称性减少重复计算,时间复杂度O(n)。

  • 初中生版
    Manacher像聪明的镜子:找最长对称子串时,利用已知对称信息避免重复检查。


20. 什么是最大子数组和问题?如何用分治法解决?
  • 专业解答
    分治法将数组分为左右两半,递归求解左、右、跨中间的最大子数组和。

  • 初中生版
    最大子数组和像找最赚钱的连续几天:分成左半、右半、中间跨界的三种情况,取最大值。


21. 什么是编辑距离?动态规划的实现步骤是什么?
  • 专业解答
    编辑距离通过动态规划计算两字符串最少操作次数(增删改)。状态转移方程分三种操作。

  • 初中生版
    编辑距离像改错字:每次改一个字母,记录最少步骤。动态规划像填表格,一步步推导。


22. 什么是位运算?如何用位运算实现加法?
  • 专业解答
    位运算直接操作二进制位。加法可通过异或(无进位和)和与运算(进位)循环实现。

  • 初中生版
    位运算像手动算加法:异或是个位相加,进位是十位进位,循环直到无进位。


23. 什么是蒙特卡洛方法?在算法中的应用场景是什么?
  • 专业解答
    蒙特卡洛通过随机采样近似求解,适用于高维积分、概率模拟等复杂问题。

  • 初中生版
    蒙特卡洛像掷骰子估算面积:随机撒点,统计落在目标区域的比例。


24. 什么是NP完全问题?举例说明(如旅行商问题)。
  • 专业解答
    NP完全问题无法在多项式时间内求解,但解可快速验证。旅行商问题:找最短路径遍历所有城市。

  • 初中生版
    NP完全问题像超级难题:找不到快方法,但猜到答案后能很快验证是否正确。


25. 什么是滑动窗口算法?如何解决子数组最大和问题?
  • 专业解答
    滑动窗口维护窗口左右边界,动态调整区间。子数组最大和问题:窗口扩展,和小于0时重置左边界。

  • 初中生版
    滑动窗口像望远镜:调整视野范围,找到最亮的星星(最大和)。


26. 什么是前缀和数组?如何优化区间查询?
  • 专业解答
    前缀和数组存储前i项和,区间和可通过前缀和相减O(1)计算。

  • 初中生版
    前缀和像记账本:记录每天累计花费,查某段时间的总花费直接相减。


27. 什么是线段树?如何实现区间查询和更新?
  • 专业解答
    线段树每个节点代表区间,支持区间查询(如求和)和更新,时间复杂度O(log n)。

  • 初中生版
    线段树像分治工具:把大问题拆成小问题,每个小问题存结果,查询和更新都很快。


28. 什么是树状数组(Fenwick Tree)?与线段树的区别是什么?
  • 专业解答
    树状数组通过二进制分解实现区间查询和单点更新,代码更简洁但功能较线段树少。

  • 初中生版
    树状数组像分层统计:每层存部分数据,查改时合并多层结果。比线段树更轻量。


29. 什么是A*算法?启发函数的作用是什么?
  • 专业解答
    A*结合Dijkstra和贪心,启发函数h(n)估计剩余代价,优先扩展总代价f(n)=g(n)+h(n)最小的节点。

  • 初中生版
    A*像聪明的导航:不仅看已走路程(g(n)),还猜剩余距离(h(n)),选最优路线。


30. 什么是遗传算法?基本原理及适用场景?
  • 专业解答
    遗传算法模拟自然选择,通过选择、交叉、变异迭代优化,适用于复杂优化问题。

  • 初中生版
    遗传算法像养宠物:选表现好的个体(选择),繁殖后代(交叉),偶尔变异,一代代优化。

相关文章:

计算机基础面试(数据结构)

1. 数组和链表的区别是什么&#xff1f;各自的优缺点是什么&#xff1f; 专业解答&#xff1a; 数组内存连续&#xff0c;支持随机访问&#xff0c;但插入删除效率低&#xff1b;链表内存离散&#xff0c;插入删除高效&#xff0c;但访问需遍历。 初中生版&#xff1a; 数组像…...

DBGPT安装部署使用

简介 DB-GPT是一个开源的AI原生数据应用开发框架(AI Native Data App Development framework with AWEL(Agentic Workflow Expression Language) and Agents)。 目的是构建大模型领域的基础设施&#xff0c;通过开发多模型管理(SMMF)、Text2SQL效果优化、RAG框架以及优化、Mul…...

【蓝桥杯单片机】第十二届省赛

一、真题 二、模块构建 1.编写初始化函数(init.c) void Cls_Peripheral(void); 关闭led led对应的锁存器由Y4C控制关闭蜂鸣器和继电器 由Y5C控制 2.编写LED函数&#xff08;led.c&#xff09; void Led_Disp(unsigned char ucLed); 将ucLed取反的值赋给P0 开启锁存器…...

开源嵌入式实时操作系统NuttX介绍

一、NuttX RTOS的发展历程&#xff1a;从个人项目到Apache顶级开源项目 NuttX 是一款轻量级、可扩展的实时操作系统&#xff08;RTOS&#xff09;&#xff0c;其发展历程堪称开源社区的经典案例。 起源与初创&#xff08;2003-2007&#xff09; NuttX 由 Gregory Nutt 于2003…...

阿里云服务器部署项目笔记 实操 centos7.9

阿里云服务器部署项目笔记 实操 centos7.9 springboot vue elementUImysqlredis 相关的redis,mysql,nginx镜像,jdk 通过网盘分享的文件&#xff1a;docker镜像 链接: https://pan.baidu.com/s/15VwcWBP4Jy07xADuvylgQw?pwdm2g9 提取码: m2g9 配置环境 连接云服务器 安装…...

Java-实现PDF合同模板填写内容并导出PDF文件

可用于公司用户合同导出pdf文件 效果图 一、导入所需要jar包 <!--生成PDF--><dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.11</version></dependency><dependency&…...

Docker安装Grafana数据可视化平台

介绍 Grafana是一个开源的监控和数据可视化平台&#xff0c;主要用于展示和分析时间序列数据。提供功能强大且灵活的数据可视化和监控工具&#xff0c;适用于多种场景&#xff0c;它广泛应用于DevOps、IT运维、物联网&#xff08;IoT&#xff09;和业务分析等领域。 Grafana的主…...

MyBatis-Plus 自动填充功能

MyBatis-Plus&#xff08;MP&#xff09; 提供了一个非常强大的功能——自动填充功能。该功能可以在执行插入或更新操作时&#xff0c;自动为某些字段赋值&#xff0c;免去手动设置这些字段的麻烦。常见的应用场景包括 创建时间 和 更新时间 字段的自动填充&#xff0c;帮助开发…...

解决redis lettuce连接池经常出现连接拒绝(Connection refused)问题

一.软件环境 windows10、11系统、springboot2.x、redis 6 7 linux&#xff08;centos&#xff09;系统没有出现这问题&#xff0c;如果你是linux系统碰到的&#xff0c;本文也有一定大参考价值。 根本思路就是&#xff1a;tcp/ip连接的保活(keepalive)。 二.问题描述 在spr…...

武汉大学生命科学学院与谱度众合(武汉)生命科技有限公司举行校企联培座谈会

2025年2月21日下午&#xff0c;武汉大学生命科学学院与谱度众合&#xff08;武汉&#xff09;生命科技有限公司&#xff08;以下简称“谱度众合”&#xff09;在学院学术厅举行校企联培专业学位研究生合作交流会。武汉大学生命科学学院副院长刘星教授、生命科学学院周宇教授、产…...

4.网络技术与应用

一、计算机网络基础 1. 网络基本原理 通信模型&#xff1a; OSI七层模型&#xff1a; 物理层&#xff08;传输比特流&#xff0c;如网线、光纤&#xff09;数据链路层&#xff08;MAC地址&#xff0c;交换机&#xff09;网络层&#xff08;IP地址&#xff0c;路由器&#xff0…...

Kafka 主题 retention.ms 配置修改及深度问题排查指南

文章目录 Kafka 主题 retention.ms 配置修改及深度问题排查指南版本背景查看 Kafka 主题当前状态修改 retention.ms 配置的正确方式为什么不能使用 kafka-topics.sh&#xff1f;使用 kafka-configs.sh 动态更新配置 深入解析 retention 配置retention.ms 与 retention.bytes 的…...

React实现无缝滚动轮播图

实现效果&#xff1a; 由于是演示代码&#xff0c;我是直接写在了App.tsx里面在 文件位置如下&#xff1a; App.tsx代码如下&#xff1a; import { useState, useEffect, useCallback, useRef } from "react"; import { ImageContainer } from "./view/ImageC…...

deepseek+mermaid【自动生成流程图】

成果&#xff1a; 第一步打开deepseek官网(或百度版&#xff08;更快一点&#xff09;)&#xff1a; 百度AI搜索 - 办公学习一站解决 第二步&#xff0c;生成对应的Mermaid流程图&#xff1a; 丢给deepseek代码&#xff0c;或题目要求 生成mermaid代码 第三步将代码复制到me…...

分布式锁的简单实现

1. 什么是分布式锁&#xff1f; 在分布式系统中&#xff0c;也会涉及到多个节点访问同一个公共资源的情况&#xff0c;和 Java 中多线程的锁不一样&#xff0c;由于分布式系统中涉及到多个进程多个主机&#xff0c;所以说 Java 中 synchronized 就不合适了。 2. 分布式锁的简…...

C语言(19)----------->函数(2)

本文介绍了C语言的return语句及其它在C语言函数中的作用&#xff0c;以及介绍了二维数组和一维数组传参时的一些注意事项和使用数组传参时的方法。 若没有学习过C语言的一维数组和二维数组&#xff0c;建议参考如下文章&#xff1a; C语言&#xff08;15&#xff09;--------…...

动态扩缩容引发的JVM堆内存震荡:从原理到实践的GC调优指南

目录 一、典型案例&#xff1a;系统发布后的GC雪崩事件 &#xff08;一&#xff09;故障现象 1. 刚刚启动时 GC 次数较多 2. 堆内存锯齿状波动 3. GC日志特征&#xff1a;Allocation Failure &#xff08;二&#xff09;问题定位 二、原理深度解析&#xff1a;JVM内存弹…...

为何在用户注销时使用 location.href 而非 Vue Router 的 router.push

在开发 Web 应用时&#xff0c;用户注销功能的设计看似简单&#xff0c;但背后隐藏着对状态管理、安全性和用户体验的深层考量。以下将详细探讨为何许多项目在注销跳转时选择 location.href&#xff08;强制刷新页面&#xff09;而非 Vue Router 的 router.push&#xff08;单页…...

开源工具推荐:Uptime Kuma监控

1. 概述 Github&#xff1a;louislam/uptime-kuma: A fancy self-hosted monitoring tool Uptime Kuma is an easy-to-use self-hosted monitoring tool. Uptime Kuma 是一款开源的监控工具&#xff0c;可以帮助你实时监测网站或服务的状态&#xff0c;并在发生故障时及时通…...

《基于Selenium的论坛系统自动化测试实战报告》

一、项目背景与技术选型 项目简介 目标系统&#xff1a;论坛系统 核心功能&#xff1a;用户注册/登录、会话框发送信息、好友列表、信息发送 技术栈&#xff1a;html Springboot MySQL数据库 为什么选择Selenium 支持多浏览器兼容性测试&#xff08;Chrome/Firefox/Edge&…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...