第一章概论自测题答案 填空题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系 和运算等的学科 2.数据结构被形式地定义为(D,R),其中D是数据元素的有限集合,R是D上的关系有限集 合 3.数据结构包括数据的逻誓结构、数据的存储结构和数据的运算这三个方面的内容。 4.数据结构按逻辑结构可分为两大类,它们分别是线性结构和非线性结构 5.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在 多对多关系。 6.在线性结构中第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点没 有后续结点,其余每个结点有且只有1个后续结点。 7.在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 个前驱结点;叶子结点没有 后续结点,其余每个结点的后续结点数可以任意多个 8.在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个 9.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序、链式、索引和散列。 10.数据的运算最常用的有5种,它们分别是插入、删除、修改、查找、排序。 1l.一个算法的效率可分为时间效率和空间效率。 二、单项选择题 (B)1.非线性结构是数据元素之间存在一种: A)一对多关系 B)多对多关系C)多对一关系D)一对一关系 C)2.数据结构中,与所使用的计算机无关的是数据的结构; A)存储B)物理 C)逻辑 D)物理和存储 (C)3.算法分析的目的是: 4)找出数据结构的合理性B)研究算法中的输入和输出的关系 C)分析算法的效率以求改进D)分析算法的易懂性和文档性 (A)4.算法分析的两个主要方面是: A)空间复杂性和时间复杂性B)正确性和简明性 可读性和文档性 D)数据复杂性和程序复杂性 (C)5.计算机算法指的是: 4)计算方法B)排序方法O)解决问题的有限运算序列D)调度方法 (B)6.计算机算法必须具备输入、输出和等5个特性。 A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性
1 第一章概论 自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中 D 是 数据元素 的有限集合，R 是 D 上的 关系 有限集 合。 3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在 多对多关系。 6．在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点 没 有 后续结点，其余每个结点有且只有 1 个后续结点。 7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。 10. 数据的运算最常用的有 5 种，它们分别是插入 、 删除、修改、 查找 、排序。 11. 一个算法的效率可分为 时间 效率和 空间 效率。 二、单项选择题 （ B ）1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 （ C ）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （ A ）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （ B ）6. 计算机算法必须具备输入、输出和 等 5 个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性 三、简答题 2.【严题集12②】数据结构和数据类型两个概念之间有区别吗? 答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素,而且 还在其上定义了一组操作。 3.简述线性结构与非线性结构的不同点 答:线性结构反映结点间的逻辑关系是一对一的,非线性结构反映结点间的逻辑关系是多对多的。 四、【严题集18④】分析下面各程序段的时间复杂度 or(=0;j<m;j++) for i=0; i<n; i++) A[OL=O for(=0,j<n;j++) 答:O(n2) for(i=1; i<n; 1++) for(=1; j<=n-1;j++) 解:因为x++共执行了n-1+n-2+……+1= while(i<=n) n(n-1)2,所以执行时间为O(n2) 答:O(logn) f()=2∑1=2(n-) n(n-1) 2 五、设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图示,并确定相 对于关系R,哪些结点是开始结点,哪些结点是终端结点? 1.【严蔚敏习题集P713②】 D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4)} 答:d1→d2→d3→d4 d1一无直接前驱,是首结点d4—无直接后继是尾结点 2。D={d1,d2,…,d9} R={(d1,d2),(d1l,d3),(d3,d4),(d3,d6),(Gd6,d8),(d4,d5),(d6,d7),(G8,d9)
2 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 三、简答题 2.【严题集 1.2②】数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且 还在其上定义了一组操作。 3. 简述线性结构与非线性结构的不同点。 答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。 四、【严题集 1.8④】分析下面各程序段的时间复杂度 五、设有数据逻辑结构 S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相 对于关系 R，哪些结点是开始结点，哪些结点是终端结点？ 1. 【严蔚敏习题集 P7 1.3②】 D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) } 答： d1→d2→d3→d4 d1—无直接前驱，是首结点 d4—无直接后继是尾结点 2。D={d1,d2,…,d9} R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) } 2. s=0; for i=0; i<n; i++) for(j=0; j<n; j++) s+=B[i][j]; sum=s; 答：O（n 2） 1. for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0; 答：O（m*n） 3. x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++; 解：因为 x++共执行了 n-1+n-2+……＋1= n(n-1)/2，所以执行时间为 O（n 2） 4. i=1; while(i<=n) i=i*3; 答：O（log3n）
答:此图为树形结构d1一无直接前驱,是根结点d2,d5,d7,d9无直接后继是叶子结点 3.D={d1,d2,…,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(G8,d9),(d9,d7),(d4,d7) (d4,d6)} 答:此图为图形结构d1,d2-无直接前驱,是开始结点 d6,d7-无直接后继是终端结点
3 答： 此图为树形结构 d1—无直接前驱，是根结点 d2,d5,d7,d9—无直接后继是叶子结点 3．D={d1,d2,…,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)} 答： 此图为图形结构 d1，d2—无直接前驱，是开始结点 d6,d7—无直接后继是终端结点 (2) (3)