NOIP初赛复习

.初赛复习

一 题型

单项选择题(共10题,每题1.5分,共计15分)

不定项选择题(共10题,每题1.5分,共计15分。多选或少选均不得分) 问题求解(共2题,每题5分,共计10分)

阅读程序写结果(共4题,每题8分,共计32 分)

完善程序 (前5空,每空2分,后6空,每空3分,共28分) 二 知识要点

1、计算机的基本常识

计算机产生与发展 、计算机的系统及工作原理、网络的基本知识 、网上搜索信息的基本方法 、计算机中有关数、编码的基本常识 2、数据结构的基本知识

线性表的知识 :(1)栈 : 先进后出(FILO)(2)队列:先进先出(FIFO) 树的基本知识 图的基本知识

3、数学知识:如集合、排列组合等 4、算法的基本知识

(1)初等算法(计数、统计、数学运算等)

(2)排序算法(冒泡法、插入排序、合并排序、快速排序) (3)查找(顺序查找、二分法) (4)回溯算法

数制及数制转换

1.数制

常用的进制:十进制(D) 二进制(B) 八进制(O) 十六进制(H) 基数: 10 2 8 16

位权: 10的幂数 2的幂数 8的幂数 16的幂数 数字符号: 0~9 0~2 0~7 0~9、A~F 2.数制转换

? 2、8、16或其他进制~10进制的转换: ∑(该位上的数×该位上的位权值)

210-1-2-3

如:(101.101)B=1×2+0×2+1×2+1×2+0×2+1×2=(5.625)D ? 10进制~2、8、16或其他进制的转换:

对于整数,采用除进制倒取余法;对于小数,采用乘进制正取整法 如:(13.6875)D=(1101.1011)B ▲注意:一个二进制的小数能完全准确地转换成十进制小数,但一个十进制的小数不一定能完全准确地转换成二进制小数,如0.1,可根据精度要求转换到某一位为止。 ? 2进制与8进制之间的转换:每三个二进制位对应一个八进制位,以小数点分隔

如:(111010.110)2=(72.6)8

? 2进制与16进制之间的转换:每四个二进制位对应一个十六进制位

如:(111010.110)2=(3A.C)16

? 8进制与16进制之间的转换可借助二进制

1

初赛题

2005 年 3. 以下二进制数的值与十进制数23.456 的值最接近的是( )。 A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111 2005年 12. (3725)8 + (B)16的运算结果是( )。

A. (3736)8 B. (2016)10 C. (11111100000)2 D. (3006)10 E. (7E0)16

3.计算机中数的表示

? 正负数的表示:用最高位表示符号位,规定用0表示正,用1表示负。其表示范围由硬

件决定,当使用8位寄存器时,字长为8位,则无符号数的范围是0~255;有符号数的范围是-128~127。当使用16位寄存器时 ,字长为16位,则无符号数的范围是0~65535;有符号数的范围是-32768~32767 ? 定点数和浮点数:根据小数点位置的不同约定两种表示方法,一种是小数点位置固定不

变,称为定点数。一种是小数点位置可以浮动,称为浮点数。

定点数只能表示定点整数和定点纯小数,对于定点整数,约定小数点的位置在最低位;对于定点纯小数,约定小数点的位置在符号位之后。

浮点数能表示既有整数又有小数的数,通常由阶码和尾数组成,类似指数形式 4.原码、反码、补码

? 原码:普通二进制形式,比较自然的表示法,最高位表示符号,0为正,1为负。优点:

简单易懂;缺点:异号数加减法运算复杂。

如:+50的原码为00110010 -50的原码为10110010

? 反码:为计算补码方便而引入。一个正数的反码是原码本身;一个负数的反码是除符号

位之外各位取反,即0变1,1变 0。一个数的反码的反码是原码本身。 如:-50的反码为00110010 -50的反码为11001101

? 补码:加减法运算方便,减法可以转换为加法。一个正数的补码是原码本身,一个负数

的补码是其反码的低位加1。一个数的补码的补码是原码本身。 如:+50的补码为00110010 -50的补码为11001110 ? 两个数的补码之和等于两个数和的补码,符号位参与运算。 5.BCD码(二—十进制编码)

