信息学奥赛基础知识讲义全.docx
《信息学奥赛基础知识讲义全.docx》由会员分享，可在线阅读，更多相关《信息学奥赛基础知识讲义全.docx（16页珍藏版）》请在冰点文库上搜索。
信息学奥赛基础知识讲义全
[信息学奥赛基础知识讲义]
基础部分
一、进制：
2进制数与8进制、10进制、16进制数的换算
换算1：
将N进制数换算成10进制数（N可以为2,8,16或其它自然数）
换算2：
将10进制数换算成N进制数（N可以为2,8,16或其它自然数）
1.下列无符号数中，最小的数是（）
A.（11011001）2B.（75）10C.（37）8D.（2A）16
7、小张用十六进制，八进制和十进制写下了如下一个等式：
52-19=33
式中三个数是各不相同进位制的数，试问52,19,33，分别为
（A）8，10，16（B）10,16,8（c）8,16,10（D）10,8,16
二、数据的存储和编码所有的数据都是以二进制存储在计算机的存储器中的，数据的传送、存储、加工、处理或指令都是以二进制形式进行的。
对于数值:
弄清原码、反码、补码以及定点数和浮点数。
负数在计算机中以补码形式存放，小数在计算机中是以浮点数形式存放。
0的原码表示法有两种，+0和—0
8位定点整数的补码表示范围为-128+127
14、计算机中的数有浮点数与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。
A.指数与基数B.尾数与小数C.阶码与尾数D.整数与小数
8、如果用一个字节表示一个整数，最高位用作符号位，其他位表示数值，例如
1）试问这样表示法的整数a的范围应是
（2）在这样表法法中，以下说法是下确的
A、范围内的每一个数都只有唯一的格式B、范围内的每一个数有两种格式
对于字符
ASCII
对英文的字母和其它打印字符：
（扩展）ASCII码（美国标准信息交换码）
标准的ASCII码为7位二进制编码，但在计算机中以8位二进制位来存储（最高位为校验们位），扩充的码为8位二进制编码对汉字，中国大陆常用的有GB码、GBK码、Unicode
GBK码于1980年发布，是中文信息处理的国家标准，在大陆及海外使用简体中文的地区（如新加坡等）是强制使用的唯一中文编码。
P-Windows3.2和苹果OS就是以GB2312为基本汉字编码，Windows95/98则以GBK为基本汉字编码、但兼容支持GB2312。
GB码共收录6763个简体汉字、682个符号，其中汉字部分：
一级字3755，以拼音排序，二级字3008，以偏旁部首排序。
l8．组成'教授'（jiaoshou）'副教授'（fujiaoshou）与'讲师'（jiangshi）这三个词的汉字，在GB2312－80字符集中都是一级汉字．对这三个词排序的结果是（）．
A教授，副教授，讲师B．副教授，教授，讲师
C讲师，副教授，教授D．副教授，讲师，教授
）为序排列的。
3.GB2312-80规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（
D.以机内码
码值是6D，则小写字母'c'的十六进制的ASCII码值是（）
A.以笔划多少B.以部首C.以ASCⅡ码
13.已知小写字母'm'的十六进制的ASCll
D.63
A.98B.62C.99
三、计算机的硬件结构
算器C.输入、输出设备D.运算器是实现算术运算或逻辑运算的装置，对数据进行传送和加工。
控制器是计算机的控制中心，它分析从存储器取出的信息，然后据此向计算机的各个部分发出各种控制信号，指挥与协调整台计算机自动而有序地工作。
它是计算机的“神经中枢”。
存储器的功能是存储信息，以备调用，它由成千上万个存储单元组成，每个单元可存放一定位数的二进制信息，存储器的容量以字节Byte为基本单位，还有KB（=1024Byte）、MB（1024KB）、GB（1024MB）等计量单位（如称某台计算机的内存为64MB，硬盘为10GB）。
存储器是计算机的“记忆系统”
微机内存储器的地址是（按辅（助）存编储址器的）。
A.二进制位B.字长C.字节D.微处理器的型号
5.RAM中的信息是（）
A.生产厂家预先写入的B.计算机工作时随机写入的
C.防止计算机病毒侵入所使用的D.专门用于计算机开机时自检用的
12.某种计算机的内存容量是640K，这里的640K容量是指（）个字节
A.640B.640*1000C.640*1024D.640*1024*1024
16.不同类型的存储器组成了多层次结构的存储器体系,按存取速度从快到慢的排列是（）
A.快存/辅存/主存B.外存/主存/辅存
C.快存/主存/辅存D.主存/辅存/外存
计算机病毒的特点：
隐藏性、潜伏性、可激活性、危害性、可传染性
7.计算机病毒的特点（）
A.传播性、潜伏性、易读性与隐蔽性B.破坏性、传播性、潜伏性与安全性
C.传播性、潜伏性、破坏性与隐蔽性D.传播性、潜伏性、破坏性与易读性
二进制/位/字节/字/字长
bit/byte/word/在计算机内部，用来传送、存储、加工、处理或指令都是以形式进行的。
（A）十进制头（B）智能拼音码（C）二进制码（D）五笔字型码微机内存储器的地址是按（）编址的。
A.二进制位B.字长C.字节D.微处理器的型号
[信息学奥赛基础知识讲义]初赛基础知识2
本课内容：
1、数据结构之线性表
2、构造数据结构的重要工具：
指针
程序（读程序写结果、完善程序）
算法+数据结构
相关知识点：
１.数据类型与数据结构的基本概念。
２.线性表的基本概念和实现技术。
３.栈和队列的基本概念和实现技术。
４.树形结构的基本概念，二*树的表示和遍历算法，树与二*树的转换。
５.排序的基本概念和排序算法（插入排序、选择排序、交换排序）。
算法（P62-85）特定的问题采用特定的算法
1.数据类型与数据结构的基本概念。
数据类型用来表示数据元素的特性（p24）数据结构用来描述数据元素之间的关系数据元素之间的关系有四种
（1）集合：
同数学中的集合概念,结构中的数据元素之间除了同属于一个集合外，别无其它关系
（2）线性表：
数据元素之间为一个对一个的关系
（3）树：
数据之间存在一对多的关系
（4）图：
数据之音存在多对多的关系
二、线性表
1、线性表的应用实例：
排队时的队列，一个含班上全部同学的成绩的表
2、概念：
线性表是N（N>=0）个数据元素的有限序列
3、特征：
（1）数据表中的元素具有相同的特性（相同的数据类型）
3、
（2）元素之间具备线性关系（有顺序，并且是一对一的关系）
相关名词：
表头、表尾
eg:
学习资料
线性表是：
A、有限序列，可以为空；B、有限序列，不能为空
C、无限序列，可以为空D、无限序列，不能为空
三、常用的两种线性表模型
队列：
特点：
只能在表的一端进行插入，在表的另一端进行删除的线性表相关名词：
队首、队尾
堆栈：
特点：
只能在表的一端进行插入和删除操作应用：
求解数学表达式、实现递归算法相关名词：
栈顶、栈底
eg:
设栈S的初始状态为空，现有个元素组成的序列（1，2，3，4，5），对该序列在S栈上依次进行如下操作（从序列中
的1开始，出栈后不再进栈）：
进栈，进栈，进栈，出栈，进栈，出栈，进栈，请问出栈的元素序列是:
四、线性表的存储：
（顺序存储和链表存储）
顺序存储：
是按数据元素在存储器中的相对位置来表示数据元素间的逻辑关系程序描述：
用一维数组来描述顺序存储结构,二维数组的每一个元素为一个线性表链表存储：
用一组任意的存储单元来存储数据元素，元素之间的关系通过指针来表现。
程序描述：
用指针
eg：
找同学
两种存储结构的特点对比
顺序表
链表
一个表必须用一组连续的内存地址存储内存地址可以是连续的也可以是不连续的插入和删除元素难度大
插入和删除元素简单（不需移动元素，只需修改头尾指针即可）存取数据快（只要确定了起始位置，线性表中任一数据元素可随机存取）存取数据慢
17.线性表若采用链表存贮结构,要求内存中可用存贮单元地址（）
A.必须连续B.部分地址必须连续
C.一定不连续D.连续不连续均可
18.下列叙述中,正确的是（）
A.线性表的线性存贮结构优于链表存贮结构
B.队列的操作方式是先进后出
C.栈的操作方式是先进先出
D.二维数组是指它的每个数据元素为一个线性表的线性表14、线性表有两种存储结构：
一是顺序表，二是链表。
试问：
（1）有一个线性表，在处理过过程中表的长度会根据需要动态发生变化，在这种情况下应选用哪种存储结构学习资料
（2）有一个线性表，很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应采用哪种存储结构
15.已知数组A中，每个元素A[I,J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。
试问：
A[5,8]的起始地址为（）
A.SA+144B.SA+180C.SA+222D.SA+225
（4*10+8）*3
1.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。
A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖
2.在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。
A.gcc/g++B.TurboPascal
C.RHIDED.freepascal
3.以下断电之后仍能保存数据的有（）。
A.寄存器B.ROMC.RAMD.高速缓存
4．Linux是一种（）。
A.绘图软件B.程序设计语言C.操作系统D.网络浏览器
5.CPU是（）的简称。
A.硬盘B.中央处理器C.高级程序语言D.核心寄存器
6.在计算机中，防火墙的作用是（）。
A.防止火灾蔓延B.防止网络攻击
C.防止计算机死机D.防止使用者误删除数据
7.在下列关于计算机语言的说法中，不正确的是（）。
A.Pascal和C都是编译执行的高级语言
B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上
C.C++是历史上的第一个支持面向对象的计算机语言
D.与汇编语言相比，高级语言程序更容易阅读
8.在下列关于计算机算法的说法中，不正确的是（）。
A.一个正确的算法至少要有一个输入
B.算法的改进，在很大程度上推动了计算机科学与技术的进步
C.判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性
D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法
9.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。
A.选择排序B.冒泡排序C.插入排序D.基数排序10．在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大
的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。
A.没有区别B.按行读的方式要高一些
C.按列读的方式要高一些D.取决于数组的存储方式。
11．在Pascal语言中，表达式（21xor2）的值是（）
A.441B.42C.23D.24
12．在Pascal语言中，判断a不等于0且b不等于0的正确的条件表达式是（）
A.nota=0ornotb=0B.not（（a=0）and（b=0））
C.not（a=0andb=0）D.（a<>0）and（b<>0）
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,2
14．高度为n的均衡的二叉树是指：
如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。
A.10B.11C.12D.13
15.与十进制数1770对应的八进制数是（）。
A.3350B.3351C.3352D.3540
16．将5个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到
大的排序。
A.6B.7C.8D.9
17.设A=B=D=true，C=false，以下逻辑运算表达式值为真的有（）。
A.（?
A∧B）∨（C∧D）B.?
（（A∨B∨D）∧C）
C.A∧（B∨C∨D）D.（A∧B∧C）∨D
18.（2010）16+（32）8的结果是（）。
A.（8234）10B.（202B）16
C.（20056）8D.（100000000110）2
19.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有（）A.a,b,c,e,dB.b,c,a,e,d
C.a,e,c,b,dD.d,c,e,b,a
20.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是
325641，则该二叉树的可能的中根遍历是（）
A.321465B.321546
C.213546D.231465
4.完全二叉树的结点个数为11，则它的叶结点个数为（）
A.4B.3C.5D.2E.6
5.
。
以这五点作为完全图G的顶点，G的最小生成树中的边（）。
平面上有五个点A（5,3）,B（3,5）,C（2,1）,D（3,3）,E（5,1）每两点之间的直线距离是图G中对应边的权值。
以下哪条边不是图A.ADB.BDC.CDD.DEE.EA
6.Intel的首颗16位处理器是（）。
A.8088B.80386C.80486D.8086E.Pentium
7.处理器A每秒处理的指令数是处理器B的2倍。
某一特定程序P分别编译为处理器A和处理器B的指令，编译结果处理器A的指令数是处理器B的4倍。
已知程序P在处理器A上执行需要1个小时，那么在输入相同的情况下，程序P在处理器B上执行需要（）小时。
A.4B.2C.1D.1/2
E.1/4
8.
以下哪个不是计算机的输出设备（
）。
A.
音箱B.显示器C.
打印机D.扫描仪E.
绘图仪
9.
下列活动中不属于信息学奥赛的系列活动的是（）。
A.NOIPB.NOIC.IOID.冬令营E.程序员等级考试
10.以下断电之后仍能保存数据的是（）。
A.硬盘B.寄存器C.显存D.内存E.高速缓存
11.以下哪个软件不是即时通信软件（）。
A.网易泡泡B.MSNMessengerC.GoogleTalkD.3DSMaxE.QQ
12.下列关于高级语言的说法错误的是（）。
A.Fortran是历史上的第一个面向科学计算的高级语言
B.Pascal和C都是编译执行的高级语言
C.C++是历史上的第一个支持面向对象的语言
D.编译器将高级语言程序转变为目标代码
E.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上
13.下列设备不具有计算功能的是（）。
A.笔记本电脑B.掌上电脑C.智能手机
D.电子计算器E.液晶显示器
14.常见的邮件传输服务器使用（）协议接收邮件。
A.HTTPB.SMTPC.TCPD.FTPE.POP3
15.下列浏览器中，由微软公司开发的浏览器是（）。
A.InternetExploreB.NetscapeC.OperaD.FirefoxE.Mozilla
16.一位艺术史学家有20000幅真彩色图像，每幅图像约占3M空间。
如果将这些图像以位图形式保存在CD光盘上（一张CD光盘的容量按600M计算），大约需要（）张CD光盘。
A.1B.10C.100D.1000E.10000
17.设A=true，B=false，C=false，D=true，以下逻辑运算表达式值为真的是（）。
A.（A∧B）∨（C∧D）B.（（A∧B）∨C）∧DC.A∧（（B∨C）∧D）
D.（A∧（B∨C））∨DE.（A∨B）∧（C∧D）
18.（3725）8+（B）16的运算结果是（）。
A.（3736）8B.（2016）10C.（1111110000）2D.（3006）10E.（7B0）16
19.二叉树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.a,e,d,c,b,f,g
D.d,c,f,e,b,a,gE.g,e,f,d,c,b,a
练习三
1.美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（）。
A.提出理想计算机的数学模型，B.成为计算机科学的理论基础。
C.是世界上第一个编写计算机程序的人。
D.提出存储程序工作原理，E.并设计出第一台具有存储程序功能的计算机EDVA。
C
F.采用集成电路作为计算机的主要功能部件。
G.指H.出计算机性能将以每两年翻一番的速度向前发展。
2.下列哪个不3.是CPU（中央处理单元）（）。
A.IntelItaniumB.DDRSDRAMC.AMDAthlon64
D.AMDOpteronE.IBMPower5
4.下列网络上常用的名5.字缩写对应的中文解释错误的是（）
A.WWW（WorldWideWeb）：
万B.维网。
C.URL（UniformResourceLocator）：
统一资源定位器。
D.HTTP（HypertextTransferProtocol）：
超文本传输协议。
E.FTP（FileTransferProtocol）：
快速传输协议。
F.TCP（TransferControlProtocol）：
传输控制协议。
6.下面哪个部件对于个人桌面电脑的正常运行不7.是必需的（）。
A.CPUB.图形卡（显卡）C.光驱D.主板E.内存
8.下列哪个软件属于操作系统软件（）。
E.RedHatLinux
A.MicrosoftWordB.金山词霸C.FoxmailD.WinRAR
9.下列哪个不10.是计算机的存储设备11.（）。
A.文件管理器B.内存C.高速缓存D.硬盘E.U盘
12.下列说法中错误的是（）。
A.CPU的基本功能就是执行指B.令。
C.CPU访问内存的速度快于访问高速缓存的速度。
D.CPU的主频是指E.CPU在1秒内完成的指F.令周期数。
G.在一台计算机内部，H.一个内存地址编码对应唯一的一个内存单元。
I.数据总线的宽度决定了一次传递数据量的大小，J.是影响计算机性能的因素之一。
A.C++B.ObjectPascalC.CD.SmalltalkE.Java
28.由3个a，29.1个b和2个c构成的所有字符串中，30.包含子串“abc”的共有（）个
A.20B.8C.16D.12E.24
31.某个车站呈狭长形，32.宽度只能容下一台车，33.并且只有一个出入口。
已知某时刻该车站状态为空，34.从这一时刻开始的出入记录为：
“进，35.出，36.进，37.进，38.出，39.进，40.进，
41.进，42.出，43.出，44.进，45.出”。
假设车辆入站的顺序为1，46.2，47.3，48.⋯⋯，
49.则车辆出站的顺序为（）。
A.1,2,3,4,5
B.1,2,4,5,7
C.1,3,5,4,6
D.1,3,5,6,7
E.
1,3,6,5,7
50.二叉树T，51.
已知其前序遍历序列为
1243576，52.
中序遍历序列为4215736
，53.则
其后序遍历序列为（
）。
A.4257631
B.4275631
C.4275361
D.4723561
E.
4526371
54.满二叉树的叶结点个数为N，55.则它的结点总数为（）。
A.NB.2*NC.2*N–1D.2*N+1E.2N–1
56.十进制数2004等值于八进制数（）。
A.3077B.3724C.2766D.4002E.3755
57.（2004）10+（32）16的结果是（）
A.（2036）10B.（2054）16
58.在下图中，59.从顶点（一次。
C.（4006）10D.（100000000110）2E.（2036）16
）出发存在一条路径可以遍历图中的每条边一次，而60.且仅遍历
A.A点B.B点C.C点D.D点E.
升级会员 