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

第1章绪论

一、选择题（每小题2分，共20分） 1.以下哪一个不是算法的特性（ ）。

A.有穷性 B.确定性 C.简洁性 D.可行性 2.数据结构的定义为(D，S)，其中D是( )的集合。

A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构

3.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。 x=2；

while(x

2

A. O(log2n) B. O(n) C. O(nlog2n) D. O(n) 4.执行下面程序段时，执行Ｓ语句的次数为（ ）． for （int i=1；i<=n；i++）

for (int j=1； j<=i； j++) S；

A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 5.在下面的程序段中，对x的赋值语句的频度为（ ）。 for(i=1；i<=n;i++)

for(j=1；j<=n；j++) x=x+1;

2

A. O(2n) B. O(n) C. O(n) D. O(log2n) 6.在数据结构的讨论中把数据结构从逻辑上分为 （ ）。 A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构。 7.下面程序段的时间复杂度为（ C ） for (int i=0 ；i

for (int j=0 ；j

22

A.O(m) B.O(n) 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 ；i

for(j=0 ；j

for (j=0 ；j

9. 数据结构中评价算法的两个重要指标是算法的__________ 和__________ 。 10.计算机执行下面的语句时，语句s的执行次数为 _______。

FOR(i=l；i=i ；j--) s ；

11.数据结构是研讨数据的__________和__________，以及它们之间的相互关系，并对与这种结构定义相应的__________，设计出相应的__________。 12.数据的物理结构包括_________的表示和_________的表示。

13.一个算法具有5个特性: __________、__________、__________，有零个或多个输入、有一个或多个输出。

14.抽象数据类型的定义仅取决于它的一组_________，而与_________无关，即不论其内部结构如何变化，只要它的__________不变，都不影响其外部使用。 15.一个数据结构在计算机中_________称为存储结构。

16.在有n个选手参加的单循环赛中，总共将进行______场比赛。

17.对于给定的n个元素，可以构造出的逻辑结构有_______，_______，_______，______四种。

18.数据的逻辑结构是指_________________________________________________________。

参考题：

20.下面程序段的时间复杂度为________。(n>1) 答案O(n) sum=1；

for (i=0 ；sum

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(m

{return f(m,m);} if (m==n)

{return 1+__(3)___;}

return f(m.n-1)+f(m-n,___(4)___); }

②执行程序，f(6,4)=_______。

答案① (1)1 (2)1 (3)f(m,n-1) (4)n ② 9

23.下面程序段的时间复杂度为________。(n>1) 答案 O(n) sum=1；

for (i=0;sum

24.下面程序段中带有下划线的语句的执行次数的数量级是_______。答案 log2n i：=n*n WHILE i<>1 DO i:=i_div_2;

25.下面程序段中带下划线的语句的执行次数的数量级是_______。答案 nlog2n i:=1;

WHILE i

26.下面程序段中带下划线的语句的执行次数的数量级是：_________答案 log2n i：=1； WHILE i

答案1+25.在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）。（1+2++

3

（1+2+3）+?+（1+2+?+n）=n(n+1)(n+2)/6 O(n) FOR i：＝１ TO n DO FOR j：＝１ TO i DO

FOR k：＝1 TO j DO

ｘ：＝ｘ＋delta；

27.已知如下程序段

FOR i:= n DOWNTO 1 DO {语句1} BEGIN

x:=x+1； {语句2}

FOR j:=n DOWNTO i DO {语句3} y:=y+1; {语句4}

END；

语句1执行的频度为__________；语句2执行的频度为__________；语句3执行的频度为__________；语句4执行的频度为___________。答案n+1 n n(n+3)/2 n(n+1)/2。

四、简答题（共10分）

1.什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。

2.数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括线性表、栈、队列、数组等；非线性结构包括树、图等；这两类结构各自的特点是什么？

3.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

参考题：

4.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？ 答案简单来说，数据结构定义了一组按某些关系结合在一起的数据元素；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作；而程序设计语言中的数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。 5.算法的时间复杂度仅与问题的规模相关吗?

答案不是,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 6.常用的存储表示方法有哪几种? 答案常用的存储表示方法有四种:

顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。

2

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。

索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：根据结点的关键字直接计算该结点的存储地址。

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.时

2

间、空间 7. m*n 8.n (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)。例如，一个操作系统在用户未使用前一直处于\等待\的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。此外，算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。

2.数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括线性表、栈、队列、数组等；非线性结构包括树、图等；这两类结构各自的特点是什么？

答案线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构

非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。

3.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

答案数据：指能够被计算机识别、存储和加工处理的信息载体。

数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。

存储结构：就是数据的逻辑结构用计算机语言的实现。

线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。

非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

本文来源：https://www.bwwdw.com/article/bky6.html