一、名词解释（见教材）
数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵 二、填空
1、数据的逻辑结构被分为_集合结构_、_线性结构___、_树形结构__、__图形结构__4种。
2、数据的存储结构被分为_顺序结构__、链接结构_、索引结构_、和__散列结构__4种。
3、在定义某种数据结构时，其数据域的数据类型可分为 简单类型 和 结构体类型 两种，为增强其通用性，应将其再定义为 通用数据 类型。
4、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为 1：N 、 M：N 。
5、数据结构简单地说是指 数据 以及相互之间的 联系 。
6、算法应具备以下5个特性： 有穷性 、 正确性 、 可行性 、输入和输出。
7、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是 处理问题的样本量 。
8、对于一个单链表，在表头插入结点的时间复杂度为 O(1) ，在表尾插入元素的时间复杂度为 O(n) 。
9、 在表长为n的顺序表中，在等概率情况下，插入和删除一个元素平均需移动 表长的一半（即n/2 ） 个元素，具体移动元素的个数与表长（n） 和 该元素在表中的位置 有关。
10、顺序表的定义如下： typedef int ElemType;
1
struct List{
ElemType *list; int size; int MaxSize;
};
其中ElemType的含义是：通用数据 类型；size的含义是：顺序表中元素的个数。
11、 设单链表中指针p 指向结点A，q指针指向其后继结点。若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为p->next=q->next;。
12、栈的运算规则为 后进先出 ，队列的运算规则为 先进先出 。
13、一个函数调用了自身，这是 递归 调用。
14、非零元素个数远远少于零元素个数的矩阵称为 稀疏矩阵 。
15、顺序存储的稀疏矩阵采用三元组线性表存储，定义如下： struct Triple{ };
struct SMatrix{ };
其中row的含义是：非零元素所在的 行 ；t的含义是：非零元素的个数。
int m,n,t;
struct Triple sm[11]; int row,col; ElemType val;
三、选择题
1、顺序表物理结构中的存储单元（ A ）。
A. 一定是连续的 B. 一定是不连续的 C. 不一定是连续的 D. 经删除操作后不连续
2、对一个线性表的存取操作很少，而插入和删除操作较多时应采用 B 数据结构。
2
A．线性表 B. 队列 C. 图 D. 树
3、对一个线性表的随机存取操作较多时，应采用 B 存储结构。 A.静态顺序存储 B. 动态顺序存储 C. 动态链接存储 D. 静态链接存储
4、 顺序表适用于（ A ） 的场合。
A. 频繁查询 B. 频繁插入与删除 C. 问题规模较小 D. 问题规模较大
5、 链表不具有的特点是（A ）。
A． 可随机访问任一元素 B. 插入、删除不需