《数据结构》习题集：第1章 绪论.doc

数据结构课后练习题 第1章 绪论第1章 绪论一、 选择题1. 数据结构被形式定义为（D，S），其中D是（ B ）的有限集合，S是D上的（ H ）有限集合。A、算法 B、数据元素 C、数据操作 D、逻辑关系 E、操作 F、映象 G、存储 H、关系2. 数据结构是一门研究非数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象（2）A、结构 B、关系 C、运算 D、算法3. 算法分析的目的是（ D ），算法分析的二个主要方面是（ C ）。A、给出数据结构的合理性 B、研究算法中输入输出的关系C、空间复杂性和时间复杂性 D、分析算法的效率以求改进E、正确性和简明性 F、分析算法的易懂性和文档性4. 在数据结构中，从逻辑上可以把数据结构分成（ C ）。A、动态和静态结构 B、紧凑接和非紧凑结构C、线性与非线性结构 D、内部结构和外部结构5. 计算机算法指的是（ C ），它必具备输入、输出和（ E ）5 个特性。A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、可行性、可移植性和可扩充性 E、可行性、确定性和有穷性6. 线性表的顺序存储结构是一种（ A ）的存储结构，线性表的链式存储结构是一种（ B ）。A、随机存取 B、顺序存取 C、索引存取 D、散列存取7. 算法的时间复杂度取决于（ A ）。A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态8. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D ）。A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9. 在以下的叙述中，正确的是（ B ）。A、线性表的顺序存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10. 根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( A )。A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11. 以下说法正确的是( D )。A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、 填空题1. 数据逻辑结构包括（集合）、（线性）、(树型)、(图型)四种类型，树型和图型结构合称（非线性）。2. 对于给定的n 个元素，可以构造出的逻辑结构有（集合）、（线性）、（树型）和（图形结构）四种。3. 算法的五个重要特性是（有穷性）(确定性）、（可行性）、(输入)、(输出)。4. 评价算法的性能从利用计算机资源角度看主要从（时间复杂度和空间复杂度）方面进行分析。5. 线性结构中元素之间存在（一对一）关系，树型结构中元素之间存在（一对多）关系，图型结构中元素之间存在（多对多）关系。6. 下面程序段的时间复杂度是（O(n)）。i=s=0;while(sn) i+;s+;7. 下面程序段的时间复杂度是（O(m*n)）。s=0;for(I=0;In;I+)for(j=0;jm;j+) s+=aij;8. 所谓数据的逻辑结构指的是数据元素之间的 _逻辑关系_。9. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容_数据的逻辑结构、数据的存储结构、对数据施加的操作_。10. 在线性结构中，开始结点_没有_直接前驱结点，其余每个结点有且只有_一个_个直接前驱结点。11. 在树形结构中，根结点只有_一个_，根结点无前驱，其余每个结点有且只有_一个_直接前驱结点；叶子结点没有_后继_结点，其余每个结点的后继结点可以_任意个_。12. 在图形结构中，每个结点的前驱结点和后继结点可以有_任意个_。13. 存储结构是逻辑结构的_物理_实现。14. 从数据结构的观点看，通常所说的数据应分成三个不同的层次，即_数据_、_数据元素_和_数据项_。15. 根据需要，数据元素又被称为_结点_、_记录_、_元素_或_顶点_。16. 通常，存储结点之间可以有_顺序存储_、_链式存储_、_索引存储_、_散列存储_四种关联方式，称为四种基本存储方式。17. 通常从_正确性_、_可读性_、_健壮性_、_高效性_等几方面评价算法的(包括程序)的质量。18. 一个算法的时空性能是指该算法的_时间复杂度_ 和_空间复杂度_ ， 前者是算法包含的_计算量_，后者是算法需要的_存储量_。19. 在一般情况下，一个算法的时间复杂性是_问题规模_的函数。20. 常见时间复杂性的量级有：常数阶O(_1_)、对数阶O(_log2 n _)、线性阶O ( _ n _)、平方阶O(_n2_)、和指数阶O(_2n _)。通常认为，具有指数阶量级的算法是_不可行_的。21. 数据结构的基本任务是数据结构的_设计_和_实现_。22. 数据对象是性质相同的 数据元素 的集合。23. 抽象数据类型是指一个 数学模型 以及定义在该模型上的一组操作。三、 判断题1. 数据元素是数据的最小单位。2. 数据结构是带有结构的数据元素的集合。3. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。4. 数据项是数据的基本单位。5. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6. 数据的物理结构是数据在计算机中实际的存储形式。7. 算法和程序没有区别，所以在数据结构中二者是通用的。8. 顺序存储结构属于静态结构，链式存储结构属于动态结构。四、 计算应用题1. 设 n 为正整数。确定下列各程序段中前置以记号的语句的频度。（1） I=1;k=0;While(In-1)k+=10*I; I+;k=0;for(I=1;I=n;I+)for(j=I;j=n;j+)k+; 答案：n-2(2) I=1;j=0;While(I+jj) j+; else I+;答案：n(n+1)/22. 指出下列两个算法的时间复杂度。（1） int sum1(int n)int p=1,sum=0,I;for(I=1;I=n;I+)p*=I;sum+=p;return(sum);答案：O(n)(2)int sum2(int n)int sum=0,I,j;for(I=1;I=n;I+)p=1;for(j=1;j=I;j+)p*=j;sum+=p;returm(sum);答案：O(n2)3. 简述下列术语：数据，数据元素，数据结构，数据对象。解答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。4. 逻辑结构与存储结构是什么关系?解答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素及其之间的关系在计算机中的表示。5. 将数量级210，n，n2，n3，nlog2n，log2n，2n， n1/2 ，n!，(2/3)n，n2/3，按增长率进行排列。答案：（2/ 3）n，210，log2n， n ，n，n2/3，nlog2n，n2，n3，2n，n!4/4北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1