引言
话说,其他的大牛都写了年终总结什么的,我现在还没有写、这个公司也没有让我写述职报告,以前的公司过年的时候还让写写这个,现在貌似也不用写了,那么就写一篇面试题。
正文
说明:全部是以C/C++为基础举例的,如果有什么不正确的地方,欢迎大家指正,非常感谢,我的邮箱zy@zybug.com
1、堆栈(操作系统意义上的)
记得很久以前,又一次面试的时候我把这两个说反了,嗨、、、学艺不精啊。
栈 主要是指由操作系统自动管理的内存空间,栈总是以后进先出(LIFO)的方式工作,通常在栈上分配的空间不需要用户操心。
举例:当进入一个函数,操作系统会为该函数中的局部变量分配存储空间,系统会分配一个内存块,叠加在当前的栈上,并且利用指针指向前一个内存块的地址,函数的局部变量就存储在当前的内存块上,当该函数返回时,系统“弹出”内存块,并且根据指针回到前一个内存块。
堆 是用来存储动态分配变量的空间
说明:程序员可以随时分配或者回收内存,这意味着程序员需要用命令回收内存,否则会产生内存泄漏(memory leak),在Java、 OC(ARC)等中,语言本身引入垃圾回收和技术规则帮助用户决定在什么时候自动释放内存。
2、数组(Array)
数组 是常见的数据结构之一,用于存储一系列相同类型的数据。
所谓的“开辟一个数组”相当于系统为你提供了一段连续的内存区间用于存储数据。数组名就是一个指针,指向这段内存的起始地址。在C/C++中,标准的数组可以通过在栈(Stack)上分配空间,或者通过先声明指针,然后用new 关键字(或者C 中的malloc函数),在堆(Heap)上动态地分配空间。
3、哈希表(Hash Table)
哈希表 几乎是最为重要的数据结构,主要用于“键(key)”的查找,存储的基本元素是键-值对(key-value pair)。
逻辑上,数组可以作为哈希表的一个特例:键是一个非负整数。通常哈希表会假设键是数据的唯一标识,相同的键默认表示同一个基本存储元素。
4、链表(Linked List)
链表 是一种常见的线性数据结构。 链表的优势在于能够以较高的效率在任意位置插入或删除一个结点。
单向链表(Singly Linked List), 每个结点有一个next指针指向后一个结点;还有一个成员 变量用于存储数值;
双向链表(Doubly Linked List), 还有一个prev指针指向前一个结点。
5、树 (Tree)
树 是一种能够分层存储数据的重要数据结构,树中的每个元素称为树的结点,每个结点有若干个指针指向子结点。
从结点的角度看,树是由唯一的起始结点引出的结点集合,这个起始结点称为根(root)。
树中结点的子树数目称为结点的度(degree)。
二叉树 是指对于树中的每个结点而言,至多有左右两个子结点,即任意结点的度小于等于2.
二分查找树 是二叉树的一种特例,对于二分查找树的任意结点,该结点存储的数值一定比左子树的所有结点的值大,比右子树的所有结点的值小
二分查找树通常被用于维护有序数据,二分查找树查找、删除、插入的效率都会高于一般的线性数据结构。
平衡二叉树 是指一棵树的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一颗平衡二叉树。
高度:对一棵树而言,从根结点到某个结点的路径长度称为该结点的层数(level),根结点为第0层,非根结点的层数是其父结点的层数加1。 树的高度定义为该树中层数最大的结点的层数加1,即相当于从根结点到叶结点的最长路径加1.
满二叉树(Full Binary Tree) 如果一颗二叉树的任何结点,或者是叶结点,或者左右子树都存在,则这棵二叉树称为满二叉树。
完全二叉树 (Complete Binary Tree) 如果一颗二叉树最多只有下面的两层结点度数可以小于2, 并且最下面一层的结点都集中在该层最左边的连续位置上,则此二叉树称作完全二叉树。
二叉树遍历方式包括:
1、前序遍历 (Pre-Order Traversal):访问根结点;按前序遍历左子树;按前序遍历右子树。
2、中序遍历 (In-Order Traversal) : 按中序遍历左子树;访问根结点;按中序遍历右子树。特别地,对于二分查找树而言,中序遍历可以获取一个由小到大或者由大到小的有序序列。
3、后序遍历 (Post-Order Traversal):按后序遍历左子树;按后序遍历右子树;访问根结点。