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

线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容： (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增

admin2019-08-15  65
问题 线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：
    (1)用最少的时间在表中查找数值为x的元素。
    (2)若找到将其与后继元素位置相交换。
    (3)若找不到将其插入表中并使表中元素仍递增有序。
选项
答案 (1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。 void SearchExchangeInsert(ElemType a[]；ElemType x) ／a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的／／元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序 { low=0； high=n—l； ／／low和high指向线性表下界和上界的下标 while(low＜=high) { mid=(low+high)／2i ／／找中间位置 if(a[mid]==x)break； ／／找到x，退出while循环 else if(a[mid]＜x)low=mid+1；／／到中点mid的右半去查 else high=mid一1； ／／到中点mid的左半去查 } if(a[mid]==x＆＆mid!=n) ／／若最后一个元素与x相等，则不存在与其后继交换的操作 { t=a[mid]； a[mid]=a[mid4-1]； a[mid+1]=t； } ／／数值x与其后继元素位置交换 if(low＞high) ／／查找失败，插入数据元素x { for(i=n-1；i＞high；i一一) a[i+1]=a[i]； ／／后移元素 a[i+1]=x； ／／插入x } ∥结束插入 } ∥结束本算法 (2)算法讨论 首先是线性表的描述。算法中使用一维数组a表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体，对元素的引用应使用a．elem[i]。另外，元素类型就假定是ElemType，未指明具体类型。其次，C中一维数组下标从0开始，若说有n个元素的一维数组，其最后一个元素的下标应是n－1。最后，本算法可以写成三个函数，即查找函数、交换后继函数与插入函数，写成三个函数显得逻辑清晰、易读。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/ylCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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