一个十进制数在计算机中以二进制形式存放,需要一个转换过程。但在将所有位的数字输入完之前又不可能转换成完整的二进制数,所以可将每一位数字用二进制进行编码,称为二进制编码的十进制数。

常用的二—十进制数的编码是8421码,用四位二进制数表示一位十进制数,自左至右对应的位权是8、4、2、1。应该指出的是,四位二进制数有0000~1111十六种状态,而十进制数0~9只取0000~1001十种状态,其余六种不用。

如:(498.12)D的BCD码是 0100,1001,1000.0001,0010

二 数据结构的基本知识

(1)栈 : 先进后出(FILO) (2)队列:先进先出(FIFO)

如:某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站状态为空,从这一时刻开始的出入记录为:“进,出,进,进,出,进,进,进,出,出,进,

2

出”。假设车辆入站的顺序为1,2,3,??,则车辆出站的顺序为( )。

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 2003 19已知元素(8,25,14,87,51,90,6,19,20),问这些元素以怎样的顺序进入栈,才能使出栈的顺序满足:8在51前面;90在87的后面;20在14的后面;25在6的前面;19在90的后面。( )。

A)20,6,8,51,90,25,14,19,87 B)51,6,19,20,14,8,87,90,25 C)19,20,90,8,6,25,51,14,87 D)6,25,51,8,20,19,90,87,14 E)25,6,8,51,87,90,19,14,20

设栈S和队列Q的初始状态为空,元素e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6依次通过栈S,一个

元素出栈后即进入队列Q,若出队的顺序为e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 ,则栈S的容量至少应该为( )。 A)2 B)3 C)4 D)5

(3)树 树的概念

图1

? 树是一种重要的非线性数据结构,如图1所示,它比较形象地反映各结点之间一对多的

层次关系。如家族族谱、各种社会组织机构等。 树是由一个或多个结点组成的有限集合T,其中:

1.必须有一个特定的结点,称为是整棵树的根,这个结点没有前驱。

2.其余结点分为m个互不相交的有限子集:T1,T2,T3,??,Tm,每一个子集是一棵子树。

? 树的定义是一个递归定义,即用树来定义树。

3

? 树结构没有封闭的回路。

一、树的术语

1.结点的度——某个结点的子树的个数称为该结点的度。如图1中A结点的度为3,C结点的度为1,G结点的度为0。

2.树的度——即树的宽度,是所有结点的度中的最大值,如图1的树,其度为3; 3.树的深度——组成该树各结点的最大层次,如图1的树,其深度为4;

4.森林——指若干棵互不相交的树的集合,如图1,去掉根结点A,其原来的三棵子树T1、T2、T3的集合{T1,T2,T3}就为森林;

5.有序树——指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样的树称为有序树,否则称为无序树。

6.端结点——也叫叶子结点,如K、L、F、G、M、I、J。 7.分枝结点——度不为0的结点,如B、C、D、E、H。

8.某结点的子树的根称为该结点的儿子(或孩子),反之,该结点称为是儿子结点的父亲(或双亲),同一个父亲结点的儿子结点称为兄弟,父亲结点与儿子结点之间用枝相连。根结点到每一个分枝结点或叶子结点的路径是唯一的。

二、树的表示

1.自然界的树形表示法:如图1,用结点和边表示树,一班用于分析问题。

2.括号表示法——也称广义表表示法:先将根结点放入一对圆括号中,然后把它的子树由左至右的顺序放入括号中,对子树也采用同样的方法处理,同层子树放入它们根结点后面的圆括号中,同层子树之间用逗号隔开。如图1可写成如下形式: (A(B(E(K,L),F),C(G),D(H(M),I,J)))

三、树的存储

树的存储一般有两种:

1.静态的二维数组或一维记录数组(将儿子的下标序列作为一个记录域): 如图1的树中各结点关系可用下表表示,故可用数组存储

下标 1 2 3 4 5 6 7 8 9 10 11 12 13

4

结点 A B C D E F G H I J K L M 2 5 7 8 11 0 0 13 0 0 0 0 0 儿子的下标序列 3 6 0 9 12 0 0 0 0 0 0 0 0 4 0 0 10 0 0 0 0 0 0 0 0 0

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4