NOIP初赛整理分析 | 这些题你一定不能丢分!
NOIP初赛报名中,今天我们整体分析以下初赛考点,拿真题来告诉你一些不能丢人的知识点!
首先看一下不同知识点常考题型
![https://cdn.china-scratch.com/timg/180902/221251H25-0.jpg](https://cdn.china-scratch.com/timg/180902/221251H25-0.jpg)
题型 | 总数 | 知识点 | 数量 |
单选 | 20 | 计算机基础 | 8~10 |
C++知识点 | 2~3 | ||
数据结构及算法 | 3~4 | ||
数学逻辑 | 3~4 | ||
NOI相关 | 1~2 | ||
问题求解 | 2 | 数学 | 1 |
数据结构 | 1 | ||
读程序写结果 | 4 | C++基础知识及算法 | 4 |
完善程序 | 2 | C++基础知识及算法 | 2 |
通过分析06年到17年的考卷具体的知识点,这里我们把考点分为以下几大类:二进制、计算机基础、网络基础、编程基础、算法、数据结构、数学、数据库、NOI相关。
![https://cdn.china-scratch.com/timg/180902/2212516159-1.jpg](https://cdn.china-scratch.com/timg/180902/2212516159-1.jpg)
二进制
在二进制中考察的知识点分为:
整数和实型数二进制,十进制,八进制,十六进制之间的相互转换;
补码;
二进制编码;
Byte ,KB,MB,GB,TB
其中在试卷中出现次数最多的是整数和实型数二进制之间的相互转换,每年的试卷都会出现,并占据2~3道选择题。其次是Byte ,KB,MB,GB,TB,正在刷题的同学,你们有没有遇到呢?
计算机基础
计算机基础分类中考察到的知识点分为:
计算机基本常识
常用软件 (Adobe Acrobat Reader,microsoft软件,Photoshop等)
计算机硬件
操作系统Windows Linux Solaris 及OS基本概念
32bit 和64 bit机器:寻址空间不同
和计算机相关的奖是:图灵奖
计算机病毒
汇编语言
视频/图像文件格式 :AVI RMVB MOV MPG4 JPEG GIF PNG
摩尔定律:18个月翻一番
计算机体系结构:冯诺依曼
像计算机基本常识和常用软件这方面就看同学们的熟悉程度啦,相信同学们都不在话下。需要多注意的是计算机硬件与操作系统的部分,选择题可以考察的点有很多,出现的次数也很多!
网络基础
网络基础考察知识点分为:
邮件协议(POP3,SMTP,IMAP),地址格式
无线通信技术:wifi,蓝牙,GPRS等
传输协议:SSH,FTP,SFTP,SSL,Telnet等
即时通信:QQ,MSN,微信等
IP 地址 IPV4 IPV6
HTML语句,网页搜索
LAN,WLAN,域名
防火墙:防止网络攻击
网络基础每年大概会有1~2道选择题,以上考点在06-17年的试卷中都有出现过,概率比较大的是LAN,WLAN,域名,HTML语句和网页搜索。
编程基础
考点分为:数据类型,分支结构,循环结构,数组,函数等,尤其以循环和数组为重点。
其中C++编程基础,是考试试题中第三大题和第四大题的重点考察对象!和算法结合共占试卷50%以上的分值。敲黑板划重点啦!这类型的题,刷题的时候同学们可以秉持着多多益善的原则,有不懂的可以问我们的老师哦。
算法
算法部分考察的知识点为:
时间复杂度和空间复杂度
二分法及二分查找
贪心算法
排序(归并,插入等)
分治算法
哈希函数,哈希表
回溯
深度优先,广度优先
递归算法
高精度算法
手动给二分法及二分查找划重点,也是每年必考知识点,可能出现的地方有选择题和第四大题。另外递归算法与贪心算法也曾出现在第四答题中,复习的时候不要漏掉哦,抓住每一分的可能性!
数据结构
数据结构中考察知识点为:线性表、链表、栈、队列、树(二叉树,哈夫曼编码)、图论 (连通图,完全图,拓扑排序) 。
这里树和图论最为重要!06-17年的试卷中,基本每年的选择题都会出现,也曾以第二大题的第二小题的形式出现过3次。
数学数学可考察的点非常多,我们在这里为大家列举了近几年比较多出现的:
快速幂
排列组合
概率
逆序对
离散数学-命题逻辑
思维逻辑题
这里分几个部分给大家讲解,排列组合为每年必考,思维逻辑也是近几年问题求解的主要考察点。
另外有一些比较特别的,概率、逆序对与快速幂都是2017年试卷中的新增考点,其中逆序对更是以第四大题第一题的“身份”出现。
数据库
数据库的知识点比较少,在试卷中出现频率也很低,近10年来,只有2007年曾经出现两道选择题,分别考察了关系数据库的逻辑结构与数据库的冗余数据。
NOI相关
作为全国信息学奥林匹克竞赛联赛,考察到的NOI信息并不多,但基本每年都有,一般为1~2道选择题。
考查到的信息分别是:NOI比赛,哪些不能带入考场;NOI的中文意思;从2022年起,NOIP将不再支持Pascal;NOIP使用的评测系统是 NOI Linux;NOI的举办单位是中国计算机学会;NOIP复赛推荐的语言环境。
相信这个部分没有同学会失分,需要注意的是每一年NOI是否有一些新的政策。
单项选择题:每次共20题,每题1.5分,共计30分。每题有且仅一个正确选项。
计算机基础(每年8-10题,占选择题的一半,找份材料翻几遍就可拿分了)
NOIP2011-3. 一片容量为8G的SD卡能储存大约( )张大小为2MB的数码照片。
A.1600 B.2000 C.4000 D.16000
NOIP2011-4. 摩尔定律(Moore'slaw)是由英特尔创始人之一戈登·摩尔(GordonMoor)提出来的。根据摩尔定律,在过去几十年一级在可预测的未来纪念,单块集成电路的集成度大约每( )个月翻一番。
A.1 B.6 C.18 D.36
NOIP2011-6. 寄存器是( )的重要组成部分。
A.硬盘 B.高速缓存 C.内存 D.中央处理器(CPU)
NOIP2011-10. 有人认为,在个人电脑送修前,将文件放入回收站中就是已经将其删除了。这种想法是( )。
A .正确的,将文件放入回收站以为着彻底删除、无法恢复
B.不正确的,只有将回收站清空后,才意味着彻底删除、无法恢复
C.不正确的,即使回收站清空,文件只是被标记为删除,仍可能通过回复软件找回
D.不正确的,只要在硬盘上出现过的文件,永远不可能被彻底删除
NOIP2011-14. 生物特征识别,是利用人体本身的生物特征进行身份认证的一种技术。目前,指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生物特征识别技术及其应用的是( )。
NOIP2011-16. 关于汇编语言,下列说法错误的是(
)。
A.是一种与具体硬件相关的程序设计语言
B.在编写复杂程序时,相对于高级语言而言代码量较大,且不易调试
C.可以直接访问寄存器、内存单元、以及I/O端口
D.随着高级语言的诞生,如今已完全被淘汰,不再使用
NOIP2011-18. 1956年( )授予肖克利、巴丁和布拉顿,以表彰他们对半导体的研究和晶体管效应的发现。
A.诺贝尔物理学奖 B.约翰·冯·诺依曼奖
C.图灵奖 D.高德纳奖
NOIP2011-20. 从ENIAC到当前最先进的计算机,冯·诺依曼体系结构始终占有重要地位。冯诺依曼体系结构的核心内容是( )。
A.采用开关电路 B.采用半导体器件
C.采用存储程序和程序控制原理 D.采用键盘输入
NOIP2012-1. 计算机如果缺少( ),将无法正常启动。
A.内存 B.鼠标 C.U盘 D.摄像头
NOIP2012-3. 目前计算机芯片(集成电路)制造的主要原料是( ),它是一种可以在沙子中提炼出的物质。
A.硅 B.铜 C.锗 D.铝
NOIP2012-5. ( )不属于操作系统。
A.Windows B.DOS C.PhotoShop D.NOI Linux
NOIP2012-7. 目前个人电脑的( )市场占有率最靠前的厂商包括Intel、AMD等公司。
A.显示器 B.CPU C.内存 D.鼠标
NOIP2012-9. 1946年诞生于美国宾夕法尼亚大学的ENIAC属于( )计算机。
A.电子管 B.晶体管 C.集成电路 D.超大规模集成电路
NOIP2012-10. 无论是TCP/IP模型还是OSI模型,都可以视为网络的分层模型,每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”,以下最恰当的是( )。
NOIP2012-11. 矢量图(VectorImage)图形文件所占的存储空间较小,并且不论如何放大、缩小或旋转等都不会失真,是因为它( )。
A.记录了大量像素块的色彩值来表示图像
B.用点、直线或者多边形等基于数学方程的几何图元来表示图像
C.每个像素点的颜色信息均用矢量表示
D.把文件保存在互联网,采用在线浏览的方式查看图像
NOIP2012-13. ( )是主要用于显示网页服务器或者文件系统的HTML文件内容,并让用户与这些文件交互的一种软件。
A.资源管理器 B.浏览器 C.电子邮件 D.编译器
NOIP2012-14. ( )是目前互联网上常用的E-mail服务协议。
A.HTTP B.FTP C.POP3 D.Telnet
NOIP2012-16. 地址总线的位数决定了CPU可直接寻址的内存空间大小,例如地址总线为16位,其最大的可寻址空间为64KB。如果地址总线是32位,则理论上最大可寻址的内存空间为( )。
A.128KB B.1MB C.1GB D.4GB
NOIP2012-17. 蓝牙和Wi-Fi都是( )设备。
A.无线广域网 B.无线城域网
C.无线局域网 D.无线路由器
NOIP2012-20. 仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理,并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述,错误的是( )。
A.由研究蝙蝠,发明雷达
B.由研究蜘蛛网,发明因特网
C.由研究海豚,发明声纳
D.由研究电鱼,发明伏特电池
NOIP2013-8. 在Windows资源管理器中,用鼠标右键单击一个文件时,会出现一个名为“复制”的操作选项,它的意思是( )。
A.用剪切板中的文件替换该文件
B.在该文件所在文件夹中,将该文件克隆一份
C.将该文件复制到剪切板,并保留原文件
D.将该文件复制到剪切板,并删除原文件
NOIP2013-13. IPv4协议使用32位地址,随着其不断被分配,地址资源日趋枯竭。因此,它正逐渐被使用( )位地址的IPv6协议所取代。
A.40 B.48 C.64 D.128
NOIP2013-16. 通常在搜索引擎中,对某个关键词加上双引号表示( )。
A.排除关键词,不显示任何包含该关键词的结果
B.将关键词分解,在搜索结果中必须包含其中的一部分
C.精确搜索,只显示包含整个关键词的结果
D.站内搜索,只显示关键词所指向网站的内容
NOIP2013-17. 中国的国家顶级域名是( )。
A. .cn B. .ch C. .chn D. .china
NOIP2013-20. CCF NOIP复赛全国统一评测时使用的系统软件是( )。
A.NOI Windows B.NOI Linux C.NOI Mac OS D.NOI DOS
NOIP2014-1. 以下哪个是面向对象的高级语言( )。
A.汇编语言 B.C++ C.Fortran D. Basic
NOIP2014-2. 1TB代表的字节数量是( )。
A.2的10次方 B.2的20次方 C.2的30次方 D.2的40次方
NOIP2014-4. 以下哪一种设备属于输出设备( )。
A.扫描仪 B.键盘 C.鼠标 D.打印机
NOIP2014-5. 下列对操作系统功能的描述最为完整的是( )。
A.负责外设与主机之间的信息交换 B.负责诊断机器的故障
C.控制和管理计算机系统的各种硬件和软件资源的使用 D.将源程序编译成目标程序
NOIP2014-6. CPU、存储器、I/O设备是通过( )连接起来的。
A.接口 B.总线 C.控制线 D.系统文件
NOIP2014-7. 断电后会丢失数据的存储器是( )。
A.RAM B.ROM C.硬盘 D.光盘
NOIP2014-8. 以下哪一种是属于电子邮件收发的协议( )。
A.SMTP B.UDP C.P2P D.FTP
NOIP2014-9. 下列选项中不属于图像格式的是( )。
A.JPEG格式 B.TXT格式 C.GIF格式 D.PNG格式
NOIP2014-12. 下列几个32 位IP地址中,书写错误的是( )。
A.162.105.128.27 B.192.168.0.1
C.256.256.129.1 D.10.0.0.1
NOIP2014-20. 计算机界的最高奖是( )。
A.菲尔兹奖 B.诺贝尔奖 C.图灵奖 D.普利策奖
NOIP2015-1. 1MB等于( )。
A.10000字节 B.1024字节
C.1000×1000字节 D.1024×1024字节
NOIP2015-2. 在PC机中,PENTIUM(奔腾)、酷睿、赛扬等是指( )。
A.生产厂家名称 B.硬盘的型号
C.CPU的型号 D.显示器的型号
NOIP2015-3. 操作系统的作用是( )。
A.把源程序译成目标程序 B.便于进行数据管理
C.控制和管理系统资源 D.实现硬件之间的连接
NOIP2015-4. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以( )形式进行的。
A.二进制码 B.八进制码 C.十进制码 D.智能拼音码
NOIP2015-5. 下列说法正确的是( )。
A.CPU的主要任务是执行数据运算和程序控制
B.存储器具有记忆能力,其中信息任何时候都不会丢失
C.两个显示器屏幕尺寸相同,则它们的分辨率必定相同
D.个人用户只能使用Wifi的方式连接到Internet
NOIP2015-8. 所谓的“中断”是指( )。
A.操作系统随意停止一个程序的运行
B.当出现需要时,CPU暂时停止当前程序的执行转而执行处理新情况的过程
C.因停机而停止一个程序的运行
D.电脑死机
NOIP2015-9. 计算机病毒是( )。
A.通过计算机传播的危害人体健康的一种病毒
B.人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合
C.一种由于计算机元器件老化而产生的对生态环境有害的物质
D.利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒
NOIP2015-10. FTP可以用于( )。
A.远程传输文件 B.发送电子邮件
C.浏览网页 D.网上聊天
NOIP2015-11. 下面哪种软件不属于即时通信软件( )。
A.QQ B.MSN C.微信 D.P2P
NOIP2015-18. 下列选项中不属于视频文件格式的是( )。
A.TXT B.AVI C.MOV D.RMVB
NOIP2015-20. 在NOI系列赛事中参赛选手必须使用承办单位统一提供的设备。下列物品中不允许选手自带的是( )。
A.鼠标 B.笔 C.身份证 D.准考证
NOIP2016-1. 以下不是微软公司出品的软件是( )。
A.Powerpoint B.Word C.Excel D.AcrobatReader
NOIP2016-3. 以下不属于无线通信技术的是( )。
A.蓝牙 B.WiFi C.GPRS D.以太网
NOIP2016-4. 以下不是CPU生产厂商的是( )。
A.Intel B.AMD C.Microsoft D.IBM
NOIP2016-5. 以下不是存储设备的是( )。
A.光盘 B.磁盘 C.固态硬盘 D.鼠标
NOIP2016-6. 如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序循环按键,即CapsLock、A、S、D、CapsLock、A、S、D、......,屏幕上输出的第81个字符是字母( )。
A.A B.S C.D D.a
NOIP2016-9. 以下是32位机器和64位机器的区别的是( )。
A.显示器不同 B.硬盘大小不同
C.寻址空间不同 D.输入法不同
NOIP2016-20. 参加NOI比赛,以下不能带入考场的是( )。
A.钢笔 B.适量的衣服 C.U盘 D.铅笔
数制、编码与逻辑运算(每年2-3题,需熟练掌握数制转换与逻辑运算)
NOIP2011-1. 在二进制下,1011001+ ( ) = 1100110。
A.1011 B.1101 C.1010 D.1111
NOIP2011-2. 字符“0”的ASCII码为48,则字符“9”的ASCII码为( )。
A .39 B.57 C.120 D.视具体的计算机而定
NOIP2011-9. 一个正整数在二进制下有100位,则它在十六进制下有( )位。
A.7 B.13 C.25 D.不能确定
NOIP2012-4. 十六进制数9A在()进制下是232。
A.四 B.八 C.十 D.十二
NOIP2013-2. 二进制数11.01在十进制下是( )。
A.3.25 B.4.125 C.6.25 D.11.125
NOIP2013-4. 逻辑表达式( )的值与变量A的真假无关。
A. (A˅B)˄¬A B. (A˅B)˄¬B
C. (A˄B)˅(¬A˄B) D. (A˅B)˄¬A˄B
NOIP2013-6. 在十六进制表示法中,字母A相当于十进制中的( )。
A.9 B.10 C.15 D.16
NOIP2014-3. 二进制数 00100100 和 00010101 的和是()。
A. 00101000 B. 001010100
C. 01000101 D. 00111001
NOIP2014-11. 下列各无符号十进制整数中,能用八位二进制表示的数中最大的是( )。
A. 296 B. 133 C. 256 D. 199
NOIP2015-6. 二进制数00100100 和 00010100 的和是( )。
A. 00101000 B. 01100111
C. 01000100 D. 00111000
NOIP2015-7. 与二进制小数0.1 相等的十六进制数是( )。
A.0.8 B.0.4 C.0.2 D.0.1
NOIP2016-2. 如果256种颜色用二进制编码来表示,至少需要( )位。
A. 6 B. 7 C.8 D. 9
NOIP2016-7. 二进制数00101100 和 00010101 的和是( )。
A. 00101000 B. 01000001
C. 01000100 D. 00111000
NOIP2016-8. 与二进制小数0.1 相等的八进制数是( )。
A. 0.8 B. 0.4 C. 0.2 D. 0.1
NOIP2016-17. 下图表示一个果园灌溉系统,有 A、B、C、D 四个阀门,每个阀门可以打开或关上,所有管道粗细相同,以下设置阀门的方法中,可以让果树浇上水的是( )。
A. B打开,其他都关上 B. AB都打开,CD都关上
C. A打开,其他都关上 D. D打开,其他都关上
数据结构基础(每年4-5题,需掌握常见数据结构,特别是树、图的特征)
NOIP2011-5. 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点,则它共有( )条边。
A.7 B.21 C.42 D.49
NOIP2011-7. 如果根结点的深度记为1,则一棵恰有2011个叶结点的二叉树的深度最少是( )。
A.10 B.11 C.12 D.13
NOIP2011-11. 广度优先搜索时,需要用到的数据结构是( )。
A.链表 B.队列 C.栈 D.散列表
NOIP2011-15. 现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由4个汉字“之”、 “呼”、 “者”、 “也”组成,它们出现的次数分别为700、600、300、200。那么,“也” 字的编码长度是( )。
A.1 B.2 C.3 D.4
NOIP2011-19. 对一个有向图而言,如果每个节点都存在到达其他任何节点的路径,那么就称它是强连通的。例如,有图就是一个强连通图。事实上,在删掉边( )后,它依然是强连通的。
A.a B.b C.c D.d
NOIP2012-2. ( )是一种先进先出的线性表。
A.栈 B.队列 C.哈希表(散列表) D.二叉树
NOIP2012-6. 如果一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是( )。
A. ABC B. CBA C. ACB D. BAC
NOIP2012-12. 如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为a, b, c (如图所示),另有元素d已经出栈,则可能的入栈顺序是( )。
A. a, d, c, b B. b, a, c, d C. a, c, b, d D. d, a, b, c
NOIP2013-5. 将(2,6, 10, 17)分别存储到某个地址区间为0~10的哈希表中,如果哈希函数h(x) =( ),将不会产生冲突,其中a mod b表示a除以b的余数。
A. xmod11 B. x2 mod11 C. 2x mod 11
D.
NOIP2013-7. 下图中所使用的数据结构是( )。
NOIP2013-9. 已知一棵二叉树有10个节点,则其中至多有( )个节点有2个子节点。
A. 4 B.5 C. 6 D. 7
NOIP2013-10. 在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图,至少要删去其中的( )条边。
A. 1 B.2 C. 3 D. 4
NOIP2013-11. 二叉树的( )第一个访问的节点是根节点。
A.先序遍历 B.中序遍历 C.后序遍历 D.以上都是
NOIP2013-12. 以A0作为起点,对下面的无向图进行深度优先遍历时,遍历顺序不可能是( )。
A. A0,A1,A2,A3 B. A0,A1,A3,A2 C. A0,A2,A1,A3 D. A0,A3,A1,A2
NOIP2014-10. 链表不具有的特点是( )。
A.不必事先估计存储空间 B.可随机访问任一元素
C.插入删除不需要移动元素 D.所需空间与线性表长度成正比
NOIP2014-16. 一棵具有5层的满二叉树中结点数为( )。
A. 31 B. 32 C. 33 D. 16
NOIP2014-17. 有向图中每个顶点的度等于该顶点的( )。
A.入度 B.出度
C.入度与出度之和 D.入度与出度之差
NOIP2015-12. 6个顶点的连通图的最小生成树,其边数为( )。
A.6 B.5 C.7 D.4
NOIP2015-13. 链表不具备的特点是( )。
A.可随机访问任何一个元素
B.插入、删除操作不需要移动元素
C.无需事物估计存储空间大小
D.所需存储空间与存储元素个数成正比
NOIP2015-14. 线性表若采用链表存储结构,要求内存中可用存储单元地址( )。
A.必须连续 B.部分地址必须连续
C.一定不连续 D.连续不连续均可
NOIP2015-15. 今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈,进栈,出栈,进栈,进栈,出栈的操作,则此操作完成后,栈S的栈顶元素为( )。
A.f B.c C.a D.b
NOIP2015-16. 前序遍历序列与中序遍历序列相同的二叉树为( )。
A.根结点无左子树 B.根结点无右子树
C.只有根结点的二叉树或非叶子结点只有左子树的二叉树
D.只有根结点的二叉树或非叶子结点只有右子树的二叉树
NOIP2015-17. 如果根的高度为1,具有61个结点的完全二叉树的高度为( )。
A.5 B.6 C.7 D.8
NOIP2016-11. 一棵二叉树如图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标(2i+1)处),则图中所有结点的最大下标为 ()。
A. 6 B. 10 C. 12 D. 15
NOIP2016-15. 设简单无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。
A. 10 B. 12 C. 8 D.16
NOIP2016-18. Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图,两个人之间有边相连代表这两个人是朋友,没有边相连代表不是朋友。这个社交网站的规则是:如果某人A向他(她)的朋友B分享了某张照片,那么B就可以对该照片进行评论;如果B评论了该照片,那么他(她)的所有朋友都可以看见这个评论以及被评论的照片,但是不能对该照片进行评论(除非A也向他(她)分享了该照片)。现在Lucia已经上传了一张照片,但是她不想让Jacob看见这张照片,那么她可以向以下朋友 ( )分享该照片。
A. Dana, Michael, Eve B.Dana, Eve, Monica
C. Michael, Eve, Jacob D.Micheal, Peter, MonicaNOIP2011-1. 在二进制下,1011001+ ( ) = 1100110。
A.1011 B.1101 C.1010 D.1111
NOIP2011-2. 字符“0”的ASCII码为48,则字符“9”的ASCII码为( )。
A .39 B.57 C.120 D.视具体的计算机而定
NOIP2011-9. 一个正整数在二进制下有100位,则它在十六进制下有( )位。
A.7 B.13 C.25 D.不能确定
NOIP2012-4. 十六进制数9A在()进制下是232。
A.四 B.八 C.十 D.十二
NOIP2013-2. 二进制数11.01在十进制下是( )。
A.3.25 B.4.125 C.6.25 D.11.125
NOIP2013-4. 逻辑表达式( )的值与变量A的真假无关。
A. (A˅B)˄¬A B. (A˅B)˄¬B
C. (A˄B)˅(¬A˄B) D. (A˅B)˄¬A˄B
NOIP2013-6. 在十六进制表示法中,字母A相当于十进制中的( )。
A.9 B.10 C.15 D.16
NOIP2014-3. 二进制数 00100100 和 00010101 的和是()。
A. 00101000 B. 001010100
C. 01000101 D. 00111001
NOIP2014-11. 下列各无符号十进制整数中,能用八位二进制表示的数中最大的是( )。
A. 296 B. 133 C. 256 D. 199
NOIP2015-6. 二进制数00100100 和 00010100 的和是( )。
A. 00101000 B. 01100111
C. 01000100 D. 00111000
NOIP2015-7. 与二进制小数0.1 相等的十六进制数是( )。
A.0.8 B.0.4 C.0.2 D.0.1
NOIP2016-2. 如果256种颜色用二进制编码来表示,至少需要( )位。
A. 6 B. 7 C.8 D. 9
NOIP2016-7. 二进制数00101100 和 00010101 的和是( )。
A. 00101000 B. 01000001
C. 01000100 D. 00111000
NOIP2016-8. 与二进制小数0.1 相等的八进制数是( )。
A. 0.8 B. 0.4 C. 0.2 D. 0.1
NOIP2016-17. 下图表示一个果园灌溉系统,有 A、B、C、D 四个阀门,每个阀门可以打开或关上,所有管道粗细相同,以下设置阀门的方法中,可以让果树浇上水的是( )。
A. B打开,其他都关上 B. AB都打开,CD都关上
C. A打开,其他都关上 D. D打开,其他都关上
数据结构基础(每年4-5题,需掌握常见数据结构,特别是树、图的特征)
NOIP2011-5. 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点,则它共有( )条边。
A.7 B.21 C.42 D.49
NOIP2011-7. 如果根结点的深度记为1,则一棵恰有2011个叶结点的二叉树的深度最少是( )。
A.10 B.11 C.12 D.13
NOIP2011-11. 广度优先搜索时,需要用到的数据结构是( )。
A.链表 B.队列 C.栈 D.散列表
NOIP2011-15. 现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由4个汉字“之”、 “呼”、 “者”、 “也”组成,它们出现的次数分别为700、600、300、200。那么,“也” 字的编码长度是( )。
A.1 B.2 C.3 D.4
NOIP2011-19. 对一个有向图而言,如果每个节点都存在到达其他任何节点的路径,那么就称它是强连通的。例如,有图就是一个强连通图。事实上,在删掉边( )后,它依然是强连通的。
A.a B.b C.c D.d
NOIP2012-2. ( )是一种先进先出的线性表。
A.栈 B.队列 C.哈希表(散列表) D.二叉树
NOIP2012-6. 如果一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是( )。
A. ABC B. CBA C. ACB D. BAC
NOIP2012-12. 如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为a, b, c (如图所示),另有元素d已经出栈,则可能的入栈顺序是( )。
A. a, d, c, b B. b, a, c, d C. a, c, b, d D. d, a, b, c
NOIP2013-5. 将(2,6, 10, 17)分别存储到某个地址区间为0~10的哈希表中,如果哈希函数h(x) =( ),将不会产生冲突,其中a mod b表示a除以b的余数。
A. xmod11 B. x2 mod11 C. 2x mod 11
D.
NOIP2013-7. 下图中所使用的数据结构是( )。
NOIP2013-9. 已知一棵二叉树有10个节点,则其中至多有( )个节点有2个子节点。
A. 4 B.5 C. 6 D. 7
NOIP2013-10. 在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图,至少要删去其中的( )条边。
A. 1 B.2 C. 3 D. 4
NOIP2013-11. 二叉树的( )第一个访问的节点是根节点。
A.先序遍历 B.中序遍历 C.后序遍历 D.以上都是
NOIP2013-12. 以A0作为起点,对下面的无向图进行深度优先遍历时,遍历顺序不可能是( )。
A. A0,A1,A2,A3 B. A0,A1,A3,A2 C. A0,A2,A1,A3 D. A0,A3,A1,A2
NOIP2014-10. 链表不具有的特点是( )。
A.不必事先估计存储空间 B.可随机访问任一元素
C.插入删除不需要移动元素 D.所需空间与线性表长度成正比
NOIP2014-16. 一棵具有5层的满二叉树中结点数为( )。
A. 31 B. 32 C. 33 D. 16
NOIP2014-17. 有向图中每个顶点的度等于该顶点的( )。
A.入度 B.出度
C.入度与出度之和 D.入度与出度之差
NOIP2015-12. 6个顶点的连通图的最小生成树,其边数为( )。
A.6 B.5 C.7 D.4
NOIP2015-13. 链表不具备的特点是( )。
A.可随机访问任何一个元素
B.插入、删除操作不需要移动元素
C.无需事物估计存储空间大小
D.所需存储空间与存储元素个数成正比
NOIP2015-14. 线性表若采用链表存储结构,要求内存中可用存储单元地址( )。
A.必须连续 B.部分地址必须连续
C.一定不连续 D.连续不连续均可
NOIP2015-15. 今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈,进栈,出栈,进栈,进栈,出栈的操作,则此操作完成后,栈S的栈顶元素为( )。
A.f B.c C.a D.b
NOIP2015-16. 前序遍历序列与中序遍历序列相同的二叉树为( )。
A.根结点无左子树 B.根结点无右子树
C.只有根结点的二叉树或非叶子结点只有左子树的二叉树
D.只有根结点的二叉树或非叶子结点只有右子树的二叉树
NOIP2015-17. 如果根的高度为1,具有61个结点的完全二叉树的高度为( )。
A.5 B.6 C.7 D.8
NOIP2016-11. 一棵二叉树如图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标(2i+1)处),则图中所有结点的最大下标为 ()。
A. 6 B. 10 C. 12 D. 15
NOIP2016-15. 设简单无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。
A. 10 B. 12 C. 8 D.16
NOIP2016-18. Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图,两个人之间有边相连代表这两个人是朋友,没有边相连代表不是朋友。这个社交网站的规则是:如果某人A向他(她)的朋友B分享了某张照片,那么B就可以对该照片进行评论;如果B评论了该照片,那么他(她)的所有朋友都可以看见这个评论以及被评论的照片,但是不能对该照片进行评论(除非A也向他(她)分享了该照片)。现在Lucia已经上传了一张照片,但是她不想让Jacob看见这张照片,那么她可以向以下朋友 ( )分享该照片。
A. Dana, Michael, Eve B.Dana, Eve, Monica
C. Michael, Eve, Jacob D.Micheal, Peter, Monica
算法基础(每年2-3题,了解常见算法特征即可,更趋向解决实际问题了)
NOIP2011-8. 体育课的铃声响了,同学们都陆续地奔向操场,按老师的要求从高到矮站成一排。每个同学按顺序来到操场时,都从排尾走到排头,找到第一个比自己高的同学,并站在他的后面。这种站队的方法类似于( )算法。
A.快速排序 B.插入排序 C.冒泡排序 D.归并排序
NOIP2011-12. 在使用高级语言编写程序时,一般提到的“空间复杂度”中的“空间”是指( )。
A .程序运行时理论上所占的内存空间
B.程序运行时理论上所占的数组空间
C.程序运行时理论上所占的硬盘空间
D.程序源文件理论上所占的硬盘空间
NOIP2011-13. 在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素,最快情况下运行的时间复杂度是( )。
A . O(1 ) B . O( log n ) C. O( n ) D. O( n log n )
NOIP2011-17. ( )是一种选优搜索法,按选优条件向前搜索,以达到目标。当搜索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。
A.回溯法 B.枚举法 C.动态规划 D.贪心
NOIP2012-8. 使用冒泡排序对序列进行升序排序,每执行一次交换操作将会减少 1 个逆序对,因此序列 5, 4, 3, 2, 1需要执行( )次交换操作,才能完成冒泡排序。
A. 0 B.5 C. 10 D. 15
NOIP2012-15. ( )就是把一个复杂的问题分成两个或者更多的相同或相似的子问题,再把子问题分成更小的子问题⋯⋯直到最后的子问题可以简单的直接求解。而原问题的解就是子问题解的并。
A.动态规划 B.贪心 C.分治 D.搜索
NOIP2012-18. 在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误。
A.系统分配的栈空间溢出
B. 系统分配的堆空间溢出
C.系统分配的队列空间溢出
D. 系统分配的链表空间溢出
NOIP2013-3. 下面的故事与( )算法有着异曲同工之妙。
从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:“从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事’....”
A.枚举 B.递归 C.贪心 D.分治
NOIP2013-14. ( )的平均时间复杂度为O(n log n),其中 n 是待排序的元素个数。
A.快速排序 B.插入排序 C.冒泡排序 D.基数排序
NOIP2014-18. 设有100个数据元素,采用折半搜索时,最大比较次数为( )。
A. 6 B.7 C. 8 D. 10
NOIP2015-19. 设某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n(n为正整数)及T(0)=1,则该算法的时间复杂度为( )。
A.O(logn) B.O(nlogn) C.O(n) D.O(n2)
NOIP2016-16. 有 7 个一模一样的苹果,放到 3 个一样的盘子中,一共有( )种放法。
A. 7 B.8 C. 21 D. 37
NOIP2016-19. 周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是:先洗菜 10分钟,然后切菜 10分钟,最后炒菜 10 分钟。那么做一道菜需要 30 分钟。注意:两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗,也不能同时切。那么做完三道菜的最短时间需要( )分钟。
A. 90 B. 60 C. 50 D. 40
程序设计基础(每年2-3题,比重大了,更像程序阅读题了,有编程基础可拿分)
NOIP2012-19. 原字符串中任意一段连续的字符组成的新字符串称为子串。则字符串“ AAABBBCCC” 共有( )个不同的非空子串。
A. 3 B.12 C. 36 D. 45
NOIP2013-1. 一个32位整型变量占用( )个字节。
A. 4 B.8 C. 32 D. 128
NOIP2013-18. 把64位非零浮点数强制转换成32位浮点数后,不可能( )。
A.大于原数 B.小于原数
C.等于原数 D.与原数符号相反
NOIP2013-19. 下列程序中,正确计算1,2, ..., 100这100个自然数之和sum(初始值为0)的是( )。
NOIP2013-15. 下面是根据欧几里得算法编写的函数,它所计算的是a和b的( )。
int euclid(int a, int b)
{
if (b == 0)
return a;
else
return euclid(b, a % b);
}
A.最大公共质因子 C.最大公约数
B.最小公共质因子 D.最小公倍数
NOIP2014-13. 要求以下程序的功能是计算:s= 1 + 1/2 + 1/3 + ... + 1/10。
#include
using namespace std;
int main() {
int n;
float s;
s = 1.0;
for (n = 10; n > 1; n--)
s = s + 1 / n;
cout << s << endl;
return 0;
}
程序运行后输出结果错误,导致错误结果的程序行是( )。
A. s=1.0; B. for(n=10;n>1;n--)
C. s=s+1/n; D. cout<<s<<endl;< p="">
NOIP2014-14. 设变量 x 为float 型且已赋值,则以下语句中能将 x 中的数值保留到小数点后两位,并将第三位四舍五入的是( )。
A. x=(x*100)+0.5/100.0; B.x=(x*100+0.5)/100.0;
C. x=(int)(x*100+0.5)/100.0;
D.x=(x/100+0.5)*100.0;
NOIP2014-15. 有以下程序:
#include
using namespace std;
int main() {
int s, a, n;
s = 0;
a = 1;
cin >> n;
do {
s += 1;
a -= 2;
} while (a != n);
cout << s << endl;
return 0;
}
若要使程序的输出值为2,则应该从键盘给 n 输入的值是( )。
A. -1 B. -3 C. -5 D. 0
NOIP2014-19. 若有如下程序段,其中 s、a、b、c 均已定义为整型变量,且a、c 均已赋值,c> 0。
s = a;
for (b = 1; b <= c; b++)
s += 1;
则与上述程序段功能等价的赋值语句是( )。
A. s=a+b B. s=a+c C. s=s+c D. s=b+c
NOIP2016-10. 以下关于字符串的判定语句中正确的是( )。
A.字符串是一种特殊的线性表
B.串的长度必须大于零
C.字符串不可以用数组来表示
D.空格字符组成的串就是空串
NOIP2016-12. 若有如下程序段,其中 s、a、b、c 均已定义为整型变量,且a、c 均已赋值(c大于0)。
s = a;
for (b = 1; b <= c; b++)
s = s + 1;
则与上述程序段修改 s 值的功能等价的赋值语句是()。
A. s = a + b; B. s = a + c; C. s = s + c; D. s = b + c;
NOIP2016-13. 有以下程序:
#include
using namespace std;
int main() {
int k = 4, n = 0;
while (n < k) {
n++;
if (n % 3 != 0)
continue;
k--;
}
cout << k << "," << n << endl;
return 0;
}
程序运行后的输出结果是( )。
A. 2,2 B. 2,3 C. 3,2 D. 3,3
NOIP2016-14. 给定含有 n 个不同的数的数组L=。如果 L 中存在 x(i 1 < i <......>xn,则称L是单峰的,并称xi是L的 “峰顶”。现在已知 L 是单峰的,请把a-c 三行代码补全到算法中使得算法正确找到 L 的峰顶。
a. Search(k+1, n)
b. Search(1, k-1)
c. return L[k]
Search(1, n)
1. k←⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then __________
4. else if L[k] > L[k-1] and L[k] < p="">
5. then __________
6. else __________
正确的填空顺序是( )。
A. c,a,b B. c,b,a C. a,b,c D. b,a,c
--end--
声明:本文章由网友投稿作为教育分享用途,如有侵权原作者可通过邮件及时和我们联系删除:freemanzk@qq.com