信息学奥赛初赛天天练-79-NOIP2015普及组-基础题4-即时通讯软件、二叉树遍历、前序遍历、中序遍历、后序遍历、算法时间复杂度

本文主要是介绍信息学奥赛初赛天天练-79-NOIP2015普及组-基础题4-即时通讯软件、二叉树遍历、前序遍历、中序遍历、后序遍历、算法时间复杂度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

NOIP 2015 普及组 基础题4

11 下面哪种软件不属于即时通信软件( )
A QQ
B MSN
C 微信
D P2P

16 前序遍历序列与中序遍历序列相同的二叉树为( )
A 根结点无左子树
B 根结点无右子树
C 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D 只有根结点的二叉树或非叶子结点只有右子树的二叉树

18 下列选项中不属于视频文件格式的是( )
A TXT
B AVI
C MOV
D RMVB

19 某算法的计算时间表示为递推关系式 T(n)=T(n−1)+n(n 为正整数)及 T(0)=1,则该算法的时间复杂度为( )
A O(logn)
B O(nlogn)
C O(n)
D O(n^2)

20 在 NOI 系列赛事中参赛选手必须使用累承办单位统一提供的设备。下列物品中不允许选手自带的是( )
A 鼠标
B 笔
C 身份证
D 准考证

2 相关知识点

1) 即时通信软件

即时通信软件是一种允许用户通过互联网进行实时通信的应用程序。它们通常提供文本、语音、视频聊天功能,以及文件传输、屏幕共享等附加功能

常用的即时通信软件:QQ、微信、MSN、Skype、WhatsApp、Telegram

2) 二叉树遍历

常见的二叉树的遍历主要有3种,先序遍历,中序遍历,后序遍历

先序遍历

先序遍历又叫先根遍历,遍历的顺序为根,左孩子,右孩子

下面二叉树的前序遍历顺序为 ABDHIEJCFKG

中序遍历

中序遍历又叫中根遍历,遍历的顺序为左孩子,根,右孩子

下面二叉树的中序遍历顺序为 HDIBJEAFKCG

后序遍历

后序遍历又叫后根遍历,遍历的顺序为左孩子,右孩子,根

下面二叉树的后序遍历顺序为 HIDJEBKFGCA

3) 算法的时间复杂度
算法的时间复杂度是一个函数,它定性描述该算法的运行时间,常用大O符号表述,它可以被认为是渐进,不考虑常数
对于足够大的输入规模,我们往往不需要花费很大力气计算太精确的结果,通常指关系增长级量,即算法的渐进效率
比如:

int sum = 0;
for(int i = 1; i<=n; i ++ ){sum = sum + i;
}

我们关心for循环的时间复杂度,而 int sum=0 忽略
因此时间复杂度为O(n),而不是O(n+1)

3 思路分析

11 下面哪种软件不属于即时通信软件( D )
A QQ
B MSN
C 微信
D P2P

分析

D P2P (Peer-to-Peer)是一种网络通信协议,主要用于实现计算机之间的直接通信和资源共享。P2P并不是一个即时通信软件,而是一种网络技术
所以P2P不属于即时通信软件

16 前序遍历序列与中序遍历序列相同的二叉树为( D )
A 根结点无左子树
B 根结点无右子树
C 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D 只有根结点的二叉树或非叶子结点只有右子树的二叉树

分析

前序遍历序列的顺序是 根 左 右
中序遍历序列的顺序是 左 根 右
左和根顺序是相反的,如果没有左子树则顺序都是 根 右,遍历顺序相同
如果只有根,遍历顺序也相同
所以选D

18 下列选项中不属于视频文件格式的是( A )
A TXT
B AVI
C MOV
D RMVB

分析

A TXT是一种纯文本文件格式,用于存储文本信息,不包含任何图像或音频信息,TXT不属于视频文件格式。
B AVI(Audio Video Interleave)是一种多媒体容器格式,用于存储音频和视频数据,AVI属于视频文件格式。
C MOV(QuickTime Movie)是一种多媒体容器格式,由苹果公司开发,用于存储音频、视频和其他时间同步的数据,MOV属于视频文件格式。
D RMVB(Real Media Variable Bitrate)是一种视频压缩格式,由RealNetworks公司开发,用于存储高质量的视频数据
所以选A

19 某算法的计算时间表示为递推关系式 T(n)=T(n−1)+n(n 为正整数)及 T(0)=1,则该算法的时间复杂度为( D )
A O(logn)
B O(nlogn)
C O(n)
D O(n^2)

分析

递推关系为 T(n)=T(n−1)+n
每次减小1,但复杂度为n
从n每次减小1,需要进行n次
所以时间复杂度为n^2

20 在 NOI 系列赛事中参赛选手必须使用累承办单位统一提供的设备。下列物品中不允许选手自带的是( A )
A 鼠标
B 笔
C 身份证
D 准考证

分析

B 笔
C 身份证
D 准考证
上面3个是与考试有关的,应该携带的,鼠标与考试无关

这篇关于信息学奥赛初赛天天练-79-NOIP2015普及组-基础题4-即时通讯软件、二叉树遍历、前序遍历、中序遍历、后序遍历、算法时间复杂度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1122292

相关文章

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python如何获取域名的SSL证书信息和到期时间

《Python如何获取域名的SSL证书信息和到期时间》在当今互联网时代,SSL证书的重要性不言而喻,它不仅为用户提供了安全的连接,还能提高网站的搜索引擎排名,那我们怎么才能通过Python获取域名的S... 目录了解SSL证书的基本概念使用python库来抓取SSL证书信息安装必要的库编写获取SSL证书信息

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型,3步搞定一个应