《数据结构形考3_0002-四川电大-课程号：5110025-满分答案1》由会员分享，可在线阅读，更多相关《数据结构形考3_0002-四川电大-课程号：5110025-满分答案1（4页珍藏版）》请在金锄头文库上搜索。
1、数据结构形考3_0002四大形成性测评系统 课程代码：5110025 参考资料 、单项选择题（共 15 道试题，共 60 分。）1. 二叉树的深度为k,则二叉树最多有（ ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1参考答案：D2. 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ ）。 A. 33 B. 34 C. 35 D. 36参考答案：B3. 在一棵度具有5层的满二叉树中结点总数为（ ）。 A. 31 B. 32 C. 33 D. 16参考答案：A4. 在一棵二叉树中，若编号
2、为9的结点存在右孩子，则右孩子的顺序编号为（ ）。 A. 18 B. 16 C. 15 D. 19参考答案：D5. 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A. 2i B. 2i-1 C. 2i+1 D. 2i+2参考答案：C6. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。 A. abdec B. debac C. debca D. abedc参考答案：C7. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。 A. 4 B. 5 C. 6 D. 7参考答案：C8. 如果
3、将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ ）。 A. 哈夫曼树 B. 平衡二叉树 C. 二叉树 D. 完全二叉树参考答案：A9. 一棵采用链式存储的二叉树，有11个叶结点,5个一度结点, 该二叉树共有（ ）点。 A. 28 B. 27 C. 26 D. 25参考答案：C10. 二叉树第k层上最多有（ ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1参考答案：B11. 在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。 A. 1/2 B. 1 C. 2 D. 4参考答案：C12. 利用3、6、8、12这四个值作为叶子结点的权，
4、生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( )。 A. 18 B. 16 C. 12 D. 30参考答案：C13. 在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号为（ ）。 A. i/2 B. 2i-1 C. 2i+1 D. i/2 -1参考答案：A14. 一个具有n个顶点的无向完全图包含（ ）条边。 A. n（n-1） B. n（n+1） C. n（n-1）/2 D. n（n+1）/2参考答案：C15. 在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点空结点参考答案：C 、判断题（共 10 道试题，共 40
5、分。）1. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。 A. 错误 B. 正确参考答案：B2. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。 A. 错误 B. 正确参考答案：B3. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。 A. 错误 B. 正确参考答案：B4. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 A. 错误 B. 正确参考答案：B5. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。 A. 错误 B. 正确参考答案：B6. 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。 A. 错误 B. 正确参考答案：A7. 有回路的有向图不能完成拓扑排序。 A. 错误 B. 正确参考答案：B8. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 A. 错误 B. 正确参考答案：B9. 二叉树是一棵无序树。 A. 错误 B. 正确参考答案：A10. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。 A. 错误 B. 正确参考答案：B
