(题)数据结构复习题.doc

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

1、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

2、，则应执行下列哪一个操作？（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->li

3、nk；Key：（1）4、设单循环链表中结点的结构为（data,link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？（1）s=rear；rear=rear->link；free（s）；5（1）rear=rear->link；free（rear）；（2）rear=rear->link->link；free（rear）；（4）s=rear->link->link；rear->link->link=s->link；free（s）；Key：（4）5、设双向循环链表中

4、结点的结构为（data,prior,next），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？（1）p->next=s；s->prior=p；p->next->prior=s；s->next=p->next；（2）p->next=s；p->next->prior=s；s->prior=p；s->next=p->next；（3）s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；（4）s->prior=p；s->next=p->ne

5、xt；p->next->prior=s；p->next=s；Key：（4）二、简答题6、线性结构可用顺序表或链表存储。试问：（1）如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？Key：应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，

6、在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。5如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表（包括表的总数可能变化）共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。（2）若表的总数基本稳定，且很少进行插入和删除，但要求以最快的

7、速度存取表中的元素，这时，应采用哪种存储表示？为什么？Key：应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。7、在单链表、双向链表和单循环链表中，若仅知道指针p指向某一结点，不知道表头指针，能否将结点*p从链表中删去？若可以，其时间复杂度各为多少？三、算法设计题8、设单循环链表中结点的结构为（data,link），且head是指向带表头结点的单循环链表的表头结点的指针。试编写一个算法，统计链表的长度（不计

8、入表头结点）。9、设A和B是两个单链表，表中的元素均按结点的值（整数）升序排列。试编写一个函数，将A和B归并成一个按结点的值降序排列的单链表C。要求辅助存储空间为O（1）。10、已知head为单链表的表头指针,链表中存储的都是整型数据，试写出实现下列运算的递归算法：（1）求链表中的最大整数。（2）求链表