栈与队列考题分析

栈和队列可以看作线性表的特例,它们都具有和线性表相同的存储方式,顺序存储和链式存储。栈有顺序栈和链式栈,队列有顺序队列和链式队列。基本知识(1)栈是受限的线性表,表现在它的插入和删除(进栈,出栈)操作只能在一端进行,因此它具有后进先出的特点(如图1所示);队列也是一种受限的线性表,它的插入(入队)操作在一端进行,而它的删除(出队)操作在必须在另一端进行,因此它具有先进先出的特点。(2)为了充分利用存储空间,产生了一种循环队列,也叫做环形队列。它的特点就是队列的首尾相连,分别有指向队首和队尾的指针,且它们由始至终只朝一个方向…     

循环队列队空和队满的判定算法

<正>1队列的概念队列(queue}是限定仅在一端插人,另一端删除的线性表。.允许插人的一端叫队尾(rear),允许删除的一端叫队头伍。nt)。.不含元素的空表称为空队列。。队列的运算特性是先进先出(F irstIn First out一FIFO)。2队列的存储结构2.1队列的链式存储结构一链队列链队列需要队头和队尾两个指针来确定。说明如下:     

优先队列的并行插入和删除

优先队列广泛地使用在许多并行算法中(例如,多处理机调度和某些组合优化算法)。在这些算法中,共享优先队列的存取冲突限制了加速比的提高。本文提出一种链表优先队列的并行插入和删除方法,具有较小并行开销和较大的并行度,并且保证和串行存取算法的优先顺序完全一致,即删除操作返回已经插入和正在插入的所有元素中的最佳元素。同时,我们还介绍了目前性能最好的堆的并行插入和删除算法,并对准和链表结构并行插入和删除算法的性能和适用范围进行了比较,进一步提出了散列结构的优先队列。在ENCORE Multimax520多处理机上的实验结果验证了我们的理论分析结果:使用链表结构的并行分枝限界算法性能上可获得很大提高。     

基于分层路网的路径规划算法

为了提高路径规划的效率,提出了一种基于分层路网的二叉堆管理开启列表启发搜索算法。首先根据路网分级特点的存在,建立分层地图数据库,然后以启发式A*算法为主搜索方式,结合优先队列二叉堆来管理开启列表,完成路径规划。通过实验对比不同路径规划算法的平均耗时显示：启发式A*算法的效率是盲目式Dijkstra算法的4倍左右,同时在算法中引入二叉堆至少节省5%的规划时间。分层策略使快速路段所占比例达到90%以上,且将路径规划耗时控制在3s以内。实现结果表明,所提算法具有很高的运行效率,同时能满足驾驶者多走快速路段的行车心理。     

顺序存储的线性表中删除一批相同数据的快速方法

介绍了在顺序存储的线性表中快速删除一批相同数据的算法。     

算法和数据结构——队列

在上一期中,我们谈到了“栈”的应用。下面再来谈谈队列。队列是限定在一端进行插入,另一端进行删除的特殊线性表。就好比排队买东西,排在前面的人买完东西后离开队伍(删除),而最后来的人总是排在队伍末尾(插入)。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头,允许入队的一端称为队     

中间件的优先队列技术研究

在三层体系结构（客户端－中间件－服务器端）中,中间件作为客户端和服务端的中间层,起到至关重要的作用,优先队列是指在中间件的应用程序需要处理多个任务时,按任务的轻重顺序执行,使用户的平均等待时间最短,本文讨论了用二叉堆算法实现优先队列。     

A*算法的改进及其在移动端游戏中的运用

本文依据A*算法的特点分析了影响A*效率的因素,通过分析二叉堆的特点并且结合实际应用情况,在A*算法中引入二叉堆算法,以此达到提高A*算法效率的目的。实验结果最后证明了基于二叉堆的A*算法比初始的A*具有更快的执行速度。     

高度平衡的二叉搜索树的判定与调整

建立高度平衡的二叉搜索树是为了提高二叉搜索树的效率,减少树的平均搜索长度。为此,向二叉搜索树中每插入一个新结点时要调整树的结构,使二叉搜索树保持平衡,从而使得其高度保持在O(log2n),平均搜索长度也可保持在O(log2n)。     

北京大学计算机系2005级硕士研究生入学考试数据结构复习提要

(本课程考研总分80分)主要参考书:许卓群、杨冬青、唐世渭、张铭,《数字结构与算法》,高等教育出版社第1章 概论 (教材中本章作者为许卓群)一、 重要概念1. 数据类型2. 抽象数据结构3. 数据结构4. 存储结构5. 算法6. 算法度量(时间代价、空间代价)7. 数据结构的选择和评价二、 方法1. 根据二元组画出图示逻辑结构(注意边的方向)2. 根据要求设计数据结构3. 算法度量的大O表示法的简化法则第2章 线性表(教材中本章作者为许卓群)一、概念线性表、单链表、双链表、循环表、栈、队列、循环队列二、方法1. 线性表的运算(指针操作的正确性)2. 循环…     

堆的路径二分搜索算法

本文提出堆的路径二分搜索算法．当用堆来实现优先队列时，此算法可用较少的比较次数完成插入及删除最大元素等操作．     

一种模糊自调整的PD-RED算法

