贵州统招专升本《数据结构（C语言版第2版）》课后习题严蔚敏著第二章习题及答案

                               第 2 章线性表

1．选择题

（1）顺序表中第一个元素的存储地址是100 ，每个元素的长度为2，则第5个元素的地址是（    ）。

A．110      B．108      C．100       D．120

答案： B

解释：顺序表中的数据连续存储，所以第 5 个元素的地址为： 100+2*4=108 。

（2）在 n 个结点的顺序表中，算法的时间复杂度是O(1) 的操作是（    ）。

A．访问第i个结点（1≤i≤n）和求第 i 个结点的直接前驱（2≤i≤n）

B．在第i个结点后插入一个新结点（1≤i≤n）

C．删除第i个结点（1≤i≤n）

D．将n个结点从小到大排序

答案： A

解释： 在顺序表中插入一个结点的时间复杂度都是O(n 2) ，排序的时间复杂度为 O(n 2 ) 或 O(nlog 2n)。顺序表是一种随机存取结构，访问第 i 个结点和求第 i 个结点的直接前驱都可

以直接通过数组的下标直接定位，时间复杂度是O(1) 。

（3）向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（     ）。

A．8        B．63.5        C．63         D．7

答案： B

解释：平均要移动的元素个数为： n/2 。