CSP初赛 第14节 链表

第二章 程序设计基础知识
本题库配套信息学奥赛一本通(初赛真题解析)第79页-第82页真题在线评测。
本套题目共9题,满分45分。
需要下载错题集微信联系tony老师:makytony
*
您的姓名:
一、单项选择题(共7题,每题5分,共计35分;每题有且仅有一个正确选项)
*
1.链表不具有的特点是()。
A.不必事先估计存储空间
B.可随机访问任一元素
C.插入删除不需要移动元素
D.所需空间与线性表长度成正比
*
2.线性表若采用链表存储结构,要求内存中可用存储单元地址()。
A.必须连续
B.部分地址必须连续
C.一定不连续
D.连续不连续均可
*
3.在含有n个元素的双向链表中查询是否存在关键字为k的元素,最坏情况下运行的时间复杂度是()。
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
*
4.对长度为n的有序单链表,若检索每个元素的概率相等,则顺序检索到表中任一元素的平均检索长度为()。
A.n/2
B.(n+1)/2
C.(n-1)/2
D.n/4
*
5.有以下结构体说明和变量定义,如图所示,指针p、q、r分别指向一个链表中的三个连续结点。

现要将q和r所指结点的先后位置交换,同时要保持链表的连续,以下程序段中错误的是()。*
A.q->next = r->next; p->next = r; r->next = q;
B.p->next = r; q->next = r->next; r->next = q;
C.q->next = r->next; r->next = q; p->next = r;
D.r->next = q; q->next = r->next; p->next = r;
*
6.双向链表中有两个指针域 llink 和 rlink,分别指向该结点的前驱及后继。设 p 指向链表中的一个结点,它的左右结点均非空。现要求删除结点 p,则下面语句序列中错误的是()。
A. p->rlink->llink = p->rlink;p->llink->rlink = p->llink; delete p;
B. p->llink->rlink = p->rlink; p->rlink->llink = p->llink; delete p;
C. p->rlink->llink = p->llink;p->rlink->llink->rlink = p->rlink; delete p;
D. p->llink->rlink = p->rlink;p->llink->rlink->llink = p->llink; delete p;
*
7.双向链表中有两个指针域,llink和rlink,分别指回前驱及后继,设p指向链表中的一个结点,q指向一待插入结点,现要求在p前插入q,则正确的插入为()。
A.p->llink = q; q->rlink = p; p->llink->rlink = q; q->llink = p->llink;
B.q->llink = p->llink; p->llink->rlink = q; q->rlink = p; p->llink = q->rlink;
C.q->rlink = p; p->rlink = q; p->llink->rlink = q; q->rlink = p;
D.p->llink->rlink = q; q->rlink = p; q->llink = p->llink; p->llink = q;
二、不定项选择题(共2题,每题5分,共计10分;每题有一个或多个正确选项,多选或少选均不得分)
*
1.在带尾指针(链表指针clist指向尾结点)的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有2个以上的结点。下面哪些说法是正确的():【多选题】
A.如果p指向一个待插入的新结点,在头部插入一个元素的语句序列为:p->next = clist->next; clist->next = p;
B.如果p指向一个待插入的新结点,在尾部插入一个元素的语句序列为:p->next = clist;clist->next = p;
C.在头部删除一个结点的语句序列为:p = clist->next; clist->next = clist->next->next; delete p;
D.在尾部删除一个结点的语句序列为。p = clist; clist = clist ->next; delete p;
*
2.双向链表中有两个指针域 llink 和 rlink,分别指向该结点的前驱及后继。设p指向链表中的一个结点,他的左右结点均为非空。现要求删除结点 p,则下列语句序列中正确的是()。【多选题】
A. p->rlink->llink=p->rlink;p->llink->rlink=p->llink; delete p;
B. p->llink->rlink=p->rlink;p->rlink->llink = p->llink; delete p;
C. p->rlink->llink = p->llink;p->rlink->llink ->rlink = p->rlink; delete p;
D. p->llink->rlink = p->rlink;p->llink->rlink->llink = p->llink; delete p;
问卷星提供技术支持
举报