《信息学奥赛基础知识讲义》由会员分享，可在线阅读，更多相关《信息学奥赛基础知识讲义（6页珍藏版）》请在金锄头文库上搜索。
1、信息学奥赛基础知识讲义基础部分一、进制：2进制数与8进制、10进制、16进制数的换算换算1：将N进制数换算成10进制数（N可以为2,8,16或其它自然数）换算2：将10进制数换算成N进制数（N可以为2,8,16或其它自然数）1. 下列无符号数中，最小的数是（）A. （11011001）2 B. （75）10 C. （37）8 D. （2A）167、小X用十六进制，八进制和十进制写下了如下一个等式：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位定点整数的补码表示X围为-128+12714、计算机中的数有浮点数与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。A.指数与基数B.尾数与小数C.阶码与尾数D.整数与小数8、如果用一个字节表示一个整数，最高位用作符号位，其他位表示数值，例如00000001 表示+1，10000001 表示-1（1）试问这样表示法的整数a的X围
3、应是A、 -127=a=127B、 -128=a=128C、 -128=a127D、 -128a=128（2）在这样表法法中，以下 说法是下确的A、X围内的每一个数都只有唯一的格式B、X围内的每一个数有两种格式C、X围内的一半数有两种格式样D、X围内只有一个数有两种表示格式 对于字符对英文的字母和其它打印字符：（扩展）ASCII码（美国标准信息交换码）标准的ASCII码为7位二进制编码，但在计算机中以8位二进制位来存储（最高位为校验们位），扩充的ASCII 码为8位二进制编码对汉字，中国大陆常用的有GB码、GBK码、UnicodeGBK码于1980年发布，是中文信息处理的国家标准，在大陆与海外
4、使用简体中文的地区（如新加坡等）是强制使用的 唯一中文编码。P-Windows3.2和苹果OS就是以GB2312为基本汉字编码，Windows 95/98则以GBK为基本汉字编码、 但兼容支持GB2312。GB码共收录6763个简体汉字、682个符号，其中汉字部分：一级字3755，以拼音排序，二级字3008，以偏旁部 首排序。18.组成教授（jiao shou ）副教授（fu jiao shou ）与讲师（jiang shi ）这三个词的汉字，在GB2312 80 字符集中都是一级汉字.对这三个词排序的结果是（）.A教授，副教授，讲师B.副教授，教授，讲师C讲师，副教授，教授D.副教授，讲师，
5、教授3. GB2312-80规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（）为序排列的。A.以笔划多少B.以部首C.以ASCII码D.以机内码13. 已知小写字母m的十六进制的ASCII码值是6D,则小写字母c的十六进制的ASCII码值是（）A.98B.62C.99D.63三、计算机的硬件结构:运算器 I圮生哽合称cpu 控制器计算机 =0）个数据元素的有限序列3、特征：（1）数据表中的元素具有相同的特性（相同的数据类型）3、（2）元素之间具备线性关系（有顺序，并且是一对一的关系）相关名词：表头、表尾eg：线性表是：A、有限序列，可以为空；B、有限序列，不能为空C
6、、无限序列，可以为空D、无限序列，不能为空三、常用的两种线性表模型队列：特点：只能在表的一端进行插入，在表的另一端进行删除的线性表相关名词：队首、队尾堆栈：特点：只能在表的一端进行插入和删除操作应用：求解数学表达式、实现递归算法相关名词：栈顶、栈底eg：设栈S的初始状态为空，现有个元素组成的序列（1, 2, 3, 4, 5）,对该序列在S栈上依次进行如下操作（从序列 中的1开始，出栈后不再进栈）：进栈，进栈，进栈，出栈，进栈，出栈，进栈，请问出栈的元素序列是四、线性表的存储：（顺序存储和链表存储）顺序存储：是按数据元素在存储器中的相对位置来表示数据元素间的逻辑关系程序描述：用一维数组来描述顺序
7、存储结构，二维数组的每一个元素为一个线性表链表存储：用一组任意的存储单元来存储数据元素，元素之间的关系通过指针来表现。程序描述：用指针eg：找同学两种存储结构的特点对比顺序表链表一个表必须用一组连续的内存地址存储内存地址可以是连续的也可以是不连续的插入和删除元素难度大插入和删除元素简单（不需移动元素，只需修改头尾指针即可）存取数据快（只要确定了起始位置，线性表中任一数据元素可随机存取）存取数据慢17. 线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）A.必须连续B.部分地址必须连续C. 一定不连续D.连续不连续均可18. 下列叙述中，正确的是（）A. 线性表的线性存贮结构优于链表存贮结
8、构B. 队列的操作方式是先进后出C. 栈的操作方式是先进先出D. 二维数组是指它的每个数据元素为一个线性表的线性表14、线性表有两种存储结构：一是顺序表，二是链表。试问：（1）有一个线性表，在处理过过程中表的长度会根据需要动态发生变化，在这种情况下应选用哪种存储结构（2）有一个线性表，很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应采用哪种存储结构15. 已知数组A中，每个元素AI,J在存贮时要占3个字节，设I从1变化到8, J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A5,8的起始地址为（）A.SA+144 B.SA+180 C.SA+222 D.S
9、A+225（4*10+8）*31. 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。A. 沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖2. 在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。A. gcc/g+ B. Turbo PascalC. RHIDE D. free pascal3. 以下断电之后仍能保存数据的有（）。A.寄存器B. ROM C. RAM D.高速缓存4. Linux 是一种（）。A.绘图软件B.程序设计语言C.操作系统D.网络浏览器5. CPU是（）的简称。A.硬盘B.中央处理器C.高级程序语言D.核心寄存器6. 在
10、计算机中，防火墙的作用是（）。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型数组），按行读（即外层循环是关于行的）与按列读（即 外层循环是关于列的）相
