第二章线性表答案

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 若某线性表最常用的操作是存取任一指定序 号的元素和

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

3、间。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. 线

4、性表的表元存储方式有（顺序）和链接两 种。试指出下列各表中使用的是何种存储方式：表1是（顺序）存储方式；表2是（循环链接）存储方式；表3是（单向链接）存储方式；表4是（双 向链接）存储方式。表左的s指向起始表 丿元。表 元 编 号货号数量表 元 间 联 系16184022205233103154450120557811766901240表1表 元货号数t表 元 间编号量联 系16184052205213103154450120257811766901243表2s f表表元编号货号数量元 间 联系16184052205213103156045012057811746901243表3s >表

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

6、 (2 ) ,(3) D. (2 )13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复 杂度为(C ) (1<=i<=n+1)。A. 0(0)B. O(1)C.O(n)D. O(n 2)14. 对于顺序存储的线性表，访问结点和增加、 删除结点的时间复杂度为(C )。A. O(n) O(n) B. O(n) 0(1)C.0(1)0( n)D. 0(1) 0(1),an )以链接方式存储C )15 .线性表(a1,a2,时，访问第i位置元素的时间复杂性为(C 0(n )D .0A .0( i) B .0( 1 )(i-1 )16(.非空的循环单链表

7、A )。head 的尾结点p满足17pin k=headC. p=NILB . p.link=NIL p= head.循环链表H的尾结点P的特点是(A. P.NEXT=HB . P.NEXT=H. NEXTC. P=H D . P=H.NEXT18 在一个以h为头的单循环链中，p指针 指向链尾的条件是（A）A. p.n ext=hB. p.n ext=NILC. p人.next. 人 next=h D. p 人.data=-1二、判断I. 链表中的头结点仅起到标识的作用。（X ）2顺序存储结构的主要缺点是不利于插入或删 除操作。（V ）3 .线性表采用链表存储时，结点和结点内部的 存储空间可以

8、是不连续的。（V ）4顺序存储方式插入和删除时效率太低，因此 它不如链式存储方式好。（X）5.对任何数据结构链式存储结构一定优于顺序 存储结构。（X ）6 .顺序存储方式只能用于存储线性结构。（X ）7 集合与线性表的区别在于是否按关键字排 序。（X ）8. 所谓静态链表就是一直不发生变化的链表。（x ）9. 线性表的特点是每个元素都有一个前驱和一 个后继。（x ）10. 取线性表的第i个元素的时间同i的大小有关.（x ）11. 循环链表不是线性表（ X ）12. 线性表只能用顺序存储结构实现。（X ）13. 线性表就是顺序存储的表。（x ）14 为了很方便的插入和删除数据，可以使用 双向链表

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

10、a为y的新结点， 若将结点y插入结点x之后，则需要执行以下 语句:p ；px->next=py_；4 .在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时，需向后移动n-i+1_ _ 个元素。5 .在单链表中设置头结点的作用是主要是使插入和删除等操作统一，在第一个元素之前插 入元素和删除第一个结点不必另作判断。另外, 不论链表是否为空，链表指针不变。 。6 .对于一个具有n个结点的单链表，在已知的 结点*p后插入一个新结点的时间复杂度为0(1,在给定值为x的结点后插入一个新结点的时间复杂度为_O(n) _。7 根据线性表的链式存储结构中每一个结点包 含的指

11、针个数，将线性链表分成单链表 和多重链表 ;而又根据指针 的连接方式，链表又可分成动态链表和_静态链表。8 .在双向循环链表中，向p所指的结点之后插 入指针f所指的结点，其操作是仁 、仁 、P 、p->next=f;o10 链接存储的特点是利用指针来表示数据元素之间的逻辑关系。11顺序存储结构是通过 物理上相邻 表示元素之间的关系的；链式存储结构是 通过 指针 表示元素之间的关系的。12. 对于双向链表,在两个结点之间插入一个新 结点需修改的指针共 4_ 个，单链表为 2_ 个。13. 循环单链表的最大优点是： 从任一结点出发都可访问到链表中每一个元素 。14. 已知指针p指向单链表L中

12、的某结点，贝I删除其后继结点的语句是： q=p->n ext:p->n ext=q->n ext;delete q; 15. 带头结点的双循环链表L中只有一个元素 结点的条件是：L->n ext->n ext=L或者L->next->prior=l或者L->prior- >n ext=L或者L->prior->prior=L 16. 在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null17. 带头结点的双循环链表L为空表的条件是：L&&l>pricr=l 。18. 在单链表p结点

13、之后插入s结点的操作是:_ s。四应用题1 .线性表有两种存储结构：一是顺序表，二是 链表。试问：（1）如果有n个线性表同时并存，并且在处理 过程中各表的长度会动态变化，线性表的总数也 会自动地改变。在此情况下，应选用哪种存储结 构？为什么？答：选链式存储结构，它可动态申请内存空间， 不受长度（即表中元素个数）的影响，插入、删 除复杂度为0（1）（2）若线性表的总数基本稳定，且很少进行插 入和删除，但要求以最快的速度存取线性表中的 元素，那么应采用哪种存储结构？为什么？答：选取顺序结构，顺序表可以随机存取， 时间复杂度为0 （1 ）。2 .线性表的顺序存储结构具有三个弱点： 其一, 在作插入或

14、删除操作时，需移动大量元素；其二, 由于难以估计，必须预先分配较大的空间，往往 使存储空间不能得到充分利用；其三，表的容量 难以扩充。线性表的链式存储结构是否一定都能 够克服上述三个弱点，试讨论之。答：链式存储结构一般说克服了顺序存储结构的 三个弱点。首先，插入、删除不需移动元素，只 修改指针，时间复杂度为 0(1);其次，不需要 预先分配空间，可根据需要动态申请空间；其三, 表容量只受可用内存空间的限制。其缺点是因为 指针增加了空间开销，当空间不允许时，就不能 克服顺序存储的缺点。3 若较频繁地对一个线性表进行插入和删除操 作，该线性表宜采用何种存储结构？为什么？ 答：采用链式存储结构，它根

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