数据结构与算法上机作业第三章 树一、选择题1、在一棵树中,假如结点 A 有 3 个兄弟,B 就是 A 得双亲,则 B 得度为 D A、 1B、 2C、 3D、 42、深度为 h 得完全二叉树至少有 D 个结点,至多有 B 个结点A、 2hB、 2h-1C、 2h+1D、 2h-12^(h-1) -1 +1=2^(h-1)前(n-1)层满,第 h 层只有一结点3、具有 n 个结点得满二叉树有 C 个叶结点。A、 n/2B、 (n-1)/2C、 (n+1)/2D、 n/2+1因为 二叉树中,有这样一个性质,假如其终端结点数(也就就是叶子节点)得个数为n1,度为 2 得结点数为 n2,则 n1=n2+1;假设叶子节点有 x 个,则度为 2 得个数为 x-1:所以: 2x-1 = n; 所以 x = (n+1)/2 (满二叉树)所以 叶子节点个数为 :(n+1)/2非终端结点为 : (n+1)/2-14、一棵具有 25 个叶结点得完全二叉树最多有 B 个结点。A、 48B、 49C、 50D、 515、已知二叉树得先根遍历序列就是 ABCDEF,中根遍历序列就是 CBAEDF,则后根遍历序列就是 A 。A、 CBEFDAB、 FEDCBAC、 CBEDFAD、 不定6、具有 10 个叶结点得二叉树中有 B 个度为 2 得结点。A、 8B、 9C、 10D、 117、一棵非空二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足 C 。A、 所有非叶结点均无左孩子B、 所有非叶结点均无右孩子C、 只有一个叶子结点D、 A 与 B 同时成立8、在线索二叉树中,t 所指结点没有左子树得充要条件就是 B 。A、 t->left=NULLB、 t->ltag=TRUEC、 t->ltag=TRUE 且 t->left=NULLD、 以上都不对9、n 个结点得线索二叉树上含有得线索数为 C 。A、 2nB、 n-1C、 n+1D、 nn-1 表示结点得左右子树,其余 n-1 指针为空线索取代原来得空链10、二叉树根据某种顺序线索化后,任一结点都有指向其前驱与后继得线索,这种说法 B 。A、 正确B、 错误C、 不确定D、 都有可能11、具有 n(n>1)个结点得完全二叉树中,结点 i(2i>n)得左孩子结点就是 D 。A、 2i B、 2i+1C、 2i-1D、 不存在12、具有 64 个结点得完全二叉树得深度为 C 。A、 5B、 6C、7D、 813、将一颗有 100 个结点得完全二叉树从上到下、从左到右一次对结点进行编号,根结点得编号为 1,则编号为 45 得结点得右孩子得编号为 C 。A、 46B、 47C、 90D、 912i 举个简单得例子就可以瞧出来,比如 7 个节点时(也就就是三层时),编号为 1 得左子树编号就是 2,编号 2 得左子树就是 4,编号 3...
