数据结构基本概念和数据结构三要素习题(试题)

一、单项选择题

1. 可以用（）定义一个完整的数据结构。
A.数据元素     B.数据对象     C.数据关系     D.抽象数据类型

2. 以下数据结构中，（ ）是非线性数据结构。
A.树     B.字符串     C.队列     D.栈

3. 以下属于逻辑结构的是（）。
A.顺序表     B.哈希表     C.有序表     D.单链表

4.以下与数据的存储结构无关的术语是（ ）。
A.循环队列     B.链表     C.哈希表     D.栈

5.以下关于数据结构的说法中，正确的是（ ）。
A.数据的逻辑结构独立于其存储结构
B.数据的存储结构独立于其逻辑结构
C.数据的逻辑结构唯一决定了其存储结构
D.数据结构仅由其逻辑结构和存储结构决定

6.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
A.数据的操作方法     B.数据元素的类型
C.数据元素之间的关系     D.数据的存取方法

7.链式存储设计时，结点内的存储单元地址（ ）。
A. 一定连续     B. —定不连续
C.不一定连续     D.部分连续，部分不连续

二、综合应用题

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

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

答案与解析

一、单项选择题

1. D
抽象数据类型（ADT)描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示，从而构成了一个完整的数据结构定义。

2. A
树和图是典型的非线性数据结构，其他选项都属于线性数据结构。

3. C
顺序表、哈希表和单链表表示几种数据结构，既描述逻辑结构，也描述存储结构和数据运算。而有序表是指关键字有序的线性表，可以链式存储也可以顺序存储，仅描述了元素之间的逻辑关系，故它属于逻辑结构。

4. D
数据的存储结构有顺序存储、链式存储、索引存储和散列存储。循环队列（易错点）是用顺序表表示的队列，是一种数据结构。栈是一种抽象数据类型，可用顺序存储或链式存储，只表示逻辑结构。

5. A
数据的逻辑结构是以面向实际问题的角度出发的，只用抽象表达方式，独立于存储结构，数据的存储方式有多种不同的选择；而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。数据结构包括三个要素，缺一不可。

6. C
在存储数据时，不仅要存储数据元素的值，还要存储数据元素之间的关系。7. A链式存储设计时，各个不同结点的存储空间可以不连续，但是结点内的存储单元地址则必须连续。

二、综合应用题

1. 解答：
应该注意到，数据的运算也是数据结构的一个重要方面。对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树，二叉排序树可以用二叉树的逻辑表示和存储方式，前者通常用来表示层次关系，而后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等，但是对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的时间复杂度为O(n),而二叉排序树的时间复杂度为O(log₂n)。

2.解答：
线性表既可以用顺序存储方式实现，也可以用链式存储方式实现。在顺序存储方式下，在线性表中插入和删除元素，平均要移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除的时间复杂度都是O(1)。