一、名词解释（见教材）
数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大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. 插入、删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比
6、栈的插入和删除操作在（ A ）进行。
A．栈顶 B．栈底 C．栈顶或栈底 D．任意位置
7、向一个顺序栈S（栈顶指针为top）中插入元素x时，首先要（ B ）。 A．S->stack[S->top]=x;
C．S ->top--;
8、对一个顺序存储结构的栈，栈满的判断条件是（ D ） A.S.top= =-1 B.S.top= =0
C.S.top= =MaxSize D. S.top= =MaxSize-1
9、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队满的条件是(C) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front
10、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队空的条件是(A) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front
3
B．S->top++;
D．x= S->stack[S->top];
11、队的插入操作在（ C ）进行。
A．队首 B．队首或队尾 C．队尾 D．任意位置
12、下面程序段的时间复杂度为（ C ）。 for (int i=0;i for (int j=0;j a[i][j]=i*j; A．O(m2) B. O(n2) C．O(m×n) D. O(m+n) 13、一个求从1到正整数n之间所有正整数之和的单循环语句的时间复杂度为（A．O(1) B. O(n) C．O (n2) D. O(n3) 14、下列是顺序存储线性表排序的算法 void Sort(List& L) { int i,j; ElemType x; for(i=1;i L.list[j+1]=L.list[j]; else break; L.list[j+1]=x; }; } 问：此算法的时间复杂性为： B A. O(n) B.(n2) C. (n*i) D. (n*j) 15、下面程序段的时间复杂度为（ B ）。 for (int i=1;i<=n;i++) 4 B ）。