第二章线性表答案.docx

1、第二章线性表答案第2章 线性表一 选择题1下述哪一条是顺序存储结构的优点（ A ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（ C ）的有限序列（n0）。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. 静态链表中指

3、针表示的是（ 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是(顺序)存储方式

4、；表2是(循环链接)存储方式；表3是(单向链接)存储方式；表4是(双向链接)存储方式。表左的s指向起始表元。表元编号货号数量表元间联系16184022205233103154450120557811766901240表1s表元编号货号数量表元间联系16184052205213103154450120257811766901243表2s表元编号货号数量表元间联系16184052205213103156450120057811746901243表3s表元编号货号数量表元间联系1 21618405 2220521 03103154 64501200 3578117616901243 5表4s 供选择

5、的答案：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=inext=px-next_；

6、 _px-next=py_;4在一个长度为n的顺序表中第i个元素（1=inext=p-next;_、_f-next=p;_、_p-next-prior=f;_、_p-next=f;_。10链接存储的特点是利用_指针_来表示数据元素之间的逻辑关系。11.顺序存储结构是通过_物理上相邻_表示元素之间的关系的;链式存储结构是通过_指针_表示元素之间的关系的。12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _4_个，单链表为_2_个。13. 循环单链表的最大优点是：_从任一结点出发都可访问到链表中每一个元素_。14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_q=

7、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!=null17.带头结点的双循环链表L为空表的条件是：_L-next=L &L-prior=L_。18. 在单链表p结点之后插入s结点的操作是：_s-next=p-next;p-next=s_。四 应用题1线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有 n

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

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

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

11、后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。7. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。8. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表答：链表逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。