文档介绍：第一章知识点、术语
数据结构的含义；数据、数据元素、数据对象，数据结构，逻辑结构/存储结构、数据类型
抽象数据类型，算法的定义与表示法，算法的特征及评价（重要）、算法的时间复杂度分析（会分析程序的时间复杂度）
一、选择it
. （）
时间发杂度和空间夏奈度是衡量一个算法优劣的重要依据. （）
•-个算法通常寿有五个将作：有穷，核' 确定性、可行性、输入和输出. （）
10.
O(n2)
一.
第1章
11.
12.
O（logjn）
程序对于精心设计的典型合法数据
1.
3.
5.
A 2. C
输入能得出符合要求的结果。
C、A 6. C» B
13.
5伪代码表示计算机语言表示
7.
B 8. D
14.
事后统计事前估计
9.
B 10. B
三*
判断题
二、
境空题
1.
x 2. x
1.
2.
线性结构非线性结构集合线性树图
3.
x
3.
—对一一时多或多对多
5.
x 6. x
4.
时间空间
7.
x 8. V
5.
前驱-后继多
9.
寸 10. V
6.
有多个
11.
7 12. x
7.
8.
—对一一对多多时多
O（n2）
13.
q 14. 4
9.
o ( 4n )
15.
V
第二章：知识点：术语
线性表的定义，线性表的运算（创建、置空，判空，求长度，取元素，元素定位（插入删除）（求元素前驱, 后继），合并表；线性表的顺序存储与链式存储的优缺点
顺序存储结构的特征使得它在运算时具有以下优点：
对基本线性表中的数据元素可以进行随机存取。
由于每个数据元素的位置可以由其下标惟一确定。进行存取操作时，其时间复杂度为常量级0(1)。
查找前驱、后继元素非常快捷。由于查找任何元素都可以由其下标随机确定，则查找其前驱、后继也非常快捷。
空间利用率高。在顺序存储结构中，存储空间的利用率接近100%□
但是，顺序存储结构也存在不足的地方：
(I )在基本线性表中插入和删除数据元素的操作效率不高。
因为在顺序存储中，基本线性表中的所有元素都是连续的，元素之间没有任何空余位置。要插入一个新数据元素就要把待插入位置上的原数据移开，这样就需要移动一连串数据元素■:同样删除数据元素时，也要移动大量的元素。
(2)建立空表时，不易确定基本线性表存储空间的大小。
因为基本线性表的最大存储空间不好估计。存储空间预留太大容易造成浪烫，预留太。
基本线性表的顺序存储虽然可以进行随机存取，但其插入和删除操作要移动太多的兀。而且从空间利用率上来说，顺序存储的效率也不一定高. 为了保证数据元素有•空间存储，顺序存储需要开辟最大的静态连续存储空间。为了克服顺序存储的不足，在许多情形中，基本线性表采用另外一种基本的存储方式，即链式存储。由于链式存储的空间分配是动态的，因此链式存储又称动态存储。链式存储是一种非常灵活的存储方式。
在链式存储中，逻辑上是相邻关系的元素在存储位置上不一定要求相邻，这就降低了基本线性表对空间的要求，同时也可以有效的利用一些零散的存储空间。
一、选择题
基本城桂表的顺序存储中，致提元素的迁辑位史与物理位史的关系是().
B. -ft的
带头站点的单铤表head为空的判断条件是( ).
head->next ==NULL B. head==NULL
C・ head*>data ==NULL D. head->next!= NULL
在一个单佐衰中，巳知q所指站点是p所指结点的后鲤诂点，若在p和q之间插入s结点则执行().
s->next = q； p->next = s;
p->next =s->next; s->next =p;
q->next =s->next; s->next =p;
p->next =s; s->next=q;
在一个具有n个诂点的有序顺序表中插入一个新站点井仍佐有序的时间曩杂度是( ).
。⑴ B. O[n2) C. O(n) D. O(nlog2n)
在一个中,若删除P所指结点的后续诂点，则执行( ).
A・ p->next=p->next->next; B. p^p->next; p->next=p->next->next;
C. p->next«p; D・ p»p->next->next;
巳知一个顺序存储的基本线柱表，若第1个结点的地址d,第3个的地址是5d,则第n个结点的地址为( ).