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

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

admin2019-08-01  31
问题 线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
    (3)分别给出算法各部分的时间复杂度。
选项
答案(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。 (2)算法的设计如下： void searchExchangeInsert(ElemType a[]，ElemType x){ int low=0：int high=n一1：int mid； ／／low和high指向线性表下界和上界的下标 while(low＜=high){ mid=(low+high)／2； ／／找中间位置 if(a[mid]==x)break； ／／找到x，退出while循环 else if(a[mid]＜x)low=mid+1； ／／~tj中点mid的右部去查 else high=mid一1： ／／到中点mid的左部去查 } if(a[mid]==x&&mid!=n){ ／／若最后一个元素与x相等， ／／则不存在与其后继交换的操作 t=a[mid]； a[mid]=a[mid+1]； a[mid+1]=t； } ／／数值x与其后继元素位置交换 if(low＞high){ ／／查找失败，插入数据元素x int i； for(i=n—1：i＞high；i一一) a[i+1]=a[i]； ／／后移元素 a[low]=x； ／／插入x } ／／结束插入 } (3)在利用折半查找的方法查找x的过程中时间复杂度为O(nlog2n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/x8Ci777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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