【免费】数据结构各章例题讲解资源-CSDN文库

数据结构

例题讲解

需积分: 0 71 浏览量 2009-12-11 11:20:59 上传评论收藏 3.05MB PDF 举报

资源详情

资源评论

资源推荐

第

第第

第 1

1 章

章章

章

绪论

绪论绪论

绪论

1-1 什么是数据? 它与信息是什么关系?

【解答】

什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物

在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、

可变换、可处理、可传递、可再生、可压缩、可利用、可共享。

什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中

4 部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能

很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、

以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形

式出现。

1-2 什么是数据结构? 有关数据结构的讨论涉及哪三个方面?

【解答】

数据结构是指数据以及相互之间的关系。记为：数据结构 = { D, R }。其中，D 是某一数据对象，R 是该

对象中所有数据成员之间的关系的有限集合。

有关数据结构的讨论一般涉及以下三方面的内容：

① 数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；

② 数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；

③ 施加于该数据结构上的操作。

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，

数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻

辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的

操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、

更新、排序等。

1-3 数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队

列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？

【解答】

线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，

并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结

构

非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络

等都是典型的非线性结构。

1-4．什么是抽象数据类型？试用 C++的类声明定义"复数"的抽象数据类型。要求

(1) 在复数内部用浮点数定义它的实部和虚部。

(2) 实现 3 个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚

部置为 0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。

(3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。

(4) 定义重载的流函数来输出一个复数。

【解答】

new complex ( Re * ob.Re - Im * ob.Im, Im * ob.Re + Re * ob.Im );

return *result;

}

complex& complex :: operator / ( complex& ) {

//重载函数：复数除法运算

double d = ob.Re * ob.Re + ob.Im * ob.Im;

complex * result = new complex ( ( Re * ob.Re + Im * ob.Im ) / d,

( Im * ob. Re - Re * ob.Im ) / d );

return * result;

}

friend ostream& operator << ( ostream& os, complex & ob ) {

//友元函数：重载<<，将复数 ob 输出到输出流对象 os 中。

return os << ob.Re << ( ob.Im >= 0.0 ) ? "+" : "-" << fabs ( ob.Im ) << "i";

}

1-5 用归纳法证明：

1-6 什么是算法? 算法的 5 个特性是什么? 试根据这些特性解释算法与程序的区别。

【解答】

通常，定义算法为"为解决某一特定任务而规定的一个指令序列。"一个算法应当具有以下特性：

① 有输入。一个算法必须有 0 个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定

的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。

② 有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。

③ 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清

晰地规定。

④ 有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。

⑤ 有效性。算法中每一条运算都必须是足够基本的。就是说，它们原则上都能精确地执行，甚至人们仅用

笔和纸做有限次运算就能完成。

算法和程序不同，程序可以不满足上述的特性(4)。例如，一个操作系统在用户未使用前一直处于"等待"

的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。

此外，算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。

1-7 设 n 为正整数, 分析下列各程序段中加下划线的语句的程序步数。

(1) for (int i = 1; i <= n; i++) (2) x = 0; y = 0;

for (int j = 1; j <= n; j++) { for (int i = 1; i <= n; i++)

c[i][j] = 0.0; for (int j = 1; j <= i; j++)

for (int k = 1; k <= n; k++) for (int k = 1; k <= j; k++)

剩余153页未读，继续阅读

评论收藏

内容反馈

guoshaoming

粉丝: 18
资源: 32

数据结构各章例题讲解

评论0

最新资源

数据结构各章例题讲解

评论0

数据结构各章例题和答案

数据结构习题课及例题讲解课件

数据结构中的排序讲解和例题

数据结构 线性表算法例题讲解.docx

数据结构课件与习题讲解

数据结构各章习题集与答案解析.doc

李春葆编著数据结构(C语言篇)习题与解析(修订版).pdf

数据结构习题解析-第二版殷人昆

数据结构与算法习题解析

数据结构习题与解析

数据结构（C++版）习题解析 第三版 邓俊辉_算法_algorithm_

《算法与数据结构》学习指导与习题解析-王晓东-傅清祥-叶东毅版

算法与数据结构学习指导与习题解析

数据结构习题解析及答案

王晓东_算法与数据结构学习指导与习题解析

清华大学-邓俊辉-数据结构c++及习题解析

数据结构 习题解析 邓俊辉 第三版

数据结构[C语言版]第三四章习题答案及解析.docx

数据结构习题与解析 B级 李春葆

数据结构习题指导

殷人昆的C++数据结构习题解析

严蔚敏数据结构课本源码及习题解析

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

最新资源

数据结构线性表算法例题讲解.docx

数据结构（C++版）习题解析第三版邓俊辉_算法_algorithm_

数据结构习题解析邓俊辉第三版

数据结构习题与解析 B级李春葆

Qt 5实现串口调试助手（源工程文件、0积分下载）