备战刷题

# ~~备战刷题！！~~ #### 初赛： 编程语言： 分两类：面向对象和面向过程。 * * * 高级语言和低级语言的区别： 高级语言需要编译运行，常数较大，运行速度慢。而低级语言常数极小，运行速度快。此外，高级语言更容易移植。 * * * 面向对象的高级语言： C++，Java，EIFFEL，Simula 67等。 面向过程的高级语言： C，Fortran语言。 递归编程： 递归是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题。简单来讲，就是“自身调用自身”（在函数中）。 二进制和其它进制的转换 ①十进制转二进制：整数部分除以2取余，直至商为0；小数部分乘以2取整，直至小数部分为0或达到所需精度为止。 ②十进制转八进制：方法同上。整数部分除以8，小数部分乘以8。 ③十进制转十六进制：方法同上。整数部分除以16，小数部分乘以16。 **计算机中的数据单位位(bit)：** 计算机存储数据的最小单元(0、1) 字节(Byte)：处理数据的基本单位(8bit/Byte) 常用的字节计数单位： $1KB＝1024 Byte (210B)$ $1MB＝1024 KB (220B)$ $1GB＝1024 MB (230B)$ $1TB＝1024 GB (240B)$ 字长：CPU一次处理数据的二进制位数。 * * * **无向完全图**： 设图有$n$个结点（例如 $4$ ）：  可见： 每两个点连一条线： 也就有3+2+1条——套上等差数列**也就是$n(n-1)/2$条线** **有向完全图：** 有向完全图与无向完全图的区别是，有向完全图的两个结点可以连接两条边。 那么结点为n的有向完全图的边数就为同节点$无向完全图*2：n×(n−1)$ ## 计算机： - 电子管计算机 - 晶体管计算机 - 小规模集成电路计算机 - 大规模集成电路计算机 * * * 世界第一台电子计算机：阿塔纳索夫-贝瑞计算机（Atanasoff–Berry Computer，简称ABC计算机） 不可编程，且非图灵完全，只能进行线性方程组的计算。 价值&意义：确定了计算机的创造思想 世界上第一台**现代**电子数字计算机：埃尼阿克(ENIAC)，诞生于1946年2月14日的美国宾夕法尼亚大学。 意义：**完全的电子计算机，能够重新编程，解决各种计算问题。** * * * 硬件：物理设备。 软件：程序和文档的集合。 * * * **算法：** 特征： 有穷性：算法的指令或者步骤的执行次数和时间都是有限的。 确切性：算法的指令或步骤都有明确的定义。 输入：有相应的输入条件来刻画运算对象的初始情况。 输出：一个算应有明确的结果输出。 可行性：算法的执行步骤必须是可行的。 * * * 结构： 一般算法有顺序结构、条件分支结构、循环结构三种基本逻辑结构。 * * * #### 树：    树是由一个集合以及在该集合上定义的一种关系构成的，集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构，在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点。 树的基本术语： - 节点的度：一个节点含有的子树的个数称为该节点的度。 - 叶节点或终端节点：度为0的节点称为叶节点。 - 非终端节点或分支节点：度不为0的节点。 - 双亲节点或父节点：若一个节点。 - 含有子节点，则这个节点称为其子节点的父节点。 - 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。 - 兄弟节点：具有相同父节点的节点互称为兄弟节点。 - 树的度：一棵树中，最大的节点的度称为树的度。 - 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。 - 树的高度或深度：树中节点的最大层次。 - 堂兄弟节点：双亲在同一层的节点互为堂兄弟。 - 节点的祖先：从根到该节点所经分支上的所有节点。 - 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 - 森林：由m（m>=0）棵互不相交的树的集合称为森林。