苏仕华版自考数据结构笔记 总结

来源:互联网 编辑:李元芳 手机版

第一章概论

1、若结点的存储地址与其关键字之间存在某种映射关系则称为:散列存储结构。

2、数据类型通常称为原子型和结构型。索引存储:附加索引表。关键字是能唯一标识一个元素的一个数据项或多个数据项的组合。

3、抽象数据类型是指数据逻辑结构及与之相关的操作

第2章线性表

4、顺序表便于按号查找结点

5、顺序表中插入一个元素平均需要移动n/2删除一个元素平均需要移

动(n-1)/2

6、最节省时间的存储结构式:仅有尾指针的单循环链表,带头结点

的双循环链表。

7、将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储

单元里,用这种方法存储的线性表称为顺序表。

8、在第i个元素之前插入一个新元素需要进n-i+1次移动,在第i个元素

之后插入一个新元素需要后移n-i个元素。

9、单链表中每个结点的存储地址是存放在其直接前驱结点的指针域

10、在双链表中要删除已知结点*p,其时间复杂度为O(1)

第3章栈和队列

11、循环队列出队列:(front+1)%m 入队列:(rear+1)%m 循环队

列元素个数:(rear-front+m)%m

12、栈的链式存储结构:不需要判断栈满单需要判断栈空。顺序存储

结构:既需要判断栈空也需要判断栈满且需要置空栈。

13、递归实现和函数调用时,处理参数及返回地址,应采用的数据结

构是堆栈。

14、初始top为n+1,则X入栈操作:top=top-1; V[top]=X;

第4章多维数组和广义表

15、二维数组Am*n按行优先顺序存储公式:LOC(aij) = LOC(a00) +

(i*n+j)*d

16、三位数组A m*n*p按行优先顺序存储公式:LOC(a ijk) = LOC(a000)+

(i*n*p+j*p+k)*d

17、应许结点共享的表称为再入表。广义表的深度:展开后所含括号

的层数。

18、稀疏矩阵的三元组表是顺序存储结构

19、广义表表头和表尾深度相同,则广义表深度+1,不同则为深度最

深。

20、假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q

中,则数组Q的大小至少为5n-6(n>5)。

第5章:树和二叉树

1、二叉树的性质

21、一个结点拥有的子树称为该树的度,一棵树中结点的最大度称为

该树的度。

22、度为零的结点称为叶子结点或终端结点,树中的最大层次称为该

树的深度或高度

23、在二叉树的第i层上至多有2i-1个节点,深度为K的二叉树至多有

2k-1个结点。

24、对任何一棵二叉树T,若其终端结点数为n0,度数为2的节点数为n2

,则n0=n2+1

25、满二叉树:一颗深度为k且有2k-1个结点的二叉树成为满二叉树.

26、完全二叉树:若一棵深度为K的二叉树,其前k-1层是一个满二叉

树,而下一层(即第k层)上的结点都集中在该层最左边的若干位置上,则称为完全二叉树

27、具有n个结点的完全二叉树的深度为logn+1或者log(n+1)。

28、已知一棵度为3的树中,度为2的结点数为4,度为3的结点数为3,

则该树中叶子结点为11

29、含有3个结点a,b,c的二叉树,前序序列a,b,c且后序序列为cba的二叉

树共有4棵。

30、哈夫曼树:带权路径长度最短的树。哈夫曼树一个有2n-1个结点。

31、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相

反,则二叉树的高度一定为n.

32、一棵左子树为空的二叉树的前序线索化后,其空指针为2。

33、在左右子树均不空的先序线索二叉树中,空链域的数目是1。

34、一棵树的后序遍历等价于该二叉树的中序遍历。

35、森林:m棵互不相交树的集合。若将一棵树的根结点删除,就得到

该树构成的森林。

36、N个顶点的生成树有n-1条边。一个带权的无向连通图的最小生成

树有一颗或多棵。

37、已知二叉树的中序序列和后序序列均为ABCDEF,则先序序列

为FEDCBA。

38、已知一颗含有50个节点的二叉树中只有一个叶子结点,则该二叉

树中度为1的结点个数为49。

