信息学奥赛基础知识讲义

1、信息学奥赛基石知识讲义根底局部一、进制：2进制数与8进制、10进制、16进制数的换算、换算1:将N进制数换算成10进制数(N可以为2,8,16或其它自然数)换算2:将10进制数换算成N进制数(N可以为2,8,16或其它自然数)1 .以下无符号数中,最小的数是()/A.()2B.(75)10C.(37)8D.(2A)167、小张用十六进制,八进制和十进制写下了如下一个等式：52-19=33式中三个数是各不相同进位制的数,试问52,19,33,分别为.(A)8,10,16(B)10,16,8(c)8,16,10(D)10,8,16二、数据的存储和编码所有的数据都是以二进制存储在计算机的存储器中的,

2、数据的传送、存储、加工、处理或指令都是以二进制形式进行的.对于数值：弄清原码、反码、补码以及定点数和浮点数.负数在计算机中以补码形式存放,小数在计算机中是以浮点数形式存放.0的原码表示法有两种,+0和一08位定点整数的补码表示范围为-128+12714、计算机中的数有浮点数与定点数两种,其中用浮点数表示的数,通常由()这两局部组成.A.指数与基数B.尾数与小数C.阶码与尾数D.整数与小数8、如果用一个字节表示一个整数,最高位用作符号位,其他位表示数值,例如00000001表示+1,表示-1(1) 试问这样表示法的整数a的范围应是A、-127=a=127B、-128=a=128C-128=a12

3、7D、-128a=0个数据元素的有限序列、/3、特征：1数据表中的元素具有相同的特性相同的数据类型3、2元素之间具备线性关系有顺序,并且是一对一的关系相关名词：表头、表尾eg:线性表是：A、有限序列,可以为空；B、有限序列,不能为空C、无限序列,可以为空D、无限序列,不能为空三、常用的两种线性表模型队列：特点：只能在表的一端进行插入,在表的另一端进行删除的线性表相关名词：队首、队尾堆栈：特点：只能在表的一端进行插入和删除操作应用：求解数学表达式、实现递归算法相关名词：栈顶、栈底eg:设栈S的初始状态为空,现有个元素组成的序列1,2,3,4,5,对该序列在S栈上依次进行如下操作从序列中的1开始,

4、出栈后不再进栈：进栈,进栈,进栈,出栈,进栈,出栈,进栈,请问出栈的元素序列是:四、线性表的存储：顺序存储和链表存储顺序存储：是按数据元素在存储器中的相对位置来表示数据元素间的逻辑关系程序描述：用一维数组来描述顺序存储结构,二维数组的每一个元素为一个线性表链表存储：用一组任意的存储单元来存储数据元素,元素之间的关系通过指针来表现.程序描述：用指针eg:找同学两种存储结构的特点比照顺序表链表一个表必须用一组连续的内存地址存储内存地址可以是连续的也可以是不连续的插入和删除元素难度大插入和删除元素简单不需移动元素,只需修改头尾指针即可存取数据快只要确定了起始位置,线性表中任一数据元素可随机存取存取数

5、据慢17.线性表假设采用链表存贮结构,要求内存中可用存贮单元地址/A,必须连续B.局部地址必须连续C.一定不连续D.连续不连续均可/18.以下表达中,正确的选项是A.线性表的线性存贮结构优于链表存贮结构/B.队列的操作方式是先进后出C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表14、线性表有两种存储结构：一是顺序表,二是链表.试问：1有一个线性表,在处理过过程中表的长度会根据需要动态发生变化,在这种情况下应选用哪种存储结构2有一个线性表,很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素,应采用哪种存储结构15.数组A中,每个元素AI,J在存贮日要占3

6、个字节,设I从1变化到8,J从1变化到10,分配内存时是从地址SA开始连续按行存贮分配的.试问：A5,8的起始地址为+144+180+222+225/4*10+8*31 .在下面各世界顶级的奖项中,为计算机科学与技术领域做出杰出奉献的科学家设立的奖项是.A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖、2 .在以下各软件中,不属于NOIP竞赛复赛推荐使用的语言环境有0A.gcc/g+B.TurboPascalC.RHIDED.freepascal3. 以下断电之后仍能保存数据的有_.A.存放器B.ROMC.RAMD.高速缓存4. Linux是一种.A.绘图软件B.程序设计语言C.操作系统D.网络

7、浏览器5. CPU是的简称.A.硬盘B.中央处理器C.高级程序语言D.核心存放器6. 在计算机中,防火墙的作用是.A.预防火灾蔓延B.预防网络攻击C预防计算机死机D.预防使用者误删除数据7. 在以下关于计算机语言的说法中,不正确的选项是.A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C.C+是历史上的第一个支持面向对象的计算机语言D.与汇编语言相比,高级语言程序更容易阅读8.在以下关于计算机算法的说法中,不正确的选项是./A.一个正确的算法至少要有一个输入8 .算法的改良,在很大程度上推动了计算机科学与技术的进步/C.判断一个算法

