数据结构第2篇作业.doc

第2章????线性表 一??选择题 1．下述哪一条是顺序存储结构的优点？（????） A．存储密度大??B．插入运算方便??C．删除运算方便??D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（????） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（????）的有限序列（n0）。 A．表元素??????B．字符??????C．数据元素?????D．数据项?????????E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（????）存储方式最节省时间。 A．顺序表??????B．双链表????????C．带头结点的双循环链表?????D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（????）存储方式最节省运算时间。 A．单链表?????B．仅有头指针的单循环链表?????C．双链表???????D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(????)最节省时间。 A.?单链表???B.单循环链表???C.?带尾指针的单循环链表???D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（????）存储方式最节省运算时间。 A．单链表??????B．双链表?????C． 单循环链表?????D．带头结点的双循环链表 8.?静态链表中指针表示的是（????）.? A．?内存地址???????B．数组下标?????C．下一元素地址??????D．左、右孩子地址 9.?链表不具有的特点是（????） A．插入、删除不需要移动元素??B．可随机访问任一元素 ?C．不必事先估计存储空间??D．所需空间与线性长度成正比 10.?下面的叙述不正确的是（????） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 ????B.?线性表在链式存储时，查找第i个元素的时间同i的值无关 C.?线性表在顺序存储时，查找第i个元素的时间同i?的值成正比 D.?线性表在顺序存储时，查找第i个元素的时间同i的值无关 11.? 12.(1)?静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 ???(2)?静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 ???(3)?静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（????） ?A．（1），（2）??????B．（1）???????C．（1），（2）,(3)??????D.（2） 13.?若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（????）(1=i=n+1)。 A. O(0)??????B. O(1)?????????C. O(n)??????????D. O(n2) 14.?对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（????）。 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位置元素的时间复杂性为（????） A．O（i）??????B．O（1）??????C．O（n）???????D．O（i-1） 16．非空的循环单链表head的尾结点p↑满足（????）。 A．p↑.link=head???????B．p↑.link=NIL?????????C．p=NIL?????D．p= head 17．循环链表H的尾结点P的特点是（????）。 ????A．P^.NEXT:=H?????????B．P^.NEXT:= H^.NEXT????????C．P:=H??????D．P:=H^.NEXT 18．在一个以?h?为头的单循环链中，p?指针指向链尾的条件是（ ） ?A. p＾.next=h????B. p＾.next=NIL??C. p＾.next.＾next=h???D. p＾.data=-1 19．完成在双循环链表结点p之后插入s的操作是（????）； A．?p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next; B．?p^.next^.priou:=s; p^.next:=s; s^.priou:=p