数据结构与算法题目

栈

1. 一个函数判断字符串中的括号是否合法，所谓合法，就是括号成对出现

sdf(ds(ew(we)rw)rwqq)qwewe   合法
(sd(qwqw)sd(sd))             合法
()()sd()(sd()fw))(           不合法

2. 计算逆波兰表达式

逆波兰表达式，也叫后缀表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式，
例如 (a+b)*(c+d)转换为ab+cd+*。

3. 实现一个有min方法的栈
4. 使用栈，完成中序表达式转后续表达式

输入:["(","1","+","(","4","+","5","+","3",")",
"-","3",")","+","(","9","+","8",")"]
输出:[ '1', '4', '5', '+', '3', '+', '+', '3', '-', '9', '8', '+', '+' ]

队列

1. 约瑟夫环

 有一个数组a[100]存放0--99;要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，
 求最后一个被删掉的数。

2. 斐波那契数列

斐波那契数列的前两项是 1 1 ，此后的每一项都是该项前面两项之和，即f(n) = f(n-1) + f(n-2)。

3. 用两个队列实现一个栈
4. 打印杨辉三角
5. 用两个栈实现一个队列
6. 迷宫问题

有一个二维数组

var maze_array = [[0, 0, 1, 0, 0, 0, 0],
                  [0, 0, 1, 1, 0, 0, 0],
                  [0, 0, 0, 0, 1, 0, 0],
                  [0, 0, 0, 1, 1, 0, 0],
                  [1, 0, 0, 0, 1, 0, 0],
                  [1, 1, 1, 0, 0, 0, 0],
                  [1, 1, 1, 0, 0, 0, 0]
                 ];

元素为0，表示这个点可以通行，元素为1，表示不可以通行，设置起始点为maze_array[2][1]，终点是maze_array[3][5]，请用程序计算这两个点是否相通，如果相通请输出两点之间的最短路径（从起始点到终点所经过的每一个点）

链表

1. 基于链表实现的Stack 和 Queue
2. 翻转链表

使用迭代和递归两种方法翻转链表

3. 从尾到头打印链表
4. 合并两个两个有序链表
5. 查找单链表中的倒数第K个节点（k > 0）
6. 查找单链表的中间结点
7. 实现双向链表（地狱模式）

BitMap

1. 已知有n整个整数，这些整数的范围是[0, 100]，请你设计一种数据结构，使用数组存储这些数据，并提供两种方法，分别是addMember 和 isExist
2. 两个数组，内容分别为[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，请用BitMap计算他们的交集
3. 课程里所讲的BitMap只能存储大于等于0的整数，请你改造BitMap类，不论正数还是负数，都可以存储并判断是否存在
4. 查找不重复的数（地狱模式）

有一个数组，内容为[1, 3, 4, 5, 7, 4, 8, 9, 2, 9]，有些数值是重复出现的，请你改造BitMap类，增加一个isRepeat(member)方法，判断member是否重复出现，并利用该方法找出数组中不重复的数。

二叉树

1. 如何用广义表来表达二叉树呢，以广义表 A(B(D,E(G,)),C(,F))# 为例
2. in_order 中序遍历算法
3. pre_order 前序遍历算法
4. post_order 后序遍历算法
5. size 返回节点数量
6. height 返回树的高度
7. 查找节点
8. 求一棵树的镜像

对于一棵树，如果每个节点的左右子树互换位置，那么就变成了这棵树的镜像
请实现mirror方法

9. 使用非递归方式实现前序遍历, 中序遍历, 后序遍历
10. 寻找两个节点的最近公共祖先
11. 分层打印二叉树
12. 输出指定层的节点个数

堆

1. 最小堆实现insert方法
2. remove_min 删除掉最小堆的最小值
3. get_min， print ， size 方法
4. 可以使用最小堆进行排序，使用待排序数组初始化最小堆，然后逐个删除堆顶元素，由于堆顶元素始终最小，所以可以得到一个有序的数组
5. 一个非常大的数据集合有n个整数，求集合中最大的K个值。
6. 实现最大堆

二叉搜索树

1. 二叉搜索树的插入，删除，搜索
2. 利用二叉搜索树实现一个简单的字典