《数据结构与算法第3次.doc》由会员分享，可在线阅读，更多相关《数据结构与算法第3次.doc（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法第3次您的本次作业分数为：100分 单选题 1.除根结点外，树上每个结点_ A 可有任意多个孩子、任意多个双亲 B 可有任意多个孩子、一个双亲 C 可有一个孩子、任意多个双亲 D 只有一个孩子、一个双亲 正确答案:B 单选题 2.在一棵二叉树中，第5层上的结点数最多有_ A 10 B 15 C 16 D 32 正确答案:C 单选题 3.树最适合用来表示_ A 有序数据元素 B 无序数据元素 C 元素之间具有分支层次关系的数据 D 元素之间无联系的数据 正确答案:C 单选题 4.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_(注意h是指数) A
2、2h-1 B 2(h-1) C 2*h-1 D 2*h 正确答案:A 单选题 5.在有n个结点的二叉链表中，值为空的链指针共有_ A n+1 B n-1 C n D 2n 正确答案:A 单选题 6.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是_ A dbafec B fecdba C efcdba D dbfeca 正确答案:D 单选题 7.具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余_个指针域为空 A 50 B 99 C 100 D 101 正确答案:D 单选题 8.设二叉树根结点的层次为1，所有含有15
3、个结点的二叉树中，最小高度是_ A 6 B 5 C 4 D 3 正确答案:C 单选题 9. 如果一棵二叉树的先序序列和后序序列相反，则其高度一定等于其结点数。 A 正确 B 不正确 正确答案:A 单选题 10.任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序_ A 不发生变化 B 发生变化 C 不能确定 D 以上都不对 正确答案:A 单选题 11.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为_ A 前序遍历 B 后序遍历 C 中序遍历 D 层次遍历 正确答案:C 单选题 12.关于二叉树的三种遍历，下列说法正确的是_ A 任意两种遍历序列都不可以唯一决
4、定该二叉树 B 任意两种遍历序列都可以唯一决定该二叉树 C 先序遍历序列和后序遍历序列可以唯一决定该二叉树 D 先序遍历序列和中序遍历序列可以唯一决定该二叉树 正确答案:D 单选题 13.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_(注意h为指数) A 2h-1 B 2(h-1) C 2*h-1 D 2*h 正确答案:A 单选题 14.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是_ A a是b祖先 B a是b子孙 C a在b左方 D a在b右方 正确答案:C 单选题 15.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac
5、,它的前序遍历序列是_ A acbed B decab C deabc D cedba 正确答案:D 单选题 16.由二叉树的前序和中序遍历序列可惟一构造这棵二叉树 A 正确 B 不正确 正确答案:A 单选题 17.一棵左右子树均不空的二叉树在后序线索化后，其中空的右链域的个数是_ A 不确定 B 0 C 1 D 2 正确答案:B 单选题 18.在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列 A 正确 B 不正确 正确答案:A 单选题 19.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们
6、把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中_是正确的 A 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D 以上都不对 正确答案:A 单选题 20.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是_的二叉树 A 空或只有一个结点 B 高度等于其结点数 C .任一结点无左孩子 D 任一结点无右孩子 正确答案:A 单选题 21.前序遍历和后序遍历结果相同的二叉树为_ A 只有根结点的二叉树 B 所有非叶子结点只有右子树的二叉树 C 根结点无右孩子的二叉树
7、D 根结点无左孩子的二叉树 正确答案:A 单选题 22.在n个结点的二叉链表中，值为非空的指针域的个数是_ A 2n B 2n+1 C 2(n-1) D n-1 正确答案:D 单选题 23.二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法_ A 正确 B 不正确 正确答案:B 单选题 24.前序遍历和中序遍历结果相同的二叉树为_ A 只有根结点的二叉树 B 所有非叶子结点只有右子树的二叉树 C 根结点无右孩子的二叉树 D 根结点无左孩子的二叉树 正确答案:B 单选题 25.由分别带权为9,2,5,7的四个叶子结点构造一棵Huffman树，则该树的带权路径长度WPL为_ A
8、23 B 37 C 44 D 46 正确答案:C 单选题 26.有m个叶子结点的Huffman树所具有的结点总数为_ A m+1 B 2m-1 C 2m D 2m+1 正确答案:B 单选题 27.用HUFFMAN 算法求最优二叉树时，权越大的叶子离根越远 A 正确 B 不正确 正确答案:B 单选题 28.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是_ A 根结点无右子树的二叉 B 根结点无左子树的二叉树 C 根结点可能有左二叉树和右二叉树 D 各结点只有一个儿子的二叉树 正确答案:C 判断题 29.n(n0)个结点的树有n-1条边 正确 错误正确答案: 对 判断题 30.n(n0)个
9、结点的树至少有log2n层 正确 错误正确答案: 错 判断题 31.二叉树中第3层结点数至少是4个结点 正确 错误正确答案: 错 判断题 32.任何二叉树的叶子数都要比度为2的结点数多 正确 错误正确答案: 对 判断题 33.若用孩子表示法存储树，则无法找到结点的双亲结点 正确 错误正确答案: 错 判断题 34.二叉树中第4层结点数至多是8个结点 正确 错误正确答案: 对 判断题 35.若用双亲表示法存储树，则无法找到结点的所有孩子结点 正确 错误正确答案: 错 判断题 36.满二叉树一定是完全二叉树，反之不然 正确 错误正确答案: 对 判断题 37.任何一个森林都可以唯一地与一棵二叉树对应 正确 错误正确答案: 对 判断题 38.哈夫曼编码使一串文字的编码长度最短 正确 错误正确答案: 对
