首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明,将应填入(n)处的字句写在对应栏内。 【函数1说明】 函数compare(SqList A, SqList B)的功能是:设A=(al,…,am)和B=(b1,…,bn)均为顺序表,“比较”,两个顺序表A和B的大小。设A’ 和B’
阅读下列函数说明,将应填入(n)处的字句写在对应栏内。 【函数1说明】 函数compare(SqList A, SqList B)的功能是:设A=(al,…,am)和B=(b1,…,bn)均为顺序表,“比较”,两个顺序表A和B的大小。设A’ 和B’
admin
2009-02-15
24
问题
阅读下列函数说明,将应填入(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,2,y,x,x,z),则两者中最大的共同前缀为 (y,x,x,z),在两表中除去最大共同前缀后的子表分别为A’=(x,z)和B’=(y,x,x,z))。若 A’=B’=空表,则A=B;若A’=空表,而B’≠空表,或者两者均不为空表,且A’的首元小于 B’首元,则A<B:否则A>B。
提示:算法的基本思想为:若相等,则j+1,之后继续比较后继元素;否则即可得出比较结果。显然,j的初值应为0,循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果,则循环结束时有3种可能出现的情况需要区分。
【函数1】
int compare ( SqListA, SqList B)
{
//若A<B,则返回-1;若A=B,则返回0:若A>B,则返回1
j =0;
while(i< (1) &&j<B. length)
if(A. elem[j] < B. elem[j] )return(-1)
else if(A. elem[j] > B. elem[j] )return(1);
else (2);
if(A. length == B. length) return(0);
else if(A. length<B. length)return(-1);
else return(1)
}//compare
//函数1的时间复杂度是(3)。
【函数2说明】
函数exchanse_L(SLnk&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) //链表不空且Lm!=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. length,B. length)) (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. length,B. length))。
函数2中,对链表来说,“插入”和“删除”仅需修改指针即可完成,并且由于前m个元素之间和后n个元素之间的链接关系都不需要改变,则算法的实际操作为:
先从链表中删除(a1,a2,…,am),然后将(b1,b2,…,bn)链接到头结点之后,再将(a1,a2,…,am)链接到bn。之后。算法的时间复杂度为O(ListLength(L))。
转载请注明原文地址:https://kaotiyun.com/show/OrDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在进行软件设计时,以下结构设计原则中,不正确的是()。
对于防病毒系统的测试是系统安全测试的重要内容,下列不属于防病毒系统安全测试基本测试点的是____________。
在ISO/IEC软件质量模型中,功能性是与一组功能及其指定的性质的存在有关的一组属性,其子特性不包括__________。
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(37)
某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用(40)排序算法最好,时间复杂度为(41)。(41)
页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4K,地址变换过程如下图所示,图中逻辑地址用十进制表示。图中有效地址经过变换后,十进制物理地址a应为(18)。
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
随机试题
患者身高170cm,体重80kg,葡萄糖耐量试验结果为:空腹血糖125mg/dL,1小时185mg/dL,2小时160mg/dL,3小时132mg/dL,单凭此结果,哪种情况的可能性大()(1992年)
(2007年)描述液体运动有迹线和流线的概念()。
下列工程索赔事项中,属于发包人向承包人索赔的有()。
剪力墙体系的剪力墙一般为钢筋混凝土墙,以下说法正确的是()。
根据《发票管理办法》的规定,填开发票的单位和个人应在发生经营业务确认营业收入时开具发票。未发生经营业务一律不准开具发票。()
五行学说中,金克木,木克土,水生木,金生土。( )
WT0对IT行业的影响()。
结合材料,回答问题:材料1在普通形势之下,国民革命的胜利,自然是资产阶级的胜利,……国民革命成功后,在普通形势之下,自然是资产阶级握得政权。所以中国农民运动,必须国民革命完全成功,然后内产业勃兴,然后普遍的农业资本化,然后农业的无产阶级发达集中起来,然
OnherfirstmorninginAmerica,lastsummer,mydaughterwentouttoexplorehernewneighborhood—alone,withouteventellingm
TheMagneticAttractionofPhysicsIt’samazingwhatyoucandowithafewpaperclipsandmargarinetubs,saysRichardWest,hea
最新回复
(
0
)