实用数据结构基础参考答案.pdfVIP

实用数据结构基础参考答案

单元练习1

一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)

(√)(1)数据的逻辑结构与数据元素本身的内容与形式无关。

(√)(2)一个数据结构就是由一个逻辑结构与这个逻辑结构上的一个

基本运算集构成的整体。

(ㄨ)(3)数据元素就是数据的最小单位。

(ㄨ)(4)数据的逻辑结构与数据的存储结构就是相同的。

(ㄨ)(5)程序与算法原则上没有区别,所以在讨论数据结构时可以通

用。

(√)(6)从逻辑关系上讲,数据结构主要分为线性结构与非线性结构

两类。

(√)(7)数据的存储结构就是数据的逻辑结构的存储映像。

(√)(8)数据的物理结构就是指数据在计算机内实际的存储形式。

(ㄨ)(9)数据的逻辑结构就是依赖于计算机的。

(√)(10)算法就是对解题方法与步骤的描述。

二.填空题

（1）数据有逻辑结构与存储结构两种结构。

（2）数据逻辑结构除了集合以外,还包括:线性结构、树形结构与

图形结构。（3）数据结构按逻辑结构可分为两大类,它们就是线性结

构与非线性结构。（4）树形结构与图形结构合称为非线性结构。

（5）在树形结构中,除了树根结点以外,其余每个结点只有1个前

趋结点。

（6）在图形结构中,每个结点的前趋结点数与后续结点数可以任

意多个。

（7）数据的存储结构又叫物理结构。

（8）数据的存储结构形式包括:顺序存储、链式存储、索引存储

与散列存储。（9）线性结构中的元素之间存在一对一的关系。

（10）树形结构结构中的元素之间存在一对多的关系,

（11）图形结构的元素之间存在多对多的关系。

（12）数据结构主要研究数据的逻辑结构、存储结构与算法(或运

算)三个方面的内容。

（13）数据结构被定义为(D,R),其中D就是数据的有限集合,R就

是D上的关系的有限集合。

（14）算法就是一个有穷指令的集合。

（15）算法效率的度量可以分为事先估算法与事后统计法。

（16）一个算法的时间复杂性就是算法输入规模的函数。

（17）算法的空间复杂度就是指该算法所耗费的存储空间,它就是

该算法求解问题规模n的函数。

（18）若一个算法中的语句频度之与为T(n)=6n+3nlog2n,则算

法的时间复杂度为O(nlog2n)。

（19）若一个算法中的语句频度之与为T(n)=3n+nlog2n+n2,则

算法的时间复杂度为O(n2)。

(20)数据结构就是一门研究非数值计算的程序设计问题中计算机

的操作对象,以及它们之间的关系与运算的学科。

三.选择题

(1)数据结构通常就是研究数据的(A)及它们之间的相互联系。

A、存储结构与逻辑结构

B、存储与抽象

C、联系与抽象

D、联系与

逻辑

(2)在逻辑上可以把数据结构分成:(C)。

A、动态结构与静态结构

B、紧凑结构与非紧凑结构

C、线性结构与非线性结构

D、内部结构与外部结构

(3)数据在计算机存储器内表示时,物理地址与逻辑地址相同并且就

是连续的,称之为(C)。

A、存储结构

B、逻辑结构

C、顺序存储结构

D、链式存

储结构

(4)非线性结构中的每个结点(D)。

A.无直接前趋结点

B.无直接后继结点

C.只有一个直接前趋结点与一个直接后继结点

D.可能有多个直接前趋结点与多个直接后继结点

(5)链式存储的存储结构所占存储空间(A)。

A.分两部分,一部分存放结点的值,另一部分存放表示结点间关系的

指针

B.只有一部分,存放结点的值