《数据结构》习题集：第2章 线性表

《《数据结构》习题集：第2章 线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课后练习题第2章线性表第2章线性表一、选择题1.表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素个数为（A）。A.(N-1)/2B.NC.N+1D.N-1E.N/2F.(N+1)/2G.(N-2)/22.线性表是具有N个（C）的有限序列。A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（B）。A、正确的B、错误的C、不一定，与具体结构有关。4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（

2、D）。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。5.带头结点的单链表为空的判定条件是（B）。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head为空的判定条件是（A）。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head的尾结点P满足（C）。A、P->NEXT=NULLB、p=NULLC、p->next==headD

3、、p==head8.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）。A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P所指结点的后继结点，则执行（A）。A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（B）。A、s->next=p;p->next=s;B、s->next=p->next

4、;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11.在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（C）。A、s-next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12.假设双链表结点的类型如下：typedefstructlinknode{intdata;／／数据域structlinknode*llink;／／指向前趋结点的

5、指针域structlinknode*rlink;／／指向后继结点的指针域}bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（D）。A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;7/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第2章线性表B、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llinkC、q->ll

6、ink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q;D、以上都不对1.如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（D）。A、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;B、p->rlink->s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink;C、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->l

7、link=s;D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;2.在一个长度为n的单链表上，设有头和尾两个指针，执行（A，C，D）操作与链表的长度无关。A、删除单链表中的第一个元素B、删除单链表中最后一个元素C、在单链表第一个元素前插入一个新元素D、在单链表最后一个元素后插入一个新元素3.线性结构中的一个结点代表一个（A）A、数据元素B、数据项C、数据D、数据结构4.非空线性表L=(a1,a2,…,ai,…,an)，下列说法正确的是（D）A、每个元素都有一个直接前驱和直接后继

8、B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有