提示：内容已过期
考试要求
笔试
- 单项选择
- 简答
- 算法设计与分析
机试
- 系统：Matrix
- 数量：10题
- 考试时间： 3个小时
- 提交次数限制不超过六次
- 不可以上网，不可以带其他电子设备
- 不可带书，不带任何纸质材料，到时统一发放草稿纸
Classification of data structures 数据结构的分类
set
linear
tree
graph
List of data structures 数据结构列表
- Data type 数据类型
原始类型：Boolean、Integer、Double、Character、Enum等
复合类型：Array、Struct、Union等
抽象数据类型：Stack、List、Map、Set、String、Queue等。
- Linear data structures 线性数据结构
Arrays 数组
Lists 列表（多级）
- Trees
Binary trees 二叉树
Heap 堆
Multiway trees 多路树
…
- Graphs
Abstract Data Type (ADT) 抽象数据类型
An Abstract Data Type (ADT) is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation on the operations.
抽象数据类型（ADT）是一种数据类型，其组织方式使对象的说明和对象操作的说明与对象的表示和操作的实现分离。
用三元组描述如下：
ADT =（D,S,P）其中：D是数据对象，S是D上的关系集，P是D的基本操作集。
ADT 抽象数据类型名{
数据对象：〈数据对象的定义〉
数据关系：〈数据关系的定义〉
基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名
Stacks 栈
A stack is a data structure in which all insertions and deletions of entries are made at one end, called the top of the stack. The last entry which is inserted is the first one that will be removed. The operations perform in a Last-In-First-Out (LIFO) manner.
堆栈是一种数据结构，其中所有条目的插入和删除都在一端进行，称为堆栈顶部。插入的最后一个条目是将被删除的第一个条目。操作以后进先出（LIFO）方式执行。
Implementing a Contiguous Stack
We set up an array to hold the entries in the stack and a counter to indicate how many entries there are.
实现连续堆栈
我们设置了一个数组来保存堆栈中的条目，并设置了一个计数器来指示有多少条条目。
Implementing a Linked Stack
A linked structure is made up of nodes, each containing both the information that is to be stored as an entry of the structure and a pointer telling where to find the next node in the structure.
实现链接堆栈
链接结构由节点组成，每个节点包含要存储为结构项的信息和一个指针，该指针指示在结构中查找下一个节点的位置。