WORD格式可编辑
第1章绪论
一、选择题（每小题2分，共20分）
1.以下哪一个不是算法的特性（）。
A.有穷性B.确定性C.简洁性D.可行性
2.数据结构的定义为(D，S)，其中D是()的集合。
A.算法B.数据元素C.数据操作D.逻辑结构
3.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。
x=2；
while(x A.O(log2n)B.O(n)C.O(nlog2n)D.O(n 4.执行下面程序段时，执行Ｓ语句的次数为（）． ) 2 for（inti=1；i<=n；i++） for(intj=1；j<=i；j++)S； A.n2B.n2/2C.n(n+1)D.n(n+1)/2 5.在下面的程序段中，对x的赋值语句的频度为（）。 for(i=1；i<=n;i++) 2 A.O(2n)B.O(n)C.O(n )D.O(log2n) 6.在数据结构的讨论中把数据结构从逻辑上分为（）。 A.内部结构与外部结构B.静态结构与动态结构 C.线性结构与非线性结构D.紧凑结构与非紧凑结构。 7.下面程序段的时间复杂度为（C） for(j=1；j<=n；j++)x=x+1; for(inti=0；i for(intj=0；j A.O(m)B.O(n )C.O(m*n)D.O(m+n) 2 )B.O(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.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 专业知识 整理分享 WORD格式可编辑 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 14.以下说法正确的是（）。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 二、判断题（每小题1分，共10分） 16.数据元素是数据的最小单位。（） 17.算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实 际上就是程序了。（） 18.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（） 19.算法的优劣与算法描述语言无关，但与所用计算机有关。（） 20.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方 面。() 21.在决定选取何种存储结构时，一般不考虑各结点的值如何。（） 22.抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一 个ADT的逻辑特性，不必考虑如何在计算机中实现。() 23.抽象数据类型与计算机内部表示和实现无关。（） 24.顺序存储结构只能用于线性结构，不能用于非线性型结构。（） 25.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（） 26.在数据结构的讨论中把数据结构从逻辑上分为内部结构与外部结构。（） 27.数据项是数据的基本单位。（） 三、填空题（每空1分，共10分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.根据数据元素之间的关系不同，通常有以下四种结构，、、和 网状结构。 3.数据的物理结构主要有_____________和______________两种不同的表示方法。 4.数据元素之间的关系在计算机中有两种不同的表示方法：和 5.算法的5个重要特性是_________、__________、__________、输入和输出。 6.一个算法的效率可分为效率和效率。 7.下面程序段的时间复杂度是。 for(i=0；i for(j=0；j 8.下面程序段的时间复杂度是_______。 for(i=0；i for(j=0；j 9.数据结构中评价算法的两个重要指标是算法的__________和__________。 10.计算机执行下面的语句时，语句s的执行次数为_______。 专业知识 整理分享 WORD格式可编辑 FOR(i=l；i 15.数据结构是研讨数据的__________和__________，以及它们之间的相互关系，并对与这 种结构定义相应的__________，设计出相应的__________。 16.数据的物理结构包括_________的表示和_________的表示。 17.一个算法具有5个特性:__________、__________、__________，有零个或多个输入、 有一个或多个输出。 18.抽象数据类型的定义仅取决于它的一组_________，而与_________无关，即不论其内部 结构如何变化，只要它的__________不变，都不影响其外部使用。 19.一个数据结构在计算机中_________称为存储结构。 20.在有n个选手参加的单循环赛中，总共将进行______场比赛。 21.对于给定的n个元素，可以构造出的逻辑结构有_______，_______，_______，______ 四种。 22.数据的逻辑结构是指_________________________________________________________。 参考题： 28.下面程序段的时间复杂度为________。(n>1)答案O(n) sum=1； for(i=0；sum 29.下面程序段的时间复杂度是（O(log3n)）。 i＝0； while（i<=n） i=i*3； 30.设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。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整 intf(m,n) intm,n; {if(m==1) return__(1)___; if(n==1){ return__(2)___;} if(m {return1+__(3)___;} returnf(m.n-1)+f(m-n,___(4)___); } ②执行程序，f(6,4)=_______。 答案①(1)1(2)1(3)f(m,n-1)(4)n②9 31.下面程序段的时间复杂度为________。(n>1)答案O(n) sum=1； for(i=0;sum 专业知识 整理分享 WORD格式可编辑 2 23.下面程序段中带有下划线的语句的执行次数的数量级是_______。答案log2n i：=n*nWHILEi<>1DOi:=i_div_2; 24.下面程序段中带下划线的语句的执行次数的数量级是_______。答案nlog2n i:=1; WHILEi 25.下面程序段中带下划线的语句的执行次数的数量级是：_________答案log2n i：=1；WHILEi 32.在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）。答案1+（1+2++ 3 ) （1+2+3）+,+（1+2+,+n）=n(n+1)(n+2)/6O(n FORi：＝１TOnDO FORj：＝１TOiDO FORk：＝1TOjDO ｘ：＝ｘ＋delta； 11.已知如下程序段 FORi:=nDOWNTO1DO{语句1} BEGIN x:=x+1；{语句2} FORj:=nDOWNTOiDO{语句3} y:=y+1;{语句4} END； 语句1执行的频度为__________；语句2执行的频度为__________；语句3执行的频度为 __________；语句4执行的频度为___________。答案n+1nn(n+3)/2n(n+1)/2。 四、简答题（共10分） 1.什么是算法?算法的5个特性是什么?试根据这些特性解释算法与程序的区别。 2.数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括线性表、栈、队列、数 组等；非线性结构包括树、图等；这两类结构各自的特点是什么？ 3.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、 非线性结构。 参考题： 4.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？ 答案简单来说，数据结构定义了一组按某些关系结合在一起的数据元素；抽象数据类型是指 一个数学模型以及定义在该模型上的一组操作；而程序设计语言中的数据类型不仅定义了一 组带结构的数据元素，而且还在其上定义了一组操作。 5.算法的时间复杂度仅与问题的规模相关吗? 答案不是,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值 等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时 间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 6.常用的存储表示方法有哪几种? 答案常用的存储表示方法有四种: 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑 关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 专业知识 整理分享 WORD格式可编辑 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附 加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：根据结点的关键字直接计算该结点的存储地址。 26.试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答案例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成 的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对 于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其 他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记 录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算 机里呢?用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记 录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题， 我们从高级语言的层次讨论这个问题。最后，我们有了这个表(数据结构)，肯定要用它，那 么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及 如何实现这些操作就是数据的运算问题了。 33.什么是数据结构?有关数据结构的讨论涉及哪三个方面? 答案数据结构是指数据以及相互之间的关系。记为：数据结构={D,R}。其中，D是某一 数据对象，R是该对象中所有数据元素之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据元素以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据元素极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储 结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无 关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用 视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖 于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数 据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 34.什么是数据?它与信息是什么关系? 答案什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是 现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。 信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可 共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如， 一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必 须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息 的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处 理的符号的集合。在计算机中，信息必须以数据的形式出现。 答案： 一、选择题1-5CBADC6-10CCBAA11-16CACABD 专业知识 整理分享
数据结构复习题-第1章答案2014-5-16
