信息学奥赛初赛知识复习1006.ppt

二叉树的五种形态 （1） （2） （3） （4） （5） 满二叉树 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称为满二叉树。 在满二叉树里，树叶的个数等于分支结点个数加一。 完全二叉树 如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层左边的若干位置，则此二叉树称作完全二叉树。 二叉树的遍历 先序：根-左子树-右子树 (abcd) 中序：左子树-根-右子树 (badc) 后序：左子树-右子树-根 (bdca) a b c d 图 习惯上，常用G=(V,E)代表一个图，图中的结点又称为顶点，V是结点的有限集合，结点的偶对称为边，E是边的集合。 任意一个具有n个结点的无向图，其边数小于等于n*(n-1)/2;我们把边数恰好等于n*(n-1)/2的n个结点的无向图称为完全图。 在一个n个结点的有向图中，最大边数为n*(n-1)。 一个结点的度就是与该结点相关联的边的数目。 1．(第七届)一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有(????)个结点? ?A)2h-1????B)2h—1????C)2h十1????D)h十1 2．(第七届)无向图G＝(V，E)，其中V＝{a，b，c，d，e，f?}??E＝{(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，??对该图进行深度优先遍历，得到的顶点序列正确的是( )? ?A)a，b，e，c，d，f????B)a，c，f，e，b，d? ?C)a，e，b，c，f，d????D)a，b，e，d，f，c 3．（第八届）按照二叉树的定义，具有3个结点的二叉树有( )种。 A)3 B)4 C)5 D)6 4．（第八届）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。 A)1／2 B)1 C)2 D)4 5.（第九届）? 假设我们用d=(a1,a2,...,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d 值合理（?????? ）。???? A）{5，4，4，3，1}???? B）{4，2，2，1，1}???? C）{3，3，3，2，2}??? D）{5，4，3，2，1}???? E）{2，2，2，2，2} 6．（第十届）满二叉树的叶结点个数为N，它的结点总数为 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1 * * 复习引入 * 原码表示法 也称为 符号-幅值 表示法 符号位用0-----正数 符号位用1-----负数 其余位表示数的大小 例:X= +1011 [X]原=01011 X= -1011 [X]原=11011 缺点： 运算（加、减法）低效 0有两个表示 +0 –0表示为-127----+127 补码表示法 [X]补=X， 当 X=0; [X]补=2(n+1)+X， 当-2n=X0 mod( 2(n+1) ); 对于定点小数：n=0 定点整数：n=1 例如：X=+100101 [X]补=0 100101 X=–100101 [X]补=1 011011 特点:1.补码的和等于和的补码,符号位和数值位一样参加运算,不必单独处理,即 [X]补+[Y]补=[X+Y]补 2.补码相减: [X]补-[Y]补=[X]补+[-Y]补 [Y]补→[-Y]补: 符号位连同数值位一起取反加1 3表示范围：-128-------+127 反码表示法 当X=0时，[X]反=X 当X=0时，符号位为1，其余各位取反。 特点: 1.反码的和等于和的反码 2.有二个零 +0=00……0 -0=11……1 3.当最高位有进位而丢掉进位(即2)时,要在最低位加1(循环进位) 表示范围：-127------+127 原码,反码和补码之间的转换 [X]反 符号位不变↑数值位 不变(符号位为0)