数据结构第1章答案

一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。

02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。

03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。

04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。

05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。

06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。

07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。

08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。

09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。

10、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。

11、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。

12、一个算法的效率可分为(时间)效率和(空间)效率。

13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。

14、一个数据结构在计算机中的(映射)称为存储结构。

15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。

16、已知如下程序段for (i=n; i>=1; i--) //语句1{ x++; //语句2for (j=n; j>=i; j--) //语句3y++; //语句4}语句 1 执行的频度为(n+1)；语句2执行的频度为(n)；语句3执行的频度为(n(n+3)/2)；语句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(n2 log))i=1;while(i<n) i=i*2;19、下面程序段中带下划线的语句的执行次数的数量级是(O(nn2 log))。

i=1;while (i<n){ for(j=1; j<=n; j++) { x=x+1;i=i*2; }}20、下面程序段中带有下划线的语句的执行次数的数量级是(O(22log n) )。

i=n*n;while(i!=1)i=i/2;21、计算机执行下面的语句时，“语句s”的执行次数为((n+3)(n-2)/2)。

for(i=1; i<n-1; i++)for(j=n;j>=i;j--)语句s;22、在有n个选手参加的单循环赛中，总共将进行(n(n-1)/2)场比赛。

二、判断题×01、数据元素是数据的最小单位。

×02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。

×03、算法的优劣与算法描述语言无关，但与所用计算机有关。

√04、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

×05、算法可以用不同的语言描述，则算法实际上就是程序了。

×06、程序一定是算法。

√07、数据的物理结构是指数据在计算机内的实际存储形式。

×08、数据结构的抽象操作的定义与具体实现有关。

×09、在顺序存储结构中，有时也存储数据结构中元素之间的关系。

×10、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

√11、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。

×12、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。

三、单项选择题B01、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的__和运算等的学科。

A) 结构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) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性A06、算法分析的两个主要方面是__。

A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性C07、计算机算法指的是__。

A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法B08、计算机算法必须具备输入、输出和__等5个特性。

A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性D) 易读性、稳定性和安全性A09、在决定选取何种存储结构时，一般不考虑__。

A) 各结点的值如何B) 结构个数的多少C) 对数据有哪些运算D) 所用编程语言实现这种结构是否方便C10、在存储数据时，通常不仅要存储各数据元素的值，而还要存储__。

A) 数据的处理方法B) 数据元素的类型C) 数据元素之间的关系D) 数据的存储方法B11、算法的计算量的大小称为计算的__。

A) 效率 B) 复杂性 C) 现实性 D) 难度A12、下面说法错误的是__。

(1) 算法原地工作的含义是指不需要任何额外的辅助空间(2) 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(n2)的算法(3) 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(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) 单链表四、分析下面各程序段的时间复杂度01、for (i=0; i<n; i++)for (j=0; j<m; j++)A[i][j]=0;m ）答：O（n02、s=0;for (i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;答：O（2n）03、x=0;for (i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;答：O（2n）04、i=1;while(i<=n)i=i*3;log）答：O（n3五、设有数据逻辑结构S=(D,R)，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？01、D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4) }答：此图为线性结构d1→d2→d3→d4d1—无直接前驱，是首结点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,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)} 答：此图为图形结构d1，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点六、简述题01、什么是数据结构?答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

02、顺序存储结构和链式存储结构的特点是什么?答：顺序存储结构是指数据元素的逻辑存储顺序和计算机中的物理存储顺序一致，即数据占用一段连续的存储单元，该存储结构便于实现在查找数据元素时的地址定位，但缺点是在插入和删除操作时需要移动大量的数据元素。

链式存储结构是指数据元素在计算机中占用不连续的存储单元，通过指针指向表示其先后顺序，该存储结构缺点是在查找数据元素时要通过指针的链接关系才能找到所要的数据元素，优点在于插入和删除操作时，不需要移动大量数据元素，只需要改变其指向关系即可。