1.1 数据结构的基本概念·习题

教材导航 · 返回本节知识

复习入口

1.1 数据结构的基本概念 · 1.1.1 基本概念和术语 · 1.1.2 数据结构三要素

本节共7题:选择题5题,综合应用题2题。每题答案紧接题目折叠显示。

文字转录进度:7/7题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P3 · 解析P4 · 目视转录

可以用( )定义一个完整的数据结构。

A. 数据元素

B. 数据对象

C. 数据关系

D. 抽象数据类型

查看答案与解析

答案:D。

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

单项选择题 02

原书题目P3 · 解析P4 · 目视转录

下列四种数据结构中,( )是非线性数据结构。

A. 树

B. 字符串

C. 队列

D. 栈

查看答案与解析

答案:A。

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

单项选择题 03

原书题目P3 · 解析P4 · 目视转录

下列选项中,属于逻辑结构的是( )。

A. 顺序表

B. 哈希表

C. 有序表

D. 单链表

查看答案与解析

答案:C。

顺序表、哈希表和单链表是三种不同的数据结构,既描述逻辑结构,又描述存储结构和数据运算。而有序表是指关键字有序的线性表,仅描述元素之间的逻辑关系,它既可以链式存储,又可以顺序存储,所以属于逻辑结构。

单项选择题 04

原书题目P3 · 解析P4 · 目视转录

下列关于数据结构的说法中,正确的是( )。

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

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

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

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

查看答案与解析

答案:A。

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

单项选择题 05

原书题目P3 · 解析P4 · 目视转录

在存储数据时,通常不仅要存储各数据元素的值,而且要存储( )。

A. 数据的操作方法

B. 数据元素的类型

C. 数据元素之间的关系

D. 数据的存取方法

查看答案与解析

答案:C。

在存储数据时,不仅要存储数据元素的值,而且要存储数据元素之间的关系。

综合应用题

综合应用题 01

原书题目P3 · 解析P4 · 目视转录

对于两种不同的数据结构,逻辑结构或物理结构一定不同吗?

查看答案与解析

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

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

综合应用题 02

原书题目P3 · 解析P4 · 目视转录

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

查看答案与解析

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