首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
admin
2015-12-30
78
问题
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为
,请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。
要求:
给出算法的基本设计思想。
选项
答案
顺序遍历两个链表到尾结点时,并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点,我们先在长链表上遍历k个结点,之后同步遍历两个链表,这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的,所以它们肯定同时到达第一个公共结点。 [*] 算法的基本设计思想: ①分别求出str1和str2所指的两个链表的长度m和n; ②将两个链表以表尾对齐(如上图所示):令指针p、q分别指向str1和str2的头结点,若m>=n,则使p指向链表中的第m-n+1个结点;若m<n,则使q指向链表中的第n-m+1个结点,即使指针p和q所指的结点到表尾的长度相等。 ③反复将指针p和q同步向后移动,并判断它们是否指向同一结点。若p和q指向同一结点,则该点即为所求的共同后缀的起始位置。
解析
转载请注明原文地址:https://kaotiyun.com/show/4Kxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
蒙古军第一次大规模进攻南宋是在()时期
汉灵帝中平元年(184),()在7州28郡同时俱起,这是中国历史上第一次组织、准备比较严密的农民起义。
论述近代法国专制制度形成的过程及其影响
论述斯巴达的阶级结构、政治制度和社会风尚
解析两个战场的地位、作用及相互关系。
《齐民要求.序》中写道:“今采摭经传,爰及歌谣,洵之老成,验之行事,起自农耕,终于醯醢(酱醋),资生之靡不毕书书;号日《齐民要术》……舍本逐末,贤哲所非……故商贾之事,阙而不录。”这段材料表明作者()。①采取古今资料的编撰原则②
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
随机试题
在附带民事诉讼的判决、裁定生效后,执行若遇到特殊情况,使判决、裁定无法执行时,依法裁定终结执行的机关是
Advertisementcanbethoughtof"asthemeansofmakingknowninordertobuyorsellgoodsorservices".Advertisementaimsto
甲个体商店(增值税小规模纳税人)2018年9月首次购买增值税税控系统专用设备,取得的专用发票上注明的金额为3200元,税额为416元。当月零售货物取得销售收入152400元;用部分外购商品抵债,抵债商品的买价为8600元。售价为1200元。该个体商店当月应
甲公司存货发出计价采用月末一次加权平均法,因管理需要将其改为移动加权平均法违背可比性原则。()
下列关于帧中继网与因特网关系的描述中,错误的是()。
材料1:全面推进依法治国,总目标是建设中国特色社会主义法治体系,建设社会主义法治国家。这就是,在中国共产党领导下,坚持中国特色社会主义制度,贯彻中国特色社会主义法治理论,形成完备的法律规范体系、高效的法治实施体系、严密的法治监督体系、有力的法治保障体系,形
幼儿园对80名小朋友参加兴趣班情况进行调查,调查发现一共报了三种兴趣班且每个小朋友都有报班。其中未报钢琴班的有40人,未报美术班的有50人,未报舞蹈班的有60人。问至少有多少人报了不止一个兴趣班?()
若某文件系统的目录结构如下图所示,假设用户要访问文件fiava,且当前工作目录为Program,则该文件的全文件名为(46),绝对路径和相对路径分别为(47)。(46)
下列表述正确的是()。
GetWhatYouPayFor?NotAlways[A]ThemostexpensiveelectioncampaigninAmericanhistoryisover.ExecutivesacrossAmerica
最新回复
(
0
)