习题

单项选择题

01．可以用 _______ 定义一个完整的数据结构。

A.

数据元素

B.

数据对象

C.

数据关系

D.

抽象数据类型

02．下列四种数据结构中， _______ 是非线性数据结构。

A.

树

B.

字符串

C.

队列

D.

栈

03．下列选项中，属于逻辑结构的是 _______ 。

A.

顺序表

B.

哈希表

C.

有序表

D.

单链表

04．下列关于数据结构的说法中，正确的是 _______ 。

A.

数据的逻辑结构独立于其存储结构

B.

数据的存储结构独立于其逻辑结构

C.

数据的逻辑结构唯一决定其存储结构

D.

数据结构仅由其逻辑结构和存储结构决定

05．在存储数据时，通常不仅要存储各数据元素的值，而且要存储 _______ 。

A.

数据的操作方法

B.

数据元素的类型

C.

数据元素之间的关系

D.

数据的存取方法

综合应用题

01．对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？

【提示】

应该注意到，数据的运算也是数据结构的一个重要方面。

对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用于表示层次关系，而后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能，但对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的平均时间复杂度为 $O(n)$ ，而二叉排序树的平均时间复杂度为 $O({\log }_{2}n)$ 。

02．试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同。

【提示】

线性表既可以用顺序存储方式实现，又可以用链式存储方式实现。

在顺序存储方式下，在线性表中插入和删除元素，平均要移动近一半的元素，时间复杂度为 $O(n)$ ；而在链式存储方式下，插入和删除的时间复杂度都是 $O(1)$ 。