数据结构自学考试辅导--应用题.pdfVIP

数据结构自学考试辅导--应用题

数据结构自学考试练习题应用题

1.简述顺序表和链表存储方式的特点。

解:顺序表的优点是可以随机访问数据元素；缺点是大小固定，不

利于增减结点(增减操作需要移动元素)。链表的优点是采用指针方式增

减结点，非常方便(只需要改变指针指向，不移动结点)。其缺点是不能

进行随机访问，只能顺序访问；另外，每个结点上增加指针域，造成

额外存储空间增大。

2.在单链表和双向链表中，能否从任意结点出发访问到其他任何

一个结点?

在单链表中不能从任意结点（若结点不是第一结点）出发访问到

任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在

双链表中求前驱和后继都容易，从任何一个结点向前到第一结点，向

后到最后结点，可以访问到任何一个结点。

3.线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有n个线性表同时并存，并且在处理过程中各表的长度

会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪

种存储结构？为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求

以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什

么？

（1）选链式存储结构。它可动态申请内存空间，不受表长度（即

表中元素个数）的影响，插入、删除时间复杂度为O（1）。

（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O

（1）。

4.线性表的存储结构分成顺序存储结构（顺序表）和链式存储结

构（单链表）。请用类C语言描述这两种结构。

顺序表类型定义：

constmaxsize=顺序表的容量

typedefstruct

{datatypedata[maxsize];

intlast;

}sqlist;

SqlistL;

单链表类型定义：

typedefstructnode*pointer;

structnode

{datatypedata;

Pointernext;

};

typedefpointerlklist;

5.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除

操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大

的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩

充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨

论之。

链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插

入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不

需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可

用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允

许时，就不能克服顺序存储的缺点。6.若频繁地对一个线性表进行插

入和删除操作，则该线性表宜采用何种存储结构，为什么?

解:宜采用链式存储结构。因为采用链式结构存储线性表，插入和

删除操作需要从头指针起查找插入、删除结点的前驱结点，并修改这

些结点的指针域，查找过程需平均移动指针域为表长的一半；而采用

顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。

移动指针域操作比移动元素操作花费的时间少得多。

7.对链表设置头结点的作用是什么?(至少说出两条好处)

解其好处有：

(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中

任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结

点都有前驱结点(若链表没有头结点，则首元素结点没有前驱结点，在

其前插入结点和删除该结点时操作复杂些)。

(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此

空表与非空表的处理是一样的。

8.在单链表、双链表和单循环链表中，若仅知道指针p指向某结

点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时

间复杂度各为多少?

解:以下分三种链表讨论：

(1)单链表。当已知指针p指向某结点时，能够根据该指针找到其