2.3练习题及参考答案.doc

《2.3练习题及参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、一定是不连续的D.连续或不连续都可以5.带头结点的单链表为空的判定条件是()。A.head==NULLB.head->next==NULLC.head->next=headD.head!=NULL6.不带头结点的单链表head为空的判定条件是()。A.head==NULLB.head->next==NULLC.head->next=headD.head!=NULL7.非空的循环单链表head的尾结点P满足（）。A.p->next==NULLB.p==NULLC.p->next==headD.p==head8.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A.O

3、(1)B.O(n)C.O(n2)D.O(log2n)9.在一个单链表中，若删除p所指结点的后继结点，则执行（）。A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;C.p->next=p->next;D.p=p->next->next;10.在一个单链表中，若在p所指点结点之后插入s所指结点，则执行（）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，则执行（）。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、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->llink;C.q->llimk=p->rlink;q->rlink=p;p->link->rlink=q;p->llink=q;D.以上都不对13.如题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（）A．p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;B.p->rlink=s

6、;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;14.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行（）操作与链表的长度无关。A.删除单链表中的第一个元素B.删除单链表中最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素二.填空题1.在线性结构中，第一个

7、结点＿＿＿＿前趋结点，其余每个结点有且只有＿＿＿＿个前趋结点。2.在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿＿元素，具体移动的元素个数与＿＿＿＿在有关。3.已知L是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：(1)表首插入S结点的语句序列是＿＿＿＿。(2)表尾插入S结点的语句序列是＿＿＿＿。①P->next=S;②P=L;③L=S;④P->next=S->next;⑤S->next=P-