.初赛复习
一 题型
单项选择题（共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