第二章线性表答案

1、第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 ）存储方式最节省时

2、间。A顺序表B 双链表C带头结点的双循环链表D 单循环链表5 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D 仅有尾指针的单循环链表6 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D) 最节省时间。A.单链表B. 单循环链表C. 带尾指针的单循环链表D. 带头结点的双循环链表7 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。A单链表B 双链表C单循环链表D 带头结点的双循环链表8.静态链表中指针表示的是（BC

3、） .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 是 ( 顺序 ) 存储方式；表

4、 2 是( 循环链接 ) 存储方式；表 3 是 ( 单向链接 ) 存储方式；表 4 是 ( 双向链接 ) 存储方式。表左的 s 指向起始表元。表表元元数货号间编量联号系1618·4022205233103154450120557811766901240表 1s表表元元数货号间编量联号系1618·4052205213103154450120257811766901243表 2s 表表元元数货号间编量联号系1618·4052205213103156450120057811746901243表 3s >表元数表元间联系货号编量12号1618·405222

5、0521031031546450120035781176169012435表 4s 供选择的答案：A. 连续B. 单向链接C. 双向链接F. 树状G. 网状H. 随机I. 顺序D. 不连接 J. 顺序循环E. 循环链接12.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i 个元素的时间与i 无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ）A （ 1），（ 2）B（ 1）C（ 1），（ 2） ,(3)D. （2）13. 若长度为 n 的线性表采用

6、顺序存储结构， 在其第 i 个位置插入一个新元素的算法的时间复杂度为（C） (1<=i<=n+1)。A. O(0)B. O(1)C. O(n)D. O(n 2)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=headB p.link=

7、NILC p=NILD p= head17循环链表 H 的尾结点 P 的特点是（A ）。A P.NEXT=HB P.NEXT= H.NEXTC P=HD P=H.NEXT18在一个以h 为头的单循环链中， p 指针指向链尾的条件是（ A）A. p.next=hB. p.next=NILC. p .next. next=hD. p .data=-1二、判断1. 链表中的头结点仅起到标识的作用。( × )2.顺序存储结构的主要缺点是不利于插入或删除操作。( )3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好

8、。(× )5.对任何数据结构链式存储结构一定优于顺序存储结构。( × )6顺序存储方式只能用于存储线性结构。( × )7 集合与线性表的区别在于是否按关键字排序。(× )8. 所谓静态链表就是一直不发生变化的链表。( × )9. 线性表的特点是每个元素都有一个前驱和一个后继。( × )10. 取线性表的第 i 个元素的时间同 i 的大小有关 . ( × )11. 循环链表不是线性表 . ( × )12. 线性表只能用顺序存储结构实现。( × )13. 线性表就是顺序存储的表。 ( × )14 为

9、了很方便的插入和删除数据，可以使用双向链表存放数据。()15.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)16. 链表是采用链式存储结构的线性表 ,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( )三、填空1 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 _ 顺序 _ 存储结构。2 线性表 L= （ a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_n-1/2_。3 设单链表的结点结构为(data,next)为 x 的结点，指针py 指向 dat

10、a为 y行以下语句 :_py->next=px->next_，next的新结点；为指针域， 已知指针px,若将结点 y 插入结点_px->next=py_;指向单链表中datax 之后，则需要执4 在一个长度为动_n-i+1_n 的顺序表中第个元素。i 个元素（1<=i<=n）之前插入一个元素时，需向后移5 在单链表中设置头结点的作用是 _ 主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。_。6 对于一个具有_o(1)_,n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为在给

11、定值为x 的结点后插入一个新结点的时间复杂度为_O(n)_。7 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_ 多重链表 _ ；而又根据指针的连接方式，链表又可分成_ 和 _ 静态链表 _。_ 单链表动态链表8 在双向循环链表中 _f->next=p->next;_, 向p 所指的结点之后插入指针、_f->next=p;_f 所指的结点，其操作是、_p->next->prior=f;_、_p->next=f;_。10 链接存储的特点是利用_ 指针 _ 来表示数据元素之间的逻辑关系。11. 顺序存储结构是通过 _ 物理上相邻 _ 表示

12、元素之间的关系的 ; 链式存储结构是通过_ 指针 _ 表示元素之间的关系的。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->pr

13、ior->next=L或者L->prior->prior=L_16.在单链表L 中，指针p 所指结点有后继结点的条件是：_ p->next!=null17. 带头结点的双循环链表 L 为空表的条件是： _ L->next=L&&L->prior=L _。18. 在单链表 p 结点之后插入 s 结点的操作是：_ s->next=p->next;p->next=s _。四应用题1 线性表有两种存储结构：一是顺序表，二是链表。试问：（1 ）如果有 n 个线性表同时并存， 并且在处理过程中各表的长度会动态变化，数也会自动地改变。在此

14、情况下，应选用哪种存储结构？ 为什么？线性表的总答：选链式存储结构， 它可动态申请内存空间， 不受长度 （即表中元素个数） 的影响， 插入、删除复杂度为 O(1)（ 2 ）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？答：选取顺序结构，顺序表可以随机存取，时间复杂度为O（1）。2 线性表的顺序存储结构具有三个弱点：其一， 在作插入或删除操作时，需移动大量元素；其二，由于难以估计， 必须预先分配较大的空间， 往往使存储空间不能得到充分利用； 其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

15、答：链式存储结构一般说克服了顺序存储结构的三个弱点。 首先，插入、删除不需移动元素，只修改指针， 时间复杂度为 O(1) ；其次，不需要预先分配空间， 可根据需要动态申请空间；其三， 表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。3 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？答：采用链式存储结构， 它根据实际需要申请内存空间， 而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。4 线性结构包括_ 线性表 _ 、 _ 栈 _ 、 _ 队列 _ 和 _ 串 _ 。线性

16、表的存储结构分成 _ 顺序存储结构_ 和 _ 链式存储结构_ 。5 线性表（a 1 ， a 2， ， an ）用顺序映射表示时，a i 和a i+1（ 1<=i<n的物理位置相邻吗？链接表示时呢？答：顺序映射时，a i 与ai+1的物理位置相邻；链表表示时a i 与a i+1的物理位置不要求相邻。6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。答：在线性表的链式存储结构中， 头指针指链表的指针， 若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的， 放在第一元素结点之前， 其数据域一般无意义 （当然有些情况下也可存放链表的长度、 用做监视哨等等） ，有头结点后， 对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。 而且无论链表是否为空， 头指针均不为空。 首元结点也就是第一元素结点，它是头结点后边的第一个结点。7.在单链