单链表L是一个带有头结点的有序链表，设计一个算法判断L是否为按数值递减的链表。如果L是递减链表，那么就返回1，否则返回0。请回答下列问题： (1)给出算法的主要思想； (2)写出算法的实现函数； (3)总结所用算法的时间和空间复杂度。

admin2014-07-18 69

问题单链表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://kaotiyun.com/show/Iaxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

《辛丑条约》的主要内容有哪些?(苏州大学2000年中国近代史真题；苏州大学2002年中国近代史真题)

叙述并评价二战后西欧主要国家的“福利国家”政策。

第二次世界大战的爆发是多种因素综合作用的结果，其最根本的原因是()。

马丁．路德提出“信仰耶稣即可得救”的原则，其意义在于()

下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》

维也纳会议争论的焦点问题是()。

中古时代实行索贡巡行赋税征收方式的国家是()。

内蒙古自治区的设立时间是()。

元代对边疆地区的统治方式不同于其他三地的一地是()。

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

关于教育组织变革程序，提出解冻、变革、再冻结三个阶段的学者是()

为了充分发挥函证的作用，注册会计师应恰当选择函证的实施时间，通常将应收账款的函证时间安排在()

S=D1-D2/H=K/H，S为锐利度；K为对比度；H是

下列关于青霉素类的叙述哪一项是不正确的

维生素B1的鉴别反应为（）

某患者左肾结核，膀胱挛缩，右肾积水，抗结核治疗1个月余，高热已有1周。查体右肾肿大有压痛，肾功能中度受损，首选治疗方式为()

专家评估单个风险因素时，涉及技术方面的因素包括()。

“未来的学校必须把教育的对象变成自己教育自己的主体。受教育的人必须成为教育他自己的人；别人的教育必须成为这个人自己的教育。”这句话反映的教育理念不包括

(2013年真题)2012年5月，缅甸籍毒贩糯康在泰国境内制造“湄公河惨案”，杀害了十余名我国船员，后被老挝移送到我国受审。我国司法机关对于糯康进行刑事审判的依据是()。

将一个PowerPoint演示文稿保存为放映文件，最优的操作方法是()。