一、选择题。
1．顺序表是线性表的（ ）存储表示。
a．数组b．连续c．有序d．顺序存取。
2．以下（ ）是一个线性表。
a．由n个实数组成的集合 b．由100个字符组成的序列。
c．所有整数组成的序列 d．邻接表。
3．带头结点的双向循环链表l为空表的条件是（ ）
a．l->llink->rlink= null b．l->rlink= link
c．l->llink= nulld．l=null
4．非空的单循环链表first的链尾结点（由p所指向）满足（ ）
a．p-> null b．p = nullc．p->link = first d．p = first
5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
a．单链表b．仅有头指针的单循环链表。
c．双链表d．仅有尾指针的单循环链表。
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
a. 单链表 b．单循环链表。
c. 带尾指针的单循环链表 d．带头结点的双循环链表。
7．设一个顺序表的长度为n，在其中删除第i个元素（1<=i<=n）时，需要向前移动（ ）个元素。
a. n b. i-1 c. n-i d. n-i+1
8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）1<=i<=n+1)。
a. o(0) b. o(1) c. o(n) d. o(n2)
9. 静态链表中指针表示的是（ ）
a．内存地址b．数组下标。
c．下一元素地址d．左、右孩子地址。
10. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）
a．o(n) o(n) b．o(n) o(1) c．o(1) o(n) d．o(1) o(1)
二、判断题。
1. 顺序存储方式只能用于存储线性结构。(
2．取线性表的第i个元素的时间同i的大小有关。(
3．为了很方便的插入和删除数据，可以使用双向链表存放数据。(
4. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(
三、填空题。
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。
2．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成。
和；而又根据指针的连接方式，链表又可分成和。
3．链接存储的特点是利用来表示数据元素之间的逻辑关系。
4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动个元素。
5.下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用l返回逆置后的链表的头指针，试在空缺处填入适当的语句。
void reverse（linklist&l）{
p=null；
q=l；while（q！=null）{
q->next=p；p=q；
6. 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域 next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为 –1。
derivative(ha){
q=ha ;
pa=ha->next;
while1if2
free(pa);
pa4else{
pa->coef5
pa->exp6q7pa8
7．下面是一个求两个集合a和b之差c=a-b的程序，即当且仅当e是a的一个元素，但不是b中的一个元素时，e才是c中的一个元素。集合用有序链表实现，初始时，a，b集合中的元素按递增排列，c为空；操作完成后a，b保持不变，c中元素按递增排列。下面的函数append(last，e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(a，b)实现集合运算a-b，并返回表示结果集合c的链表的首结点的地址。
在执行a-b运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当a-b运算执行完毕，再删除并释放表示结果集合的链表的表头结点。
typedefstruct node{
int element;
struct node *link;
node;node *a，*b，*c;
node *append (node *last，int e){
last->link=(node*) malloc (sizeof(node));
last->link->element=e;
return(last->link);
node *difference(node *a，node *b){
node *c，*last;
c=last=(node*) malloc (sizeof(node));
while1
if (a->elementelement) {
last=append(last，a->element);
a=a->link;
elseif2
a=a->link; b=b->link;
else3while4
last=append(last，a->element);
a=a->link;
last=c;
c=c->link;
free (last);
return (c);
*call form:c=difference(a，b);*
四、应用题。
1. 设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。
2. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
3．设有一带头结点的单链表，编程将链表颠倒过来。要求不用另外的数组或结点完成。
4. 如果用带头结点的单链表来表示一元多项式，试设计一个算法，计算多项式a在x处的值。
第二章线性表作业
一 判断题。1.线性表的逻辑顺序与物理顺序总是一致的。2.线性表的顺序存储表示优于链式存储表示。3.线性表若采用链式存储表示。时所有存储单元的地址可连续可不连续。4.每种数据结构都应具备三种基本运算 插入 删除和搜索。5.线性表的特点是每个元素都有一个前驱和一个后继。6.顺序存储方式插入和删除时效率...
线性表结构
include include define stacksize 16 循环队列长度 define ok 1 define true 1 define false 0 define overflow 1 define underflow 2 define maxsize 100 定义元素类型 typ...
数据结构线性表
数据结构实验报告。实验名称 线性表。信息与通信学院，电子信息工程专业。作者 周裕娟 学号 0800220308 实验日期 2010年11月4日。一 实验目的。1 掌握线性表的顺序存储结构。2 掌握顺序表的基本运算并能灵活运用。3 掌握线性表的链式存储结构。4 掌握链表的基本运算并能灵活应用。二 实验...