数据结构线性表练习及答案.doc

《数据结构线性表练习及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题1、用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（）A、当前结点所在的地址域B、指针域C、空指针域D、空闲域2、不带头结点的单链表head为空的判断条件是（）A、head==NULLB、head->next==NULLC、head->data==NULLD、head!=NULL3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（）A、s->next=p;q->next=s;B、p->next=s->next;s->next=p;C、q->next=s->next;s->next=p;D、p->next=s;s-

2、>next=q;4、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A、O（1）B、O（n）C、O（n2）D、O（nlog2n）5、一个单链表中，若删除p所指结点的后续结点，则执行（）A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p->next=p;D、p=p->next->next;6、已知一个顺序存储的基本线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为（）A、d1+(i-1)*mB、d1+i*mC、d1-i*mD、d1+(i+1)*m7、在n个结点的

3、顺序表中，算法的时间复杂度是O（1）的操作是（）A、访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)B、在第i个结点后插入一个新结点(1<=i<=n)C、删除第i个结点(1<=i<=n)D、将n个结点从小到大排序8、下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中，能正确完成要求的算法段是（）A、q->next=p;q->prior=p->prior;p->prior=q;p->prior->next=q;B、p->prior=q;q->next=p;p->prior->next=q;q->prior=p->pri

4、or;C、q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;D、以上都不对9、在循环双链表的p所指结点之后插入s所指结点的操作是（）A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B、p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C、s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D、s->prior=p;p->next->prior=s;s-

5、>next=p->next;p->next=s;10、从具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。A、nB、n/2C、(n-1)/2D、(n+1)/211、单链表的存储空间利用率（）A、大于1B、等于1C、小于1D、不能确定12、在顺序表中，有7个元素，设第1个元素的查找概率是1/4，第2个元素的查找概率是1/3，其余元素的查找概率相等，则整个顺序表的平均查找次数是（）次。A、44/12B、451/60C、36/12D、56/2413、顺序表的长度是（）。A、表中的存储空间数B、表中的数据元素个数C、存储空间数减去数据元素个数D、存储空间数加数

6、据元素个数14、在单链表中插入结点的时间复杂度是（）A、O（1）B、O（n）C、O（n2）D、O（log2n）二、填空题1、基本线性表有（顺序）和（链式）两种存储形式。2、在双链表中，每个结点有两个指针域，一个指向（前驱结点），另一个指向（后继结点）。3、按顺序存储方法存储的基本线性表称为（顺序表），按链表存储的基本线性表称为（链表）。4、顺序表相对于链表的优点有（随机存取）和（存储空间利用率高）。5、链表相对于顺序表的优点有（存储空间动态分配）和（插入删除操作效率高）。6、在n个结点的顺序表中插入一个结点需平均移动（N/2）个结点，具体的移动次数取决于（插入的位置）。7、在n个结点的顺

7、序表中删除一个结点需平均移动（(N-1)/2）个结点，具体的移动次数取决于（删除的位置）。8、在顺序表中访问任意一个结点的时间复杂度均为（1），因此，顺序表也称（随机存取或直接存取）的数据结构。9、在单链表中设置头结点的作用是（保护头指针）。10、顺序表中逻辑上相邻的元素，物理位置（一定）相邻。11、当对一个基本线性表进行插入和删除操作较频繁时，线性表应采用（链式）存储结构；当对线性表的操作不会引起它的变化时，线性应采用（顺序）存储