形考3_0002 试卷总分:100 测试时间:60分钟 剩余时间:59分47秒 单项选择题判断题 一、单项选择题(共 15 道试题,共60 分。) 1. 在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为( )。 A. 4 B. 5 C. 6 D. 7 满分:4 分 2. 在有向图的邻接表中,每个顶点邻接表链接着该顶点所有( )邻接点。 A. 入边 B. 出边 C. 入边和出边 D. 不是入边也不是出边 满分:4 分 3. 二叉树的深度为k,则二叉树最多有( )个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 满分:4 分 4. 二叉树第k层上最多有( )个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 满分:4 分 5. 在一棵二叉树中,若编号为i的结点是其双亲结点的左孩子,则双亲结点的顺序编号为( )。 A. i/2 B. 2i-1 C. 2i+1 D. i/2 -1 满分:4 分 6. 一棵采用链式存储的二叉树,有11个叶结点,5个一度结点, 该二叉树共有( )点。 A. 28 B. 27 C. 26 D. 25 满分:4 分 7. 设一棵有n个叶结点的二叉树,除叶结点外每个结点度数都为2,则该树共有( )个结点。 A. 2n B. 2n-1 C. 2n+1 D. 2n+2 满分:4 分 8. 一个具有n个顶点的无向完全图包含( )条边。 A. n(n-1) B. n(n+1) C. n(n-1)/2 D. n(n+1)/2 满分:4 分 9. 在一棵二叉树中,若编号为i的结点存在右孩子,则右孩子的顺序编号为( )。 A. 2i B. 2i-1 C. 2i+1 D. 2i+2 满分:4 分 10. 在一棵树中,( )没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点空结点 满分:4 分 11. 设某一二叉树先序遍历为abdec,中序遍历为dbeac,则该二叉树后序遍历的顺序是( )。 A. abdec B. debac C. debca D. abedc 满分:4 分 12. 在一棵度具有5层的满二叉树中结点总数为( )。 A. 31 B. 32 C. 33 D. 16 满分:4 分 13. 权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是( )。 A. 18 B. 28 C. 19 D. 29 满分:4 分 14. 在一个图G中,所有顶点的度数之和等于所有边数之和的( )倍。 A. 1/2 B. 1 C. 2 D. 4 满分:4 分 15. 将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为( )。 A. 33 B. 34 C. 35 D. 36 满分:4 分. 二、判断题(共 10 道试题,共 40分。) 1. 有回路的有向图不能完成拓扑排序。 A. 错误 B. 正确 满分:4 分 2. 如果有向图中各个顶点的度都大于2,则该图中必有回路。 A. 错误 B. 正确 满分:4 分 3. 用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶点个数有关,而与图的边数无关。 A. 错误 B. 正确 满分:4 分 4. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。 A. 错误 B. 正确 满分:4 分 5. 邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。 A. 错误 B. 正确 满分:4 分 6. 在树的存储中,若使每个结点带有指向双亲结点的指针,这为在算法中寻找双亲结点带来方便。 A. 错误 B. 正确 满分:4 分 7. 二叉树是一棵无序树。 A. 错误 B. 正确 满分:4 分 8. 在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行中序遍历和后序遍历,则具有相同的结果。 A. 错误 B. 正确 满分:4 分 9. 图中各个顶点的编号是人为的,不是它本身固有的,因此可以根据需要进行改变。 A. 错误 B. 正确 满分:4 分 10. 对于一棵具有n个结点的任何二叉树,进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。 A. 错误 B. 正确 满分:4 分
|