数据结构1800例题与答案之树和二叉树(2)

键字的有序表

F．需要对n个关键字进行动态插入 G．需要n个关键字的查找概率表 H．不需要任何前提

62．下述编码中哪一个不是前缀码（ ）。【中科院计算所 2000 一、2 （2分）】

A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）

63．下面几个符号串编码集合中，不是前缀编码的是（ ）。

A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000}

D．{b,c,aa,ac,aba,abb,abc} 【西安电子科技大学2001 应用 一、6（2分）】

64. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（ ）【南京理工大学 1999一、18(2分）】

A．A[2i](2i=

65. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ）

A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，无法确定 【南京理工大学2000 一、4(1.5分）】

66．从下列有关树的叙述中,选出5条正确的叙述(共5分) （ ）

A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

k-1

B．当K≥1时高度为K的二叉树至多有2个结点。 C．用树的前序周游和中序周游可以导出树的后序周游。

D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 E．将一棵树转换成二叉树后,根结点没有左子树。

F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+1。 G．在二叉树中插入结点,该二叉树便不再是二叉树。

H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。 I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 J．用一维数组存储二叉树时,总是以前序周游存储结点。【山东工业大学 1995 三、 (5分)】

二、判断题

1. 二叉树是度为2的有序树。【长沙铁道学院1997一、3(1分)】【中科院软件所1997一、9(1分)】

2. 完全二叉树一定存在度为1的结点。【青岛大学 2002 一、4 （1分）】 3. 对于有N个结点的二叉树，其高度为log2n。【上海海运学院 1998 一、6 （1分）】

k

4．深度为K的二叉树中结点总数≤2-1。【南京航空航天大学 1995 五、1 （1分）】 5. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。

【华南理工大学2002一、7 (1分）】

6. 二叉树的遍历结果不是唯一的.【南京理工大学 1997 二、8 （2分）】 7. 二叉树的遍历只是为了在应用中找到一种线性次序。【青岛大学 2001 四、4 （1分）】 8. 树可用投影法进行中序遍历。 【青岛大学 2002 一、6 （1分）】

9. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。

【上海海运学院 1995 一、4 （1分）】 10. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。【上海海运学院 1995 一、6 （1分）】

11. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。【上海海运学院 1996 一、6 （1分）】 12．对一棵二叉树进行层次遍历时，应借助于一个栈。【南京航空航天大学 1995 五、3 （1分）】

13．用树的前序遍历和中序遍历可以导出树的后序遍历。【北京邮电大学 1999 二、3 （2分）】 14．采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。

【北京邮电大学2000一、2(1分）】

15. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。【上海海运学院 1995 一、8 （1分）】

16． 中序遍历二叉链存储的二叉树时，一般要用堆栈；中序遍历检索二叉树时，也必须使用堆栈。

【上海海运学院1998一、7(1分）】

17．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列【中科院软件所 1999 六、1-1 （2分）】

18. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。【 长沙铁道学院 1998 一、2 (1分)】

19．任何二叉树的后序线索树进行后序遍历时都必须用栈。【西安交通大学 1996 二、2 ( 3分) 】

20．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。【西安交通大学 1996 二、1 (3分)】

21．由一棵二叉树的前序序列和后序序列可以唯一确定它。【中科院软件所 1997 一、3 （1分）】

22．完全二叉树中，若一个结点没有左孩子，则它必是树叶。

【东南大学 2001一、1-8（1分）】【中科院软件所1997一、2（1分）】【山东大学2001一、4 (1分)】

23. 二叉树只能用二叉链表表示。【南京理工大学 1997 二、6 （2分）】

24. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+1

25. 给定一棵树，可以找到唯一的一棵二叉树与之对应。【青岛大学 2001 一、5 （1分）】 26. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。【青岛大学 2002 一、5 （1分）】

27. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。

【上海海运学院1996一.5(1分）】

28. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形.

【上海海运学院1997一.5(1分）】

29．树形结构中元素之间存在一个对多个的关系。【燕山大学 1998 二、1 （2分）】

30．在二叉树的第i层上至少有2个结点(i>=1)。【燕山大学 1998 二、3 （2分）】 31．必须把一般树转换成二叉树后才能进行存储。【南京航空航天大学 1997 一、4 （1分）】 32．完全二叉树的存储结构通常采用顺序存储结构。【南京航空航天大学 1996 六、3 （1分）】

33．将一棵树转成二叉树，根结点没有左子树；【北京邮电大学 1999 二、2 （2分）】 34．在二叉树中插入结点，则此二叉树便不再是二叉树了。【北京邮电大学 2000 一、5 （1分）】

35．二叉树是一般树的特殊情形。【北京邮电大学 2000 一、9 （1分） 2002 一、6 （1分）】

36．树与二叉树是两种不同的树型结构。【东南大学 2001 一、1-7 （1分）】 37. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子

【合肥工业大学 2001 二、5 （1分）】

38．在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。【中科院软件所 1997 一、7 （1分）】 39．度为二的树就是二叉树。【大连海事大学 2001 一、7 (1分)】

k-2

40．深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ?2?+1。

【东北大学 1997 二、3 (2分)】

41.下面二叉树的定义只有一个是正确的，请在正确的地方画“√”。

（1）它是由一个根和两株互不相交的、称为左 …… 此处隐藏：5815字，全部文档内容请下载后查看。喜欢就下载吧 ……