线性表及其应用练习

一、选择题

1、用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（）

A、当前结点所在的地址域 B、指针域 C、空指针域 D、空闲域

2、不带头结点的单链表head为空的判断条件是（）

A、head==NULL B、head->next==NULL C、head->data==NULL D、head!=NULL

3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（）

A、s->next=p; q->next=s; B、p->next=s->next; s->next=p;

C、q->next=s->next; s->next=p; D、p->next=s; s->next=q;

4、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）

A、O（1） B、O（n） C、O（n2） D、O（nlog2n）

5、一个单链表中，若删除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;

6、已知一个顺序存储的基本线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为（）

A、d1+(i-1)*m B、d1+i*m C、d1-i*m D、d1+(i+1)*m

7、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）

A、访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)

B、在第i个结点后插入一个新结点(1<=i<=n)

C、删除第i个结点(1<=i<=n)

D、将n个结点从小到大排序

8、下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中，能正确完成要求的算法段是（）

数据结构（线性表）练习题与答案1

1、线性表是（）。

A.一个有限序列，可以为空

B.一个有限序列，不可以为空

C.一个无限序列，可以为空

D.一个无限序列，不可以为空

正确答案：A

解析：线性表是具有n（n≥0）个数据元素的有限序列。

2、线性表的基本运算ListInsert(&L,i,e)表示在线性表L中第i 个位置上插入一个元素e，若L的长度为n，则i的合法取值是（）。

A.1≤i≤n

B.1≤i≤n+1

C.0≤i≤n-1

D. 0≤i≤n

正确答案：B

解析：线性表的基本运算ListInsert(&L，i，e)中，位置i是指逻辑序号，可以在L的位置1到位置n+1插入元素。

3、顺序表具有随机存取特性，指的是（）。

A.查找值为x的元素与顺序表中元素个数n无关

B.查找值为x的元素与顺序表中元素个数n有关

C.查找序号为i的元素与顺序表中元素个数n无关

D.查找序号为i的元素与顺序表中元素个数n有关

正确答案：C

解析：一种存储结构具有随机存取特性指的是，对于给定的序号i，在O(1)时间内找到对应元素值。

4、在顺序表中删除一个元素所需要的时间（）。

A.与删除元素的位置及顺序表的长度都有关

B.只与删除元素的位置有关

C.与删除任何其他元素所需要的时间相等 D.只与顺序表的长度有关

正确答案：A

解析：当从顺序表中删除元素时，为了保持顺序表的逻辑特性，需要移动元素以覆盖该删除的元素。因此在顺序表中删除一个元素与该元素的位置及顺序表的长度都有关。

5、在n（n>1）个运算的顺序表中，算法时间复杂度为O(1)的运算是（）。

A.访问第i个元素（2≤i≤n）并求其前驱元素

B.在第i个元素之后插入一个新元素

C.删除第i个元素

D.将这n个元素递增排序

正确答案：A

解析：访问第i个元素（2≤i≤n）即L->data[i-1]和求其前驱元素L->data[i-2]的时间复杂度均为O(1)。

三、写一个算法合并两个已排序的线性表。〔用两种方法：数组表示的线性表〔顺序表〕和指针表示的线性表〔链表〕〕

要求：1、定义线性表节点的结构，并定义节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成此题。

4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。

四、已知一个单向链表，试给出复制该链表的算法。

要求：1、定义线性表的节点的结构以及节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成此题。

4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。

五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：

int delete(LIST &L, int x);如果x在该链表中，则删除对应结点，并返回其在链表中的位置〔逻辑位置，第一个结点的逻辑位置为1〕，否则返回-1。

要求：1、定义线性表的节点的结构以及节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成此题。

4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。

六、写出一个将两个静态链表〔属于同一个存储池〕合并的算法函数：

void Merge(cursor M, cursor N); 合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。

要求：1、定义静态链表的结点的结构以及结点的型SPACE以及位置〔position〕和游标〔cursor〕的型。

2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M中的位置为p的元素后面添加一个值为x的结点；void Delete (cursor M, position p ); 在链表M中删除位置为p的元素的后一个元素。

1 第二章 线性表练习题（1）

一、单项选择题

1、链式存储结构的最大优点是（D ）。

A.便于随机存取 B.存储密度高

C.无需预分配空间 D.便于进行插入和删除操作

2、假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（D ）。

A. 106 B. 107 C.124 D.128

3、 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（A）存储方式。

A.顺序表 B. 带头结点的单链表

C.不带头结点的单链表 D. 循环单链表

4、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：C

（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构

5、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 B

（A）110 （B）108 （C）100 （D）120

6、 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：A

（A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

（B） 在第i个结点后插入一个新结点（1≤i≤n）

（C） 删除第i个结点（1≤i≤n）

（D） 将n个结点从小到大排序

7、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B 个元素

（A）8 （B）63.5 （C）63 （D）7

8、下述哪一条是顺序存储结构的优点？（ ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

9、下面关于线性表的叙述中，错误的是哪一个？ C

A．线性表采用顺序存储，必须占用一片连续的存储单元。