文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 自学考试数据结构重点
侵权投诉

自学考试数据结构重点

自学考试数据结构重点

第一章 1.数据是信息的载体,它能够被计算机识别、存储和加工处理。 2.数据元素是数据的基本单位。有些情况下,数据元素也称为元素、结点、顶点、记录。3.数据结构指的是数据之间的相互关系,即数据的组织形式。一般包括三个方面的内容:①数据元素之间的逻辑关系,也称为数据的逻辑结构;②数据元素及其关系在计算机存储器内的表示,称为数据的存储结构;③数据的运算,即对数据施加的操作。

4.数据类型是一个值的集合以及在这些值上定义的一组操作的总称。按“值”是否可分解,可将数据类型划分为两类:①原子类型,其值不可分解;②结构类型,其值可分解为若干个成分。

5.抽象数据类型是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 6.数据的逻辑结构简称为数据结构。数据的逻辑结构可分为两大类:①线性结构(~的逻辑特征是若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继);②非线性结构(~的逻辑特征是一个结点可能有多个直接前趋和直接后继)。

7.数据存储结构可用四种基本的存储方法表示:①顺序存储方法(该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构);②链接存储方法(该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构);③索引存储方法(该方法通常是在存储结点信息的同时,还建立附加的索引表);④散列存储方法(该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址)。

8.非形式地说,算法是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或多个值为输出。因此,一个算法是一系列将输入转换为输出的计算步骤。

9.求解同一计算问题可能有许多不同的算法,究竟如何来评价这些算法的好坏以便从中选出较好的算法呢?

选用的算法首先应该是“正确”的。此外,主要考虑三点:①执行算法所耗费的时间;②执行算法所耗费的存储空间,其中主要考虑辅助存储空间;③算法应易于理解,易于编码,易于调试等等。

10.性结构反映结点的逻辑关系是一对一的,非线性结构反映结点间的逻辑关系是多对多的。

11.数据的运算最常用的五种,分别是查找、插入、删除、更新、和排序。

12.一个算法的效率可分为时间效率和空间效率。

第二章 线性表

1.线性表是由n(n≥0)个数据元素(结点)a1,a2,an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0是称为空表,常常将非空的线性表(n>0)记作:(a1,a2,an)。 2.按顺序存储方法存储的线性表称为顺序表,按链式存储的线性表称为链表。

3.顺序表上实现的基本运算有:插入、删除。在顺序表做插入运算,平均要移动表中的一半结点。当表长n较大时,算法的效率相当低。虽然EIS(n)中的n的系数较小,但就数量级而言,它仍然是线性阶的,因此算法的平均时间复杂度是0(n);在顺序表做删除运算,平均要移动表中约一半的结点,平均时间复杂度也是0(n)。

4.线性表中结点集合的元素是有限的,结点间的关系是一对一的。

5.链表的每个结点只有一个链域的链表称为单链表。建立单链表有两种方法:头插法建表、尾插法建表。

6.在链表的开始结点之前附加一个结点,称为头结点,会带来以下两个优点:①由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;②无论链表是否为空,其头指针是指向头结点的非空指针,因此空表和非空表的处理和非空表的处理也就统一了。

7.查找运算分两种:①按序号查找(链表不是随机存取结构);②按值查找。

8.循环链表是一种首尾相接的链表。其特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活。

9.双链表若希望从表中快速确定一个结点的直接前趋,可以在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这们形成的链表中有两条方向不同的链,故称之为~。和单链表类似,双链表一般也是由头指针head惟一确定 的,

1

增加头结点也能够使双链表上的某些运算变得方便,将头结点

和尾结点链接起来也能构成循环链表,并称之为双向循环链表。

10.顺序表和链表,它们各有所长。在实际应用中究竟选用哪一种存储结构呢?

答:这要根据具体问题的要求和性质来决定。通常从以下几个方面来考虑:①基于空间的考虑;②基于时间的考虑。存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储量之比;显然,顺序表的存储密度为1,而链表的存储密度小于1。当线性表的长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表作为存储结构;顺序表是由向量实现的,它是一种随机存取结构,对表中任一结点都可在0(1)时间内直接地存取,而链表中的结点,需从头指针起顺着链扫描才能取得。因此,若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;对于频繁进行插入和删除的线性表,宜采用链表做存储结构;若表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。 11.存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。即:存储密度=(结点数据本身所占的存储量)/(结点结构所占的存储总量)。存储密度越大,存储空间的利用率就越高。显然,顺序表的存储密度为1,而链表的存储密度小于1。

12.顺序表相对于链表的优点有节省存储空间和随机存取。链表相对于顺序表的优点有插入和删除操作方便。

13.双链表中要删除已知结点*p,其时间复杂度为0(1)。 14.在循环链表中,可根据任一结点的地址遍历整个链表,而单链表中需知道头指针。 第三章 和队列 1.栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是其运算规则较线性表有更多的限制,故又称它们为运算受限的线性表。 2.栈是限制仅在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶,另一端称为栈底。当表中没有元素时称为空栈。