39、一颗完全二叉树中含有1000个结点,则其中度为2的结点个数

为499.

40、用二叉链表保存有n个结点的二叉树,则结点中有n+1个空指针

域。

41、在含100个结点的完全二叉树中,叶子结点的个数为50。

42、已知完全二叉树的第4层有4个结点,则其叶子结点数是6。

43、已知完全二叉树的第7层有8个结点,则叶子结点数是32。

2、最优二叉树(哈夫曼树)

在两个节点构成的路径上的分支(边)数目称为路劲长度,而树根到树中每个结点的路径长度之和称为路径长度。完全二叉树就是这种路径长度最短的二叉树。

从树根结点到某结点之间的路径长度与该节点上权的乘积称为该结点的带权路径长度,树中所有叶子结点的带权路径长度之和称为该树的带全路径长度,通常记为:WPL = w1l1 + w2l2 + …+ w i l i

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个结点都有一条路径,对路径上的各分支约定指向左子树的分支表示“0”码,指向右子树的分子表示“1”码,取每条路径上

的“0”或“1”的序列作为每个叶子结点对应的字符编码,这就是哈夫曼编码。

第6章图

44、无向图边或弧e的取值范围0~n(n-1)/2 有向图边或弧的取值范围

0~n(n-1)

45、深度优先算法(DFS)遍历类似于树的前序遍历。广度优先遍历

依次访问O(n+e)

最小生成树:普利姆算法和克鲁斯卡尔算法

46、最短路径:迪杰斯特拉算法:按路径长度递增的顺序产生诸顶点

的最短路径算法,图中某顶点到其他顶点的最短路径。O(n+e)

47、带权图的最短路径问题,路径长度指:路径上各边的权值之和。

48、我们把这种顶点表示活动,边表示活动间先后关系的有向无环图

(DAG)称为顶点活动网,简称AOV网。在AOV网中,若不存在回路(即环),所有活动可排成一个线性序列,使得每个活动的

所有前驱活动都排在该活动的前面,此序列就是拓扑序列。由

AOV网构造拓扑序列的过程称为拓扑排序。

49、对于一个具有n个顶点和e跳变的无向图,若采用邻接表表示,则

表头向量的大小为n,所有邻接表中的节点数2e.

50、若无向图有n个顶点和e条边,则它的邻接表共用n个头结点和2e个

表头结点。

51、在无向图中,如果对任意两个顶点Vi和Vj都连通,即从Vi到Vj和

Vj到Vi都存在路径,则称图G是连通图

52、无向图的极大连通子图称为连通分量,显然,任何连通图的连通

分量只有一个,就是其本身。而非连通图的无向图有多个连通分

量。

53、在有向图中,如果对任意两个顶点Vi和Vj都连通,即从Vi到Vj和

Vj到Vi都存在路径,则称图G是强连通图

54、有向图的极大连通子图称作有向图的强连通分量

55、在每条边上标上某种值,带权图的连通图称为网络。若图G中任意

两个不同的顶点间都有路径,则称该图为连通图。

56、一个无向连通图的生成树是含有该连通图的全部顶点的极小连通

子图。

57、若用邻接矩阵表示有向图,则顶点i的入度等于邻接矩阵中第i列非

零元素个数。

58、N个顶点且含有回路的无向连同图中,至少含有n条边。

59、若要建立网络的邻接表,则需要在边表的每个结点中增加一个存

储边上权值的数据域。

第7章:排序

1、排序过程中需要进行两种基本操作:比较两个关键字的大小、改变指向记录的指针或移动记录本身。而待排序记录的存储方式一般有三

种:顺序结构、链式结构和辅助表结构。评价排序算法的标准主要有两条:执行算法需要的时间,以及算法所需要的附加空间。

2、内排序:插入、选择、交换、归并和分配排序。

3、插入排序的基本思想:每次将一个待排序的记录按其关键字的大小插入到前面已排好序的文件中的适当位置,知道全部记录插入完为止。包括:直接插入排序和希尔排序。

3.1直接插入排序是一个就地排序(若排序算法所需要的额外空间相对于输入数据量来说是一个常数,则成该类排序算法为就地排序)。

