假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，aan—1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求：给出算法的基本设计思想。

admin2017-04-28 54

问题假设有一带头结点的循环双链表表示的线性表L=(a₁，a₂，…，aa_n—1，a_n)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a₁，a₃，…，a_n，…，a₄，a₂)。要求：
给出算法的基本设计思想。

选项

答案基本设计思想：从改造后的线性表L可以看出，前部分结点为奇序号结点，并且递增；后部分结点为偶序号结点，并且递减。所以可以考虑建立两个新的循环双链表，一个带头结点的循环双链表L（由原先的L改造而来），保存原先线性表L的奇数号结点，可以采取尾插法，让其序号顺序递增；而另外一个不带头结点的循环双链表s，保存原先线性表L的偶数号结点，可以采取头插法，让其序号顺序递减。最后，将L和s两个循环双链表连接成一个循环双链表L，并且L为其头结点指针。

解析

转载请注明原文地址:https://kaotiyun.com/show/rHRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，aan—1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求：给出算法的基本设计思想。

计算机408

学硕统考专业

【《关于正确处理人民内部矛盾的问题》】

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

巴黎和会讨论的中心问题是()。

中国共产党召开七届二中全会的主要目的是()。

玛雅人的金字塔主要功能是()。

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

提出电磁感应定律的是物理学家()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

在一个双链表中，在p结点之前插入q结点的操作是()。

对行政系统的存在与运行起影响作用的各种自然因素的集合或统称是()

下列哪种碱基只存在于RNA而不存在于DNA中

已知动点的运动方程为x=2t，y=t2-t，则其轨迹方程为()。

对未办理结婚登记，而以夫妻名义同居生活，公众也认识夫妻关系的男女结合，我国法律有条件地承认双方的同居为(　　)。

下列各项中，可由省、自治区、直辖市地方税务局确定减免城镇土地使用税的有()。

America’smostpopularnewspaperwebsitetodayannouncedthattheeraoffreeonlinejournalismisdrawingtoaclose.TheNewY

Thecontractbetweenthetwocompanieswillexpiresoon.

WeallthinkthatJohnistheonlycandidate______willgetthejob.

假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，aan—1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 给出算法的基本设计思想。

计算机408

学硕统考专业

【《关于正确处理人民内部矛盾的问题》】

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

巴黎和会讨论的中心问题是()。

中国共产党召开七届二中全会的主要目的是()。

玛雅人的金字塔主要功能是()。

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

提出电磁感应定律的是物理学家()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

在一个双链表中，在*p结点之前插入*q结点的操作是()。

对行政系统的存在与运行起影响作用的各种自然因素的集合或统称是()

下列哪种碱基只存在于RNA而不存在于DNA中

已知动点的运动方程为x=2t，y=t2-t，则其轨迹方程为()。

对未办理结婚登记，而以夫妻名义同居生活，公众也认识夫妻关系的男女结合，我国法律有条件地承认双方的同居为( )。

下列各项中，可由省、自治区、直辖市地方税务局确定减免城镇土地使用税的有()。

America’smostpopularnewspaperwebsitetodayannouncedthattheeraoffreeonlinejournalismisdrawingtoaclose.TheNewY

Thecontractbetweenthetwocompanieswillexpiresoon.

WeallthinkthatJohnistheonlycandidate______willgetthejob.

假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，aan—1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求：给出算法的基本设计思想。

在一个双链表中，在p结点之前插入q结点的操作是()。

对未办理结婚登记，而以夫妻名义同居生活，公众也认识夫妻关系的男女结合，我国法律有条件地承认双方的同居为(　　)。