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

二、判断题 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.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

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

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

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

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

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

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

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构复习题-第1章答案2014-5-16(2)在线全文阅读。