《数据结构与算法》第一章-绪论习题及答案.docx

数据结构与算法第二部分习题精选一、填空题.数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的和运算等的学科。1 .数据结构被形式地定义为（D, R）,其中D是 的有限集合，R是D上的 有限集合。2 .数据结构包括数据的、数据的 和数据的 这三个方面的内容。3 .数据结构按逻辑结构可分为两大类，它们分别是 和 o.线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。4 .在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点;最后一个结点 后续结点，其余每个结点有且只有1个后续结点。5 .在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以 O6 .在图形结构中，每个结点的前驱结点数和后续结点数可以 o.数据的存储结构可用四种基本的存储方法表示，它们分别是、和 O.数据的运算最常用的有5种，它们分别是、o7 . 一个算法的效率可分为 效率和 效率。二、单项选择题8 1.非线性结构是数据元素之间存在一种：A） 一对多关系B）多对多关系C）多对一关系D） 一对一关系（）2数据结构中，与所使用的计算机无关的是数据的 结构；A）存储 B）物理0逻辑D）物理和存储（）3算法分析的目的是：A）找出数据结构的合理性C）分析算法的效率以求改进O 4算法分析的两个主要方面是：A）空间复杂性和时间复杂性0可读性和文档性（）5.计算机算法指的是：A）计算方法0解决问题的有限运算序列O 6.计算机算法必须具备输入、输出和A）可行性、可移植性和可扩充性 0确定性、有穷性和稳定性 三、阅读下列C程序段，写出相应的执行结果 1. printf （ uInput x”）；scanf （ "%d”，&x）;if （x<=30）if（x>20） y=x;B）研究算法中的输入和输出的关系D）分析算法的易懂性和文档性B）正确性和简明性D）数据复杂性和程序复杂性B）排序方法D）调度方法_等5个特性。B）可行性、确定性和有穷性D）易读性、稳定性和安全性else if (x>10) y=2*x;)；if (x>0&&x<30)printf( "x=%d, y=%d” ,x, y); else printf ("输入数据错！”试写出当x分别为18, 8时的执行结果。2.s=0;for i=0; i<n; i+)for(j=0; j<n; j+)s+=Bij;4. i=l;while (i<=n)四、分析下面各程序段的时间复杂度1. for (i=0; i<n; i+) for (j=0; j<m; j+) Aij=0;3. x=0;for(i=l; i<n; i+) for (j=l; j<=n-i; j+)x+；i=i*3；精选习题答案一、填空题.操作对象、关系 2. 数据元素、关系3.逻辑结构、存储结构、运算4.线性 结构、非线性结构5.一对一关系、一对多关系，多对多关系。6.没有、没有 7.前驱、 1、后续、任意多个 8.任意多个9.顺序、链式、索引、散列10.插入、删除、 修改、查找、排序11. 时间空间二、1、B 2、C 3、C 4、A 5、C 6、B1、答：运行结果为：x=18, y=36x=8, y=运行前的值，且从x = 30开始为数据错2、答：运行结果为：5, 120此题为递归运算 四、1、答：0 (m*n) 2、答：0 (i?) 3、0 (n2)4、0 (log3n)