第一章概论自测题 、填空题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科 2.数据结构被形式地定义为(D,R),其中D是 的有限集合,R是D上的 有限集合。 3.数据结构包括数据的 数据的 和数据的 这三个方面的内 容 4.数据结构按逻辑结构可分为两大类,它们分别是 5.线性结构中元素之间存在 关系,树形结构中元素之间存在 关系,图形结构中元 素之间存在 关系。 6.在线性结构中,第一个结点前驱结点,其余每个结点有且只有1个前驱结点;最后一个结 点后续结点,其余每个结点有且只有1个后续结点。 结点,其余每个结点有且只有 个前驱结点;叶子结点 没有结点,其余每个结点的后续结点数可以 8.在图形结构中,每个结点的前驱结点数和后续结点数可以 9.数据的存储结构可用四种基本的存储方法表示,它们分别是 10.数据的运算最常用的有5种,它们分别是 11.一个算法的效率可分为 效率和 效率。 二、单项选择题 ()1.非线性结构是数据元素之间存在一种 A)一对多关系 B)多对多关系C)多对一关系D)一对一关系 )2.数据结构中,与所使用的计算机无关的是数据的 结构; 4)存储B)物理 C)逻辑 D)物理和存储 ()3.算法分析的目的是 A)找出数据结构的合理性B)研究算法中的输入和输出的关系 C)分析算法的效率以求改进D)分析算法的易懂性和文档性 ()4.算法分析的两个主要方面是: A)空间复杂性和时间复杂性 B)正确性和简明性 可读性和文档性 D)数据复杂性和程序复杂性 ()5.计算机算法指的是: 4)计算方法B)排序方法O)解决问题的有限运算序列D)调度方法 ()6.计算机算法必须具备输入、输出和 等5个特性。 A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性
1 第一章 概论 自测题 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中 D 是 的有限集合，R 是 D 上的 有限集合。 3. 数据结构包括数据的 、数据的 和数据的 这三个方面的内 容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 和 。 5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元 素之间存在 关系。 6． 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结 点 后续结点，其余每个结点有且只有 1 个后续结点。 7. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点 没有 结点，其余每个结点的后续结点数可以 。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是 。 10. 数据的运算最常用的有 5 种，它们分别是 。 11. 一个算法的效率可分为 效率和 效率。 二、单项选择题 （ ）1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 （ ）2. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 （ ）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （ ）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （ ）6. 计算机算法必须具备输入、输出和 等 5 个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性 三、简答题 1数据结构和数据类型两个概念之间有区别吗? 2.简述线性结构与非线性结构的不同点。 四、分析下面各程序段的时间复杂度 1.for(i=0;i<n;i++) for〔=0;jm;j++) for (i=0; i<n; i++) Ailljl=0; forGj=0; j<n; j++) s+=Bjl sug for(i=1; i<n; i++) while(i<=n) or(=1;j=n-i;j++) X++; 五、设有数据逻辑结构S=(DR),试按各小题所给条件画出这些逻辑结构的图示,并确定相 对于关系R,哪些结点是开始结点,哪些结点是终端结点? 1.D={dl,d2,d3,d4} R={(dl,d2,(d,d3),(d3,d4)} 2。D={dl,d2,,d9} R={dl,d2),(d1,d3),(d3,d4),d3,d6)d6,d8),d4,d5),(d6,d7),d8,d9)}
2 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 三、简答题 1.数据结构和数据类型两个概念之间有区别吗？ 2. 简述线性结构与非线性结构的不同点。 四、分析下面各程序段的时间复杂度 五、设有数据逻辑结构 S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相 对于关系 R，哪些结点是开始结点，哪些结点是终端结点？ 1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,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; 1. for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0; 3. x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++; 4. i=1; while(i<=n) i=i*3;
3。D={dl,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)}
3 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)}