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

admin2019-08-15 67

问题线性表(a₁，a₂，a₃，…，a_n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
分别给出算法各部分的时间复杂度。

选项

答案在利用折半查找的方法查找x的过程中时间复杂度为O(nlog₂n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

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

以下()协议完成了从网卡到IP地址的映射。

三类线程search、insert、delete共享(访问)单链表，利用P、V原语操作实现这三类线程。限定如下：(1)search可以与同类线程同时执行；(2)insert类线程之间互斥，但是可以与任意多search同时执行；(3)del

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

设有A，B，C，D4台主机都处在同一个物理网络中，A主机的IP地址是192．155．28．112，B主机的IP地址是192．155．28．120，C主机的IP地址是192．155．28．135，D主机的IP地址是192．155．28．202。共

对汇编语言程序员来说，以下部件中不透明的是()。I．指令缓冲器；Ⅱ．移位器；Ⅲ．通用寄存器；Ⅳ．中断字寄存器；V．乘法器；Ⅵ．先行进位链；

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

采用散列函数H(k)===3XkMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51　　(1)构造散列表(画示意图)；　　(2)装填因子；

关于以太网交换机，下面的论述中不正确的是()。

以人为本集中体现了马克思主义历史唯物论的基本原理，体现了我们党全心全意为人民服务的根本宗旨和推动经济社会发展的根本目的。以人为本（）

关于集体劳动合同，根据《劳动合同法》，下列哪些说法是正确的?()

由施工企业的最高管理者对管理系统进行的系统评价即()

工程量清单中综合单价的构成中包括下列选项中的()。

防火卷帘外观检查中，要求双帘面卷帘的两个帘面同时升降，两个帘面之间的高度差不大于()

投资者刘小明买了1张年利率为10％的国债，其名义收益率为10％。若1年中通货膨胀率为5％，则其实际收益率为()

对于商品流通企业已经营多年的商品，如果该商品处在增长阶段，可选用的预测方法有()。

TouristA:Excuseme.HowdoIgettoPorterStreetfromhere?TouristB:______.You’dbetterasksomeoneelse.

以下关于局部总线说法正确的是()。

计算机408

学硕统考专业

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

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

以下()协议完成了从网卡到IP地址的映射。

三类线程search、insert、delete共享(访问)单链表，利用P、V原语操作实现这三类线程。限定如下：(1)search可以与同类线程同时执行；(2)insert类线程之间互斥，但是可以与任意多search同时执行；(3)del

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

设有A，B，C，D4台主机都处在同一个物理网络中，A主机的IP地址是192．155．28．112，B主机的IP地址是192．155．28．120，C主机的IP地址是192．155．28．135，D主机的IP地址是192．155．28．202。共

对汇编语言程序员来说，以下部件中不透明的是()。I．指令缓冲器；Ⅱ．移位器；Ⅲ．通用寄存器；Ⅳ．中断字寄存器；V．乘法器；Ⅵ．先行进位链；

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

采用散列函数H(k)===3XkMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51 (1)构造散列表(画示意图)； (2)装填因子；

关于以太网交换机，下面的论述中不正确的是()。

以人为本集中体现了马克思主义历史唯物论的基本原理，体现了我们党全心全意为人民服务的根本宗旨和推动经济社会发展的根本目的。以人为本（）

关于集体劳动合同，根据《劳动合同法》，下列哪些说法是正确的?()

由施工企业的最高管理者对管理系统进行的系统评价即()

工程量清单中综合单价的构成中包括下列选项中的()。

防火卷帘外观检查中，要求双帘面卷帘的两个帘面同时升降，两个帘面之间的高度差不大于()

投资者刘小明买了1张年利率为10％的国债，其名义收益率为10％。若1年中通货膨胀率为5％，则其实际收益率为()

对于商品流通企业已经营多年的商品，如果该商品处在增长阶段，可选用的预测方法有()。

TouristA:Excuseme.HowdoIgettoPorterStreetfromhere?TouristB:______.You’dbetterasksomeoneelse.

以下关于局部总线说法正确的是()。

采用散列函数H(k)===3XkMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51　　(1)构造散列表(画示意图)；　　(2)装填因子；　　