哈尔滨工程大学考研-数据结构-6

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《哈尔滨工程大学考研-数据结构-6》，欢迎阅读！

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2．在下述结论中，正确的是（ ）

① 只有一个结点的二叉树的度为0; ② 二叉树的度为2；

③ 二叉树的左右子树可任意交换;

④ 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④

3. 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（ ）

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

4．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个

A．4 B．5 C．6 D．7

5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）

A． 250 B． 500 C．254 D．505 E．以上答案都不对 6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )

A．不确定 B．2n C．2n+1 D．2n-1 7. 一个具有1025个结点的二叉树的高h为（ ）

A．11 B．10 C．11至1025之间 D．10至1024之间 8．深度为h的满m叉树的第k层有（ ）个结点。(1=

A．mk-1 B．mk-1 C．mh-1 D．mh-1 9．高度为 K的二叉树最大的结点数为（ ）。

A．2k

B．2k-1 C．2k -1



D．2k-1-1

10．在下列存储形式中，哪一个不是树的存储形式？（ ）

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 二、判断题

1．二叉树是度为2的有序树。


2．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 3．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。 4．将一棵树转成二叉树，根结点没有左子树。 5．二叉树中序线索化后，不存在空指针域。 三、填空题

1．在二叉树中，指针p所指结点为叶子结点的条件是______。

2． 中缀式a+b*3+4*（c-d）对应的前缀式为__ _，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_ __。

3．具有256个结点的完全二叉树的深度为______。

4．深度为k的完全二叉树至少有___ ____个结点，至多有___ ____个结点。 5．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。 四、应用题

1．假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,i),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题： （1） 哪个是根结点？ （2） 哪些是叶结点？ （3） 哪个是g的双亲？ （4） 哪些是g的祖先？ （5） 哪些是g的孩子？ （6） 哪些是e的子孙？

（7） 哪些是e的兄弟？哪些是f的兄弟？ （8） 结点b和n的层次各是多少？ （9） 树的深度是多少？

（10） 以结点c为根的子树的深度是多少？ （11） 树的度数是多少？

2．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

3．已知一棵树为m的树中有n1个度为1的结点，n2个度为2的结点，…nm个度为m的结点，问该树中有多少片叶子？

4．试找出分别满足下面条件的所有二叉树：

本文来源：https://www.dy1993.cn/wq74.html