发布日期:2018-08-18 16:07:57 来源:青海中公考研
一、队列和栈结构的概念理解
栈是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为栈顶。表中无元素时为空栈。栈的修改是按后进先出的原则进行的。通常栈有顺序栈和链栈两种存储结构。
队列是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进行,允许删除的一端称为队头,允许插入的一端称为队尾,队列的操作原则是先进先出的。队列也有顺序存储和链式存储两种存储结构。
二、线性表中单链表相关算法设计与实现
一些基础但又重要的单链表相关算法,如:
1.打印单链表,voidPrintList(Listlist);使用一个指针遍历所有链表节点。
2.两个升序链表,打印tarList中的相应元素,这些元素的序号由SeqList指定,voidPrintLots(ListtarList,ListseqList);使用两个指针分别遍历两个链表,每次取出序列链表的一个序号后,根据该序号,到达目标链表指定节点。
3.两个升序链表的交集,ListIntersect(Listl1,Listl2)。
4.两个升序链表的并集,ListJoin(Listl1,Listl2)。
5.单链表就地置逆,voidReverse(Listl);使用三个指针表示前驱,当前和后继节点,每次将当前节点的Next指向前驱节点,然后向后遍历直到链表末尾。
三、二叉树的遍历
遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。
二叉树遍历方法可分为两大类,一类是“宽度优先”法,即从根结点开始,由上到下,从左往右一层一层的遍历;另一类是“深度优先法”,即一棵子树一棵子树的遍历。
四、带权图的最短路径算法及应用
迪杰斯特拉(Dijkstra)算法求单源最短路径,算法思想:
设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点集(看作蓝点集)。
1.初始化:初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝点集为空。
2.重复以下工作,按路径长度递增次序产生各顶点最短路径,在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证算法按路径长度递增的次序产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。
注意:①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。
五、堆排序
大根堆的定义:完全二叉树,任一非叶子结点都大于等于它的孩子,也就是说根结点是最大的。而且显然大根堆的任一棵子树也是大根堆。
堆排序的基本思想:记录区的分为无序区和有序区前后两部分;用无序区的数建大根堆,得到的根(最大的数)和无序区的最后一个数交换,也就是将该根归入有序区的最前端;如此重复下去,直至有序区扩展至整个记录区。
免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用,不涉及商业盈利目的。如涉及版权问题,请联系本站管理员予以更改或删除。
上一篇: 2019考研:翻译硕士专业就业解析
课程系列 | 班次名称 | 价格 | 免费试听 |
考研政治网络课堂 | 2020考研政治全程班 | ¥980.00 | 免费试听 |
2020考研政治全程协议班 | ¥1080.00 | 免费试听 | |
考研英语网络课堂 | 2020考研英语一全程班 | ¥980.00 | 免费试听 |
2020考研英语二全程班 | ¥980.00 | 免费试听 | |
考研数学网络课堂 | 2020考研数学一全程班 | ¥499.00 | 免费试听 |
2020考研数学二全程班 | ¥399.00 | 免费试听 | |
2020考研数学三全程班 | ¥499.00 | 免费试听 | |
全程联报课程 |
2020考研政治+英语一+数学一全程联报协议班 |
¥2140.00 | 免费试听 |
2020考研政治+英语二+数学三全程联报协议班 |
¥2140.00 | 免费试听 | |
2020考研英语二+数学二全程联报协议班 |
¥1560.00 | 免费试听 |
课程系列 | 班次名称 | 价格 | 免费试听 |
经济学考研网络课堂 | 2020考研经济学精品班(宏观+微观+政经) | ¥1580.00 | 免费试听 |
2020考研经济学全科精品班 |
¥1280.00 | 免费试听 | |
管理学考研网络课堂 | 2020考研管理学精品班(周三多) | ¥1580.00 | 免费试听 |
2020考研管理学全科精品班 |
¥3040.00 | 免费试听 | |
西医考研网络课堂 |
2020考研西医综合精品班 |
¥2480.00 | 免费试听 |
2020考研西医综合全科精品班 |
¥3040.00 | 免费试听 | |
教育学考研网络课堂 |
2020考研教育学精品班 |
¥1880.00 | 免费试听 |
心理学考研网络课堂 |
2020考研心理学精品班 |
¥1880.00 | 免费试听 |
中医考研网络课堂 |
2020考研中医综合精品班 |
¥1880.00 | 免费试听 |
2020考研中医综合全科精品班 |
¥3040.00 | 免费试听 | |
计算机考研网络课堂 | 2020考研计算机精品班 | ¥1580.00 | 免费试听 |
艺术学考研网络课堂 |
2020考研中国美术史精讲班 |
¥1580.00 | 免费试听 |
考研学习礼包+院长导学课+会员超值尊享+专属福袋+白皮书+密卷领取预约。GO>
各科目研发均由院长亲自主持,根据每年最新考研大纲、 政策方向,从阶段到模块,再由模块到切片化的知识点, 既成体系又足够精细GO>
周一至周日 9:00-18:00 全年无休在线客服