第一章 绪论 （答案版）

第一章 绪论 一、填空题 1、数据结构被形式地定义为（D, R），其中D是 数据的 有限集合，R是 关系的 有限集合。 2、数据结构包括数据的 逻辑结构 、数据的 物理结构 和数据的 运算 这个方面的内容。 3、数据结构按逻辑结构可分为两大类，它们分别是 线性的 和 非线性的 。 4、线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 的关系。 5、数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序存储、 链式存储、索引存储、 散列存储 。 6、数据的运算常用的有5种，它们分别是 插入、删除、查找、排序、修改 。 7、一个算法的效率可分为 时间 效率和 空间 效率 二、单项选择题 1. 非线性结构是数据元素之间存在一种： B A、一对多关系 B、多对多关系 C、多对一关系 D、一对一关系 2. 数据结构中，与所使用的计算机无关的是数据的什么结构； C A、存储 B、 物理 C、 逻辑 D、 物理和存储 3. 算法分析的目的是： C A、找出数据结构的合理性 B、研究算法中的输入和输出的关系 C、 分析算法的效率以求改进 D、分析算法的易懂性和文档性 4. 算法分析的两个主要方面是： A A、 空间复杂性和时间复杂性 B、正确性和简明性 C、 可读性和文档性 D、数据复杂性和程序复杂性 5. 计算机算法指的是： C A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、调度方法 三、分析下面各程序段的时间复杂度1. for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0; 两个for循环嵌套，第一个规模是n，内循环规模是m,所以整个程序的时间复杂度为O(m*n) 两个for循环嵌套，第一个规模是n，内循环规模是分别是1，2，3，…，故整个程序的时间效率为：1+2+3+…+n=n(n+1)/2=O(n*n)2. s=0; for (i=0; i<n; i++) for(j=0; j<n; j++) s+=B[i][j]; sum=s; 3. x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++; 与上一条类似，内循环相反，故整个程序的时间效率为： n+n-1+…+3+2+1=n(n+1)/2=O(n*n)4. i=1; while(i<=n) i=i*3; 假设整个循环次数为fn，则有,故，该程序的时间效率为O() 四、简答题： 1、 简述将一个现实问题转化为可用计算机解决的过程 答：第一步，分析：对现实问题进行分析，找出已知条件和要求解的结果； 第二步，建模：依据第一步分析结果，采用相关知识构建求解模型，这一步的关键是相关知识对具体问题的吻合度； 第三步，实现：利用开发工具，在计算机上编写应用程序，开发求解软件。 2、 简述构建或使用函数应关注那些属性 答：函数名、函数的参数、函数的返回值、函数体。 其中，函数名需要有一定的意义，以便于他人的调用，函数的参数个数、类型、可否缺省等是正确调用一个函数的关键，函数的返回值类型是函数是否被正确调用的又一关键，函数体的编写体现了函数开发者的水平。 3、 设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对应关系R，哪些结点是开始结点，哪些结点是终端结点？ 1、D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) } d1->d2->d3->d4->d5 线性 开始节点d1 终端结点d5 2、D={d1,d2,…,d9} R={(d1,d2) (d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }d6 d1 d2 d3 d4 d55 d7 d8 d9 非线性（树） 开始结点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)