信息学奥赛初赛天天练-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

相关文章

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

Feign Client超时时间设置不生效的解决方法

《FeignClient超时时间设置不生效的解决方法》这篇文章主要为大家详细介绍了FeignClient超时时间设置不生效的原因与解决方法,具有一定的的参考价值,希望对大家有一定的帮助... 在使用Feign Client时,可以通过两种方式来设置超时时间:1.针对整个Feign Client设置超时时间

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

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

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