最好情况最坏情

时间复杂度空间复杂

排序算法

直接插入正序

O(n)

逆序

O(n2)

O(n2)O(1)稳定

希尔排序O(nlog2n)或

O(n1.25)

O(1)不稳定

4、交换排序的基本思想:两两比较待排序记录的关键字,如果发现两个记录的次序相反时即进行交换,知道所有记录都没有反序时为止。包括:冒泡排序和快速排序

4.1冒泡排序是相邻元素之间的比较和交换,快速排序记录关键字的比较和记录的交换是从两端向中间进行的,即该元素将比它大的和小的区分在两边,例如:23 16 35 67 36 70

最好情况最坏情

况时间复杂度空间复杂

排序算法

冒泡排序O(n2)O(1)稳定

快速排序(划分交换

排序)

O(nlog2n)O(log2n)不稳定

5、选择排序的基本思想:每一趟在待排序的记录中选出关键字最小的记录,一次存放在已排序号的记录序列的最后,知道全部记录排序完为止。包括:直接选择排序和堆排序

5.1堆排序:完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在联系,在当前无序区中选择关键字最大(或最小)记录。堆排序正是利用大根堆(小根堆)来选取当前无序区中关键字最大(最小)的记录实现排序的。每一趟排序的操作是:将当前无序区调整成一个大根堆,选取关键字最大的堆顶记录,将它和无序区中最

苏仕华版自考数据结构笔记总结.doc

标签: 工学| 数据结构| 自考|苏仕华版自考数据结构笔记总结_工学_高等教育_教育专区。考点总结,历年试题分析,常考体型归纳。 第一章 概论 1、若结点的存储......[本文更多相关]

数据结构课设 报告.doc

北京:清华大学出版社.2010.09 [4]苏仕华 等编著....数据结构(C 语言版)习题与解析.北京:清华大学出版...东北师大附中理科学霸高中化学选修5笔记 78份文档 ......[本文更多相关]

数据结构课设 报告DOC.doc

3.设计总结部分主要写本人完成工作简介以及自己的设计体会,包括通过课程设计学到...[3]滕国文.数据结构课程设计.北京:清华大学出版社.2010.09 [4]苏仕华 等编著......[本文更多相关]

数据结构课程设计报告模板(参考).doc

[4]苏仕华等,数据结构课程设计,机械工业出版社 4、课程设计工作进度计划 1) ...(论文) 总结 开始 进入录入系统 获得关键字 key 用 Hash1(key)计算地址 比较......[本文更多相关]

数据结构课程设计.doc

7 总结以上是综合设计基础部分的所有内容,做基础部分只是为了给后面的综合设计打...《数据结构课程设计第 2 版》机械工业出版社苏仕华魏韦巍王敬生刘燕君编著 31 ......[本文更多相关]

自考.doc

自考_其它考试_资格考试/认证_教育专区。自考 计算机及应用(本科)专业考试计划:...数据结构 践 苏仕华 外语教学与 2012 研究出版社 年 10 02331 数据结构 11 0......[本文更多相关]

数据结构课程设计报告.doc

总结 经过此次课程设计,我对赫夫曼有了一定的了解。在当今信 息爆炸时代, 如何...6. 参考文献 (包括书籍、论文、网络资料等) [1] 苏仕华等.《数据结构课程......[本文更多相关]

《数据结构 课程设计》航班查询系统实验报告.doc

运行由于测试 11 12 13 14 15 六、总结与心得在本次试验中,遇到了很多的...[3]苏仕华.数据结构 课程设计.机械工业出版社 附录 #include <stdio.h> #......[本文更多相关]

数据结构学籍管理系统.doc

图 2.8 共 17 页 第 10 页 长春大学五.设计总结 课程设计纸 ┊┊┊┊┊...(C 语言版)》 《数据结构课程设计》 李春葆等编 黄国瑜 叶乃菁编 苏仕华 等......[本文更多相关]

数据结构课设.doc

[3]滕国文.数据结构课程设计.北京:清华大学出版社.2010.09 [4]苏仕华 等编著...3.设计总结部分主要写本人完成工作简介以及自己的设计体会,包括通过课程设计学到 ......[本文更多相关]

