数据结构第1章-答案.doc

1、第 1 章 概论 数据结构作业答案 1 一、填空题 01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的 学科。 02、数据结构被形式地定义为(D,R)，其中 D 是(数据元素)的有限集合，R 是 D 上的(关系)有限集合。 03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。 04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。 05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存 在(多对多)关系。 06、在线性结构中，第一个结

2、点(没有)前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点(没有) 后续结点，其余每个结点有且只有 1 个后续结点。 07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续) 结点，其余每个结点的后续结点数可以(任意多个)。 08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。 09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。 10、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。 11、数据的运算最常用的有 5 种，

3、它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。 12、一个算法的效率可分为(时间)效率和(空间)效率。 13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。 14、一个数据结构在计算机中的(映射)称为存储结构。 15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。 16、已知如下程序段 for (i=n; i=1; i-) /语句1 x+; /语句2 for (j=n; j=i; j-) /语句3 y+; /语句4 语句 1 执行的频度为(n+1)；语句2执行的频度为(n)；语句3执行的频度为(n(n+3)/2)；语句4执 行的频度

4、为(n(n+1)/2)。 17、在下面的程序段中，对的赋值语句的频度为(n(n+1)(n+2)/6)。 for(i=1; i=n; i+) for(j=1; j=i; j+) for(k=1; k=j; k+) x+=y; 解释：1+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3) 18、下面程序段中带下划线的语句的执行次数的数量级是(O( ) n2log i=1; while(in) i=i*2; 19、下面程序段中带下划线的语句的执行次数的数量级是(O(n )。 n2l i=1; while (in) for(j=1; j=n; j+) x=x+1; i=i

5、*2; 20、下面程序段中带有下划线的语句的执行次数的数量级是(O( ) )。 2logn i=n*n; while(i!=1) i=i/2; 21、计算机执行下面的语句时，“语句s”的执行次数为(n+3)(n-2)/2)。 for(i=1; i=i;j-) 第 1 章 概论 数据结构作业答案 2 语句s; 22、在有 n 个选手参加的单循环赛中，总共将进行(n(n-1)/2)场比赛。 二、判断题 01、数据元素是数据的最小单位。 02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。 03、算法的优劣与算法描述语言无关，但与所用计算机有关。 04、健壮的算法不会因非法的输入数据而出现莫名其妙

6、的状态。 05、算法可以用不同的语言描述，则算法实际上就是程序了。 06、程序一定是算法。 07、数据的物理结构是指数据在计算机内的实际存储形式。 08、数据结构的抽象操作的定义与具体实现有关。 09、在顺序存储结构中，有时也存储数据结构中元素之间的关系。 10、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 11、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。 12、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 三、单项选择题 B01、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的_和运算等的学科。 A)

7、 结构 B) 关系 C) 运算 D) 算法 BD02、数据的逻辑结构被形式地定义为 B=(K,R)，其中 K 是_的有限集合，R 是 K 上的_有限集合。 第 1 空的选项： A) 算法 B) 数据元素 C) 数据操作 D) 逻辑结构 第 2 空的选项： A) 操作 B) 映像 C) 存储 D) 关系 A03、数据结构在计算机内存中的表示是指_。 A) 数据的存储结构 B) 数据结构 C) 数据的逻辑结构 D) 数据元素之间的关系 C04、数据结构中，与所使用的计算机无关的是数据的_结构。 A) 存储 B) 物理 C) 逻辑 D) 物理和存储 C05、算法分析的目的是_。 A) 找出数据结构的

8、合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 A06、算法分析的两个主要方面是_。 A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 C07、计算机算法指的是_。 A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 B08、计算机算法必须具备输入、输出和_等 5 个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 第 1 章 概论 数据结构作业答案 3 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 A09、在决定选取何种

9、存储结构时，一般不考虑_。 A) 各结点的值如何 B) 结构个数的多少 C) 对数据有哪些运算 D) 所用编程语言实现这种结构是否方便 C10、在存储数据时，通常不仅要存储各数据元素的值，而还要存储_。 A) 数据的处理方法 B) 数据元素的类型 C) 数据元素之间的关系 D) 数据的存储方法 B11、算法的计算量的大小称为计算的_。 A) 效率 B) 复杂性 C) 现实性 D) 难度 A12、下面说法错误的是_。 (1) 算法原地工作的含义是指不需要任何额外的辅助空间 (2) 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O( )的算法n2 (3) 所谓时间复杂度是指最坏情况下

10、，估算算法执行时间的一个上界 (4) 同一个算法，实现语言的级别越高，执行效率就越低 A) (1) B) (1)、(2) C) (1)、(4) D) (3) C13、从逻辑上可以把数据结构分为_两大类。 A) 动态结构、静态结构 B) 顺序结构、链式结构 C) 线性结构、非线性结构 D) 初等结构、构造型结构 D14、以下与数据的存储结构无关的术语是_。 A) 循环队列 B) 链表 C) 哈希表 D) 栈 A15、以下数据结构中，_是非线性数据结构。 A) 树 B) 字符串 C) 队列 D) 栈 C16、以下属于逻辑结构的是_。 A) 顺序表 B) 哈希表 C) 有序表 D) 单链表 四、分析

11、下面各程序段的时间复杂度 01、for (i=0; in; i+) for (j=0; jm; j+) Aij=0; 答：O（ ）nm 02、s=0; for (i=0; in; i+) for(j=0; jn; j+) s+=Bij; sum=s; 答：O（ ）2n 03、x=0; for (i=1; in; i+) for (j=1; j=n-i; j+) x+; 答：O（ ）2n 04、i=1; while(i=n) i=i*3; 答：O（ ）n3log 第 1 章 概论 数据结构作业答案 4 五、设有数据逻辑结构 S=(D,R)，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关

12、系 R，哪些 结点是开始结点，哪些结点是终端结点？ 01、D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答：此图为线性结构 d1d2d3d4 d1无直接前驱，是首结点 d4无直接后继是尾结点 02、D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答：此图为树形结构 d1无直接前驱，是根结点 d2,d5,d7,d9无直接后继是叶子结点 03、D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d

13、9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6) 答：此图为图形结构 d1，d2无直接前驱，是开始结点 d6,d7无直接后继是终端结点 六、简述题 01、什么是数据结构? 答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 02、顺序存储结构和链式存储结构的特点是什么? 答：顺序存储结构是指数据元素的逻辑存储顺序和计算机中的物理存储顺序一致，即数据占用一段连续的存储 单元，该存储结构便于实现在查找数据元素时的地址定位，但缺点是在插入和删除操作时需要移动大量的数据 元素。链式存储结构是指数据元素在计算机中占用不连续的存储单元，通过指针指向表示其先后顺序，该存储 结构缺点是在查找数据元素时要通过指针的链接关系才能找到所要的数据元素，优点在于插入和删除操作时， 第 1 章 概论 数据结构作业答案 5 不需要移动大量数据元素，只需要改变其指向关系即可。