请以外教上课为准，本文档仅供参考！
数据结构的定义
数据结构应该符合三个指标：正确性，时间复杂度，空间复杂度
interface correctly.
应该确保其正确性
Time Complexity 时间复杂度− Running time or the execution time of
operations of data structure must be as small as possible.
应该消耗更少的时间来完成工作
Space Complexity 空间复杂度− Memory usage of a data structure operation
should be as little as possible.
应该占用更少的内存来完成工作
算法
会考一道大题，10分
算法是一种人类能够理解的抽象的描述性语言，一般以描述步骤为主
算法的核心是创建问题抽象的模型和明确求解目标
算法也有对应的属性
该算法应从外部提供0个或多个输入。
输出 Output
至少应获得1个输出。
确定性 Definiteness
算法的每一步都应该清晰明确。
正确性 Correctness
算法的每一步都必须产生正确的输出。
有限度 Finiteness
该算法应具有有限数量的步骤。
考试会考的是要求写步骤
比如
Step 1 START
Step 2 declare three integers x, y & z
Step 3 define values of x & y
Step 4 multiply values of x & y
Step 5 store the output of step 4 in z
Step 6 print z
Step 7 STOP
设计一种算法以将两个数字x和y相乘并在z中显示结果。
步骤1开始
第2步声明三个整数x，y和z
步骤3定义x和y的值
步骤4将x和y的值相乘
步骤5将步骤4的输出存储在z中
步骤6列印z
步骤7停止
就像这种的，考试要写的是 Step1 Step2 这样的步骤
写代码的话一分都没有
复杂度的计算
会有题目涉及到这个
复杂度分为两种，时间复杂度Time Complexity 和 Space Complexity 空间复杂度
指这个代码需要使用的变量/数组在计算机中占用内存的大小
比如布尔类型的变量就是一字节
例：z = a + b + c 占用的空间复杂度是？
答：20， int每个变量占用 4 ， 还有一个return值也是4
例：在 x = 0, i = 1 的 i 循环的for 循环中，完整的空间复杂度？
答：4n + 16 ， 4n指for循环，n指i循环的次数，后面的16是每一个元素，x, i, n, return
递归
考对递归的理解
递归就是在一个方法内部调用自己
也可以理解为一个循环
在设置递归的时候要有一个基本情况 base case，否则程序会变成一个死循环
比如我想要一个6的阶乘，也就是n*（n-1）
当代码执行到（n-1）这一行的时候，相当于调用了自己
如果我们不设置 n=0 就停止这个条件，代码将会无限制地运行下去
这里的 n = 0 就是 base case
栈
栈顶部叫做 top， 遵循 LIFO 原则， 弹出元素叫 pop, 压进元素叫 push
假如定义一个列表，这个列表充当着栈的角色
但是对于普通数组来说，没有实现LIFO的功能
所以，如果要把元素push进去，算法应该如何实现？
这个一定会考
Step 2 − If the stack is full, produces an error and exit.
Step 3 − If the stack is not full, increments top to point next empty space.
Step 4 − Adds data element to the stack location, where top is pointing.
Step 5 − Returns success.
步骤1-检查堆栈是否已满。
步骤2-如果堆栈已满，则产生错误并退出。
步骤3-如果堆栈未满，则从顶部开始递增以指向下一个空白空间。
步骤4-将数据元素添加到堆栈位置，顶部是
指向。
步骤5-返回成功。
同样的，pop也是必考的
Step 2 − If the stack is empty, produces an error and exit.
Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
Step 4 − Decreases the value of top by 1.
Step 5 − Returns success.
步骤1-检查堆栈是否为空。
步骤2-如果堆栈为空，则产生错误并退出。
步骤3-如果堆栈不为空，则访问顶部指向的数据元素。
步骤4-将top的值减小1。
步骤5-返回成功。
波兰表达式
Infix Notation
Prefix Notation / Polish Notation 波兰表达式
Postfix Notation / Reverse-Polish Notation 逆波兰表达式
考试点：计算postfix的值， infix notation to postfix notation
如果我是你我就会去看看汉诺塔 towners of Hanio
你先记一下，汉诺塔的移动需要 (2 ^ n) -1 步，万一用到了呢？
链表
链表是一个 线性的数据额结构 Linear data Structure ，
链表的节点用 Node 来表示，一个节点中包含两个最基本元素：数据值和下一个元素的指针
在 双向链表 double linked list 中，有两个指针，一个指向前一个指向后
在 循环链表 Circular Doubly Linked List 中，会自动回到开始的节点
链表确实会考，但是考的不是很深，主要涉及到各个链表的定义和相关指针
排序
归并排序：分而治之 divide and conquer algorithm
归并排序相关的应该会考
哈希
哈希，叫Hashing
哈希会将元素存放在哈希表 Hash table 里面
一般来说，哈希表格大小都是质数
冲突 collision
冲突的解决方式：开放地址法
Separate Chaining 分离链接法
open addressing 开放地址法
- Linear Probing 线性探测
- Quadratic Probing 平方探测
记单词，必考
开放地址法考大题和选择题，就是线性探测和平方探测
线性探测优点：易于计算
缺点：导致聚集 cluster，聚集有 首要聚集 primary clustering 和 二级聚集 secondary clustering
平方探测中，key + (1^2)，这个key是指余数，比如66 % 11 ,key就是0
树
树的概念和相关单词需要记忆
Hierarichical 分层的
Ancestor node 祖先
Degree 程度
Binary tree 二叉树
二叉搜索树：必须遵循左小右大的原则
树的部分考了很多的 遍历 Traversal
in-order 中序遍历
pre-order 先序遍历
post-order 后序遍历
这几种遍历方式很重要，必考
Edge 边缘
Vertex 节点
Undirected graph 无方向
Directed graph有方向的
Breadth first search 广度优先搜索
他会给一张图来考 广度优先搜索的结果
广度优先就是会按照设定好的结果去访问，先按照某种规定（一般是字母表顺序）访问相同等级上的所有元素，走完之后才会走到下一个。就是会一条路走到底，走到不能走的状态才会回头
图
完全图 complex graph
这张图上的任何节点与其他的任何节点都有链接，那么这张图就是完全图
假设有4个节点，那么边就是6条边
计算公式为： n*(n-1) / 2
Comment here is closed