重磅更新!强推每日两题栏目!助你408统考高分上岸!

发布时间:2024年01月17日

? ? ???各位计算机专业考研的小伙伴们,大家好!翔逸学长将按数据结构-计算机组成原理-操作系统-计算机网络的顺序发布每日两题。题目来源于自命题往年真题和课本习题以及408统考真题。希望能够帮助大家2025考研顺利上岸!我们一起努力!

1.下列操作时间复杂度为O(1)的是_____. (上海大学 2018年)

A. ?在顺序表中插入一个元素

B. ?在单链表中访问一个元素

C. ?在单链表中插入一个元素

D. ?在顺序表中访问一个元素

2.假设一个栈由一个线性链表实现,其中仅有一个指针指向链表的第一个元素(栈顶)。下面哪一个关于进栈和出栈操作的算法复杂度是正确的?_______(上海科技大学 2018年)

A. ? (1)O(n)?(2)O(1)

B. ?(1)O(1) (2)O(n)

C. ?(1)O(1)?(2)O(1)

D. ? (1)O(n) (2)O(n)

请认真思考再看下面的解析哦!

解析:

1.选D。顺序表支持随机访问,访问一个元素时间复杂度为O(1);顺序表的插入可能需要移动大量元素,平均时间复杂度为O(n);单链表访问或插入一个元素都需要从头结点查询到指定的位置,平均时间复杂度为O(n)。

2.选C。栈(Stack)是只允许在一端进行插入或删除操作的线性表。依题意,当仅有一个指针指向链表的第一个元素(栈顶)时,链栈的进栈和出栈操作相当于对一个单链表的第一个结点进行插入和删除,故算法复杂度均为O(1)。

后续更新请关注微信公众号--翔逸学长

声明:本公众号部分资料由于是花费大量时间和精力制作完成,故不免费分享,希望大家能多多理解。但为了满足关注的小伙伴复习需要,因此推出此栏目。待资料整理完成后将通过视频或公众号推文展示部分,售价是按付出的时间和精力来划定,会考虑实际情况。免费资源谁不想要,但是如果都免费的话,靠广告收入是不行的哈。不信请看下图:

图片

? ? ? 部分关注者一看到思维导图等资料需要付费才能获取,就立刻取关,这很正常,我考研的时候也这样,看到要转发多少多少群聊或者都是满满水印的资料,而且因为我家庭条件很差,连电脑都是爱心人士捐赠的,我大学期间曾吃了2-3年的2.3元的午餐或晚餐,连早餐都舍不得花2块钱。我的考研复习资料还是同高中毕业的学长送我的旧版呢,没钱开百度网盘会员,也是学长借用给我的。还有,同样的资料,网上有的需要付费9.9元以上,不都还是大把人去付费,而我的资料仅仅需要2-4元,怎么还会有人在后台骂人呢?后台骂了还不行,还去我视频下面评论区乱喷,我只能说,如果你不想付费就想拿到我的资料的话,你说你是我什么人?朋友还是同学?后台骂了就骂了吧,还去评论区骂?能不能换位思考一下咯?还是希望大家能够多多理解,谢谢!

文章来源:https://blog.csdn.net/Protinx/article/details/135654102
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。