《数据结构》第二章线性表习题.pdf

《数据结构》第二章线性表习题 本资源是《数据结构》第二章线性表习题，涵盖了线性表的基本概念、顺序表和链表的存储结构、线性表的操作等知识点。 一、线性表的基本概念 线性表是一种有限序列，可以为空或不为空。它是由零个或多个数据元素组成的一个序列，具有有限长度的性质。线性表可以为空，例如一个空的链表或顺序表。 二、顺序表和链表的存储结构 顺序表是一种连续存储的数据结构，每个元素占用固定大小的存储空间。链表是一种非连续存储的数据结构，每个元素占用不固定大小的存储空间。 在顺序表中，元素的存储地址是连续的，插入和删除操作需要移动元素；在链表中，元素的存储地址是非连续的，插入和删除操作可以在O(1)时间内完成。 三、线性表的操作 线性表的操作包括插入、删除、查找和遍历等。插入操作是指在线性表中插入一个新元素的过程，删除操作是指从线性表中删除一个元素的过程。查找操作是指在线性表中查找一个元素的过程，遍历操作是指从线性表中取出所有元素的过程。 四、线性表的应用 线性表在实际应用中非常广泛，例如，在数据库系统中，线性表可以用来存储数据记录；在编译器中，线性表可以用来存储符号表；在操作系统中，线性表可以用来存储进程控制块等。 五、习题解析 1. 线性表是 ________。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空 答案：A．一个有限序列，可以为空 2. 在一个长度为n 的顺序表中删除第i 个元素 (0<=i<=n) 时，需向前移动个元素。A．n-i B．n-i+l C．n-i-1 D． i 答案：C．n-i-1 3. 线性表采用链式存储时，其地址________。A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以 答案：B．一定是不连续的 4. 从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，需平均比较________个元素结点。A．n/2 B．n C．（n+1）/2 D．（n-1 ）/2 答案：A．n/2 5. 在双向循环链表中，在p 所指的结点之后插入s 指针所指的结点，其操作是____。A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 答案：B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; ...（省略）