线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思想。 (

admin2023-02-06 83

问题线性表(a₁，a₂，a₃，…，a_n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)分别给出算法各部分的时间复杂度。

选项

答案(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。 (2)算法的设计如下： [*] (3)在利用折半查找的方法查找x 的过程中时间复杂度为O(nlog₂n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

学习策略的掌握需要学生不断实践。在训练学生运用各种学习策略时，应遵循的原则是()。

说出新旧知识点的衔接点、生长点；正确提出教学的重点、难点、关键；阐明课程目标对这部分内容有什么要求等内容属于说课中的()。

当联结建立时，导致满意结果的联结会被加强，而导致烦恼结果的联结则会被削弱或淘汰。这是桑代克提出的学习律中的()。

关于教学过程的基本阶段，以下排列顺序正确的是()。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

“揭榜挂帅”是通过高额悬赏征集科技创新成果，把需要攻关的科研项目张榜，谁有本事谁就揭榜。这充分体现了国家对改革科研项目管理模式、提高科技创新支撑能力的高度重视。下列说法不准确的是()。

负压是测量时大气压力低于绝对压力的压力。()

具有“利水渗湿，温阳化气”功用的方剂是

小儿肺炎时室温一般维持在：

根据《国家赔偿法》的规定，侵犯公民人身自由的每日赔偿金应怎样计算?()

在运输合同中，对货物毁损、灭失的赔偿额，当事人没有约定的，根据《合同法》的规定，计算赔偿额的具体原则是()。

对流层与人类活动的关系密切，主要表现为()

小王认为在无风险条件下持有一笔确定的货币财富的效用等于风险条件下彩票的期望效用，通常称小王是()。

劳动法对确定和调整最低工资标准需考虑的因素做了哪些原则性规定?

Electroniccommunication,duetoitsspeedandbroadcastingability,isfundamentallydifferentfromPaper-basedcommunications

Whatisthenameoftheprojectforbids?_____________Project.WhatistheitemofBIDNo.0703-CICJ02012227?