2. 考研
  3. 线性表(a1，a2，a3…，an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素，请设计一个时间复杂度最低的算法。找到x后，将其与后继元素位置相交换。如果线性表中没有x，将其插入表中并使表中元素仍递增有序。

线性表(a1，a2，a3…，an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素，请设计一个时间复杂度最低的算法。找到x后，将其与后继元素位置相交换。如果线性表中没有x，将其插入表中并使表中元素仍递增有序。

admin2014-07-18  68
问题 线性表(a1，a2，a3…，an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素，请设计一个时间复杂度最低的算法。找到x后，将其与后继元素位置相交换。如果线性表中没有x，将其插入表中并使表中元素仍递增有序。请回答下列问题：
  (1)给出算法的主要思想；
  (2)写出算法的实现函数；
  (3)总结所用算法的时间和空间复杂度。
选项
答案(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。 (2)算法实现如下： void SearchExchangeInesert(ElemType a[]，ElemType x) ∥a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序 low=0： high=n-1：／／low和high指向线性表下界和上界的下标 while(low<=high){ mid=(low+high)／2；／／找中间位置 if(a[mid]==x)break；／／找到x，退出while循环 else if(a[mid]high)／／查找失败，插入数据元素x V{ for(i=n-1；i>high；i--) a[i+1]=a[i]；／／后移元素 a[i+1]=x；／／插入x }∥结束插入 }∥结束本算法 (3)折半的时间复杂度为0(10gn)，如果不存在x的情况下，在线性表中插入元素的时候，时间复杂度取决于x插入的位置，最坏情况下为0(n)。算法实现过程中使用的辅助空间为常量，空间复杂度为0(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/paxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)