数据结构与算法题目
2020-09-30 本文已影响0人
孙静静
栈
1. 一个函数判断字符串中的括号是否合法，所谓合法，就是括号成对出现
sdf(ds(ew(we)rw)rwqq)qwewe 合法
(sd(qwqw)sd(sd)) 合法
()()sd()(sd()fw))( 不合法
- 计算逆波兰表达式
逆波兰表达式，也叫后缀表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式，
例如 (a+b)*(c+d)转换为ab+cd+*。
- 实现一个有min方法的栈
- 使用栈，完成中序表达式转后续表达式
输入:["(","1","+","(","4","+","5","+","3",")",
"-","3",")","+","(","9","+","8",")"]
输出:[ '1', '4', '5', '+', '3', '+', '+', '3', '-', '9', '8', '+', '+' ]
队列
- 约瑟夫环
有一个数组a[100]存放0--99;要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，
求最后一个被删掉的数。
- 斐波那契数列
斐波那契数列的前两项是 1 1 ，此后的每一项都是该项前面两项之和，即f(n) = f(n-1) + f(n-2)。
- 用两个队列实现一个栈
- 打印杨辉三角
- 用两个栈实现一个队列
- 迷宫问题
有一个二维数组
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]，请用程序计算这两个点是否相通，如果相通请输出两点之间的最短路径（从起始点到终点所经过的每一个点）
链表
- 基于链表实现的Stack 和 Queue
- 翻转链表
使用迭代和递归两种方法翻转链表
- 从尾到头打印链表
- 合并两个两个有序链表
- 查找单链表中的倒数第K个节点（k > 0）
- 查找单链表的中间结点
- 实现双向链表（地狱模式）
BitMap
- 已知有n整个整数，这些整数的范围是[0, 100]，请你设计一种数据结构，使用数组存储这些数据，并提供两种方法，分别是addMember 和 isExist
- 两个数组，内容分别为[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，请用BitMap计算他们的交集
- 课程里所讲的BitMap只能存储大于等于0的整数，请你改造BitMap类，不论正数还是负数，都可以存储并判断是否存在
- 查找不重复的数（地狱模式）
有一个数组，内容为[1, 3, 4, 5, 7, 4, 8, 9, 2, 9]，有些数值是重复出现的，请你改造BitMap类，增加一个isRepeat(member)方法，判断member是否重复出现，并利用该方法找出数组中不重复的数。
二叉树
- 如何用广义表来表达二叉树呢，以广义表 A(B(D,E(G,)),C(,F))# 为例
- in_order 中序遍历算法
- pre_order 前序遍历算法
- post_order 后序遍历算法
- size 返回节点数量
- height 返回树的高度
- 查找节点
- 求一棵树的镜像
对于一棵树，如果每个节点的左右子树互换位置，那么就变成了这棵树的镜像
请实现mirror方法
- 使用非递归方式实现前序遍历, 中序遍历, 后序遍历
- 寻找两个节点的最近公共祖先
- 分层打印二叉树
- 输出指定层的节点个数
堆
- 最小堆实现insert方法
- remove_min 删除掉最小堆的最小值
- get_min， print ， size 方法
- 可以使用最小堆进行排序，使用待排序数组初始化最小堆，然后逐个删除堆顶元素，由于堆顶元素始终最小，所以可以得到一个有序的数组
- 一个非常大的数据集合有n个整数，求集合中最大的K个值。
- 实现最大堆
二叉搜索树
- 二叉搜索树的插入，删除，搜索
- 利用二叉搜索树实现一个简单的字典
