第1、2章讨论题答案.doc

第一章 绪论 1、研究和讨论数据结构的目的 【参考答案】研究和讨论数据结构的目的是为了让计算机能够对数据进行更好的处理。从软件设计和程序设计角度看，应包括两个方面： （1）概念上一致；（2）更高的处理效率。 数据结构与程序设计的关系 【参考答案】数据结构就是为程序设计而产生，没有程序设计，数据结构就无用武之地，设计出的各种结构将会变成纯粹的脑力游戏而已，无实际价值；而没有数据结构，程序设计的效用将大打折扣，而且面对复杂问题时根本不现实。可以这样说，没有程序设计，就没有数据结构，反之亦然。 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 【参考答案】数据类型是一个值的集合和定义在这个值集上的一组操作的总称，如C语言中的整型、实型、字符型等；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。抽象数据类型可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。 抽象数据类型的主要特点是数据抽象和数据封装，它的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。 4、数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？ 【参考答案】数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? 【参考答案】通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点：（1）程序运行时所需输入的数据总量。（2）计算机执行每条指令所需的时间。（3）程序中指令重复执行的次数。 仅供参考：可以从两方面进行讨论：针对通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方便，既能顺序查找也可随机查找；而如果通讯录经常有增删操作，用链式存储结构较为合适，将每个人的情况作为一个元素（即一个结点存放一个人），设姓名作关键字，链表安排成有序表，这样可提高查询速度。 第二章 线性表 1、线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 【参考答案】(1)选用链表，由于多个线性表在处理过程中长度都在动态变化，主要操作是插入、删除操作，顺序表插入或删除元素时不方便，而用链表的存储结构更加灵活。 选用顺序表，由于线性表很少进行插入和删除，主要用于存取，用顺序表能更好的实现这样的要求。 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 【参考答案】① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。 优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。 ② 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 举出生活中常见的几种线性表（至少5种），并说明如何用程序加以实现。生活中的线性表是否均可以用本章讨论的线性表结构予以表示或模拟呢？为什么? 【参考答案】排队买票、火车车厢、12星座列表、班级同学的点名册、手机通讯录等等，对于排队买票、班级同学的点名册、手机通讯录可以用顺序表按一定序存储，而火车车厢、12星座列表可以用链表存储。 生活中的线性表并不是都可以用本章讨论的线性表结构予以表示或模拟，存储结构实际还包括索引结构和散列结构，由此产生的索引表和散列表在生活中应用也是很广泛的。 4、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist