《数据结构》习题集线性表.doc

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

1、第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.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、

2、连续或不连续都可以。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、p==head8.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）。A、O(

3、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;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11.在一个单链表中，已知q是p的

4、前趋结点，若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;／／指向前趋结点的指针域structlinknode*rlink;／／指向后继结点的指针域}bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语

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

6、;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->llink=s;D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;1.在一个长度为n的单链表上，设有头和尾两个指针，执行（A，C，D）操作与链表的长度无关。A、删除单链表中的第一个元素B、删除单链表中最后一个元素C、在单链表第一个元素前插入一个新元素D、在单链表最后一个元素后插入一个新元素2

7、.线性结构中的一个结点代表一个（A）A、数据元素B、数据项C、数据D、数据结构3.非空线性表L=(a1,a2,…,ai,…,an)，下列说法正确的是（D）A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继4.顺序表是线性表的（B）A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构5.对于顺序表，以下