2.2.1　概念题

1. 线性表的静态链表存储结构与顺序存储结构相比优点是( )。

A. 所有的操作算法实现简单　B. 便于随机存取

C. 便于插入和删除　　　　　 D. 便于利用零散的存储器空间

【解答】 根据链表的优点，选C。

2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为( )。

A. O(log2n) 　　B. O(1) 　　C. O(n)　　 D. O(n2)

【解答】 在第i个位置上插入新元素，需要从最后一个元素开始后移直到第i个元素后移为止，后移元素的次数为n-i+1，也即时间复杂度为O(n)，所以选C。

3. 将图2-6所示的s所指结点加到p所指结点之后，其语句应为( )。

图2-6　插入结点示意图

A. s-＞next=p+1; p-＞next=s;　　　　B.(*p).next=s; (*s).next=(*p).next;

C. s-＞next=p-＞next;p-＞next=s-＞next;　　D.s-＞next=p-＞next;p-＞next=s;

【解答】 A错在s-＞next=p+1,因为p+1作为指向后继结点的地址是错误的；B的错误是前后两个语句的顺序颠倒；C错在p-＞next=s-＞next,因为p-＞next与s-＞next都指向p的原后继结点，这导致了结点并未插入链表中。因此，选D。

4. 在一双向链表存储结构中，删除p所指的结点时须修改指针( )。

【解答】 根据图2-7可知应选A。

A. p-＞next-＞prior=p-＞prior;p-＞prior-＞next=p-＞next;

B. p-＞next= p-＞next-＞next；p-＞next-＞prior=p；

C. p-＞prior-＞next=p;p-＞prior=p-＞prior-＞prior;

D. p-＞prior=p-＞next-＞next;p-＞nexr=p-＞prior-＞prior;

图2-7　双向链表删除p结点示意图

5. 在双向循环链表中，在p指针所指的结点后插入一个指针q，指向新结点，其修改指针的操作是( )。

A. p-＞next=q;q-＞prior=p;p-＞next-＞prior=q;q-＞next=q;

B. p-＞next=q;p-＞next-＞prior=q;q-＞prior=p;q-＞next=p-＞next;

C. q-＞prior=p;q-＞next=p-＞next;p-＞next-＞prior=q;p-＞next=q;

D. q-＞next=p-＞next;q-＞prior=p;p-＞next=q;q-＞next=p;

【解答】 根据图2-8所示，在双向循环链表中插入一个结点结点的要点有二：①首先修改待插入q的前趋和后继指针；②其次修改p的后继结点的前趋指针(prior)，然后再修改p 的后继指针(next)。这两个操作的顺序不能颠倒，由此可知选C。

图2-8　双向链表插入结点示意图

6. 以下说法中错误的是( )。

A. 对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表

B. 对单链表来说，只有从头结点开始才能扫描表中全部结点

C. 双链表的特点就是找结点的前趋和后继都很容易

D. 对双链表来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在后继结点的前趋指针中

【解答】　A错，对循环链表来说，从表中任意一个结点出发都能通过后移操作扫描整个循环链表；因无前趋指针，故不能进行前移操作，因此选A。

7. 以下说法中正确的是( )。

A. 顺序存储方式的优点是存储密度大且插入、删除运算效率高

B. 链表的每个结点中都恰好包含一个指针

C. 线性表的顺序存储结构优于链式存储结构

D. 顺序存储结构属于静态结构，而链式结构属于动态结构

【解答】 A错，顺序存储方式的删除和插入运算效率低；B错，双向链表每个结点有两个指针；C错，顺序与链式这两种存储结构各有其优、缺点；D对，故选D。

8. 单链表中设置头结点的作用是( )。

【解答】 不管单链表是否为空表，头指针均不空，使得对单链表的操作在各种情况下均统一。

9. 在一个循环单链表中，表尾结点的指针域与表头指针值( )。

【解答】 相同

10. 单链表表示法的基本思想是用( )表示结点间的逻辑关系。

【解答】 指针

11. 对一个线性表分别进行遍历和逆置运算，其最好的时间复杂性量级分别为( )和( )。

【解答】遍历时间的量级为O(n),进行逆置运算时，顺序表的时间要小于单链表的时间，其量级也为O(n), 故填O(n),O(n)。

12. 线性表的顺序存储具有三个弱点:其一,在作插入或删除操作时,需要移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之：

【解答】 不一定。由于链式存储需要额外的空间来存储指针，所以要比顺序存储多占用空间。在空间允许的情况下，链式存储结构可以克服顺序存储结构的弱点，但空间不允许时，链式存储结构会出现新的问题。

13. 链表所表示的元素是否有序？如果有序，则有序性体现在何处？链表所表示的元素是否一定要在物理上相邻？有序表的有序性又如何理解?

【解答】 链表所表示的元素是有序的，其有序性体现在逻辑上有序，即按指针指向的顺序有序。链表所表示的元素在物理上不一定相邻，但也可以相邻。有序表的有序性不仅体现在逻辑结构上有序，而且在物理结构上也有序。

14. 用线性表的顺序存储结构来描述一个城市的设计和规划是否合适?为什么?

【解答】 不合适。因为一个城市的设计和规划涉及非常多的项目，比较复杂，需要经常改动、扩充和删除各种信息，这样才能适应不断发展的需要，所以顺序表不能很好地适应其需要。

15. 设A是一个线性表(a₁，a₂，…，a_n),采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数是多少？若元素插在a_i和a_i+1之间 (0≤i≤n-1) 的概率为，则平均每插入一个元素所要移动的元素个数又是多少？

【解答】 在等概率的前提下，平均每插入一个元素需要移动的元素个数为：

若元素插在a_i和a_i+1之间 (0≤i≤n-1) 的概率为，则平均每插入一个元素需要移动的元素个数为：