计算机基础知识:数据结构

2. 栈的两个应用:括号匹配和表达式的计算。是怎么应用的?表达式计算用的是哪种表达方式?有什么好处?

1. 中缀表达式转后缀表达式,如果读到数字,直接输出数字。如果读到字符,'('存入栈中,如果是')',将第一个'('之前的符号输出,如果读到运算符,和栈顶的运算符比较,如果高于加入栈中,否则弹出栈中的运算符,然后入栈。扫描完成之后所有运算符出栈。
2. 卡特兰数:Cn=C(2n,n)/(n+1),简单证明:用1表示进栈,用0表示出栈,相当于求合法的进栈出栈序列,首先考虑全部情况,相当于在2n个位置里面找出n个位置放1,然后在剩下的位子里面放0。考虑第一个0超过1的位置,在这个位置之前,所有0和1呼唤,最后生成n+1个1和n-1个0,然后这样相当于在2n个位置里面找出n个位置放1,这就是非法的数,然后算一下就可以得到卡特兰数了。

3. 字符串匹配算法:朴素的匹配算法、KMP算法。

4. 二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。

5. 堆,建堆算法,堆的插入和删除算法,堆排序。

6. 哈希。哈希函数的有哪些种?余数的取法? 处理冲突的方法? 闭散列方法有哪些?

1. 空间换时间,哈希函数,O(1)得到位置。
2. 处理冲突:链地址法(把冲突关键字存储在一个线性表中)、开放定址法(探测下一个di的单元是否使用了,线性探测+1,二次探测+-k*k,伪随机探测)、再散列法以及建立公共溢出区

7. 二叉搜索树的搜索、插入、删除。时间复杂度。

8. 二叉平衡树的插入结点的原理,有哪几种旋转方式?分别适用于哪种情况。分析二叉平衡树的时间复杂度。

9. 红黑树的定义,红黑树的性能分析和与二叉平衡树的比较。

11. 链表插入排序、链表归并排序。

12. 常见的有哪几种排序算法,试比较其时间复杂度,以及是否稳定,及各自使用的情形。

1. 插入排序:往有序表中插入待排的数,稳定
2. 希尔排序:按步长分组,然后每一组做插入排序
3. 冒泡排序:两两交换,每次得到待排数中最大的一个
4. 快速排序:选出一个基准,把数组分成两部分,一部分大于基准另一部分小于基准,然后分别递归直到所有的元素都在最终的位置上。分组过程中,找一个比基准大的放在左端,找一个比基准小的放在右端,最后基准放在退出的位置。
5. 选择排序:每次选择最小的元素
6. 堆排序:

13. 常用分配排序有哪几种? 基数排序的定义,分类及原理。

14. B树、B+树、Trie的概念及用途,添加删除结点的原理。

15. 数组和链表的区别

1. 存取:数组顺序存取,也可以随机存取,链表只能从表头顺序存取元素。
2. 查找、插入和删除操作
3. 链式存储的结点空间在需要的时候申请分配,操作灵活、高效。

相关日志

发表评论

电子邮件地址不会被公开。 必填项已用*标注