p=p*x;}

return(p);

}

算法的时间复杂度：T(n)=O(n)

第 2

章线性表

习题

1.填空：

(1)在顺序表中插入或删除一个元素，需要平均移动

一半

元素，具体移动的元素个数与

插

入或删除的位置

有关。

(2)线性表有

顺序和链式

两种存储结构。在顺序表中，线性表的长度在数组定义时就已经

确定，是

静态

“

”

保存，在链式表中，整个链表由头指针来表示，单链表的长度是

动态

保

存。
(3)在顺序表中，逻辑上相邻的元素，其物理位置＿

一定

＿＿＿＿＿相邻。在单链表中，

逻辑上相邻的元素，其物理位置

不一定

相邻。

(4)在带头结点的非空单链表中，头结点的存储位置由

头指针

指示，首元素结点的存储位

置由

头结点

指示，除首元素结点外，其它任一元素结点的存储位置由

其直接前趋的 next

域

指示。

2.选择题

(1) A
(2) 已知 L 是无表头结点的单链表，且 P 结点既不是首元素结点，也不是尾元素结点。按
要求从下列语句中选择合适的语句序列。
a. 在 P 结点后插入 S 结点的语句序列是：

E、A

。

b. 在 P 结点前插入 S 结点的语句序列是：

H、L、I、E、A

。

c. 在表首插入 S 结点的语句序列是：

F、M

。

d. 在表尾插入 S 结点的语句序列是：

L、J、A、G

。

供选择的语句有：

A P->next=S;
B P->next= P->next->next;
C P->next= S->next;
D S->next= P->next;
E S->next= L;
F S->next= NULL;
G Q= P;
H while (P->next!=Q) P=P->next;
I while (P->next!=NULL) P=P->next;
J P= Q;
K P= L;
L L= S;