首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O1)(不计new和dispose时间)。
admin
2016-03-29
54
问题
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O1)(不计new和dispose时间)。
选项
答案
本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:linkedlistl x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s ↑.data:=x;s ↑.1ink:=p ↑.link; //将s结点入队 p ↑.link:=s;p:=s; //尾指针p移至新的队尾 endp; (2)proc deleq(val p:linkedlist,var x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针,本算法实 //现队列元素的出队,若出队成功,返回出队元素,否则给出失败信息 if(p ↑.1ink==p)then{writeln(”空队列”);return(0);} //带头结点的循环队列 else{s:=p ↑.link t.link; //找到队头元素 p ↑.link ↑.1ink:=s ↑.link; //删队头元素 x:=s ↑.data,; //返回出队元素 if(p:=s)then p:=p ↑.1ink; //队列中只有一个结点,出队后成为空队列 dispose(s); //回收出队元素所占存储空间 } endp;
解析
转载请注明原文地址:https://jikaoti.com/ti/LbfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述太平天国起义对晚清政局的影响。(中南大学2014年中国近代史真题)
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
在某一个单处理机的系统中,外接了一台打印机,一台输入设备。当前在系统中有二个进程P0、P1已经就绪,进程P0首先获得处理机运行,调度算法为先来先服务,进程P0、P1的运行要求是这样的:P0:计算100ms,打印信息200ms,继续计算100ms,打印信息
随机试题
肺石棉沉着病的病变特点不包括()。
患者,女,37岁。右侧面部发作性电击样疼痛3个月,临床拟诊三叉神经痛。若对其采用肠线埋藏治疗,该疗法属于
根据民事诉讼法律制度规定,下列有关侦查终结的说法中,错误的是()。
某公司是一家生产家用电器的民营企业,面对激烈的全球市场竞争,他们认识到质量已成为竞争的底线,公司决定全面开展“质量领先”活动,活动的第一步是通过全员培训,在全公司范围内达成质量的共识。依照ISO9000标准的定义,质量是“一组固有特性满足要求的程度”,
强调民间音乐在音乐教育中的重要地位,重视以歌唱作为音乐教育的基本手段,并且创设了一套手势帮助学生理解音级关系的音乐教育家是()。
《中华人民共和国义务教育法》规定由()为盲、聋哑和弱智的儿童、少年举办特殊教育学校。
2,3,7,19,136,()
有一项实验的内容是:受试者被要求从一大堆抽象的图样中识别出一个样式,然后选择另一种图样来完善这个样式。实验的结果令人吃惊,在实验中表现最出色的受试者正是那些脑神经细胞耗能最少的人。如果以下哪项为真,最能对上述陈述中表面上的矛盾现象做出解释?
历史唯物主义把社会意识理解为()。
下面不能作为结构化方法软件需求分析工具的是
最新回复
(
0
)