8、的好坏的主要标准是算法的时间复杂性与空间复杂性/D.目前仍然存在许多涉及到国计民生的重大课题,还没有找到能够在计算机上实施的有效算法9 .在以下各种排序算法中,不是以“比拟作为主要操作的算法是./A.选择排序B.冒泡排序C.插入排序D.基数排序10 .在编程时使用任一种高级语言,工不一定是Pascal,如果需要从磁盘文件中输入一个很大的二维数组例如1000*1000的double型数组,按行读即外层循环是关于行的与按列读即外层循环是关于列的相比,在输入效率上.A.没有区别B.按行读的方式要高一些/C.按列读的方式要高一些D.取决于数组的存储方式./11 .在Pascal语言中,表达式21xor

9、2的值是A.441B.4212 .在Pascal语言中,判断a不等于0且b不等于0的正确的条件表达式是A.nota=0ornotb=0B.nota=0andb=0C.not(a=0andb=0)D.(a0)and(b0)13 .某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口.某时刻该车站状态为空,从这一时刻开始的出入记录为:的顺序为1,2,3,:“进,出,进,进,进了出,出,进,进,进,出,出.假设车辆入站,那么车辆出站的顺序为A.1,2,3,4,5B.1,2,4,5,7/C.1,4,3,7,6D.1,4,3,7,214 .高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝,它应

10、该是高度为n-1的满二叉树.在这里,树高等于叶结点的最大深度,根结点的深度为0,如果某个均衡的二叉树共有2381个结点,那么该树的树高为(A.10B.11C.12D.1315.与十进制数1770对应的八进制数是A.3350B.3351C.3352D.354016 .将5个数的序列排序,不管原先的顺序如何,最少都可以通过大的排序.A.6B.7C.8D.917 .设A=B=D=true,C=false,以下逻辑运算表达式值为真的有A.(?AAB)V(CAD)C.AA(BVCVD)D.(A18 .(2021)16+(32)8A.(8234)10B.(202B)16C.(20056)8D.()219

11、.设栈S的初始状态为空,A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,aABACVD的结果是次比拟,完成从小到B.?(AVBVD)AC)元素a,b,c,d,e依次入栈,以下出栈序列不可能出现的有20 .6个结点的二叉树的先根遍历是123456数字为结点的编号,以下同,后根遍历是325641,那么该二叉树的可能的中根遍历是A.321465B.321546C.213546D.231465练习二1 .在字符串“ababacbabcbdeccedA.6B.5C.4D.32 .设全集I=a,b,c,d,e,f,g,h)d,那么集合A?B?C为()中出现次数最多的字

12、母出现了次.E.2,集合A=a,b,c,d,e,f,B=c,d,e/,C=a,A.c,eB.d,eC.eD.c,d,eE.d,f)3 .和十进制数23的值相等的二进制数是A.10110B.11011C.11011D.10111E.100114 .完全二叉树的结点个数为11,那么它的叶结点个数为.A.4D.2E.6.以这五点作为完全图G的顶点,5.平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)每两点之间的直线距离是图G中对应边的权值.以下哪条边不是图G的最小生成树中的边.A.ADB.BDC.CDD.DEE.EA6. Intel的首颗16位处理器是A.8088B

13、.80386C.80486D.8086E.Pentium7. 处理器A每秒处理的指令数是处理器B的2倍.某一特定程序P分别编译为处理器A和处理器B的指令,编译结果处理器A的指令数是处理器B的4倍.程序P在处理器A上执行需要1个小时,那么在输入相同的情况下,程序P在处理器B上执行需要()小时.A.4B.2C.1D.1/2E.1/48. 以下哪个不是计算机的输出设备().A.音箱B.显示器C.打印机D/扫描仪E.绘图仪9. 以下活动中不属于信息学奥赛的系列活动的是().A.NOIPB.NOIC.IOID.冬令营E.程序员等级测试10. 以下断电之后仍能保存数据的是().A.硬盘B.存放器C./显存

14、D.内存E.高速缓存11. 以下哪个软件不是即时通信软件().A.网易泡泡B.MSNMessengerC.GoogleTalkD.3DSMaxE.QQ12. 以下关于高级语言的说法错误的选项是().A. Fortran是历史上的第一个面向科学计算的高级语言B. Pascal和C都是编译执行的高级语言、C. C+是历史上的第一个支持面向对象的语言D. 编译器将高级语言程序转变为目标代码E. /高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上13. 以下设备不具有计算功能的是().A.笔记本电脑B.掌上电脑C.智能D.电子计算器E.液晶显示器14. 常见的邮件传输效劳器使用()协议

