数据结构与算法教程 习题答案作者 朱明方 吴及 第2章习题解答.doc

《数据结构与算法教程 习题答案作者 朱明方 吴及 第2章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第2章习题解答2.1从逻辑结构和存储结构的角度来看，顺序表属于什么结构？它有什么特点？［解答］所谓顺序表是指线性表的顺序表示方式，它属于存储结构。顺序表具有以下特点：①线性表中各元素存放在连续的存储单元中；②顺序表中各元素的顺序与它们在线性表中的逻辑顺序相同。也就是说，把线性表中各元素按照它们在线性表中的逻辑顺序依次存放于连续的存储单元中，即构成顺序表。由于顺序表中的元素是按照逻辑顺序存放在一块连续的存储空间的，其明显的优点是实现简单，也非常直观。但是数据元素的插入和删除操作需要移动表中的元素，从而会使运算的效率比较低；同时由于顺序表的存储空间是使用之前给定的，这样

2、会给表空间的扩充带来不便，而有时却又不能充分利用表空间。这就对顺序表的使用带来局限性，使得它不适合在表很大且表的长度经常变化的情况下使用。所以，只有在表不大或表建立起来以后其中的元素不太变化的情况下才适合采用顺序表。2.2栈中的元素具有什么性质？什么情况适合使用栈结构？举例说明。［解答］栈是只允许在表的一端进行插入与删除操作的特殊的线性表，表中允许作插入和删除操做的一端称之为栈顶，相应地，另一端称之为栈底。正是因为有这样的限制，使得栈中的数据元素具有“后进先出”的特性。即最先进栈的元素一定是最后出栈的元素。栈的特性决定了栈具有记忆“逆序”的功能，因为栈中元素出栈的顺

3、序就是入栈顺序的逆序。因此，凡是需要记忆“逆序”的情况，在计算机中处理时都可以使用栈结构来实现。比如，要按照与进入时相反的顺序返回，可以把进入步骤顺序入栈，然后按出栈的步骤依次返回即可；又如，拆卸与组装，只要把拆卸步骤顺序入栈，然后按出栈的步骤依次恢复即可。还有象程序的调用与返回，中断的调用与返回等要求按正、逆顺序处理的问题，计算机处理时都是利用栈来解决的。按照上述思路，实际问题中采用栈可以方便得到解决的问题很多：例如，若希望存储在计算机系统中的文件按存入的时间以“由近到远”的方式显示出来。此时只要依照文件存入的时间先后依次将各文件的目录项保存到栈中，然后根据目录项

4、的出栈顺序依次显示各文件内容，就可以达到目的。又如，要想按照时间“由近到远”的方式显示出所收到的手机短信。也可以借助栈，把收到的手机短信依次入栈，然后从栈中逐条退出短信并将其显示出来即可。2.3队列中的元素具有什么性质？处理哪类问题适合用队列结构？试举例说明。［解答］队列是允许在表的一端进行插入操作在表的另一端进行删除操作的特殊的线性表，表中允许进行插入操作的一端称之为队尾，允许进行删除操作的一端称之为队头。正是因为有这样的限制，使得队列中的数据元素具有“先进先出”的特性。即最早进入队列的元素一定是最先出队列的元素。队列的结构特性使它具有“记忆顺序”作用。因此，在计

5、算机中凡是需要“按次序进行”的处理和操作都可以采用队列这种结构来解决。实际问题中确定要按“先到先服务”或“先发生先处理”的原则进行处理的情况，利用队列结构很容易得到解决。由于实际问题中需要按“先到先服务”或“先发生先处理”15的原则进行处理的情况很多，因此队列结构的应用非常广泛。例如，医院里挂号就诊，就是一个需要按“先到先服务”的原则进行处理的问题。该问题在计算机中处理时，只要把患者所挂的号及相应的信息(单位、姓名、性别、年龄等)按照挂号顺序依次入队，然后按照出队号码顺序让患者就诊，即可达到先挂号先就诊的目的。又如，厂家对出厂产品的发货管理，通常应该按照先生产的产品

6、先发出去的原则发货；若采用计算机系统进行管理，则可以用队列把产品的批号按生产时间依次入队，发货时则从队头取出产品批号，并将该批号的产品发出即可达到目的。2.4什么是队列的假溢出？可以采用哪些有效的方法来解决假溢出问题？［解答］所谓假溢出是指，一般顺序队列中队头方向有空闲单元，但因为队尾方向已经没有空闲单元而致使新元素不能入队的情况。图2-1所示就是队列处于假溢出状态的情形。图2-1顺序队列中的假溢出状态顺序队列的假溢出现象，是因为在顺序队列中数据元素入队时队尾指针移动和数据元素出队时队头指针移动方向相同，也就是说，从队列中删除数据元素时其空闲单元向队尾方向扩展，向队

7、列中插入数据元素时其填满单元也向队尾方向扩展，这样就致使删除数据元素后的空出的单元不能再用，而一旦队列中最后一个单元填满则判断为溢出，实际上此时队列的前端可能是空的，从而造成假溢出。解决假溢出问题可以有多种方法。例如，可以采用“删除—平移”的方法来解决，即每当删除队头元素时，随后即把队列中的所有元素依次向队头方向平移一个位置，这样只要队列中有数据元素存在，队列头部总是填满，空闲单元总是在队列尾部，只要队列中有空闲单元新元素就可以入队，从而避免了假溢出的发生。还可以采用“判断—平移”的方法来解决，即每当发现队列“满”时，马上判断队头方向是否有空闲单元，若发现队头方