第二章线性表答案.docxVIP

第二章线性表答案 第2章线性表 一个选择题 1．下述哪一条是顺序存储结构的优点？（a） a、 高存储密度B.方便的插入操作C.方便的删除操作D.它可以方便地用于各种逻辑结构的存储和表示 2．下面关于线性表的叙述中，错误的是哪一个？（b）a．线性表采用顺序存储，必须占用一片连续的存储单元。b．线性表采用顺序存储，便于进行插入和删除操作。c．线性表采用链接存储，不必占用一片连续的存储单元。d．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（c）的有限序列（n0）。 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的值无关。有两种方法存储线性表的元素：顺序和链接。试着指出下表中使用的存储模式：表1是（顺序）存储模式；表2显示了（循环链接）存储模式；表3显示了（单向链接）存储模式；表4显示了（双向链接）存储模式。表格左侧的s指向起始表格元素。表元素编号123456表1s→ 表元件编号1234表元件触点5142表元件触点234560项目编号数量6182051035017819014021520724项目编号数量618205103501402152056表2S→ 781901172463表元编号123456表3S表元编号12345数量表元联系人12表元联系人516043项目编号6182051035017819014021520724项目编号618205103501781402155202252104603616表4S→ 9012435供选择的答案： 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(n2) 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=nilc。P=零。P=头17。循环链表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。下一个下一个=高清。p。数据=-1