首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明,将应填入(n)处的字句写在答卷纸的对应栏内。 【函数1说明】 函数compare(SqList A,SqList B)的功能是:设A=(al,…,am)和B=(b1,…,bn)均为顺序表,“比较”两个顺序表A和B的大小。设A’
阅读下列函数说明,将应填入(n)处的字句写在答卷纸的对应栏内。 【函数1说明】 函数compare(SqList A,SqList B)的功能是:设A=(al,…,am)和B=(b1,…,bn)均为顺序表,“比较”两个顺序表A和B的大小。设A’
admin
2009-02-15
18
问题
阅读下列函数说明,将应填入(n)处的字句写在答卷纸的对应栏内。
【函数1说明】
函数compare(SqList A,SqList B)的功能是:设A=(al,…,am)和B=(b1,…,bn)均为顺序表,“比较”两个顺序表A和B的大小。设A’和B’分别为A和B中除去最大共同前缀后的子表(例如,A=(y,X,X,Z,X,Z),B=(y,x,x,z,y,x,x,2),则两者中最大的共同前缀为(y,x,x,2),在两表中除去最大共同前缀后的子表分别为A’=(X,Z)和B’=(y,x,x,2))。若A’=B’=空表,则 A=B:若A’=空表,而B’≠空表,或者两者均不为空表,且A’的首元小于B,的首元,则A<B;否则A>B。
提示:算法的基本思想为:若相等,则j+1,之后继续比较后继元素:否则即可得山比较结果。显然,j的初值应为0,循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果,则循环结束时有3种可能出现的情况需要区分。
【函数1】
int compare(SqList A,SqList B)
{
//若A<B,则返回-1;若A=B,则返回o:若A>B,则返回1
j=0;
while(j<(1)&&j<B.1ength)
if( A.elem[j] < B.elem[j] ) return(-1);
else if( A.elem[j] > B.elem[j] ) return(i);
else (2)
ff (A.length == B.length) return (0);
else fi(A.length < B.length ) return(-1);
else return(1);
}//compare
//函数1的时间复杂度是 (3)
【函数2说明】
函数 exchange_L( SLink &L, int m )的功能是:用尽可能少的辅助空间将单链表中前 m个结点和后 n 个结点的互换。即将单链表(a1,a2,...,am,b1,b2,...,bn) 改变成 (b1,b2,...,bn,a1,a2,…,am)。
【函数2】
void exchange_L( SLink &L, int m )
{
if((4)&& L->next) // 链表不空且 m!=0
{
p = L->next; k = 1;
while( k< m && p ) // 查找am所在结点
{
p =(5); ++k;
}
if((6)&&p->next) //n!=0 时才需要修改指针
{
ha = L->next; // 以指针ha记a1 结点的位置
L->next = p->next; // 将b1结点链接在头结点之后
p->next = NULL; // 设am的后继为空
q:(7); // 令q 指向b1结点
while(q->next)q=(8); // 查的bn结点
q->next =(9); // 将a1 结点链接到bn 结点之后
}
}
}
//函数2的时间复杂度是(10)。
选项
答案
(1)A.length (2)j++ (3)O(Min(A.1ength,B.1ength)) (4)m (5)p->next (6) p (7)L->next (8)q->next (9) ha (10)O(ListLength(L))
解析
函数1中,算法要求对两个顺序表进行“比较”,是一种“引用型”操作,因此在算法中不应该破坏己知表。按题目中的规定,只有在两个表的长度相等,且每个对应元素都相同时才相等;否则,两个顺序表的大小主要取决于两表中除去最大公共前缀后的第一个元素。因此,比较两表的大小不应该先比较它们的长度,而应该设一个下标变量i同时控制两个表,即对两表中“位序相同”的元素进行比较。
上述算法中只有一个while循环,它的执行次数依赖于待比较的顺序表的表长,因此,算法的时间复杂度为O(Min(A.1enZ出,B.length))。
函数2中,对链表来说,“插入”和“删除”仅需修改指针即可完成,并且由于前m个元素之间和后n个元素之间的链接关系都不需要改变,则算法的实际操作为:
先从链表中删除(a1,a2,…,am),然后将(b1,b2,…,bn)链接到头结点之后,再将(a1,a2,…,am)链接到bn之后。
算法的时间复杂度为O(L1stlen2出(L))。
转载请注明原文地址:https://kaotiyun.com/show/EgDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
软件测试的对象不包括________。
某高校人事管理系统中,规定讲师每课时的教学酬金不能超过100元,副教授每课时的教学酬金不能超过130元,教授每课时的教学酬金不能超过160元。这种情况下所设置的数据完整性约束条件称之为______。
若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是_______。
关于软件测试与软件开发的认识,不正确的是______。A.软件生命周期各个阶段都可能产生错误B.软件测试是独立于软件开发的一个工作C.软件开发的需求分析和设计阶段就应开始测试工作D.测试越早进行,越有助于提高被测软件的质量
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则___________(41)是一个大项堆结构,该堆结构用二叉树表示,其高度(或层数)为___________(42)。(41)
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则完成该项目的最少时间为_____________(34)天。活动BD最多可以晚开始______________(35)天而不会影响整个项目的进度。(35)
双层双面只读DVD盘片的存储容量可以达到(59)。
软件工程概念的提出是由于______。A.计算技术的发展B.软件危机的出现C.程序设计方法学的影响D.其他工程科学的影响
通用的风险分析表应包括()。(54)①风险问题②发生的呵能性③影响的严重性④风险预测值⑤风险优先级
流程图中文件F的纪录格式设定为见表4形式: 其中的①、②应定义为何种数据项?简述处理2、处理3和处理4作何种处理,若有排序处理则需指明排序的键及序(升序或降序)。
随机试题
建设期现金流量一般包括__________、__________、__________、__________。
FlyingintoHistoryWhenyouturnonthetelevisionorreadamagazine,celebrities(名人)areeverywhere.Althoughfameandthe
某女性患者,50岁。颊黏膜有红斑样病损,表面糜烂,周围有白色放射状条纹。鼻梁两侧皮肤有蝴蝶斑。镜下可见上皮层萎缩变薄,表层过度角化,基底细胞层液化变性,固有层浅层胶原纤维水肿、变性。毛细血管扩张,周围有慢性淋巴细胞浸润。据此可诊断为()
若P(A)=0.8,等于:
垃圾发电产业作为一项新能源产业,在我国也得到了快速发展。从1988年在深圳建成了我国第一座工业化垃圾焚烧发电厂后,到2009年垃圾焚烧发电厂已经达到93座,而且还有许多垃圾发电项目正在建设中。我国垃圾发电产业的发展得益于以下因素:(1)目前中国城市生活垃
2007年,甲公司出资60%、乙公司出资40%,投资创办丙有限责任公司,甲公司总经理刘平兼任丙公司的董事长。赵成打算加入丙公司成为股东,并拟入资20万元,下列几种方式中,符合《公司法》的是()。
酒店星级划分条件中,设施设备环节总分600分,按最终得分进行星级划分,以下说法正确的是()。
我国刑法规定的完全刑事责任年龄是()。
A、Amovie.B、Aparty.C、Aconcert.D、Aplay.CM:I’vegottwoticketsoftheconcertthisevening.Willyougowithme?W:Certa
Whenthepolicearrived,thethieves(run)______away.
最新回复
(
0
)