信息学奥赛基础知识讲义

WORD完美格式..整理分享..[信息学奥赛基础知识讲义]基础部分一、进制：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）167、小张用十六进制，八进制和十进制写下了如下一个等式：52-19=33式中三个数是各不相同进位制的数，试问52,19,33，分别为______。（A）8，10，16（B）10,16,8(c)8,16,10(D)10,8,16二、数据的存储和编码所有的数据都是以二进制存储在计算机的存储器中的，数据的传送、存储、加工、处理或指令都是以二进制形式进行的。对于数值:弄清原码、反码、补码以及定点数和浮点数。负数在计算机中以补码形式存放，小数在计算机中是以浮点数形式存放。0的原码表示法有两种，+0和—08位定点整数的补码表示范围为-128_____+12714、计算机中的数有浮点数与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。A.指数与基数B.尾数与小数C.阶码与尾数D.整数与小数8、如果用一个字节表示一个整数，最高位用作符号位，其他位表示数值，例如00000001表示+1，10000001表示-1（1）试问这样表示法的整数a的范围应是————————A、-127=a=127B、-128=a=128C、-128=a127D、-128a=128（2）在这样表法法中，以下________说法是下确的A、范围内的每一个数都只有唯一的格式B、范围内的每一个数有两种格式C、范围内的一半数有两种格式样D、范围内只有一个数有两种表示格式对于字符对英文的字母和其它打印字符：（扩展）ASCII码（美国标准信息交换码）标准的ASCII码为7位二进制编码，但在计算机中以8位二进制位来存储（最高位为校验们位），扩充的ASCII码为8位二进制编码对汉字，中国大陆常用的有GB码、GBK码、UnicodeGBK码于1980年发布，是中文信息处理的国家标准，在大陆及海外使用简体中文的地区（如新加坡等）是强制使用的唯一中文编码。P-Windows3.2和苹果OS就是以GB2312为基本汉字编码，Windows95/98则以GBK为基本汉字编码、但兼容支持GB2312。GB码共收录6763个简体汉字、682个符号，其中汉字部分：一级字3755，以拼音排序，二级字3008，以偏旁部首排序。WORD完美格式..整理分享..l8．组成'教授'（jiaoshou）'副教授'（fujiaoshou）与'讲师'（jiangshi）这三个词的汉字，在GB2312－80字符集中都是一级汉字．对这三个词排序的结果是（）．A教授，副教授，讲师B．副教授，教授，讲师C讲师，副教授，教授D．副教授，讲师，教授3.GB2312-80规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（）为序排列的。A.以笔划多少B.以部首C.以ASCⅡ码D.以机内码13.已知小写字母'm'的十六进制的ASCll码值是6D，则小写字母'c'的十六进制的ASCII码值是（）A.98B.62C.99D.63三、计算机的硬件结构2.在外部设备中，绘图仪属于（）A.输入设备B.输出设备C.辅（外）存储器D.主（内）存储器6.计算机主机是由CPU与（）构成的A.控制器B.运算器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*102416.不同类型的存储器组成了多层次结构的存储器体系,按存取速度从快到慢的排列是（）A.快存/辅存/主存B.外存/主存/辅存计算机系统运算器控制器存储器（硬盘、内存、光盘、软盘等）输入设备（键盘、鼠标、话筒、扫描仪、数码相机等）输出设备（显示器、音箱、打印机、光盘刻录机等）合称CPU存储器内存储器外存储器只读存储器ROM随机存储器RAM（主存储器）（辅助存储器）WORD完美格式..整理分享..C.快存/主存/辅存D.主存/辅存/外存计算机病毒的特点：隐藏性、潜伏性、可激活性、危害性、可传染性7.计算机病毒的特点（）A.传播性、潜伏性、易读性与隐蔽性B.破坏性、传播性、潜伏性与安全性C.传播性、潜伏性、破坏性与隐蔽性D.传播性、潜伏性、破坏性与易读性二进制/位/字节/字/字长bit/byte/word/在计算机内部，用来传送、存储、加工、处理或指令都是以形式进行的。（A）十进制头（B）智能拼音码（C）二进制码（D）五笔字型码微机内存储器的地址是按（）编址的。A.二进制位B.字长C.字节D.微处理器的型号[信息学奥赛基础知识讲义]初赛基础知识2本课内容：1、数据结构之线性表2、构造数据结构的重要工具：指针程序（读程序写结果、完善程序）算法+数据结构相关知识点：１.数据类型与数据结构的基本概念。２.线性表的基本概念和实现技术。３.栈和队列的基本概念和实现技术。４.树形结构的基本概念，二*树的表示和遍历算法，树与二*树的转换。５.排序的基本概念和排序算法（插入排序、选择排序、交换排序）。一.数据类型与数据结构的基本概念。数据类型用来表示数据元素的特性（p24）数据结构用来描述数据元素之间的关系数据元素之间的关系有四种（1）集合：同数学中的集合概念,结构中的数据元素之间除了同属于一个集合外，别无其它关系（2）线性表：数据元素之间为一个对一个的关系（3）树：数据之间存在一对多的关系（4）图：数据之音存在多对多的关系二、线性表1、线性表的应用实例：排队时的队列，一个含班上全部同学的成绩的表2、概念：线性表是N（N=0）个数据元素的有限序列3、特征：（1）数据表中的元素具有相同的特性（相同的数据类型）3、（2）元素之间具备线性关系（有顺序，并且是一对一的关系）相关名词：表头、表尾eg:算法（P62-85）特定的问题采用特定的算法WORD完美格式..整理分享..线性表是：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）有一个线性表，在处理过过程中表的长度会根据需要动态发生变化，在这种情况下应选用哪种存储结构WORD完美格式..整理分享..（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)*31.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖2.在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。A.gcc/g++B.TurboPascalC.RHIDED.freepascal3.以下断电之后仍能保存数据的有（）。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.在下列关于计算机算法的说法中，不正确的是（）。WORD完美格式..整理分享..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.2412．在Pascal语言中，判断a不等于0且b不等于0的正确的条件表达式是（）A.nota=0ornotb=0B.not((a=0)and(b=0))C.not(a=0andb=0)D.(a0)and(b0)13．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2