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