3.栈的基本运算有六种:①InitStack(S)构造一个空栈S;②StaclEmpty(S)判栈空。若S为空栈,则返回TRUE,否则返回FALSE;③StackFull(S)判栈满。若S为满栈,则返回TRUE,否则返回FALSE。该运算只适用于栈的顺序存储结构;④Push(S,x)进栈。若栈S不满,则将元素X插入S的栈顶;⑤Pop(S)退栈。若栈S非空,则将S的栈顶元素删去并返回该元素;⑥StackTop(S)取栈顶元素。若栈S非空,则返回栈顶元素,但不改变栈的状态。

4.栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 5.在顺序栈上实现的六种基本运算:

6.栈的链式存储结构称为链栈,它是运算受限的单链表,其插入和删除操作仅限制在表头位置上进行。

7.队列也是一种运算受限的线性表。队列也称作先进先出的线性表,简称为FIFO表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一段称为队头,允许插入的一段称为队尾。

8.队列的基本运算有六种:①InitQueue(Q)置空队。构造一个空队列Q。②QueueEmpty(Q)判队空。若队列Q为空,则返回真值,否则返回假值。③QueueFull(Q)判队满。若队列Q为满,则返回真值,否则返回假值。此操作只适用于队列的顺序存储结构。④EnQueue(Q,X)若队列Q非满,则将元素X插入Q的队尾。此操作简称入队。⑤DeQueue(Q)若队列Q非空,则删去的队头元素,并返回该元素。此操作简称出他。⑥QueueFront(Q)若队列Q非空,则返回队头元素,但不改变队列Q的状态。

9.递归是指若在一个函数、过程或者数据结构定义的内部又直接(或间接)出现有定义本身的应用,则称它们是递归的,或者是递归定义的。

10递归算法的设计一般有两步:①将规模较大的原问题分解一个或多个规模更小、但具有类似于原问题特性的子问题,即较大的问题递归地用较小的子问题来描述,解原问题的方法同样可用来解这些子问题;②确定一个或多个无须分解、可直接求解的最小子问题。上述第一步称为递归步骤,第二步中所述的最小子问题称为递归的终止条件。 第四章 串

1. 串是零个或多个字符组成的有限序列。一般记为S=”a1a2

an”

2. 将仅由一个或多个空格组成的串称为空白串;不包括任何

字符的串称为空串。

3.串中任意个连续字符组成的子序列称为该串的子串,包含

第1页

你可能喜欢

  • 数据结构试题及答案
  • 自考数据库系统原理
  • 自考马克思主义基本原理概论
  • 英语二自考复习资料
  • 数据结构复习重点

热门文档

相关文档

  • 自学考试数据结构学习重点(2010年最新版)

    自学考试数据结构学习重点(2010年最新版)_工学_高等教育_教育专区。2010年自考类计算机应用技术独立本科段,专用《数据结构》的学习重点。根据章节和考试特点进行的分析...

  • 自学考试《数据结构》各章要点(1)

    自学考试《数据结构》各章要点(1)_工学_高等教育_教育专区。第一章 概论 数据...自学考试数据结构重点 4页 免费 全国2010年1月自学考试数... 7页 免费 数据...

  • 自考数据结构重点(珍藏版)

    自考数据结构重点(珍藏版)_工学_高等教育_教育专区。自考数据结构重点(珍藏版)自考...科目三实际道路驾驶考试注意事项 驾考新题抢先版文档贡献者 牧梦_伟 贡献于201...

  • 自学考试《数据结构》各章要点

    自学考试数据结构重点 4页 免费 自考《数据结构》各章要点 11页 2财富值 02331...自学考试《数据结构》各章要点 第一章 概论 数据就是指能够被计算机识别、存储...

  • 自考数据结构重点知识

    二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中...自考数据结构考试重点 2页 免费 自考数据结构重点(珍藏版... 31页 免费 自考...

  • 2010年自学考试《数据结构》各章复习要点总结

    自考数据结构重点(珍藏版) 31页 免费 自考数据结构公式汇总 2页 免费 自学考试数据结构重点 4页 免费 自考数据结构历年试题及答... 50页 免费 自考数据结构重点...

  • 2010年自学考试《数据结构》各章复习要点总结

    第 2 页共 7 页 2010 自学考试《数据结构》各章复习要点 栈的基本运算: (1) 插入元素称为入栈运算; (2)删除元素称为退栈运算; (3)读栈顶元素是 将栈...

  • 2010年自学考试《数据结构》各章复习要点总结

    全国2010年1月自学考试数... 7页 免费喜欢此文档的还喜欢 自考数据结构 串讲笔记 210页 免费 自考数据结构串讲资料 93页 免费 自考数据结构重点(珍藏版... 31...

  • 数据结构自学考试辅导--选择题

    2006年10月自学考试数据... 3页 免费喜欢此文档的还喜欢 自考数据结构重点(珍藏...数据结构自学考试练习题---选择题 *** 第 1 章*** 1.从逻辑...

  • 2010年自学考试《数据结构》各章复习要点总结

    自考数据结构重点(珍藏版... 31页 免费 自考 计算机系统结构课后... 60页 免费...数据结构各章复习要点总结第一章 概论 数据就是指能够被计算机识别、存储和加工...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email