15、接收邮件.A.HTTPB.SMTPC.TCPD.FTPE.POP315. 以下浏览器中,由微软公司开发的浏览器是().A.InternetExploreB.NetscapeC.OperaD.FirefoxE.Mozilla16. 一位艺术史学家有20000幅真彩色图像,每幅图像约占3M空间.如果将这些图像以位图形式保存在CD光盘上(一张CD光盘的容量按600M计算),大约需要()张CD光盘.A.1B.10C.100D.1000E.1000017. 设A=true,B=false,C=false,D=true,以下逻辑运算表达式值为真的是().A.(AAB)V(CAD)B.(AAB)VC)ADC

16、.AA(BVC)AD)D.(AA(BVC)VDE.(AVB)A(CAD)/18. (3725)8+(B)16的运算结果是()./A.(3736)8B.(2021)10C.(00)2D.(3006)10E.(7B0)1619. 二叉树T的宽度优先遍历序列为ABCDEFGHI,A是C的父结点,D是G的父结点,F是I的父结点,树中所有结点的最大深度为3(根结点深度设为0),可知F的父结点是()./A.无法确定B.BC.CD.DE.E/20. 设栈S的初始状态为空,元素a,b,c,d,e,f,g依次入栈,以下出栈序列不可能出现的是()./A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.

17、a,e,d,c,b,f,gD.d,c,f,e,b,a,gE.g,e,f,d,c,b,a练习三1 .美籍匈牙利数学家冯诺依曼对计算机科学开展所做出的奉献是().A.提出理想计算机的数学模型,B.成为计算机科学的理论根底.C.是世界上第一个编写计算机程序的人.D.提出存储程序工作原理,E.并设计出第一台具有存储程序功能的计算机EDVACF.采用集成电路作为计算机的主要功能部件.G.指H.出计算机性能将以每两年翻一番的速度向前开展.2 .以下哪个不3.是CPU中央处理单元A.IntelItaniumB.DDRSDRAMC.AMDAthlon64D.AMDOpteronE.IBMPower54.以下网

18、络上常用的名5.字缩写对应的中文解释错误的选项是、.A.WWWWorldWideWeb:万B.维网.C. URL.UniformResourceLocator:统一资源定位器.D. HTTPHypertextTransferProtocol:超文本传输协议.E. FTPFileTransferProtocol:快速传输协议.F. TCPTransferControlProtocol:传输限制协议.、6.下面哪个部件对于个人桌面电脑的正常运行不7.是必需的.A.CPU/B.图形卡显卡C.光驱D.主板E.内存8 .以下哪个软件属于操作系统软件.A.MicrosoftWordB.金山词霸C.Foxm

19、ailD.WinRARERedHatLinux9 .以下哪个不10.是计算机的存储设备11.A.文件治理器B.内存C.高速缓存D.硬盘E.U盘12.以下说法中错误的选项是.A.CPU的根本功能就是执行指B.令.C. CPU访问内存的速度快于访问高速缓存的速度.D. CPU的主频是指E.CPU在1秒内完成的指F.令周期数.G.在一台计算机内部,H.一个内存地址编码对应唯一的一个内存单元.I.数据总线的宽度决定了一次传递数据量的大小,J.是影响计算机性能的因素之一.13.彩色显示器所显示的五彩斑斓的色彩,14.是由红色、蓝色和色混合而15.成的.A.紫B.白C.黑D.绿E.橙16.用静电吸附墨粉后

20、转移到纸张上,17.是哪种输出设备18.的工作方式.A.针式打印机B.喷墨打印机C.激光打印机D.笔式绘图仪E.喷墨绘图仪19.一台计算机如果要利用线上网,20.就必须配置能够对数字信号和模拟信号进行相互转换的设备,21.这种设备22.是./A.调制解调器B.路由器C.网卡D.网关E.网桥/23.以下哪个不24.是数据库软件的名25.称.A.MySQLB.SQLServerC.OracleD.金山影霸E.Foxpro26.以下哪个程序设计语言不27.支持面向对象程序设计方法./A.C+B.ObjectPascalC.CD.SmalltalkE.Java28.由3个a,29.1个b和2个c构成的所有字符串中,30.包含子用“abc的共有个.A.20B.8C.16D.12E.2431.某个车站呈狭长形,32.宽度只能容下一台车,33.并且只有一个出入口.某时刻该车站状态为空,34.从这一时刻开始的出入记录为：“进,35.出,36.z进,37.进,38.出,39.进,40.进,41.进,42.出,43.出,44.进,45.出.假设车辆入站的顺序为1,46.2,47.3,48.