内容发布更新时间 : 2024/12/27 22:10:50星期一 下面是文章的全部内容请认真阅读。

《数据结构》期末复习题及参考答案 - 第2章 线性表

一、选择题

1、下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。

2、线性表是具有n个（ ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

4、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表

5、 静态链表中指针表示的是（ ）.

A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址

6、链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比

7、长度为N的线性表，如果是顺序存储，则访问、删除某个结点的时间复杂度分别是（ ）和（ ）；如果是链式存储，则访问、删除某个结点的时间复杂度分别是（ ）和（ ）。

A. O(N) , O(1), O(1) , O(N) B. O(N) , O(1), O(N) , O(1) C. O(1) , O(1), O(N) , O(1) D. O(1) , O(N), O(N) , O(1)

8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。

A. O(0) B. O(1) C. O(n) D. O(n2)

9、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)

10、线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）

A．O（i） B．O（1） C．O（n） D．O（i-1）

11、在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。

A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；

B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

1

C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

12、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。

A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;

13、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）

A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 14、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

(A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)；

二、填空题

1、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 O(n) ，在表尾插入元素的时间复杂度为 O(1) 。 2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___顺序 ____存储结构。 1、长度为N的线性表中插入一个结点，对于顺序存储和链式存储的线性表，其插入操作的时间复杂度分别是O( N )和O( 1 )。

3、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____（n-1）/2 ___。 3、顺序存储的线性表中已有n个结点，插入一个新结点平均需要移动数据 n/2 次。

4、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:

py->next=px->next; px->next=py；

5、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动___ n-i+1___个元素。 6、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___ O(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为____ O(n)____。 7、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成___单链表2

_____和___多重链表____；而又根据指针的连接方式，链表又可分成__（动态）链表______和___静态链表_____。 8、顺序存储结构是通过___物理上相邻 _____表示元素之间的关系的；链式存储结构是通过____ 指针____表示元素之间的关系的。

9、一个顺序存储的线性表，第1、第2个元素的存储地址分别是16进制的16A、17A，那么第10个元素的存储地址是16进制的 1FA 。

10、 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ___4 ___个，单链表为____ 2___个。

11、循环单链表的最大优点是：___从任一结点出发都可访问到链表中每一个元素。_____。 12、在单链表L中，指针p所指结点有后继结点的条件是：__ p->next!=NULL 13、线性表的存储结构分为__顺序存储结构____和__链式存储结构____。

14、采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作 不需要 移动元素。 15、设单链表结点指针域为next，则删除链表中指针p所指结点的直接后继的的操作是：

q=p->next;

p->next=q->next; free(q); 16、设单链表的头结点的头指针为head,且pre=head，单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，则在p结点之前插入s结点的操作是： while(pre->next!=p) pre=pre->next; s->next=p;

pre->next=s;

17、在单链表p结点之后插入s结点的操作是：

s->next=p->next; p->next=s;

三、简答题

1、已知顺序表La 和Lb中数据元素按值非递减有序排列，归并La 和 Lb得到新的顺序表Lc，使Lc中的数据元素也按值非递减有序排列-这种操作称为顺序表的归并操作。请阅读下列顺序表的归并操作算法代码，分析该算法的时间复杂度，并作简要解释。 void MergeList(SqList La, SqList Lb, SqList &Lc) { pa = La.elem ; pb = Lb.elem ;

Lc.listsize = Lc.length = La.length +Lb.length;

3

pc= Lc.elem = (ElemType*) malloc( Lc.listsize*sizeof ( ElemType )); if (! Lc.elem)exit(OVERFLOW); //存储分配失败 pa_last = La.elem + La.length-1 ; pb_last = Lb.elem + Lb.length-1 ;

while ( pa<= pa_last && pb<= pb_last ) { if ( *pa<= *pb ) *pc++ = *pa++;

else *pc++ = *pb++; }

while ( pa<= pa_last ) *pc++ = *pa++; //将La的剩余元素插入 while ( pb<= pb_last ) *pc++ = *pb++;//将Lb的剩余元素插入 }

参考答案：

上述算法将归并后的数据元素存放在新的顺序表Lc中，顺序表La 和Lb不用变化，只是把顺序表La 和Lb中的数据元素一个个新插入到顺序表Lc的末尾，最多有La.length +Lb.length个数据元素要插入到顺序表Lc中，所以该算法的时间复杂度是O(La.length+Lb.length)。

2、已知顺序表La 和Lb，现在将存在于顺序表Lb中而不存在于顺序表La中的数据元素插入到顺序表La中去（如果发现顺序表La的空间不够，则需要扩大顺序表La）。具体做法是从顺序表Lb中依次取得每个数据元素，并依值在顺序表La中进行查访，若不存在，则插入之-这种操作称为顺序表的合并操作。请阅读下列顺序表的合并操作算法代码，分析该算法的时间复杂度，并作简要解释。 void union(List &La, List Lb) { ElemType e;

int La_len, Lb_len, i;

La_len = ListLength(La); //求顺序表的长度 Lb_len = ListLength(Lb);

for (i = 1; i <= Lb_len; i++) {

GetElem(Lb, i, e); //依次取Lb中第i个数据元素赋给e

if (!LocateElem(La, e, equal ) //依值e在顺序表La中进行查访

ListInsert(La, ++La_len, e);//La中不存在和 e 相同的数据元素，则在La的最后面插入

} }

参考答案：

在顺序表La中查访是否存在和Lb中第i个数据元素（值为e）相同的数据元素的方法是: 令e和La中的数据元素逐个比较。若La中存在和e相同的数据元素ai，则比较次数为

i(1≤i≤La.length), 否则为La.length，即算法LocateElem的时间复杂度为O(La.length)。而最多有Lb.length个数据元素要插入到顺序表La中，由此，算法union的时间复杂度为: O(La.length×Lb.length) 。

4

3、线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。 参考答案：

链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

四、算法分析题 1、下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。

typedef struct node { int data; struct node *next; } linklist; void linklistcreate(___linklist _ * &head ) { for (i=1;i<=n;i++)

{ p=(linklist *)malloc(sizeof(linklist)); scanf(“%d”,&(p->data)); p->next= NULL; if(i==1) head=q=p;

else { q->next=p;____ _ q=p _____;} }

}

2、下面的结构体定义了双向链表的节点结构。请分析如下程序代码，填写其中缺少的语句代码：

typedef struct node { int data；

struct node *last; struct node *next; } Node;

void deleteOne (Node *head, int target) { Node *p = head?next; while (p != NULL)

{ if (p?data != target) ____ p = p?next _____; else {

if (p?next != NULL) p?next?last = ____ p?last _____; p?last?next __ = p?next; free(p);

} } }

3、说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首结点的

5