首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
单链表L是一个带有头结点的有序链表,设计一个算法判断L是否为按数值递减的链表。如果L是递减链表,那么就返回1,否则返回0。请回答下列问题: (1)给出算法的主要思想; (2)写出算法的实现函数; (3)总结所用算法的时间和空间复杂度。
单链表L是一个带有头结点的有序链表,设计一个算法判断L是否为按数值递减的链表。如果L是递减链表,那么就返回1,否则返回0。请回答下列问题: (1)给出算法的主要思想; (2)写出算法的实现函数; (3)总结所用算法的时间和空间复杂度。
admin
2014-07-18
33
问题
单链表L是一个带有头结点的有序链表,设计一个算法判断L是否为按数值递减的链表。如果L是递减链表,那么就返回1,否则返回0。请回答下列问题:
(1)给出算法的主要思想;
(2)写出算法的实现函数;
(3)总结所用算法的时间和空间复杂度。
选项
答案
(1)遍历链表L,将前后两个结点的数值依次作比较,判断链表是否为递减的,如果是就返回1,不是就返回0。 (2)算法的实现过程如下: #include“stdio.h” int increase(LinkList*L) { int min; //记录链表中的最小值 LinkList *P,*q;//辅助指针 P=L->next: if(P) min=P->data;//因为链表带头结点 q=P->next: while(q!=null){ if(q->data>min) //当前元素的值大于其相邻的前一个元素的值,则不为降序 return 0; else{ min=q->data; //修改最小值 q=q->next; //指针后移 } } return 1: } (3)遍历链表的时间复杂度为O(n),算法实现过程中使用的辅助空间为常量,空间复杂度为O(1)。
解析
转载请注明原文地址:https://jikaoti.com/ti/kUajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于农耕世界与游牧世界文明特征的叙述中,不正确的是()。
《凡尔赛和约》中,战胜国以何种方式处置德国的全部海外殖民地?()。
使用天然火最早出现于人类发展过程的哪一阶段?()
列宁在()中系统地阐明了马克思主义的国家学说。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
试析凡尔赛一华盛顿体系的实质及其对一战后国际关系的影响。
提出电磁感应定律的是物理学家()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
随机试题
销售部助理小王需要根据2012年和2013年的图书产品销售情况进行统计分析,以便制订新一年的销售计划和工作任务。现在,请你按照如下需求,在文档“EXCEL.XLSX”中完成以下工作并保存。在“2013年图书销售分析”工作表中,统计2013年各类图书在每
(2013年第75题)下列治疗风湿病的非甾体抗炎药物中,胃肠道不良反应最小的是
卵巢蒂扭转最主要的症状是( )。
设计图纸是设计工作的最终成果,监理工程师应对设计图纸进行审核,施工图审核的内容着重于( )。
合同索赔一般分为()。
基金管理人对股票投资组合基本策略的选择,建立在对股票市场的有效性的认识上。()
合同的形式,是指当事人之间订立合同的方式,包括()。
为了使不同测验分数可以相互比较,在经典测验理论的指导下,测验等值的计算方法主要有两大类:一类叫等百分位等值法;另一类叫线性等值法。线性等值法计算就是用相同的()作等值的基础。
教师在教育工作中要做到循序渐进,这是因为()。
许多情境条件都会影响助人行为的发生,比如天气、时间等,当有旁观者出现的时候,助人行为会()。
最新回复
(
0
)