面试常见问题[数据结构]

可以说除了大体的设计,上课学的数据结构忘光光了。发现现在面试都是这种问题,我就自己复习一遍把

线性表

数组

没啥好说的

链表

开空间的话可以有两种方法

1
2
int *p; p = new int[10];
int *p; p = (int *)malloc(sizeof(int)*10);

几种内存分配的函数
<1>alloca是向栈申请内存,因此无需释放.
<2>malloc分配的内存是位于堆中的,并且没有初始化内存的内容,因此基本上malloc之后,调用函数memset来初始化这部分的内存空间.
<3>calloc则将初始化这部分的内存,设置为0.
<4>realloc则对malloc申请的内存进行大小的调整.

堆,栈,静态存储区的 区别
对于堆区、栈区和静态存储区它们之间最大的不同在于,栈的生命周期很短暂。但是堆区和静态存储区的生命周期相当于与程序的生命同时存在(如果您不在程序运行中间将堆内存delete的话),我们将这种变量或数据成为全局变量或数据。但是,对于堆区的内存空间使用更加灵活,因为它允许你在不需要它的时候,随时将它释放掉,而静态存储区将一直存在于程序的整个生命周期中。

单链表

只能向一个方向走呗

双向链表

两个方向呗

循环链表

没啥好说的

栈与队列

stack

满足后进先出

queue

满足先进先出

只有父节点的东西

二叉树

每个节点最多只有两个子节点

三种遍历方式

  • 先序遍历 中左右
  • 中序遍历 左中右
  • 后序遍历 左右中

平衡二叉树

就是对节点加入了左右旋的操作,目的在于控制深度

这个就是满足
ai>=a2ia_i >= a_{2*i}ai>=a2i+1a_i >= a_{2*i}+1
的一种数据结构,可以用线性表来实现,保证这个就行,然后就是满足了O(1)查找,O(log(n))更新。

红黑树

这个还是我第一次看到这个

  • (1)每个节点或者是黑色,或者是红色。
  • (2)根节点是黑色。
  • (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
  • (4)如果一个节点是红色的,则它的子节点必须是黑色的。
  • (5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

左旋

这里的左旋很简单,就是把现在节点的右节点变成现节点,把原来右节点的左儿子变成原来的右节点。

右旋

差不多把,左儿子变爸爸,左儿子的右孙子变成爸爸的左儿子

添加

这个还是挺麻烦的。要考虑很多情况,主要思想就是

  • 按二叉树的方式,插进去。
  • 节点变红
  • 开始调整。关键思想就是将红色的节点移到根节点;然后,将根节点设为黑色

删除

这个怎么说呢,感觉上就是分情况讨论为主。

b树

这个就是平衡多路查找树

B 树是为了磁盘或其它存储设备而设计的一种多叉平衡二叉树,他好在啥,好像是在硬盘i/o方面有一定的好处。

性质

  • 根节点至少有两个子节点
  • 每个节点有M-1个key,并且以升序排列
  • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
  • 其它节点至少有M/2个子节点

插入删除

这个就比那些奇奇怪怪的东西好多了,他的关键思想就是,找到位置,插进去。塞不下了,就飞到父亲节点那去,父亲节点满了就分裂嘛。删除的思想就是找到中序遍历的比根节点第一个大的点,替上去,下面再进行修改。

b+树

相对那个b树来说多了几个性质

  • 有k个子节点的节点有k个关键码
  • 非叶子节点只有索引的功能
  • 树的所有叶节点构成一个有序链表,可以按照关键码排序的次序遍历。

插入删除方面

相对b树来说主要的问题就是,b树有个节点上浮的过程,但是b+不是,只是把那个复制一个上去。

应用

文件存储系统以及数据库系统
局部性原理,程序运行期间所需要的数据很集中。