首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
admin
2019-08-15
83
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容:
(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://kaotiyun.com/show/ylCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
二战后,美苏关系从盟友走向对抗,其根源是()
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为:intIsFull_Bitree(BitreeT)。
设备管理中,设备映射表(DMT)的作用是()。
某计算机的主存地址空间大小为256MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下:假定int类型数据用32位补码表示,程序
以太网交换机进行转发决策时使用的PDU地址是()。
生成多项式为x3+x+1,则数据信息10101的CRC编码是()。
已知主机A的主频为40MHz,现在用这台主机运行一组标准测试程序A,A中包含的各种指令和响应所需要的时间如下表所示:请回答以下问题:(1)求主机有效的CPI。(2)求主机的MIPS。(3)假设程序A在计算机上运行的时间为100
CSMA/CA是如何实现“冲突避免”的?
随机试题
控告人张某(女,28岁,系某县卫生局办事员),平日性格比较开朗,说话爽快且多。一天,在县卫生局李局长儿子的婚宴上,张某对同桌的同事王某说了句冒犯上司的话:“可惜了这么个漂亮的新娘子。”事后王某将此话告诉了李局长。尔后不久,这位李局长为母亲办八十寿宴,作为下
划分信息不对称性的角度通常有
A.多发性骨髓瘤B.食管癌C.黑色素瘤D.胃癌对放射治疗中度敏感的肿瘤是
患儿10岁.上前牙牙龈时常流脓1个月余。查远中舌面深龋,探无反应,无穿髓孔,松I度,叩痛(+),冷热测无反应,唇侧牙龈近根尖处有一窦道口。临床拟诊断为
市场调查中,统计分析及解释的过程包括()。
固定式泡沫灭火系统的泡沫喷射可分为液上喷射和液下喷射两种方式,其中液上喷射泡沫灭火系统适用于()。
Readingmakesafullman;conferenceareadyman;andwritinganexactman.
Mr.Smithhasbeenawayfromhomeforalongtime.Heislookingforwardto______hiswife.
除非动手术,要不然治不好他的病。
Thestrikeistoprotestagainst
最新回复
(
0
)