第 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 的结点，所以时
