首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明,将应填入(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
64
问题
阅读下列函数说明,将应填入(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在数据库系统中,数据的()是指保护数据库,以防止不合法的使用所造成的数据泄漏、更改或破坏。
单元测试的测试内容包括_____________。①模块接口②局部数据结构③模块内路径④边界条件⑤错误处理⑥系统性能
在ISO/IEC软件质量模型中,功能性是与一组功能及其指定的性质的存在有关的一组属性,其子特性不包括__________。
以下关于软件测试原则的叙述中,正确的是()。
设用2K×4位的存储器芯片组成16K×8位的存储器(地址单元为0000H~3FFFH,每个芯片的地址空间连续),则地址单元0B1FH所在芯片的最小地址编号为______。A.0000HB.2800HC.2000HD.0800H
以下关于模块耦合关系的叙述中,耦合程度最低的是__________(39),其耦合类型为___________(40)耦合。(39)
以下关于汇编语言的叙述中,错误的是______。A.汇编语言源程序中的指令语句将被翻译成机器代码B.汇编语言的指令语句必须具有操作码字段,可以没有操作数字段C.汇编程序以汇编语言源程序为输入,以机器语言表示的目标程序为输出D.汇编程序先将源程序中的
某文件管理系统采用位示图(bitmap)记录磁盘的使用情况。如果系统的字长为32位,磁盘物理块的大小为4MB,物理块依次编号为:0、1、2、…,位示图字依次编号为:0、1、2、…,那么16385号物理块的使用情况在位示图中的第(24)个字中描述;如果磁盘的
对某商店业务处理系统采用数据流图(DFD)进行功能建模,其中“检查订货单”是其中的一个①。由于在进行订货单检查时,需要根据客户的欠款情况、订单金额等多个条件判断是否采取发出催款单、准备货物、发出发货单等行为,此时适合采用②进行描述。①处
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
随机试题
女,38岁,腰痛1年,加重2个月,体格检查怀疑是腰椎结核,下列哪项是不恰当的
患者48岁,G0P0,绝经1年,自觉左侧下腹部钝痛半年。近2个月来阴道偶有阵发性阴道排液,呈血水样,无特殊气味,偶自扪及下腹部有包块。下列哪项是其首选的辅助诊断手段
《民用建筑节能条例》规定,民用建筑节能的监督管理部门为()。
由指定分包单位造成的与其分包工作有关的一切索赔、诉讼和损失赔偿由指定分包单位直接对()负责。
9.消毒剂
对于二手个人住房贷款,商业银行最主要的合作单位是()。
这两天,一位其貌不扬的老先生在高铁二等座上笔耕不辍的照片刷屏网络,感动无数网友。照片中,白发苍苍、脚穿旧皮鞋,专注于修改文件的老人,正是中国工程院院士、著名摄影测量与遥感专家刘先林。他今年已经78岁。网友称他为“高铁二等座最高贵乘客”,直呼“又见扫地僧”。
2017年1-8月,W省完成民间固定资产投资(以下简称民间投资)10287.23亿元,同比增长12.6%,比全国民间投资增速快6.2个百分点,比上年同期快10.2个百分点,比上半年和一季度分别加快1.1个和6.0个百分点。1-8月,全省民间投资增
正向查找区域用于将域名解析为IP地址,在WindowsServer2003系统中可以测试域名到IP地址解析功能的命令是()。
________yousayisofnousenow.
最新回复
(
0
)