首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明,将应填入(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
38
问题
阅读下列函数说明,将应填入(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
函数f()、g()的定义如下所示,已知调用f时传递给其形参x的值是10,若以传值方式调用g,则函数f的返回值为__________。
已知函数f()、g()的定义如下所示,调用函数f时传递给形参x的值是5。若g(a)采用引用调用(callbyreference)方式传递参数,则函数f的返回值为(12);若g(a)采用值调用(callbyvalue)的方式传递参数,则函数f
两名以上的申请人分别就同样的发明创造申请专利时,专利权授权给(35)。
以下关于信息安全的叙述,不正确的是______。A.SYN洪水攻击通过发送大量TCP连接请求以占满网络带宽,使其他用户无法正常连接服务B.缓冲区溢出攻击能通过修改函数返回地址并执行恶意代码,进而获得系统的控制权C.计算机病毒的主要特征包括破坏性、寄生
在计算机系统中总线宽度分为地址总线宽度和数据总线宽度。若计算机中地址总线的宽度为32位,则最多允许直接访问主存储器_____的物理空间。
()不是RISC的特点。
假设磁盘块与缓冲区大小相同,每个盘块读入缓冲区的时间为10μs,由缓冲区送至用户区的时间是5μs,系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区,并送至用户区进行处理,那么采用单缓冲区需要花费的时间
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。1.将(1)处空缺设备的名称填写在答题纸的相应位置。2.(1)所在局域网内的PC机或笔记本的IP地址有
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)请用300字以内的文字,以提纲形式描述该21层教学综合大楼综合布线设计的方案要点。
随机试题
怀疑胃癌者的首选诊断方法是
A、心功能不全B、贫血C、核黄素缺乏症D、脑血管疾病E、急性支气管炎口角歪斜,常见于
A.补气,养血B.补气,解毒C.补气,活血D.补气,养阴E.补气,燥湿白术的功效是
1999年9月,某铁合金厂与某铁路分局签订了年度货运合同。合同规定,由铁路分局将20万吨钢材,逐月从甲站发至乙站,收货人为某机械厂。合同还载明了违约责任和双方约定的其他事项。同年10月,铁合金厂将6000吨钢材运至甲站,交付该铁路分局承运。交运货物过程中,
《环境空气质量标准》中,以下污染物项目未规定年平均浓度限值的是()。
当需要采取税收保全措施时,下列资产中,不能纳入税收保全范围的是()。
银行财务报表中反映企业某一时点状况的静态报表是()。
贾某,男,40岁,无子无女,无工作无收入,三年前丧偶,从此疯疯癫癫。父母因病也已去世,留下遗产200万。现在贾某的哥哥、外祖父都想担任其监护人,为此发生争议。以下说法正确的是()。
最初的人类,为了寻找足够的食物,经常过着一种漂泊不定的生活,漂泊到一个地方,即随便找个临时夜宿处。这种时常迁徙但又随遇而安的居住方式,应当视作人类从巢居形式进入穴居形式之前所经历的一个过渡阶段。对文中“过渡阶段”的概括最正确的一项是( )。
Modempeoplewearmanymasksthatkeeptheirrealityconfinedand【C1】______,eventothemselves.Thepossibilityofencounterin
最新回复
(
0
)