NOIP初赛选择题.ppt

初赛选择题 1 进制转换 1 十进制转换成二进制 2 十进制转换成八进制 十六进制 以二进制为跳板 3 二进制 八进制 十六进制转换成十进制 以二进制为跳板 4 不同进制比较大小 5 不同进制运算 6 B二进制O八进制D十进制H十六进制 二进制数11 01在十进制下是 A 3 25B 4 125C 6 25D 11 125在十六进制表示法中 字母A相当于十进制中的 A 9B 10C 15D 16十六进制数9A在 进制下是232 A 四B 八C 十D 十二在二进制下 1101001 1110110 A 1011B 1101C 1010D 1111一个正整数在二进制下有100位 则它在十六进制下有 位 A 7B 13C 25D 不能确定十进制小数125 125对应的八进制数是A 100 1B 175 175C 175 1D 100 175 A B B B C C 2 逻辑运算 逻辑运算符 逻辑运算描述 1 true 真 0 false 假 非1 0 非0 1 解题 排除法 找反例 逻辑表达式 的值与变量A的真假无关 A A B AB A B BC A B A B D A B A B C 3 栈和队列 栈 栈是一种特殊的线性表 其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行 有后进先出的特点 队列 Queue 也是一种运算受限的线性表 它的运算限制与栈不同 是两头都有限制 插入只能在表的一端进行 只进不出 而删除只能在表的另一端进行 只出不进 允许删除的一端称为队尾 rear 允许插入的一端称为队头 Front 有先进先出的特点 是一种先进先出的线性表 A 栈B 队列C 哈希表 散列表 D 二叉树如果一个栈初始时为空 且当前栈中的元素从栈顶到栈底依次为a b c 另有元素d已经出栈 则可能的入栈顺序是 A a d c bB b a c dC a c b dD d a b c广度优先搜索时 需要用到的数据结构是 A 链表B 队列C 栈D 散列表有六个元素FEDCBA从左到右依次顺序进栈 在进栈过程中会有元素被弹出栈 问下列哪一个不可能是合法的出栈序列 A EDCFABB DECABFC CDFEBAD BCDAEF在程序运行过程中 如果递归调用的层数过多 会因为 引发错误 A 系统分配的栈空间溢出B 系统分配的堆空间溢出C 系统分配的队列空间溢出D 系统分配的链表空间溢出 B D 深度 栈 B C A 4 算法描述 1 算法 故事2 算法执行过程的形式穷举法 递归 递推 分治 回溯 下面的故事与 算法有着异曲同工之妙 从前有座山 山里有座庙 庙里有个老和尚在给小和尚讲故事 从前有座山 山里有座庙 庙里有个老和尚在给小和尚讲故事 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 A 枚举B 递归C 贪心D 分治体育课的铃声响了 同学们都陆续地奔向操场 按老师的要求从高到矮站成一排 每个同学按顺序来到操场时 都从排尾走向排头 找到第一个比自己高的同学 并站在他的后面 这种站队的方法类似于 算法 A 快速排序B 插入排序C 冒泡排序D 归并排序 是一种选优搜索法 按选优条件向前搜索 以达到目标 当探索到某一步时 发现原先选择并不优或达不到目标 就退回一步重新选择 A 回溯法B 枚举法C 动态规划D 贪心法 B B A 5 树 二叉树 树的相关概念 度 任一结点拥有子树的数目 称为结点的度 所有结点的度的最大值 称为树的度 层 根为第一层 最大层数为树的深 高 度 根节点 叶子节点 度为0的结点 树的遍历 先 根左右 中 左根右 后 左右根 表达式中的前 中 后 缀表达式 已知一棵二叉树有10个节点 则其中至多有 个节点有2个子节点 A 4B 5C 6D 7二叉树的 第一个访问的节点是根节点 A 先序遍历B 中序遍历C 后序遍历D 以上都是如果一棵二叉树的中序遍历是BAC 那么它的先序遍历不可能是 A ABCB CBAC ACBD BAC如果根结点的深度记为1 则一棵恰有2011个叶结点的二叉树的深度最少是 A 10B 11C 12D 13表达式a b c d的后缀表达式是A abcd B abc d C abc d D abcd一个包含n个分支节点 非叶节点 的非空二叉树 它的叶节点数目最多为 A 2n 1B 2n 1C n 1D n 1 A A B D C 6 图 有向图 若图中的每条边都是有方向的 则称为有向图 有向图中的边是由两个顶点组成的有序对 有序对通常用尖括号表示 如表示一条有向边 其中vi是边的始点 vj是边的终点 和代表两条不同的有向边 有n个顶点的有向图有n n 1 条边 则此图称为完全有向图 在有n个顶点的有向图中 每个顶点的度最大可达2 n 1 无向图 边均是顶点的无序对 无序对通常用圆括号表示 如 无序对 vi vj 和 vj vi 表示同一条边 举例 V G2 v1 v2 v3 v4 E G2 vl v2 v1 v3 v1 v4 v2 v3 v2 v4 v3 v4 图的遍历 深度遍历 类似树的先根遍历 广度遍历 类似树的层次遍历 有向图顶点的度 入度 指向该顶点的边的个数 出度 从该顶点出发的边的个数 完全图 若一个图的每一对不同顶点恰有一条边相连 则称为完全图 完全图是每对顶点之间都恰连有一条边的简单图 n个端点的完全图有n个端点及n n 1 2条边 强连通图 一个有向图是强连通的 当且仅当G中有一个回路 它至少包含每个节点一次 在一个无向图中 如果任意两点之间都存在路径相连 则称其为连通图 下图是一个有4个顶点 6条边的连通图 若要使它不再是连通图 至少要删去其中的 条边 A 1B 2C 3D 4以A0作为起点 对下面的无向图进行深度优先遍历时 遍历顺序不可能是 A A0 A1 A2 A3B A0 A1 A3 A2C A0 A2 A1 A3D A0 A3 A1 A2无向完全图是图中每对顶点之间都恰有一条边的简单图 已知无向完全图G有7个顶点 则它共有 条边 A 7B 21C 42D 49已知n个顶点的有向图 若该图是强连通的 从所有顶点都存在路径到达其他顶点 则该图中最少有多少条有向边 A nB n 1C n 1D n n 1 C B B A 2020 3 17 15 可编辑 7 搜索排序与时间复杂度 各种搜索排序算法算法时间复杂度 的平均时间复杂度为O nlogn 其中n是待排序的元素个数 A 快速排序B 插入排序C 冒泡排序D 基数排序在含有n个元素的双向链表中查询是否存在关键字为k的元素 最坏情况下运行的时间复杂度是 A O 1 B O logn C O n D O nlogn 快速排序最坏情况下的算法复杂度为 A O log 2n B O n C O nlog2n D O n2 使用冒泡排序对序列进行升序排列 每执行一次交换操作系统将会减少1个逆序对 因此序列5 4 3 2 1需要执行 次操作 才能完成冒泡排序 A 0B 5C 10D 15排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变 下列哪种排序算法是不稳定的 A 冒泡排序B 插入排序C 归并排序D 快速排序 A C D C D 8 网络相关 1 邮件相关SMTP SimpleMailTransferProtocol简单邮件传输协议 邮件的发 POP3 PostOfficeProtocol3邮局协议的第3个版本 邮件的收 2 网络相关概念WWW WorldWideWeb环球信息网 HTML 超文本标记语言 标准通用标记语言的一个应用 com为顶级域名 baidu为二级域名 以此类推 TCP IP TransmissionControlProtocol InternetProtocol的简写 传输控制协议 因特网互联协议 又名网络通讯协议 是Internet最基本的协议 Internet国际互联网络的基础 由网络层的IP协议和传输层的TCP协议组成 TCP IP定义了电子设备如何连入因特网 以及数据如何在它们之间传输的标准 协议采用了4层的层级结构 每一层都呼叫它的下一层所提供的协议来完成自己的需求 TCP IP五层模型的协议应用层 传输层 网络层 数据链路层 物理层IPv4 IPv4是InternetProtocolversion4 网际协议版本4 IPv4中规定IP地址长度为32 最多有2 32 1个地址 IPv6 IPv6是InternetProtocolVersion6 为IPv4下一版本 IPv6使用的128位地址 最多2 128 1个地址 IPV6地址格式 优先选用的形式是X X X X X X X X 其中X是8个16位地址段的十六进制值 例如 CD79 BA98 7654 4210 FEDC BA98 7654 3210 3 网络OSI模型7层模型 中国的国家顶级域名是 AB chC chnD china 是主要用于显示网页服务器或者文件系统的HTML文件的内容 并让用户与这些文件交互的一种软件 A 资源管理器B 浏览器C 电子邮件D 编译器 是目前互联网上常用的E mail服务协议 A HTTPB FTPC POP3D Telnet关于HTML语言下面哪种说法是正确的 A HTML实现了文本 图形 声音乃至视频信息的统一编码 B HTML全称为超文本标记语言 C 网上广泛使用的Flash动画都是由HTML编写的 D HTML也是一种高级程序设计语言 关于互联网 下面的说法哪一个是正确的 A 新一代互联网使用的IPv6标准是IPv5标准的升级与补充 B 互联网的入网主机如果有了域名就不再需要IP地址 C 互联网的基础协议为TCP IP协议 D 互联网上所有可下载的软件及数据资源都是可以合法免费使用的 A B C B C 无论是TCP IP模型还是OSI模型 都可以视为网络的分层模型 每个网络协议都会被归入某一层中 如果用现实生活中的例子来比喻这些 层 以下最恰当的是 A 中国公司的经理与波兰公司的经理交互商业文件B 军队发布命令C 国际会议中 每个人都与他国地位对等的人直接进行会谈D 体育比赛中 每一级比赛的优胜者晋级上一级比赛 A 9 操作系统相关 在Windows资源管理器中 用鼠标右键单击一个文件时 会出现一个名为 复制 的操作选项 它的意思是 A 用剪切板中的文件替换该文件B 在该文件所在文件夹中 将该文件克隆一份C 将该文件复制到剪切板 并保留原文件D 将该文件复制到剪切板 并删除原文件通常在搜索引擎中 对某个关键词加上双引号表示 A 排除关键词 不显示任何包含该关键词的结果B 将关键词分解 在搜索结果中必须包含其中的一部分C 精确搜索 只显示包含整个关键词的结果D 站内搜索 只显示关键词所指向网站的内容 C C 关于计算机内存 下列说法哪个是正确的 A 随机存储器 RAM 的意思是当程序运行时 每次具体分配给程序的内存位置是随机而不确定的 B 1MB内存通常是指1024 1024字节大小的内存 C 计算机内存严格说来包括主存 memory 高速缓存 cache 和寄存器 register 三个部分 D 一般内存中的数据即使在断电的情况下也能保留2个小时以上 下列软件中不是计算机操作系统的是 A WindowsB LinuxC OS 2D WPS有人认为 在个人电脑送修前 将文件放入回收站中就是已经将其删除了 这种想法是 A 正确的 将文件放入回收站意味着彻底删除 无法恢复B 不正确的 只有将回收站清空后 才意味着彻底删除 无法恢复C 不正确的 即使将回收站清空 文件只是被标记为删除 仍可能通过恢复软件找回D 不正确的 只要在硬盘上出现过的文件 永远不可能被彻底删除 B D C 10 程序设计语言相关 汇编语言 汇编语言 AssemblyLanguage 是面向机器的程序设计语言 依赖于硬件体系 且助记符量大难记 高级语言 这种语言下 其语法和结构更类似汉字或者普通英文 且由远离对硬件的直接操作 如pascal c语言等 面向对象程序设计 ObjectOrientedProgramming OOP 面向对象程序设计 是一种计算机编程架构 OOP的一条基本原则是计算机程序是由单个能够起到子程序作用的单元或对象组合而成 OOP达到了软件工程的三个主要目标 重用性 灵活性和扩展性 为了实现整体运算 每个对象都能够接收信息 处理数据和向其它对象发送信息 关于汇编语言 下列说法错误的是 A 是一种与具体硬件相关的程序设计语言B 在编写复杂程序时 相对于高级语言而言代码量较大 且不易调试C 可以直接访问寄存器 内存单元 以及I O端口D 随着高级语言的诞生 如今已完全被淘汰 不再使用关于程序设计语言 下面哪种说法是正确的 A 加了注释的程序一般会比同样的没有加注释的程序运行速度慢 B 高级语言开发的程序不能使