第 2 章 线性表 2005-07-14 第 2 章 线性表 课后习题讲解 1. 填空 ⑴ 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（ ）个元素，具体移动元素的个数与（ ）和（ ）有关。 【解答】表长的一半，表长，该元素在表中的位置 ⑵ 顺序表中第一个元素的存储地址是 100，每个元素的长度为 2，则第5 个元素的存储地址是（ ）。 【解答】108 【分析】第5 个元素的存储地址=第1 个元素的存储地址＋(5－1)× 2=108 ⑶ 设单链表中指针 p 指向结点 A，若要删除 A 的后继结点（假设 A 存在后继结点），则需修改指针的操作为（ ）。 【解答】p->next=(p->next)->next ⑷ 单链表中设置头结点的作用是（ ）。 【解答】为了运算方便 【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 ⑸ 非空的单循环链表由头指针 head 指示，则其尾结点（由指针 p 所指）满足（ ）。 【解答】p->next=head 【分析】如图 2-8 所示。 ⑹ 在由尾指针 rear 指示的单循环链表中，在表尾插入一个结点 s 的操作序列是（ ）；删除开始结点的操作序列为（ ）。 【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图 2-9 所示： ⑺ 一个具有n 个结点的单链表，在指针p 所指结点后插入一个新结点的时间复杂度为（ ）；在给定值为x 的结点后插入一个新结点的时间复杂度为（ ）。 【解答】Ο(1)，Ο(n) 【分析】在p 所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x 的结点后插入一个新结点需要先查找值为x 的结点，所以时间复杂度为Ο(n)。 ⑻ 可由一个尾指针唯一确定的链表有（ ）、（ ）、（ ）。 【解答】循环链表，循环双链表，双链表 2. 选择题 ⑴ 线性表的顺序存储结构是一种（ ）的存储结构，线性表的链接存储结构是一种（ ）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】参见 2.2.1。 ⑵ 线性表采用链接存储时，其地址（ ）。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。 ⑶ 单...
VIP
