文档介绍:第一章知识点
P3 ·数据结构从 逻辑上 划分为:( 1)线性结构 (2)非线性结构 : 树型结构和图型结构
P4 ·从存储结构(物理结构)上划分:
1)顺序结构 :所有元素存放在一片连续的存储单元中,逻辑上相邻的元素存放到计算机内存中仍然相邻
2)链式结构:所有元素存放在可以不连续的存储单元中,但元素之间的关系可以通过地址确定,逻辑上相邻的元素存放到计算机内存后不一定是相邻的。
P5 ·算法的五大特性: ( 1)输入 ( 2)输出 ( 3)有穷性 ( 4)确定性 ( 5)可行性(可执行)
P6 ·算法分析的任务 /方面:
(1)时间复杂度 (重点是计算时间复杂度 [P9 1-5 P10 1-12)
(2)空间复杂度(性) :一个算法在执行时所占有的内存开销,称为空间频度
课后部分习题解释:
1-2 简述下列概念:数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结
构、非线性结构。
◆ 数据:指能够被计算机识别、存储和加工处理的信息载体。
◆ 数据元素:就是数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理
◆ 数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。
◆ 数据结构: 指的是数据之间的相互关系, 即数据的组织形式。 一般包括三个方面的内容 :
数据的逻辑结构、存储结构和数据的运算。
◆ 逻辑结构:指各数据元素之间的逻辑关系。
◆ 存储结构:就是数据的逻辑结构用计算机语言的实现。
◆ 线性结构:数据逻辑结构中的一类,它的特征是若结构为非空集,则该结构有且只有一
个开始结点和一个终端结点, 并且所有结点都最多只有一个直接前趋和一个直接后继。 线性表就是一个典型的线性结构。
◆ 非线性结构:数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个直接前驱和直接后继。
补充习题
⑴( )是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素
⑶ 从逻辑关系上讲,数据结构主要分为( )、( )、( )和( )。
【解答】集合,线性结构,树型结构,图型结构
⑶ 算法指的是( )。
对特定问题求解步骤的一种描述,是指令的有限序列。
计算机程序 C 解决问题的计算方法 D 数据处理【解答】 A
【分析】计算机程序是对算法的具体实现;简单地说,算法是解决问题的方法;数据处理是通过算法完成的。所以,只有 A 是算法的准确定义。
⑷ 下面( )不是算法所必须具备的特性。
A 有穷性 B 确切性 C 高效性 D 可行性
【解答】 C
【分析】高效性是好算法应具备的特性。
⑸ 算法分析的目的是( ),算法分析的两个主要方面是( )。
A 找出数据结构的合理性 B 研究算法中输入和输出的关系
C 分析算法的效率以求改进 D 分析算法的易读性和文档性
E 空间性能和时间性能 F 正确性和简明性
G 可读性和文档性 H 数据复杂性和程序复杂性
【解答】 C, E
6. 对下列用二元组表示的数据结构 ,试分别画出对