数据结构复习题-第1章答案2014-5-16.doc

第1章绪论一、选择题（每小题2分，共20分）1.以下哪一个不是算法的特性（ ）。A.有穷性 B.确定性 C.简洁性 D.可行性2.数据结构的定义为(D，S)，其中D是( )的集合。A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构3.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。x=2； while(xn/2) x=2*x ；A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)4.执行下面程序段时，执行语句的次数为（ ）for （int i=1；i=n；i+）for (int j=1； j=i； j+) S； A. n B. n/2 C. n(n+1) D. n(n+1)/25.在下面的程序段中，对x的赋值语句的频度为（ ）。for(i=1；i=n;i+) for(j=1；j=n；j+) x=x+1;A. O(2n) B. O(n) C. O(n2) D. O(log2n)6.在数据结构的讨论中把数据结构从逻辑上分为 （ ）。 A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构。7.下面程序段的时间复杂度为（ C ） for (int i=0 ；im ；i+) for (int j=0 ；jn ；j+) aij=i*j ；A.O(m2) B.O(n2) C.O(m*n) D.O(m+n)8.算法的计算量的大小称为计算的（ ）。A效率 B. 复杂性 C. 现实性 D. 难度9.数据结构在计算机内存中的表示是指（ ）。 A数据的存储结构 B数据结构 C数据的逻辑结构 D数据元素之间的关系 10.在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A逻辑 B存储 C逻辑和存储 D物理 11.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。A数据的处理方法 B数据元素的类型 C数据元素之间的关系 D数据的存储方法 12.在决定选取何种存储结构时，一般不考虑（ ）。A各结点的值如何 B结点个数的多少 C对数据有哪些运算 D所用的编程语言实现这种结构是否方便。13.算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 （1）A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易读性和文档性 （2 ）A空间复杂度和时间复杂度 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性 15.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。A数据元素具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C每个数据元素都一样D数据元素所包含的数据项的个数要相等16.以下说法正确的是（ ）。A数据项是数据的基本单位 B数据元素是数据的最小单位 C数据结构是带结构的数据项的集合 D一些表面上很不相同的数据可以有相同的逻辑结构 二、判断题（每小题1分，共10分）1.数据元素是数据的最小单位。（ ）2.算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。（ ）3.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）4.算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）5.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。( )6.在决定选取何种存储结构时，一般不考虑各结点的值如何。（ ）7.抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。( ) 8.抽象数据类型与计算机内部表示和实现无关。（ ）9.顺序存储结构只能用于线性结构，不能用于非线性型结构。（ ）10.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）11.在数据结构的讨论中把数据结构从逻辑上分为内部结构与外部结构。（ ）12.数据项是数据的基本单位。（ ）三、填空题（每空1分，共10分）1.通常从四个方面评价算法的质量：_、_、_和_。2.根据数据元素之间的关系不同，通常有以下四种结构， 、 、 和网状结构。3.数据的物理结构主要有_和_两种不同的表示方法。4.数据元素之间的关系在计算机中有两种不同的表示方法： 和 5.算法的5个重要特性是_、_、_、输入和输出。6. 一个算法的效率可分为 效率和 效率。7.下面程序段的时间复杂度是 。 for (i=0 ；in ；i+) for(j=0 ；jm ；j+) Aij=0 ；8.下面程序段的时间复杂度是_。for (i=0 ；in；i+) for (j=0 ；jn ；j+) s+=Bij ；9. 数据结构中评价算法的两个重要指标是算法的_ 和_ 。10.计算机执行下面的语句时，语句s的执行次数为 _。 FOR(i=l；i=i ；j-) s ； 11.数据结构是研讨数据的_和_，以及它们之间的相互关系，并对与这种结构定义相应的_，设计出相应的_。12.数据的物理结构包括_的表示和_的表示。13.一个算法具有5个特性: _、_、_，有零个或多个输入、有一个或多个输出。14.抽象数据类型的定义仅取决于它的一组_，而与_无关，即不论其内部结构如何变化，只要它的_不变，都不影响其外部使用。15.一个数据结构在计算机中_称为存储结构。16.在有n个选手参加的单循环赛中，总共将进行_场比赛。17.对于给定的n个元素，可以构造出的逻辑结构有_，_，_，_四种。18.数据的逻辑结构是指_。参考题：20.下面程序段的时间复杂度为_。(n1) 答案O(n) sum=1； for (i=0 ；sumn ；i+) sum+=1 ；21.下面程序段的时间复杂度是（ O(log3n) ）。 i 0 ； while （i=n ） i = i * 3 ； 22.设m,n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。以下是该函数的程序段，请将未完成的部分填入，使之完整int f(m,n)int m,n; if(m=1)return _(1)_;if(n=1) return _(2)_;if(m1) 答案 O(n)sum=1； for (i=0;sumn;i+) sum+=1; 24.下面程序段中带有下划线的语句的执行次数的数量级是_。答案 log2n2i：=n*n WHILE i1 DO i:=i_div_2;25.下面程序段中带下划线的语句的执行次数的数量级是_。答案 nlog2ni:=1;WHILE in BEGIN FOR j:=1 TO n DO_x:=x+1;i:=i*2 END；26.下面程序段中带下划线的语句的执行次数的数量级是：_答案 log2ni：=1； WHILE in DO i：=i*2;25.在下面的程序段中，对的赋值语句的频度为_（表示为n的函数）。 答案1+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3)FOR i： TO n DO FOR j： TO i DOFOR k：1 TO j DO ：delta；27.已知如下程序段FOR i:= n DOWNTO 1 DO 语句1BEGIN x:=x+1； 语句2FOR j:=n DOWNTO i DO 语句3 y:=y+1; 语句4END；语句1执行的频度为_；语句2执行的频度为_；语句3执行的频度为_；语句4执行的频度为_。答案n+1 n n(n+3)/2 n(n+1)/2。四、简答题（共10分）1.什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。2.数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括线性表、栈、队列、数组等；非线性结构包括树、图等；这两类结构各自的特点是什么？3.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。参考题：4.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？答案简单来说，数据结构定义了一组按某些关系结合在一起的数据元素；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作；而程序设计语言中的数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。5.算法的时间复杂度仅与问题的规模相关吗?答案不是,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。6.常用的存储表示方法有哪几种?答案常用的存储表示方法有四种:顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：根据结点的关键字直接计算该结点的存储地址。7.试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。答案例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们从高级语言的层次讨论这个问题。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。7.什么是数据结构? 有关数据结构的讨论涉及哪三个方面?答案数据结构是指数据以及相互之间的关系。记为：数据结构 = D, R 。其中，D是某一数据对象，R是该对象中所有数据元素之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容： 数据元素以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； 数据元素极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； 施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。8.什么是数据?它与信息是什么关系?答案什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 答案：一、选择题 1-5 CBADC 6-10 CCBAA 11-16 CACABD二、判断题 1-5 6-10 11-12三、填空题 1. 正确性 易读性 健壮性 高效率 2. 集合、线性、树形 3. 顺序存储结构、链式存储结构 4.顺序映像、非顺序映像 5.有穷性、确定性、可行性 6.时间、空间 7. m*n 8.n2 (n*n) 9. 时间复杂度 空间复杂度。 10. n(n+1)/2-3 或 (n+3)(n-2)/2 11.逻辑结构 物理结构 操作（运算） 算法 12.数据元素 数据元素间关系 13.有穷性 确定性 可行性 14.逻辑特性 在计算机内部如何表示和实现 数学特性 15.表示（又称映像） 16. n(n-1)/2 17.集合 线性结构 树形结构 图状结构或网状结构 18.数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。四、简答题（共10分）1.什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。答：通常，定义算法为“为解决某一特定任务而规定的一个指令序列。”一个算法应当具有以下特性： 有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。 有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。 有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。 可行性。算法中每一条运算都必须是足够基本的。就是说，它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。算法和程序不同，程序可以不满足上述的特性(4)。例如，一个操作系统在用户未使用前一直处于等待的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。此外，算法是面向功能的，通常