RED算法作为第一代主动队列管理技术,能够有效地控制队列长度。然而RED算法在实现中存在着其队列长度依赖于流量负载的变化,网络性能对参数敏感的问题。论文将模糊控制技术与比例微分控制方法相互结合,采用模糊控制器在线调整比例微分控制器参数的方法实现RED算法控制。仿真结果证明,所提出的模糊自调整的PD-RED算法动态响应快,稳态误差小,能够使队列保持期望队列长度。     

动态拓扑网络最短路径启发式算法

针对动态拓扑网络的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法.在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用椭圆曲线参数设定启发函数初始值,进一步缩小搜索范围.采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率.仿真试验结果表明该算法具有良好的性能.     

系数自调整的PD-RED算法

随着技术发展,民机上的网络环境渐渐趋于日常生活中的网络环境。为了避免拥塞,需要对飞机上的链路数据进行主动队列管理。在比例微分控制的随机早期检测（random early detection based on proportional derivative control principle,PD-RED）算法基础上,提出一种系数自调整的PD-RED（improved PD-RED,IPD-RED）算法。在IPD-RED算法中,引入比例系数和微分系数的调整函数来减小参数选取对算法的影响。考虑队列偏差,将其归一化处理后,作为调整函数的参数来使系数动态变化,根据系数变化规律设计函数。实验通过改变上下门限值组合、路由节点间延时和端节点数量来分析算法改善效果,通过改变比例系数和微分系数的初值来探究初值对算法性能的影响。NS2仿真结果表明,IPD-RED算法使平均队列长度更接近期望值,提高了吞吐量,减小了丢包率。初值影响表明,一定范围内增大比例系数可使平均队列长度更快更接近期望值且减小丢包率,但会使延时和振荡增加。微分系数的动态范围很大,对几个网络性能参数的影响很小。实际应用中适当选取系数初值,可使算法更好地适配飞机上的业务。     

物联网数据融合的动态队列感知CSMA调度方案

物联网环境下的数据融合要求采集和处理各种具有不同时间特性的数据,包括实时数据和非实时数据。数据的实时交付作为数据融合的前提对融合结果有着极其重要的影响。论文提出了一种基于动态队列感知的分布式调度算法（QACSMA）,该机制考虑了数据的丢包率、时延约束和队列预测占用率,利用贪婪算法动态调整竞争窗口,以在链路队列长度变大时,提高长队列的服务效率,降低队列长度和时延,提高吞吐量。仿真结果表明,与其他典型调度方案相比,该算法的吞吐量和延迟性能均有所提高。     

GIS中使用改进的Dijkstra算法实现最短路径的计算

地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等,而最短路径分析是其中关键的环节,因而对其算法进行优化很有必要,为此在传统的最短路径算法,即Ｄｉｊｋｓｔｒａ算法的基础上,采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了该算法的分析效率。讨论了地理网络数据的组织结构和最短路径的具体实现过程,并引入了相关概念,并引入了相关概念,通过具体案例分析表明,改进算法在提高网络系统空间分析效率方面是可行的。     

Dijkstra最短路径算法的堆优化实验研究

Dijkstra最短路径算法是图论的经典算法。设有向图G有n个顶点和m条弧,则该算法的时间复杂度为Θ(m+n~2)。前人的理论研究表明,若用二叉堆或d堆作为辅助数据结构,可不同程度地降低算法的时间复杂度。但是,这些研究给出的都是比较松弛的上界描述。本文设计了一系列实验,利用二叉堆和d堆实现了该算法的优化,并通过模型拟合回归的方式研究了优化算法的时间复杂度。我们发现,对于稠密图,采用二叉堆优化算法,实际的时间复杂度可降低为m和nlogn的线性函数;而采用d堆,时间复杂度可降低为m、ndlog_dn、nlog_dn、dlog_dn和n的线性函数,其中的d值对复杂度有显著影响,变化趋势呈现某些共同特征,而最优d值位于[5,7]区间。     

基于C语言的线性表链式存储算法

在进行线性表的插入和删除操作时,采用线性表的链式存储将会降低算法的空间复杂度和时间复杂度,合理利用存储空间,提高处理效率。基于C语言的线性表链式存储算法的实现有尾插法和头插法两种。     

基于路由最短路径树的动态多节点删除算法

提出一种基于路由最短路径树的多节点删除动态算法。算法建立一个最短路径树更新队列,将所有将被删除节点的子孙节点保存到该队列;从原最短路径树中删除需要被删除的节点和其所有子孙节点;从队列中选取与根节点距离最短的节点进行更新,已更新节点不再被插入队列,从而减少节点更新次数。实验结果表明,该算法能有效减少节点的更新冗余。     

一种基于卡尔曼滤波的队列长度自适应算法

传统主动队列管理(AQM)算法在处理传感器网络突发流时具有响应速度慢、抗网络突变性能弱的缺点.针对此问题,提出了一种新的AQM算法,算法首先将队列长度作为早期拥塞检测参量,运用卡尔曼滤波理论预测队列长度;其次根据队列长度在缓冲区的占用比来划分网络状态;最后根据不同占用比采取相应的丢包策略,自适应地调整丢包率,当出现网络突变时,加大调整幅度,使队列长度保持在理想区间.仿真实验表明:新算法能够较好地适应网络波动,提高网络服务质量(QoS),算法综合性能优于主流AQM算法.