一绪论¶

什么是数据结构?
带结构的数据元素的集合
数据结构 = 数据对象 + 结构

一个数据结构由哪三部分构成?
逻辑结构
存储结构
数据运算

顺序存储结构的特点是什么?
所有元素存放在一片连续的存储单元
逻辑上相邻的元素在逻辑位置上也是相邻的

链式存储结构的特点是什么?
数据元素存放在任意的存储单元, 这组存储单元可以是连续的, 也可以是不连续的
通过指针将组与组之间串起来, 所有组内是连续的

四种常见的存储结构是什么?
顺序存储结构
链式存储结构
索引存储结构
哈希(散列)存储结构

判断题
同一逻辑结构可以对应多种存储结构
同样的运算，在不同的存储结构中，其实现过程是不同的。

C
C
一对一一对多
顺序存储、链式存储、索引存储和哈希存储
逻辑、存储、运算

CCC
算法是对特定问题求解步骤的一种描述，它是指令的有限序列。
有穷性
确定性
可行性
有输入
有输出

CACA

BACA
BADC

二线性表¶

什么是线性表, 线性表元素的三个特征是什么?
线性表是具有相同特性的数据元素的一个有限序列
三个特征:

数据元素类型都是相同的
数据元素个数是有限的
数据元素是有序列的, 即有唯一的序号

A D A A D
A
n - i + 1
O(1) 随机存取结构
顺序链式
n n + 1

单链表是如何实现逆置的(编码实现)?
更改指针

public static void Reverse(LinkListClass<Interger> L){
    LinkNode<Integer> p=L.head.next, q  // p指向首结点
    L.head.next = null; // 将L置为一个空表
    while(p!=null){
        q=p.next;  // q临时保存p结点的后继结点
        p.next=L.head.next; // 将p结点插入到表头
        L.head.next = p;
        p=q;
    }
}

ADA

4 front.next p
5 前趋结点 O(n)

顺序表相比与链表具有什么特点, 适用于什么样的运算?
空间上
顺序表的存储密度为1，而链表的存储密度小于1
顺序表需要预先分配空间, 二链表的存储空间是动态分配的
时间上
顺序表具有随机存取特性，给定序号查找对应的元素值的时间为0(1)；
链表不具有随机存取特性，只能顺序访问，给定序号查找对应的元素值的时间为0(n)。
在顺序表中插入和删除操作时，通常需要平均移动半个表的元素。
在链表中插入和删除操作仅仅需要修改相关结点的指针成员，不必移动结点。