文档介绍:Ch3链表 (共18题,11道算法设计题)一、选择题1、设单链表中结点的结构为(data,link)。已知指针q所指结点是指针p所指结点的直接前驱,若在*q与*p之间插入结点*s,则应执行下列哪一个操作? (1)s->link=p->link;p->link=s; (2)q->link=s;s->link=p;(3)p->link=s->link;s->link=p; (4)p->link=s;s->link=q;Key:(2)2、设单链表中结点的结构为(data,link)。已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列哪一个操作? (1)s->link=p; p->link=s; (2)s->link=p->link;p->link=s;(3)s->link=p->link;p=s; (4)p->link=s; s->link=p;Key:(2)3、设单链表中结点的结构为(data,link)。若想摘除结点*p的直接后继,则应执行下列哪一个操作? (1)p->link=p->link->link; (2)p=p->link;p->link=p->link->link;(3)p->link=p->link; (4)p=p->link->link;Key:(1)4、设单循环链表中结点的结构为(data,link),且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点,则应执行下列哪一个操作?s=rear;rear=rear->link;free(s);rear=rear->link;free(rear);rear=rear->link->link;free(rear);(4)s=rear->link->link;rear->link->link=s->link;free(s);Key:(4)5、设双向循环链表中结点的结构为(data,prior,next),且不带表头结点。若想在指针p所指结点之后插入指针s所指结点,则应执行下列哪一个操作? p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;Key:(4)二、简答题6、线性结构可用顺序表或链表存储。试问:(1)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下,应选用哪种存储表示?为什么?Key:应选用链接存储表示。如果采用顺序存储表示,必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快,必须平均分配空间。在程序运行过程中,有的表占用的空间增长得快,有的表占用空间增长得慢;有的表很快就用完了分配给它的空间,有的表才用了少量的空间,在进行元素的插入时就必须成片地移动其他的表的空间,以空出位置进行插入;在元素删除时,为填补空白,也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示,一个表的存储