第二章 线性表

习 题 二 一、单选题

1.在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时， 需要从年向前依次移 B 个元素。

A n-i B n-i+1 C n-i-1 D i

2.在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次

前移 A 个元素。

3.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度（即x同元素

的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A n B n/2 C (n+1)/2 D (n-1)/2

4.在一个单链表HL中，若要向表头插入一个自由指针p指向的结点，则执行 B 。 A HL=p;p->next=HL; B p=next=HL; HL=p;

C p->next=HL; p=HL; D p->next=HL->next;HL->next=p;

5.在一个单链表HL中，若要在指针q所指结点的后面插入一个自由指针p所指向的结点，则执行 D 。

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

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

6.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 C 。 A p=q->next;p->next=q->next; B p=q->next;q->next=p;

C p=q->next;q->next;q->next=q; D q->next=q=->Next->next;q->next=q;

二、填空题

1.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 值 ，另一个叫 指针 域。

2.在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为 (38,56,25,?? 60,42,74) 。

a 0 1 2 3 4 5 6 7 8

data 60 56 42 38 74 25 next 4 3 7 6 2 0 1

3.对于一个长度为l的顺序存储的线性表，在表头插入元素的时间复杂度帾 o(n) ，在表尾插

入元素的时间复杂度为 O(1) 。

4.对于一个单链接存储的线性表，在表头插入结点祫时话里有话复杂度为 o(1) ，在表尾插入

元素的时间复杂度为 o(n) 。

5.在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 i-1 ，后继元素

的下标为 i+1 。

6.在线性表的单链接存储中，若一个元素所在结点的地址为p，则后继结点的地址为 p->next ，

若假定p为一个数组a中的下标，则其后继结点的下标为 a[p].next 。

7.在循环单链接表中，最后一个结点的指针域指向 表头 结点。

8.在双向链接表中每个结点包含有两个针域，一个指向其 前驱 结点，另一个指向其 后继 结点。

9.在循环双向链接表中表头结点的左指针域指向 表尾 结点，最后一个结点的右指针域指 向 表头 结点。

10.在以HL为表头指针的带表头附加结点的单链接表中，链表为空的条件分别为 HL->next==NULL HL->next==HL 。

11.在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的

表头，具体操作为 a[i].next=a[1].next;a[1].next=i; 。

12.在由数组a中元素结点构成的单链表中，在插入下标为i的结点后，需要从空闲表头中删除一个

结点，并将该结点下标赋给i，具体操作为 i=a[1].next;a[1].next=a[i].next; 。

13.在由数组a中元素结点构成的单链表中，删除下标为i的后继结点并将被删除结点的下标赋给i时

，所进行的操作描述为 p=a[i].next;a[i].next=a[p].next;i=p; 。

14.在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需

要进行的操作为 a[j].next=a[i].next;a[i].next=j; 。

三、普通题 1.

⑴解：(79,62,34,57,26,48)

⑵解：(26,34,48,57,62,79)

⑶解：(48,56,57,62,79,34)

⑷解：(56,57,79,34)

⑸解：(26,34,39,48,57,62) 2. 解：

为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元

素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为

表头指针。

⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0)) ⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0)) ⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0)) ⒋(8(56,4),(57,7),(79,5),(34,0))

3.对于List类型的线性表,编写出下列每个算法。

⑴ 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若 线性表为空则显示出错信息并退出运行。 解： ElemType DMValue(List&L)

//从线性表中删除具有最小值的元素并由函数返回,空出的位置 //由最后一个元素填补,若线性表为空则显示出错信息并退出运行 {

if(ListEmpty(L)){

cerr<<\ exit(1); }

ElemType x; x=L.list[0]; int k=0;

for(int i=1;i

L.list[k]=L.list[L.size-1]; L.size--; return x; }

⑵ 从线性表中删除第i个元素并由函数返回。 解：int Deletel(List& L,int i)

//从线性表中删除第i个元素并由函数返回 {

if(i<1||i>L.size){

cerr<<\ exit(1); }

ElemType x; x=L.list[i-1];

for(int j=i-1;j

⑶ 向线性表中第i个元素位置插入一个元素。 解：void Inser1(List& L,int i,ElemType x)

//向线性表中第i个元素位置插入一个元素 {

if(i<1||i>L.size+1){

cerr<<\ exit(1); }

if(L.size==MaxSize) {

cerr<<\ exit(1); }

for(int j=L.size-1;j>i-1;j--) L.list[j+1]=L.list[j]; L.list[i-1]=x; L.size++; }

⑷ 从线性表中删除具有给定值x的所有元素。 解：void Delete2(List& L,ElemType x)

//从线性表中删除具有给定值x的所有元素 {

int i=0;

while(i

for(int j=i+1;j