《数据结构》习题解析.doc

第 1 章 绪 论 1 1.1 本章导学 1 1.2 习题解析 2 第 2 章 线性表 9 2.1 本章导学 9 2.2 习题解析 10 第 3 章 栈和队列 19 3.1 本章导学 19 3.2 习题解析 20 第 4 章 字符串和多维数组 26 4.1 本章导学 26 4.2 习题解析 27 第 5 章 树和二叉树 32 5.1 本章导学 32 5.2 习题解析 33 第 6 章 图 43 6.1 本章导学 43 6.2 习题解析 44 第 7 章 查找技术 56 7.1 本章导学 56 7.2 习题解析 57 第 8 章 排序技术 67 8.1 本章导学 67 8.2 习题解析 68 第 9 章 索引技术 78 9.1 本章导学 78 9.2 习题解析 78  第 1 章 绪 论 1.1 本章导学 1. 知识结构图 本章的知识结构如图1-1所示，其中第二层的椭圆代表本章的学习主线。 2. 学习要点 对本章的学习要从两条主线出发，一条主线是数据结构，包括数据结构的相关概念及含义，另一条主线是算法，包括算法的相关概念、描述方法以及时间复杂度的分析方法。 在学习数据结构时要抓住两个方面：逻辑结构和存储结构，并注意把握二者之间的关系。在学习算法时，要以算法的概念和特性为基本点，并在以后的学习中注意提高算法设计的能力。对于算法时间性能的分析，要将注意力集中在增长率上，即基本语句执行次数的数量级，在设计算法时，养成分析算法时间性能的习惯，进而有效地改进算法的效率。 1.2 习题解析 1. 填空 （1）nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 （1）顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 （2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承遗产。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据继承关系画出逻辑结构图如图1-2所示。 （3）计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A 数据和数据之间存在某种关系 B 元素和元素之间存在某种关系 C 元素内部具有某种结构 D 数据项和数据项之间存在某种关系 【解答】B 【分析】数据结构是指相互之间存在一定关系的数据元素的集合，数据元素是讨论数据结构时涉及的最小数据单位，元素内部各数据项一般不予考虑。 （4）对于数据结构的描述，下列说法中不正确的是（ ）。 A 相同的逻辑结构对应的存储结构也必相同 B 数据结构由逻辑结构、存储结构和基本操作三方面组成 C 对数据结构基本操作的实现与存储结构有关 D 数据的存储结构是数据的逻辑结构的机内实现 【解答】A 【分析】相同的逻辑结构可以用不同的存储结构实现，一般来说，在不同的存储结构下基本操作的实现是不同的，例如线性表可以顺序存储也可以链接存储，在顺序存储和链接存储结构下插入操作的实现截然不同。 （5）可以用（ ）定义一个完整的数据结构。 A 数据元素 B 数据对象 C 数据关系 D 抽象数据类型 【解答】　　　 【解答】⑴ 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 ⑵ 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 ⑶ 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。 ⑷ 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即： (T(n)+1)2≤n，所以T(n)=O(n1/2)。 ⑸ x++是基本语句，所以 5．解答下列问题 （1）设有数据结构（D，R），其中D = {1, 2, 3, 4, 5, 6}，R = {(1, 2),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 5