1.2　典型例题解析

1.2.1　选择题

1.数据结构是一门研究非数值计算程序设计中计算机的（①）以及它们之间的（②）和运算的学科。

①A.操作对象　　B.计算方法　　C.逻辑存储　　D.数据映像

②A.结构　　B.关系　　C.操作　　D.算法

【分析】数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。

【答案】①A　②B

2.从逻辑上可以把数据结构分为（　）两大类。

A.动态结构、静态结构　　B.顺序结构、链式结构

C.线性结构、非线性结构　　D.初等结构、构造型结构

【分析】数据的逻辑结构可以看作从具体问题抽象出来的数学模型，它与数据的存储无关。数据的逻辑结构有两类，分别是线性结构和非线性结构。

【答案】C

3.线性结构的顺序存储结构是一种（①）的存储结构，线性结构的链式存储是一种（②）的存储结构。

A.随机存取　　B.顺序存取　　C.索引存取　　D.散列存取

【分析】顺序存储结构是一种随机存取结构，链式存储结构是一种顺序存取结构。

【答案】①A　②B

4.计算机算法指的是（　）。

A.计算方法　　B.排序方法

C.解决问题的步骤序列　　D.调度方法

【分析】算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。

【答案】C

5.算法必须具备（　）这3个特性。

A.可执行性、可移植性、可扩充性　　B.可行性、确定性、有穷性

C.确定性、有穷性、稳定性　　D.易读性、稳定性、安全性

【分析】一个算法应该具有下列特性：有穷性、确定性、可行性、输入、输出。

【答案】B

6.算法的时间复杂度取决于（　）。

A.问题的规模　　B.待处理数据的初态

C.A和B　　D.机器的运行速度

【分析】某算法的时间复杂度是执行该算法所耗费的时间，通常某算法的时间复杂度是问题规模n的函数T（n）。

【答案】A

7.下面程序的时间复杂度为（　）。

A.O（m2）　　B.O（n2）　　C.O（m×n）　　D.O（m+n）

【分析】第一个for循环执行m次，第二个for循环执行n次，两个for循环嵌套起来共执行m×n次。

【答案】C

8.在下面的程序段中，最后一行的语句频度在最坏情况下是（　）。

A.O（n）　　B.O（nlog2n）　　C.O（n3）　　D.O（n2）

【分析】第一个for循环执行n-1次，第二个for循环分别执行n-1、n-2、…、1次，两个for循环嵌套起来在最坏情况下共执行n×（n-1）/2次。

【答案】D

1.2.2　判断题

1.数据元素是数据的最小单位。

【分析】数据元素是数据的基本单位，一个数据元素可由若干数据项组成。

【答案】错误

2.顺序存储方式只能用于线性结构，不能用于非线性结构。

【分析】顺序存储方式能用于存储非线性结构。例如，存储树形结构中，完全二叉树的数组存储和堆排序中堆的存储。

【答案】错误

3.基于某种逻辑结构之上的运算，其实现是唯一的。

【分析】基于某种逻辑结构，其存储结构不唯一，因此运算实现也就不唯一。

【答案】错误

4.抽象数据类型只是一个数学模型。

【分析】抽象数据类型是指一个数学模型及定义在该模型上的一组操作。

【答案】错误

5.数据的逻辑结构是指数据的各数据项之间的逻辑关系。

【分析】数据的逻辑结构是指数据之间的逻辑关系。数据元素是数据的基本单位，数据项是数据的最小单位。

【答案】错误

6.数据结构是带有结构的数据元素的集合。

【分析】若对数据结构进行形式化描述，则可从逻辑上认为数据结构DS是数据元素的集合D和D上关系的集合R所构成的二元组：DS=（D，R）。这里的关系R用于描述数据之间的逻辑关系，即数据的结构。

【答案】正确

7.算法可以用不同的语言描述，如果用C语言或Pascal等高级语言来描述，则算法实际上就是程序。

【分析】算法用各种计算机语言描述表现为一个程序但并不等同于程序，因为程序的逻辑不一定能满足有穷性。

【答案】错误

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

【分析】算法的健壮性是指当输入不合法数据时，应能进行适当处理，不至于导致严重后果。

【答案】正确

1.2.3　填空题

1.线性结构中元素的关系是_______，树形结构中元素的关系是_______，图形结构中元素的关系是_______。

【分析】线性结构数据元素之间存在着一对一的关系；树形结构数据元素之间存在着一对多的关系；图形结构数据元素之间存在着多对多的关系。

【答案】一对一；一对多；多对多

2.抽象数据类型的定义仅取决于它的一组_______，而与_______无关，即不论其内部结构如何变化，只要它的_______不变，都不影响其外部使用。

【分析】抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

【答案】逻辑特性；表示和实现；数学特性

3.数据的逻辑结构是指_______。

【分析】数据的逻辑结构可以看作从具体问题抽象出来的数学模型，它与数据的存储无关。

【答案】数据之间的逻辑关系

4.一个数据结构在计算机中的_______称为存储结构。

【分析】数据结构在计算机中的标识（又称映像）称为数据的物理结构，或称为存储结构。

【答案】标识（或映像）

5.算法的5个重要特性是_______、_______、_______、_______和_______。

【分析】一个算法应该具有下列特性：有穷性；确定性；可行性；输入；输出。

【答案】有穷性；确定性；可行性；输入；输出

1.2.4　简答题

1.说明数据结构的概念与程序设计语言中数据类型概念的区别和联系。

【解答】数据类型是一个值的集合以及在这些值上定义的一组运算的集合。例如，C语言中的int类型，表示集合{x|x是整数且-32 768≤x≤32 767}，其运算包括“+”“-”“×”“/”和“％”等。

数据结构指存在特定关系的数据元素的集合。数据结构包括3方面的内容：①数据的逻辑结构，指数据元素之间的逻辑关系；②数据的存储结构，指数据元素及其关系在计算机中的实现方法；③数据的运算，指对数据元素施加的操作。

二者都是数据元素和运算的集合，但是数据结构还涉及数据元素之间的逻辑关系。

2.编写一个程序，计算一元多项式Pn（x）=P0+P1x+P2x2+…+Pnxn的值Pn（x0），设n、x0和Pi（0≤i≤n）均为已知量，从键盘读入。程序中Pi（0≤i≤n）的值是采用什么结构存储的？

【分析】将一元多项式改写为如下形式：

Pn（x）=P0+P1x+P2x2+…+Pnxn=（…（（Pnx+Pn-1）x+Pn-2）x+…+P1）x+P0

程序中Pi的值可以采用顺序结构进行存储。

【算法】

Pi的读入次序为：Pn，Pn-1，…，P1，P0。