《数据结构（C#语言描述）》习题答案

《《数据结构（C#语言描述）》习题答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章一、选择题1.AF2.D3.B4.BH5.C6.B7.A&B二、判断题1.V2.X3.74.X5.X6.V7.V8.X三、填空题1.集合结构、线性结构、树形结构、图状结构2.没有、1、没有、13.前驱、14.任意个5.一对一、一对多、多对多6.可行性、确定性、有穷性、输入、输出7.0(n)&0(log2n)四、简答题1.①数据是客观事物的符号表示，在计算机科学屮指能输入计算机并能由计算机程序进行处理的符号总称。②数据元素是数据的基本单位，在程序中通常是作为一个整体来进行考虑和处理的。③数据対象也称数据记录，是性质相同的

2、数据元素的集合，是数据的一个子集。④数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。2.①顺序存储结构是将逻辑上相邻的结点存储在物理位置上也相邻的存储单元里，结点Z间的逻辑关系由存储单元的邻接关系来表示，这样只需要存储结点的值，不必存储结点之间的关系，这种存储方式称为顺序存储结构。特点：(1)结点中只有自身信息域，没有连接信息域。因此，存储密度大，存储空间利用率高。(2)可以通过计算直接确定任意一个结点作为存储的地址。(3)插入和删除都将改变结点的位置。②链式存储结构不要求逻辑上相邻的结点在物理位置上也相邻，在结

3、点中附设地址域来存储与该结点相邻的结点的地址来实现结点间的逻辑关系。特点：(1)结点中除自身信息外，还有连接信息的地址域，因此，比顺序存储结构的存储密度小，存储空间利用率较低。(2)逻辑上相邻的结点，在物理上不必邻接。(3)删除和插入操作灵活方便，不必移动结点，只要改变结点中地址域的值即可。③索引存储是在存储结点信息的同吋，再建立一个附加的索引表，然后利用索引表中索引号的值來确定结点的存储单元地址。其特点是检索速度快。④散列存储方法的基本思想是根据结点的值来确定结点的存储地址。特点是把结点的值作为自变量，通过一个称为散列函数

4、的计算机规则，确定出该结点的存储单元地址。3.设计一个“好”的算法应考虑达到下面几个目标：①正确性，算法应与所需解决问题的需求一致。②可读性，算法主要是为了便于人们阅读和交流，其次才是机器的执行。③健壮性，算法应该具有较强的容错能力，当输入非法的数据时，算法应当能做适当的处理，而不会产生莫名其妙的输出结果或者死机。④效率与低存储量需求一般来说，效率就是算法的执行时间，存储量需求则是指算法在执行过程屮所需要占用的最大存储空I'可。1.算法的时间复杂度(TimeComplexity)又称为计算复杂度(ComputationalC

5、omplexity),是算法有效性的度量之一。算法的时间复杂度是一个算法运行时间的相对度量。而一个算法的运行吋间是指在计算机上从开始运行到结束整个算法所使用的吋I'可，大致等于计算机执行一种基本操作(如赋值、比较、计算、转向、返回、输入、输出等)所需要的时间与算法中进行基本操作次数的乘积。第二章一、选择题1.D2.A3.C4.C5.A6.D7.D&B二、判断题l.X2.V3.V4.V5.X6.V7.X三、填空题1.(n-1)/22.数据元素的前后顺序、元素中的指针3.顺序、链式4.必定、不一定5.主要是使插入和删除等操作统一

6、，在第一个元素之前插入元素和删除第一个结点不必另作判断。6.从任一结点出发都可访问到链表中每一个元素7.4、28.144四、简答题1.①容量固定，存储顺序表的元素需要一整块内存空间，因而顺序表的容量一旦确定，便不能更改。②访问速度快，在顺序表使用索引访问数据元素是非常简单，只需按照公式计算便可以快速的访问指定元素。2.当线性表的操作主要是进行查找，很少做插入和删除操作：线性表的长度变化不大，易于事先确定其大小时，易采用顺序表作为存储结构。当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除操作，易采用键

7、表作为存储结构。3.优点：①链表是在需要空I'可时才申请，不需要即可以释放，它可以有效地利用和共享内存空间。②链表结点的增删除和调整只需修改儿个相关结点的指针地址即可，方便、快捷,可用于需要经常增删结点的领域。③双向链表从两个方向搜索结点，能够大大简化算法的复杂度。若链表其屮一条链有损坏，仍可从另一条链来完成操作，并修复其屮的链表损伤。缺点：①链表算法实现较为复杂和抽彖，算法实现需要额外的内存空间，以保存结点间的逻辑关系。②链表结点只能顺序访问，随机访问性能不佳。③单向链表结点均含有其后续结点的地址信息，无法方便、快捷地获取

8、各自前驱结点的地址。④链表有可能会把它的节点存放在托管堆的每个角落。这使得强制垃圾回收在处理托管堆中的节点对象时需要花费更多的力气。4.单链表：在每个结点中除包含数据域外，只设置一个指针域，用以指向其后继结点；双链表：在每个结点屮除包含数值域外，设置两个指针域，分別用以指向其前驱结点和后继