《数据结构_课程设计》航班查询系统实验报告.doc

参考文献 [1]严蔚敏 吴伟民.数据结构(C 语言版). 北京:清华大学出版社.2007. [2]谭浩强.C 程序设计.北京:清华大学出版社.1999.12. [3]苏仕华.数据结构 ......[本文更多相关]

数据结构课程设计表达式求值问题.doc

参考文献 [1]苏仕华等. 数据结构课程设计.机械工业出版社.2005.05 [2]严蔚敏,吴伟明. 数据结构(C 语言版).清华大学出版社.2007 [3]谭浩强. C 程序设计(第......[本文更多相关]

北理珠校园导游咨询与最短路径 数据结构完整报告.doc

课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会, 有利于...数据结构教程(第 2 版) ,清华大学出版社,2008 年; [5]苏仕华,数据结构课程......[本文更多相关]

数据结构课程设计 栈和队列_图文.doc

8 参考文献 [1] 《数据结构课程设计》 苏仕华 等编著 机械工业出版社 [2] 《数据结构》 语言版) 严蔚敏 吴伟民 编著 清华大学出版社 (C [3] 《C 程序设计......[本文更多相关]

数据结构课程设计报告_哈夫曼编码.doc

数据结构及应用算法教程.北京:清华大学出版社,2001 [5] 苏仕华编著.数据结构与算法分析.合肥:中国科技大学出版社,2004 [6] 苏仕华等著.数据结构课程设计.北京:......[本文更多相关]

数据结构课设.doc

数据结构课设_学习总结_总结/汇报_实用文档。计算机科学与技术系 数据结构 课设...苏仕华.数据结构课程设计.北京:机械工业出版社,2010. [3] 滕国文.数据结构课程......[本文更多相关]

数据结构课设.doc

课程设计说明书是体现和总结课程设计成果的载体,主要内容包括:设计题目、设 计...[3]滕国文.数据结构课程设计.北京:清华大学出版社.2010.09 [4]苏仕华 等编著......[本文更多相关]

数据结构课程设计日历系统设计.doc

[4]苏仕华等,数据结构课程设计,机械工业出版社 攀枝花学院课程设计(论文) 4、...每月前的空格及数字之间的域宽都满足要求; 13 攀枝花学院课程设计(论文) 总结 ......[本文更多相关]

数据结构课设 表达式求值_图文.doc

总结 1、设计中遇到的问题及解决过程 在输入 i,j,w 的值时对数据的输入规则...7.参考文献说明数据结构(C 语言版) 数据结构课程设计 严蔚敏 苏仕华 清华大学......[本文更多相关]

数据结构之生命游戏及活期账目管理课程设计.doc

1. 《数据结构课程设计》 ,苏仕华等编著,机械工业出版社。 2.严蔚敏,吴伟民. 数据结构(C 语言版). 北京:清华大学出版社,2002. 3.李春葆,李三铁. 数据结构......[本文更多相关]

[苏仕华版自考数据结构笔记 总结]相关文章:

  • 高中军训总结15篇精华版
  • 高中军训总结15篇精华版
  • 高一英语教学工作总结8篇精华版
  • 高一英语教学工作总结8篇精华版
  • 数据结构知识点全面总结—精华版
  • 数据结构知识点全面总结—精华版
  • 高中英语教学总结18篇精华版
  • 高中英语教学总结18篇精华版
  • 高三数学教学总结10篇精华版
  • 高三数学教学总结10篇精华版
  • 初中英语教学工作总结8篇精华版
  • 初中英语教学工作总结8篇精华版
  • 小学英语教师工作总结10篇精华版
  • 小学英语教师工作总结10篇精华版
  • 小学英语教研组工作总结12篇精华版
  • 小学英语教研组工作总结12篇精华版
  • 高三教学工作总结10篇精华版
  • 高三教学工作总结10篇精华版
  • 语文教学工作总结10篇精华版
  • 语文教学工作总结10篇精华版
  • 苏仕华版自考数据结构笔记 总结相关搜索
    最新推荐
    热门推荐