[信息学奥赛基础知识讲义]
基础部分
一、进制:2进制数与8进制、10进制、16进制数的换算
换算1:将N进制数换算成10进制数(N可以为2,8,16或其它自然数)
换算2:将10进制数换算成N进制数(N可以为2,8,16或其它自然数)
1.下列无符号数中,最小的数是( )
A.()2 B.(75)10 C.(37)8 D.(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、如果用一个字节表示一个整数,最高位用作符号位,其他位表示数值,例如
00000001表示+1,表示-1
(1) 试问这样表示法的整数a的范围应是————————
A、-127<=a<=127 B、-128<=a<=128
C、-128<=a<127 D、-128<a<=128
(2) 在这样表法法中,以下 ________说法是下确的
A、范围内的每一个数都只有唯一的格式 B、范围内的每一个数有两种格式
C、范围内的一半数有两种格式样 D、范围内只有一个数有两种表示格式
对于字符
对英文的字母和其它打印字符:(扩展)右派分子ASCII码(美国标准信息交换码)
标准的ASCII码为7位二进制编码,但在计算机中以8位二进制位来存储(最高位为校验们位),扩充的ASCII码为8位二进制编码
对汉字,中国大陆常用的有GB码、GBK码、Unicode
GBK码于1980年发布,是中文信息处理的国家标准,在大陆及海外使用简体中文的地区(如新加坡等)是强制使用的唯一中文编码。和苹果OS就是以GB2312为基本汉字编码, Windows 95/98则以GBK为基本汉字编码、但兼容支持GB2312。
GB码共收录6763个简体汉字、682个符号,其中汉字部分:一级字3755,以拼音排序,二级字3008,以偏旁部首排序。
l8.组成'教授'(jiao shou )'副教授'(fu jiao shou )与'讲师'( jiang shi)这三个词的汉字,在GB2312-80字符集中都是一级汉字.对这三个词排序的结果是().
A教授,副教授,讲师 B.副教授,教授,讲师
C讲师,副教授,教授 D.副教授,讲师,教授
规定了一级汉字3755个,二级汉字3008个,其中二级汉字字库中的汉字是以( )为序排列的。
A.以笔划多少 B.以部首 C.以ASCⅡ码 D.以机内码
13.已知小写字母'm'的十六进制的ASCll码值是6D,则小写字母'c'的十六进制的ASCII码值是()
2.在外部设备中,绘图仪属于( )
A.输入设备 B.输出设备 C.辅(外)存储器 D.主(内)存储器
6.计算机主机是由CPU与( )构成的
A.控制器 B.运算器 C.输入、输出设备 D.内存储器
运算器是实现算术运算或逻辑运算的装置,对数据进行传送和加工。
控制器是计算机的控制中心,它分析从存储器取出的信息,然后据此向计算机的各个部分发出各种控制信号,指挥与协调整台计算机自动而有序地工作。它是计算机的“神经中枢”。
存储器的功能是存储信息,以备调用,它由成千上万个存储单元组成,每个单元可存放一定位数的二进制信息,存储器的容量以字节Byte为基本单位,还有KB(=1024Byte)、MB(1024KB)、GB(1024MB)等计量单位(如称某台计算机的内存为64MB,硬盘为10GB)。存储器是计算机的“记忆系统”
微机内存储器的地址是按()编址的。
A. 二进制位 B. 字长sai马达 C.字节 D. 微处理器的型号
中的信息是( )
A.生产厂家预先写入的 B.计算机工作时随机写入的
C.防止计算机病毒侵入所使用的 D.专门用于计算机开机时自检用的
12.某种计算机的内存容量是640K,这里的640K容量是指( )个字节
*1000 *1024 *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、构造数据结构的重要工具:指针
程 序 (读程序写结果、 完善程序)
算法+数据结构
相关知识点:
1.数据类型与数据结构的基本概念。
2.线性表的基本概念和实现技术。
3.栈和队列的基本概念和实现技术。
4.树形结构的基本概念,二*树的表示和遍历算法,树与二*树的转换。
5.排序的基本概念和排序算法(插入排序、选择排序、交换排序)。
一.数据类型与数据结构的基本概念。
数据结构用来描述数据元素之间的关系
数据元素之间的关系有四种
(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]的起始地址为( )