数据结构域算法设计-第二部分 线性表 答案教案

《数据结构域算法设计-第二部分 线性表 答案教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二部分线性表一、选择题1．关于顺序存储的叙述中,哪一条是不正确的(B)A.存储密度大B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的位置D.插入、删除操作不方便2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为(C)AO(n)BO(1)CO(m)DO(m+n)3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：(A)A访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）B在第i个结点（1<=i<=n）后插入一个新结点C删除第i个结点（1<=i<

2、=n）D将n个结点从小到大排序4．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：(B)（A）110（B）108（C）100（D）1205．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：(A)A）da+(i-1)*mB)da+i*mC)da-i*mD)da+(i+1)*m6．在具有n个结点的单链表中，实现（A）的操作，其算法的时间复杂度为O(n)。A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点C）删除开

3、始结点D）删除地址为p的结点的后继结点7．链表是一种采用（B）存储结构存储的线性表。（A）顺序（B）链式（C）星式（D）网状8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（D）（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以9．线性表Ｌ在（B）情况下适用于使用链式结构实现。（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂10．在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为

4、(  A)A.n-i+1       B.n-i C.i           D.i-111．线性表是（　A　）。a、一个有限系列，可以为空             b、一个有限系列，不能为空c、一个无限系列，可以为空             d、一个无限系列，不能为空12.（　A　）线性表。A.(孔子,诸葛亮,曹雪芹)B.{A,B,C,D}C.{10,11,12,13,14}D.(1,2,3,...)13.（　　）是表示线性数据结构的。A.循环链表B.邻接多重表C.孩子链表D.单链表14.将线性表的数据元素以（

5、B）结构存放,查找一个数据元素所需时间不依赖于表长。A.循环双链表B.哈希(Hash)表C.一维数组D.单链表15.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。（A）s->link=p;p->link=s;（B）s->link=p->link;p->link=s;（C）s->link=p->link;p=s;（D）p->link=s;s->link=p;16.在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾

6、的语句是(D)。（A）current->link=NULL(B)first->link=current（C）first=current(D)current->link=first17.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较(D)个结点。A.nB.n/2C.（n-1）/2D.(n+1)/218.在一个具有n个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为(B)。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)19.用链表表示线性表的优点是(  C)。A

7、.便于随机存取         B.花费的存储空间比顺序表少C.便于插入与删除      D.数据元素的物理顺序与逻辑顺序相同20.当需要随机查找线性表的元素时,宜采用(C)作存储结构。A.双向链表B.循环链表C.顺序表D.单链表21.线性表的链接实现有利于（ A ）运算。A、插入  b、读表元   c、查找  d、定位22.线性表采用链式存储时，其地址（D）。A 必须是连续的          B 部分地址是连续的C 一定是不连续的        D 连续与否均可以23.设单链表中指针p指着结点a，若要删除a之

8、后的结点（若存在），则需要修改指针的操作为（　A　）。A、p->next=p->next->next        b、p=p->nextC、p=p->next->next　　　　　　d、p->next=p24.向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（B）个元素。A、8B、63.5C、63D、725.向一个有127个元素的顺序表中删除一