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

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

第一章概论

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

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

数据结构课程设计.doc

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

数据结构课设.doc

仔细笔记, 还需要自己利用课余时间去图书馆查阅有关图书,增长知识,以及用电脑浏览...苏仕华 等编著.《 数据结构课程设计.》 北京:机械工业出版社.2005.05 [10].......[本文更多相关]

济南大学_计10_数据结构课程设计题目 - 副本.doc

2. 3. 4. 朱振元, 《数据结构——C++语言描述》 ,清华大学出版社,2008 年 严蔚敏, 《数据结构(C 语言版),清华大学出版社,2009 年》 苏仕华, 《数据结构......[本文更多相关]

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

  • 高三数学教学工作总结10篇精华版
  • 高三数学教学工作总结10篇精华版
  • 高一英语教学工作总结8篇精华版
  • 高一英语教学工作总结8篇精华版
  • 高中英语教学总结18篇精华版
  • 高中英语教学总结18篇精华版
  • 初中英语教学工作总结8篇精华版
  • 初中英语教学工作总结8篇精华版
  • 小学英语教师工作总结10篇精华版
  • 小学英语教师工作总结10篇精华版
  • 高二语文教学工作总结5篇精华版
  • 高二语文教学工作总结5篇精华版
  • 小学英语教研组工作总结12篇精华版
  • 小学英语教研组工作总结12篇精华版
  • 高中语文教师工作总结12篇精华版
  • 高中语文教师工作总结12篇精华版
  • 初中英语教学总结8篇精华版
  • 初中英语教学总结8篇精华版
  • 小学英语教师总结10篇精华版
  • 小学英语教师总结10篇精华版
  • 苏仕华版自考数据结构笔记 总结相关搜索
    最新推荐
    热门推荐
    <上页热点Q热点106 114下页下页社会娱乐体育军事汽车财经科技育儿历史美食数码时尚宠物收藏家居心理文化三农健康科学游戏动漫教育职场旅游电影国际 知识100106 114 52 107 115 55 120 57 100z48 100z100 100z106 100z114 100z52 100z107 100z115 100z55 100z120 100z57 106z48 106z100 106z106 106z114 106z52 106z107 106z115 106z55 106z120 106z57 114z48 114z100 114z106 114z114 114z52 114z107 114z115 114z55 114z120 114z57 52z48 52z100 52z106 52z114 52z52 52z107 52z115 52z55 52z120 52z57 107z48 107z100 107z106 107z114 107z52 107z107 107z115 107z55 107z120 107z57 115z48 115z100 115z106 115z114 115z52 115z107 115z115 115z55 115z120 115z57 55z48 55z100 55z106 55z114 55z52 55z107 55z115 55z55 55z120 55z57 120z48 120z100 120z106 120z114 120z52 120z107 120z115 120z55 120z120 120z57 57z48 57z100 57z106 57z114 57z52 57z107 57z115suiji 106 114 52 107 115 55 120 57 100g48 100g100 100g106 100g114 100g52 100g107 100g115 100g55 100g120 100g57 106g48 106g100 106g106 106g114 106g52 106g107 106g115 106g55 106g120 106g57 114g48 114g100 114g106 114g114 114g52 114g107 114g115 114g55 114g120 114g57 52g48 52g100 52g106 52g114 52g52 52g107 52g115 52g55 52g120 52g57 107g48 107g100 107g106 107g114 107g52 107g107 107g115 107g55 107g120 107g57 115g48 115g100 115g106 115g114 115g52 115g107 115g115 115g55 115g120 115g57 55g48 55g100 55g106 55g114 55g52 55g107 55g115 55g55 55g120 55g57 120g48 120g100 120g106 120g114 120g52 120g107 120g115 120g55 120g120 120g57 57g48 57g100 57g106 57g114 57g52 57g107 57g115 57g55 57g120 57g57 100g48g48 100g48g100... 1000000new106 new114 new52 new107 new115 new55 new120 new57 new100g48 new100g100 new100g106 new100g114 new100g52 new100g107 new100g115 new100g55 new100g120 new100g57 new106g48 new106g100 new106g106 new106g114 new106g52 new106g107 new106g115 new106g55 new106g120 new106g57 new114g48 new114g100 new114g106 new114g114 new114g52 new114g107 new114g115 new114g55 new114g120 new114g57 new52g48 new52g100 new52g106 new52g114 new52g52 new52g107 new52g115 new52g55 new52g120 new52g57 new107g48 new107g100 new107g106 new107g114 new107g52 new107g107 new107g115 new107g55 new107g120 new107g57 new115g48 new115g100 new115g106 new115g114 new115g52 new115g107 new115g115 new115g55 new115g120 new115g57 new55g48 new55g100 new55g106 new55g114 new55g52 new55g107 new55g115 new55g55 new55g120 new55g57 new120g48 new120g100 new120g106 new120g114 new120g52 new120g107 new120g115 new120g55 new120g120 new120g57 new57g48 new57g100 new57g106 new57g114 new57g52 new57g107 new57g115 new57g55 new57g120 new57g57 new100g48g48 new100g48g100 下页>... new100g48g48g48g48g48g48g48top106 top114 top52 top107 top115 top55 top120 top57 top100g48 top100g100 top100g106 top100g114 top100g52 top100g107 top100g115 top100g55 top100g120 top100g57 top106g48 top106g100 top106g106 top106g114 top106g52 top106g107 top106g115 top106g55 top106g120 top106g57 top114g48 top114g100 top114g106 top114g114 top114g52 top114g107 top114g115 top114g55 top114g120 top114g57 top52g48 top52g100 top52g106 top52g114 top52g52 top52g107 top52g115 top52g55 top52g120 top52g57 top107g48 top107g100 top107g106 top107g114 top107g52 top107g107 top107g115 top107g55 top107g120 top107g57 top115g48 top115g100 top115g106 top115g114 top115g52 top115g107 top115g115 top115g55 top115g120 top115g57 top55g48 top55g100 top55g106 top55g114 top55g52 top55g107 top55g115 top55g55 top55g120 top55g57 top120g48 top120g100 top120g106 top120g114 top120g52 top120g107 top120g115 top120g55 top120g120 top120g57 top57g48 top57g100 top57g106 top57g114 top57g52 top57g107 top57g115 top57g55 top57g120 top57g57 top100g48g48 top100g48g100幼儿教育小学教育初中教育高中教育高等教育教学研究外语学习资格考试/认证成人教育职业教育IT/计算机经管营销医药卫生自然科学农林牧渔人文社科工程科技PPT模板PPT制作技巧求职/职场计划/解决方案总结/汇报党团工作工作范文表格/模板法律文书饮食游戏体育/运动音乐旅游购物娱乐时尚美容化妆家具家电社会民生影视/动漫保健养生随笔摄影摄像幽默滑稽人文社科法律资料军事/政治广告/传媒设计/艺术教育学/心理学社会学文化/宗教哲学/历史文学研究经管营销人力资源管理财务管理生产/经营管理企业管理公共/行政管理销售/营销金融/投资经济/市场工程科技信息与通信电子/电路建筑/土木城乡/园林规划环境/食品科学电力/水利交通运输能源/化工机械/仪表冶金/矿山/地质纺织/轻工业材料科学兵器/核科学IT/计算机互联网电脑基础知识软件及应用硬件及网络自然科学数学物理化学生物学天文/地理医药卫生临床医学基础医学预防医学中医中药药学农林牧渔农学林学畜牧兽医水产渔业求职/职场简历封面/模板求职/面试职业规划自我管理与提升计划/解决方案学习计划工作计划解决方案商业计划营销/活动策划总结/汇报学习总结实习总结工作总结/汇报党团工作入党/转正申请思想汇报/心得体会党团建设工作范文制度/规范演讲/主持行政公文表格/模板合同协议书信模板 表格类模板饮食游戏体育/运动音乐旅游购物娱乐时尚美容化妆影视/动漫保健养生随笔幽默滑稽幼儿教育幼儿读物少儿英语唐诗宋词育儿理论经验育儿知识家庭教育小学教育小升初学科竞赛其它课程 初中教育中考科学学科竞赛其它课程高中教育学科竞赛其它课程职业教育中职中专职高对口职业技术培训 其他成人教育成人考试电大自考专升本远程、网络教育高等教育理学工学经济学管理学文学哲学历史学法学教育学农业医学军事艺术研究生入学考试院校资料其它