3.利用广义表的 head 和 tail 操作写出函数表达式,把以下各
题中的单元素 banana 从广义表中分离出来:
(1) L1(apple, pear, banana, orange)
(2) L2((apple, pear), (banana, orange))
(3) L3(((apple), (pear), (bananA), (orange)))
( 4 ) L4 (((( apple ))) , ((pear)) , ( bananA ) ,
orange)
(5) L5((((apple), pear), bananA), orange)
【答案】
(1) Head (Tail (Tail (L1) ) )
(2) Head (Head (Tail (L2) ) )
(3) Head (Head (Tail (Tail (Head (L3) ) ) ) )
(4) Head (Head (Tail (Tail (L4) ) ) )
(5) Head (Tail (Head(L5) ) )
1.从概念上讲,树,森林和二叉树是三种不同的数据结构,将
树,森林转化为二叉树的基本目的是什么,并指出树和二叉树的
主要区别。
【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法,本
质是一样的,只是解释不同,也就是说树(树是森林的特例,即
森林中只有一棵树的特殊情况)可用二叉树惟一表示,并可使用
二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有 3:一是二叉树的度至多为 2,树无此限制;
二是二叉树有左右子树之分,即使在只有一个分支的情况下,
也必须指出是左子树还是右子树,树无此限制;三是二叉树允许
为空,树一般不允许为空(个别书上允许为空)。
2.若在内存中存放一个完全二叉树,在二叉树上只进行下面两
个操作:
(1)寻找某个结点双亲 ; (2)寻找某个结点的子女;
请问应该用何种结构来存储该二叉树?
【答案】用顺序存储结构存储 n 个结点的完全二叉树。编号为 i
的结点,其双亲编号是 ëi/2û(i=1 时无双亲),其左子女是 2i(若
2i≤n,否则 i 无左子女),右子女是 2i+1(若 2i+1≤n,否则无
右子女)。
3.求含有 n 个结点、采用顺序存储结构的完全二叉树中的序号
最小的叶子结点的下标。要求写出简要步骤。
评论0
最新资源