上海电力大学计算机算法期末考试卷.pdfVIP

上海电力大学计算机算法期末考试卷--第1页

上海电力大学计算机算法期末考试卷

1.对于一棵具有n个结点、度为4的树来说，_______________。[单选题]*

A.树的高度至多是n-3(正确答案)

B.树的高度至多是n-4

C.第i层上至多有4*(i-1)个结点

D.至少在某一层上正好有4个结点

2.一棵完全二叉树上有1001个结点，其中叶子结点的个数是___________。[单选

题]*

A.250

B.501(正确答案)

C.254

D.505

3.在高度为h的完全二叉树中，______________________。[单选题]*

A.度为0的结点都在第h层上

B.第i（1≤i≤h）层上结点都是度为2的结点

C.第i（1≤ih）层上有个结点(正确答案)

D.不存在度为1的结点

4.若二叉树的中序遍历序列是abcdef，且c为根结点，则________________。[单

选题]*

上海电力大学计算机算法期末考试卷--第1页

上海电力大学计算机算法期末考试卷--第2页

A.结点c有两个孩子(正确答案)

B.二叉树有两个度为0的结点

C.二叉树的高度为5

D.以上都不对

5.在任何一棵二叉树中，如果结点a有左孩子b和右孩子c，则在结点的先序序

列、中序序列和后序序列中，___________。[单选题]*

A.结点b一定在结点a的前面

B.结点a一定在结点c的前面

C.结点b一定在结点c的前面(正确答案)

D.结点a一定在结点b的前面

6.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是

___________。[单选题]*

A.n在m的右方

B.n是m的祖先

C.n在m的左方(正确答案)

D.n是m的子孙

7.如果在一棵二叉树的先序序列、中序序列和后序序列中，结点a、b的位置都是

a在前、b在后（形如…a…b…），则___________。[单选题]*

A.a、b可能是兄弟(正确答案)

B.a可能是b的双亲

C.a可能是b的孩子

D.不存在这样的二叉树

上海电力大学计算机算法期末考试卷--第2页

上海电力大学计算机算法期末考试卷--第3页

8.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个

数是_________。[单选题]*

A.11(正确答案)

B.9

C.18

D.15

9.具有10个叶结点的二叉树中有_________个度为2的结点。[单选题]*

A.8

B.9(正确答案)

C.10

D.11

10.一棵完全二叉树上有1001个结点，其中叶子结点的个数是_________。[单选

题]*

A.254

B.505

C.501(正确答案)

D.250

11.二叉树的第l（只有根结点时的层数为1）层上最多含有结点数为_________。

[单选题]*

A.2^(l-1)(正确答案)

B.2^(l-1)-1

C.2^l

上海电力大学计算机算法期末