NOIP初赛选择题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,初赛选择题,1,、进制转换,1,）十进制转换成二进制。,2,）十进制转换成八进制、十六进制。（以二进制为跳板）,3,）二进制、八进制、十六进制转换成十进制。（以二进制为跳板）,4,）不同进制比较大小。,5,）不同进制运算。,6,）,B,二进制,O,八进制,D,十进制,H,十六进制,二进制数,11.01,在十进制下是（）。,A.3.25 B.4.125 C.6.25 D.11.125,在十六进制表示法中，字母,A,相当于十进制中的（）。,A.9 B.10 C.15 D.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,B,A,与,B,（,A,B,）,A,或,B,（,A,B,）,0,0,0,0,0,1,0,1,1,0,0,1,1,1,1,1,逻辑表达式（）的值与变量,A,的真假无关。,A.(A,B),A B.(A,B),B,C.(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,b B.b,a,c,d C.a,c,b,d D.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.4 B.5 C.6 D.7,二叉树的（）第一个访问的节点是根节点。,A.,先序遍历,B.,中序遍历,C.,后序遍历,D.,以上都是,如果一棵二叉树的中序遍历是,BAC,，那么它的先序遍历不可能是（）。,A.ABC B.CBA C.ACB D.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-1 C)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),V1,V3,V2,V4,图的遍历：,深度遍历：类似树的先根遍历。,广度遍历：类似树的层次遍历。,有向图顶点的度：,入度：指向该顶点的边的个数。,出度：从该顶点出发的边的个数。,完全图：若一个图的每一对不同顶点恰有一条边相连则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。,n,个端点的完全图有,n,个端点及,n(n 1)/2,条边。,强连通图：一个有向图是强连通的，当且仅当,G,中有一个回路，它至少包含每个节点一次。,在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有,4,个顶点、,6,条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。,A.1 B.2 C.3 D.4,以,A0,作为起点，对下面的无向图进行深度优先遍历时，,遍历顺序不可能是（）。,A.A0,A1,A2,A3 B.A0,A1,A3,A2,C.A0,A2,A1,A3 D.A0,A3,A1,A2,无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图,G,有,7,个顶点，则它共有（,）条边。,A,、,7B,、,21C,、,42D,、,49,已知,n,个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？,A)nB)n+1 C)n-1D)n*(n-1),C,A0,A3,A2,A1,B,B,A,7,、搜索排序与时间复杂度,各种搜索排序算法,算法时间复杂度,排序法,最差时间分析,平均时间复杂度,稳定度,空间复杂度,冒泡排序,O(n,2,),O(n,2,),稳定,O(1),快速排序,O(n,2,),O(n*log,2,n),不稳定,O(log,2n)O(n),选择排序,O(n,2,),O(n,2,),稳定,O(1),二叉树排序,O(n,2,),O(n*log,2,n),不一顶,O(n),插入排序,O(n,2,),O(n,2,),稳定,O(1),堆排序,O(n*log,2,n),O(n*log,2,n),不稳定,O(1),希尔排序,O,O,不稳定,O(1),（）的平均时间复杂度为,O(n log n),，其中,n,是待排序的元素个数。,A.,快速排序,B.,插入排序,C.,冒泡排序,D.,基数排序,在含有,n,个元素的双向链表中查询是否存在关键字为,k,的元素，最坏情况下运行的时间复杂度是（,）。,A,、,O(1)B,、,O(log n)C,、,O(n)D,、,O(n log n),快速排序最坏情况下的算法复杂度为：,A)O(log,2,n)B)O(n)C)O(nlog,2,n)D)O(n,2,),使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少,1,个逆序对，因此序列,5,4,3,2,1,需要执行（）次操作，才能完成冒泡排序。,A.0 B.5 C.10 D.15,排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：,A),冒泡排序,B),插入排序,C),归并排序,D),快速排序,A,C,D,C,D,8,、网络相关,1,）邮件相关,SMTP,（,Simple Mail Transfer Protocol,简单邮件传输协议，邮件的,发,）,POP3,（,Post Office Protocol 3,邮局协议的第,3,个版本，邮件的,收,）,2,）网络相关概念,WWW,（,World Wide Web,环球信息网）,HTML,（超文本标记语言，标准通用标记语言的一个应用。）,（,.com,为顶级域名，,baidu,为二级域名，以此类推）,XXXX,XXX,用户名,标识符,邮箱服务器,TCP/IP,（,Transmission Control Protocol/Internet Protocol,的简写，传输控制协议,/,因特网互联协议，又名网络通讯协议，是,Internet,最基本的协议、,Internet,国际互联网络的基础，由网络层的,IP,协议和传输层的,TCP,协议组成。）,TCP/IP,定义了电子设备如何连入因特网，以及数据如何在它们之间传输的标准。协议采用了,4,层的层级结构，每一层都呼叫它的下一层所提供的协议来完成自己的需求。,TCP/IP,五层模型的协议应用层、传输层、网络层、数据链路层、物理层,IPv4,：,IPv4,是,Internet Protocol version 4:,网际协议版本,4,，,IPv4,中规定,IP,地址长度为,32,。最多有,232-1,个地址。,IPv6,：,IPv6,是,Internet Protocol Version 6,，为,IPv4,下一版本。,IPv6,使用的,128,位地址。最多,2128-1,个地址。,IPV6,地址格式：优先选用的形式是,X:X:X:X:X:X:X:X,，,其中,X,是,8,个,16,位地址段的十六进制值。例如：,CD79:BA98:7654:4210:FEDC:BA98:7654:3210,类别,A,B,C,D,E,首段,0XXXXXXX,10XXXXXX,110XXXXX,1110XXXX,1111XXXX,3,）网络,OSI,模型,7,层模型,具体,7,层,数据格式,功能与连接方式,典型设备,应用层,Application,网络服务与使用者应用程序间的一个接口,表示层,Presentation,数据表示、数据安全、数据压缩,会话层,Session,建立、管理和终止会话,传输层,Transport,数据组织成数据段,Segment,用一个寻址机制来标识一个特定的应用程序（端口号）,网络层,Network,分割和重新组合数据包,Packet,基于网络层地址（,IP,地址）进行不同网络系统间的路径选择,路由器,数据链路层,Data Link,将比特信息封装成数据帧,Frame,在物理层上建立、撤销、标识逻辑链接和链路复用 以及差错校验等功能。通过使用接收系统的硬件地址或物理地址来寻址,网桥、交换机、网卡,物理层,Physical,传输比特（,bit,）流,建立、维护和取消物理连接,光纤、同轴电缆、,双绞线、中继器和集线器,中国的国家顶级域名是（）。,A.cn B.ch C.chn D.china,（）是主要用于显示网页服务器或者文件系统的,HTML,文件的内容，并让用户与这些文件交互的一种软件。,A.,资源管理器,B.,浏览器,C.,电子邮件,D.,编译器,（）是目前互联网上常用的,E-mail,服务协议。,A.HTTP B.FTP C.POP3 D.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,语言等。,面向对象程序设计：,Object Oriented Programming,，,OOP,，,面向对象程序设计，是一种计算机编程架构。,OOP,的一条基本原则是计算机程序是由单个能够起到子程序作用的单元或对象组合而成。,OOP,达到了软件工程的三个主要目标：重用性、灵活性和扩展性。为了实现整体运算，每个对象都能够接收信息、处理数据和向其它对象发送信息。,封装性,封装是一种信息隐蔽技术，它体现于类的说明，是对象的重要特性。,继承性,继承性是子类自动共享父类之间数据和方法的机制。,多态性,对象根据所接收的消息而做出动作。,关于汇编语言，下列说法错误的是（,）。,A,、是一种与具体硬件相关的程序设计语言,B,、在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试,C,、可以直接访问寄存器、内存单元、以及,I/O,端口,D,、随着高级语言的诞生，如今已完全被淘汰，不再使用,关于程序设计语言，下面哪种说法是正确的：,A),加了注释的程序一般会比同样的没有加注释的程序运行速度慢。,B),高级语言开发的程序不能使用在低层次的硬件系统（如：自控机床）或低端手机上。,C),高级语言相对于低级语言更容易实现跨平台的移植。,D),以上说法都不对。,D,C,11,、其他,1,）,ASCII,码：全称、变换关系、某些特定字符的,ASCII,码,2,）冯,诺依曼：冯,诺依曼结构、冯,诺依曼提出的存储思想,3,）计算机硬件：存储换算、硬件组成等,4,）霍夫曼编码,5,）最短路径,6,）,NOIP,竞赛环境等,1,、,4G,技术,2,、,3D,打印技术,3,、云技术、大数据,4,、,HTML5,5,、人工智能、机器视觉、智能可穿戴,6,、固态硬盘,7,、全息存储,8,、光学计算机、量子计算机,9,、无线通讯、,WIFI,10,、可编程物质,