204. 对数据结构了解吗?说说你常用的数据结构。
了解,数据结构是每个程序员都要会一点的。链表、列表、散列表最常用,队列和栈也经常使用。二叉树偶尔使用。
205. 什么是状态机,什么是行为树
有限状态机系统:是指在不同阶段会呈现出不同的运行状态的系统,这些状态是有限的、不重叠的。这样的系统在某一时刻一定会处于其所有状态中的一个状态,此时它接收一部分允许的输入,产生一部分可能的响应,并且迁移到一部分可能的状态。
- 基本节点是状态:他包含了一系列运行在该状态的行为以及离开这个状态的条件。
- 状态可以任意跳转,实现简单,但是对于大的状态机很难维护.状态逻辑的重用性低.
- 每一个状态的逻辑会随着一些新状态的增加而越来越复杂。维持状态的数量和状态逻辑复杂性是一个很大的难点。需要合理的分割以及重用状态。
- 状态机状态的复用性很差,一旦一些因素变化导致这个环境发生变化。你只能新增一个状态,并且给这个新状态添加连接他以及其他状态的跳转逻辑。
- 状态机的跳转条件一旦不满足,就会一直卡在某一个状态。
行为树:一个流行的 AI 技术,涵盖了层次状态机,事件调度,事件计划,行为等一系列技术。
- 高度模块化状态,去掉状态中的跳转逻辑,使得状态变成一个“行为”。
- “行为”和”行为”之间的跳转是通过父节点的类型来决定的。比如并行处理两个行为,在状态机里面无法同时处理两个状态。
- 通过增加控制节点的类型,可以达到复用行为的目的。
- 可视化编辑。
206. 对 List 的理解
有序的对象列表,属于数据结构的一种:顺序结构
泛型集合类,引入 System.Collections.Generic 命名空间,
常用操作有,Count 属性查看长度,Add()添加,Remove()去除,AddRange()添加集合,Clear()清空集合。
207. 数组和 List 的核心区别
数组在 C#中最早出现的。在内存中是连续存储的,所以它的索引速度非常快,而且赋值与修改元素也很简单。
数组存在一些不足的地方。在数组的两个数据间插入数据是很麻烦的,而且在声明数组的时候必须指定数组的长度,数组的长度过长,会造成内存浪费,过段会造成数据溢出的错误。如果在声明数组时我们不清楚数组的长度,就会变得很麻烦。
List是集合,集合元素的数量可以动态变化。增加、插入、删除元素很方便。
208. 数据结构的看法
具有一定关系的数据元素集合,好的数据结构有利于简化算法的编写
209. 深度优化会么
会一点,比如在代码消耗上经常使用 StopWatch 类去优化算法,通常用 IDisposable 去显式的释放资源。
210. 实现二分要什么条件
有序结构
211. c++,socket 网络编程会不会
C++上学的时候学过,工作之后一直没用过。
Socket 就是一套实现双向通信的 API。使用过 C#的 TCP(面向连接、可靠)和 UDP 连接(面向非连接、不可靠)
212. 二叉树的所有遍历方式的原理及优缺点
前序遍历,先访问根节点在访问左节点在访问右节点。
中序遍历,先访问左节点在访问根节点在访问右节点。
后序遍历,先访问左节点在访问右节点在访问根节点。
前中后代表的是访问根节点的时序。
这一点上没有什么本质上的优缺点,要看实际需求决定采用何种遍历方式
采用递归方式和非递归方式。前者优点是直观,编写起来简单,缺点是但其开销也比较大。非递归形式开销小,但编写复杂。
213. 数据结构中数组和链表各有什么特点,什么场合下应该使用数组,什么 场合下应该使用链表
二者都属于一种数据结构
从逻辑结构来看
- 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费;数组可以根据下标直接存取。
- 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项,非常繁琐)链表必须根据 next 指针找到下一个元素从内存存储来看1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
- 链表从堆中分配空间, 自由度大但是申请管理比较麻烦。从上面的比较可以看出,如果需要快速访问数据,很少或不插入和删除元素,就应该用数组;相反,如果需要经常插入和删除元素就需要用链表数据结构了。