数据结构作业题

第3章栈和队列

3．1设将整数l、2、3、4依次进栈，只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：

(1)当入、出栈次序为Push(1)，Pop()，Push(2)，Push(3)，Pop()，Push(4)，Pop()，出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?

(2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。

3．2循环队列的优点是什么?如何判别它的空和满?

第6章树：

6．1假设有一棵树用广义表表示如下：（a(b(d,e(i(m,n))),c(f,g(j,k),h(l)))）请用树形表示法画出此树，并回答下列问题：(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少?(9)树的深度是多少?(10)以结点c为根的子树的深度是多少?(11)树的度数是多少?

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

6．3试采用顺序存储方法和链接存储方法分别画出如图6—4所示的各二叉树的存储结构。

图6-4

6．4分别写出图6—4所示的各二叉树的前序、中序和后序序列。

6．5若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。

(2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。

(3)已知两棵二叉树的前序序列均为AB，后序序列均为BA，请画出这两棵不同的二叉树。

6．6如图6-6给定的森林

(1)求各树的前序序列和后序序列。

(2)求森林的前序序列和后序序列。

(3)将此森林转换为相应的二叉树。

(4)给出(a)所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等4种存储结构。

图6-6

6．7画出如图6-8所示的各二叉树所对应的森林。

图6-8

6．8假设用于通信的电文由字符集{a，b，C，d，e，f,g，h)中的字母构成，这8个字母在电文中出现的概率分别为{0．07，0．19，0．02，0．06，0．32，0．03，0．21，0．10}。为这8个字母设计哈夫曼编码。