数据结构理论
1. 数据结构的定义。
在计算机科学或信息科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。
一般而言，数据结构的选择首先会从抽象数据类型的选择开始。一个设计良好的数据结构，应该在尽可能使用较少的时间与空间资源的前提下，为各种临界状态下的运行提供支持。数据结构可通过编程语言所提供的数据类型、引用及其他操作加以实现。
不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，当计算机网络依赖于路由表运作时，B树高度适用于数据库的封装。
在许多类型的程序设计中，选择适当的数据结构是一个主要的考虑因素。许多大型系统的构造经验表明，封装的困难程度与最终成果的质量与表现，都取决于是否选择了最优的数据结构。在许多时候，确定了数据结构后便能很容易地得到算法。而有些时候，思路则会颠倒过来：例如当某个关键作业需要特定数据结构下的算法时，会反过来确定其所使用的数据结构。然而，不管是哪种情况，数据结构的选择都是至关重要的。
2.栈的两个应用：括号匹配和表达式的计算是怎么应用的？表达式计算用的是哪种表达方式？有什么好处?
符号的平衡问题
在语言中往往需要判断一些符号是否是成对出现的，比如<>,{},[],()，通常在C++中也只有这几种对称问题，如何让判断符号的对称也是很多代码判断的首要任务。当然实现的方式是多种多样的，采用栈的实现会相对更加简单。基本的实现思路如下：
假设在读入一串字符串以后，如果遇到对称符号的左边部分，则将其压入栈中，当遇到对称符号的右边部分，则弹出栈中的一个对象，实现比对，如果是对称的，则说明当前的符号是平衡的，如果不对称，则说明当前字符串是不平衡的，当字符串读完以后，如果所有的符号都是平衡的，栈中此时应该就是为空，通过判断栈中是否为空，说明字符串是否是符号平衡的。
表达式的求值问题
主要涉及到操作符的优先级问题，比如（）、*/、+-这几种符号的优先级是不一样的，其中括号的优先级最好，乘除其次，加减最低，我们通常看到的表达式都是中缀表达式，也就是在操作符的两边都有对象，当然括号除外啦，这种中缀表达式是不便于在程序中处理的，因为存在很多的优先级差别，很难把握从那个位置先计算。
如果在表达式中没有了优先级的问题，求值问题也就变得相对来说更加简单，后缀表达式是一种非优先级的表达式表示方式，但是如何实现中缀表达式到后缀表达式的切换也是很难实现的。
中缀表达式到后缀表达式的实现如下:
中缀表达式：
a*b+c*d-e/f
后缀表达式：
ab*cd*+ef/-
从上面的表达式可以知道后缀表达式相对来说比较容易判断计算的基本过程，而且不存在括号的烦恼。采用栈实现转换的基本思路如下：
对一个中缀表达式进行遍历，当遇到非操作符的字符直接保存到后缀表达式的存储空间中，如果遇到左括号，则将左括号压入栈中,因为优先级最高，只有遇到右括号才会被弹出。如果遇到右括号，则将左括号之前的操作符全部弹出，并保存到后缀表达式的存储空间中，当然这种存储的顺序和出栈的顺序是一致的，括号操作符在后缀表达式中是不存在的，因此不需要将括号保存到后缀表达式的存储空间中。如果遇到乘除操作符（*/），则判断栈中的操作符优先级是否低于当前的操作符也就是判断是否是加减操作符，如果不是则将栈中的操作符（也就是*、/），并保存到后缀表达式存储空间中，然后将当前的操作符压入栈中，如果是则直接将操作符入栈。如果操作符是加减操作符，则弹出栈中左括号之前的所有操作符，并保存到后缀表达式存储空间中，然后将操作符本身压入栈中。当字符串遍历完成以后，依次弹出操作符，并保存到后缀表达式存储区中。
后缀表达式求值的问题
实现了后缀表达式的转换，实现表达式的求值问题也就比较简单了，实现的基本思路如下：
遍历后缀表达式，遇到非操作符的字符则直接压入栈中，如果遇到操作符则从栈中弹出两个对象，进行对应的操作，然后将计算的结果又压入栈中。继续遍历，直到表达式被遍历完成，此时栈中保存的值也就是当前表达式的值，需要注意除法和减法的操作数顺序问题以及除数不能为0的。
3.字符串匹配算法：朴素的匹配算法(Brute Force 暴力搜索)、KMP算法。
字符串匹配问题就是在一个大的字符串T中搜索某个字符串P的所有出现位置。其中，T称为文本，P称为模式，T和P都定义在同一个字母表∑上。
4.红黑树的定义，红黑树的性能分析和与二叉平衡树的比较。
红黑树与平衡二叉树的查找性能相同。
但是当插入节点和删除节点从而破坏树的平衡性时，红黑树需要做旋转调整的次数比平衡二叉树所需的旋转调整的次数要少的多，其查找，插入，删除的操作时间复杂度均为O(Log2n)。
5.图有哪些储存表示。
A.邻接矩阵
图的邻接矩阵存储也称数组表示法，其方法是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
B.邻接表
对于图的每个顶点Vi，将所有邻接于的顶点Vi链成一个单链表，称为顶点Vi的边表。为了方便对所有边表的头指针进行存取操作，可以采取顺序存储。存储边表头指针的数组和存储顶点信息的数组构成了邻接表的表头数组，称为顶点表。所以，在邻接表中存在两种节点结构：顶点表节点和边表节点。
相关题目
1.把二叉搜索树转变成排序的双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
比如将
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表。
解答：中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。
所需的双向链表的节点顺序是该二叉树的中序遍历结果，可在中序遍历时，对节点进行处理（改变左右孩子）。代码与中序遍历的算法类似，只是多加了一个步骤。
2.设计包含min函数的栈
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
考虑到时间复杂度的需求，添加一个辅助栈，每次入栈时将元素分别存入数据栈和辅助栈，
辅助栈中的数据始终保持最小值在栈顶，需要获取最小值时，直接Peek()辅助栈即可。
3.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12和10, 5, 7。
4.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
5.二元查找树的后序遍历结果
输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
|
1
2
3
4
5
6
7
8
9
|
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回
true
。
|
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
6.求二叉树中节点的最大距离
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。
7.单链表就地逆置
就地逆置，指不借助任何中间变量进行链表逆置
8.判断两个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
9.输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
10.实现一个队列。
队列的应用场景为：
一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列
11.用C++设计一个不能被继承的类。
分析：这是Adobe公司2007年校园招聘的最新笔试题。
这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。
12.在O（1）时间内删除链表结点（链表、算法）。
题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：考察编程基本功，反应速度，
更重要的是，还能考察我们对时间复杂度的理解。
13.找出链表的第一个公共结点（链表）。
题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
14.BSTree转换成有序双向链表
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
struct
BSTreeNode{
int
n_value;
//value of node
BSTreeNode *pleft;
//left child of node
BSTreeNode *pright;
//right child of node
}
BSTreeNode *treeToLinkedList(BSTreeNode *root){
BSTreeNode *head,*tail;
helper(head,tail,root);
return
head;
}
void
helper(BSTreeNode *&head,BSTreeNode*&tail,BSTreeNode *&root){
BSTreeNode *lft,*rgt;
if
(root==NULL){
head=NULL;
tail=NULL;
return
;
}
}
|
15.把二元查找树转变成排序的双向链表
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
比如将二元查找树
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16
16.判断二叉树是不是平衡
输入一棵二叉树的根结点，判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
例如下图中的二叉树就是一棵平衡二叉树：
17.两链表的第一个公共结点
两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
|
1
2
3
4
5
|
struct
ListNode
{
int
m_nKey;
ListNode* m_pNext;
};
|
18.在O(1)时间删除链表结点
给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
|
1
2
3
4
5
|
struct
ListNode
{
int
m_nKey;
ListNode* m_pNext;
};
|
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：
在链表中删除一个结点，最常规的做法是从链表的头结点开始，顺序查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度自然就是O(n) 了。
我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点，由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的。当然，在删除之前，我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为O(1)。
19.从尾到头输出链表
输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
|
1
2
3
4
5
|
struct
ListNode
{
int
m_nKey;
ListNode* m_pNext;
};
|
20.二元树的深度
输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
例如：输入二元树：
10
/ \
6 14
/ / \
4 12 16
输出该树的深度3。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/**
* 获得树的高度
*/
public
int
getLevel(TreeNode node){
if
(node==
null
)
return
0
;
int
left=getLevel(node.leftNode);
int
right=getLevel(node.rightNode);
return
(left>right)?left+
1
:right+
1
;
}
|
21.栈的push、pop序列
输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。
比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
分析：这到题除了考查对栈这一基本数据结构的理解，还能考查我们的分析能力。
22.反转链表
输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如下：
|
1
2
3
4
5
|
struct
ListNode
{
int
m_nKey;
ListNode* m_pNext;
};
|
23.用两个栈实现队列
某队列的声明如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
template
<
typename
T>
class
CQueue
{
public
:
CQueue() {}
~CQueue() {}
void
appendTail(
const
T& node);
// append a element to tail
void
deleteHead();
// remove a element from head
private
:
T> m_stack1;
T> m_stack2;
};
|
24.从上往下遍历二元树
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
|
1
2
3
4
5
6
7
8
9
|
例如输入
8
/ \
6 10
/\ /\
5 7 9 11
输出8 6 10 5 7 9 11。
|
