第2章    线性表

一  选择题

1．下述哪一条是顺序存储结构的优点？（  A ）

A．存储密度大  B．插入运算方便  C．删除运算方便  D．可方便地用于各种逻辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个？（  B  ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素      B．字符      C．数据元素     D．数据项         E．信息项

4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（  A  ）存储方式最节省时间。

A．顺序表      B．双链表        C．带头结点的双循环链表     D．单循环链表

5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（  D  ）存储方式最节省运算时间。

A．单链表     B．仅有头指针的单循环链表     C．双链表       D．仅有尾指针的单循环链表

6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(  D  )最节省时间。

A. 单链表   B.单循环链表   C. 带尾指针的单循环链表   D.带头结点的双循环链表

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（  D  ）存储方式最节省运算时间。

A．单链表      B．双链表     C．单循环链表     D．带头结点的双循环链表

8. 静态链表中指针表示的是（  BC  ）.

A． 内存地址       B．数组下标     C．下一元素地址      D．左、右孩子地址

9. 链表不具有的特点是（  C  ）

A．插入、删除不需要移动元素  B．可随机访问任一元素

 C．不必事先估计存储空间  D．所需空间与线性长度成正比

10. 下面的叙述不正确的是（ BC   ）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比

    B. 线性表在链式存储时，查找第i个元素的时间同i的值无关

C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比

D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

11. 线性表的表元存储方式有(顺序)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(顺序)存储方式；表2是(循环链接)存储方式；表3是(单向链接)存储方式；表4是(双向链接)存储方式。表左的s指向起始表元。                                                                    

表元编号	货号	数量	表元间联系
1	618·	40	2
2	205	2	3
3	103	15	4
4	501	20	5
5	781	17	6
6	901	24	0

表1

s→
                                              

表元编号	货号	数量	表元间联系
1	618·	40	5
2	205	2	1
3	103	15	4
4	501	20	2
5	781	17	6
6	901	24	3

表2

 s→
                                       

表元编号	货号	数量	表元间联系
1	618·	40	5
2	205	2	1
3	103	15	6
4	501	20	0
5	781	17	4
6	901	24	3

表3

 s—>
                                     

表元编号	货号	数量	表元间联系 1         2
1	618·	40	5         2
2	205	2	1         0
3	103	15	4         6
4	501	20	0         3
5	781	17	6          1
6	901	24	3          5

表4

s→
   供选择的答案：

A.连续  B.单向链接  C.双向链接   D.不连接  E.循环链接

F.树状   G.网状   H.随机  I.顺序  J.顺序循环

12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

   (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

   (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（  B  ）

 A．（1），（2）      B．（1）       C．（1），（2）,(3)      D.（2）

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

A. O(0)      B. O(1)         C. O(n)          D. O(n²)

14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（  C  ）。

A．O(n)  O(n)     B. O(n)  O(1)       C. O(1)  O(n)        D. O(1) O(1)

15．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C   ）

A．O（i）     B．O（1）      C．O（n）       D．O（i-1）

16．非空的循环单链表head的尾结点p满足（ A   ）。

A．p.link=head       B．p.link=NIL         C．p=NIL     D．p= head

17．循环链表H的尾结点P的特点是（  A  ）。

    A．P.NEXT=H         B．P.NEXT= H.NEXT        C．P=H      D．P=H.NEXT

18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（A）

 A. p.next=h    B. p.next=NIL  C. p＾.next.＾next=h   D. p＾.data=-1

二、判断

1. 链表中的头结点仅起到标识的作用。(  × )

2. 顺序存储结构的主要缺点是不利于插入或删除操作。(√ )

3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(  √  )

4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(  × )

5. 对任何数据结构链式存储结构一定优于顺序存储结构。(× )

 6．顺序存储方式只能用于存储线性结构。(  ×  )

7．集合与线性表的区别在于是否按关键字排序。( ×  )

8. 所谓静态链表就是一直不发生变化的链表。( ×  )

9. 线性表的特点是每个元素都有一个前驱和一个后继。( ×  )

10. 取线性表的第i个元素的时间同i的大小有关. (  ×  )

11. 循环链表不是线性表. (  ×  )

12. 线性表只能用顺序存储结构实现。(  × )

13. 线性表就是顺序存储的表。(  ×  )

14．为了很方便的插入和删除数据，可以使用双向链表存放数据。(  √  )

15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(  ×  )

16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 (  √ ) 

 

三、填空

1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用____顺序___存储结构。

2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是____n-1/2____。

3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:___py->next=px->next___； ____px->next=py__;

4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动____n-i+1____个元素。

5．在单链表中设置头结点的作用是___主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。_____。

6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___o(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为___O(n)_____。

7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成___单链表_____和___多重链表____；而又根据指针的连接方式，链表又可分成____动态链表____和___静态链表_____。

8． 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是____f->next=p->next;___、___f->next=p;____、___p->next->prior=f;____、____p->next=f;____。

10．链接存储的特点是利用____指针____来表示数据元素之间的逻辑关系。

11.顺序存储结构是通过____物理上相邻____表示元素之间的关系的;链式存储结构是通过_____指针___表示元素之间的关系的。

12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ___4___个，单链表为____2___个。

13. 循环单链表的最大优点是：____从任一结点出发都可访问到链表中每一个元素____。

14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：___q=p->next; p->next=q->next;delete q;_____

15. 带头结点的双循环链表L中只有一个元素结点的条件是：___ L->next->next==L  或者L->next->prior==L 或者L->prior->next==L或者L->prior->prior==L_____

16. 在单链表L中，指针p所指结点有后继结点的条件是：__ p->next!=null  

17.带头结点的双循环链表L为空表的条件是：____ L->next==L &&L->prior==L ____。

18. 在单链表p结点之后插入s结点的操作是：__ s->next=p->next;p->next=s _____。

 

四  应用题

1．线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？

答：选链式存储结构，它可动态申请内存空间，不受长度（即表中元素个数）的影响，插入、删除复杂度为O(1)

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？

    答：选取顺序结构，顺序表可以随机存取，时间复杂度为O（1）。

 

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

答：链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

 

3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？

答：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。

 

4．线性结构包括___线性表___、___栈___、___队列____和___串____。线性表的存储结构分成___顺序存储结构___和____链式存储结构__。

 

5．线性表（a₁，a₂，…，a_n）用顺序映射表示时，a_i和a_i+1（1<=i<n〉的物理位置相邻吗？链接表示时呢？

答：顺序映射时，a_i与a_i+1的物理位置相邻；链表表示时a_i与a_i+1的物理位置不要求相邻。

 

6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。

答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。

 

7. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?

答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。

 

8. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？

答：链表逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。