资源描述:
《习题五和上机答案.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、习题五5.1已知一棵树边的集合为(I,M),(I,N),(E,I),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(TABLE,L),(C,TABLE),(A,C),画出这棵树,并回答下列问题:⑴哪个是根结点?⑵哪些是叶子结点?⑶哪个是结点G的双亲?⑷哪些是结点G的祖先?⑸哪些是结点G的孩子?⑹哪些是结点E的子孙?⑺哪些是结点E的兄弟?哪些是结点F的兄弟?⑻结点B和N的层次号分别是什么?⑼树的深度是多少?⑽以结点C为根的子树的深度是多少?解:依题意,树的表示如
2、图8.23所示。(1)根结点是:a(2)叶子结点是:d,m,n,f,j,k,l(3)g的双亲是:c(4)g的祖先是:a,c(5)g的孩子是:j,k(6)e的子孙是:i,m,n(7)e的兄弟是d,f的兄弟是g,h(8)b的层次是2,n的层次是5(9)树的深度是5(10)以结点c为根的子树的深度是3(11)树的度数是35.2一棵度为2的树与一棵二叉树有何区别?解:二叉树的度也可以为1。5.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。解:二叉树:5.4一棵深度为N的满K叉树有如下性质:
3、第N层上的结点都是叶子结点,其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号,问⑴各层的结点数目是多少?⑵编号为n的结点的父结点(若存在)的编号是多少?⑶编号为n的结点的第i个儿子(若存在)的编号是多少?⑷编号为n的结点有右兄弟的条件是什么?其右兄弟的编号是多少?解:(1)第i层的结点数为ki-1。(2)编号为n的结点的双亲点为:「(n-2)/k」+1。(3)编号为n的结点的第i个孩子结点为:(n-1)*k+i+1。(4)编号为n的结点有右兄弟的条件是(n-1)%k≠0,其
4、右兄弟的编号是n+1。5.5已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,...,nm个度为m的结点,问该树中有多少个叶子结点?解:依题意:设n为总的结点个数,n0为叶子结点(即度为0的结点)的个数,则有:n=n+n+n+...+n①又有:n-1=度的总数,即:n-1=n*1+n*2+...+n*m②①-②式得:1=n-n-2n-...-(m-1)n则有:n=1+n+2n+...+(m-1)n=1+5.6试列出下列二叉树的终端结点、非终端结点以及每个结点的层次题5.6解:终端结点:
5、E、G、H非终端结点:A、B、C、D、F结点ABCDEFGH层次122333445.7对于5.6题中给出的二叉树,分别列出先根次序、中根次序、后根次序的结点序列。解:先根次序:ABDGCEFH中根次序:DGBAECHF后根次序:GDBEHFCA5.8在二叉树的顺序存储结构中,实际上隐含着双亲的信息,因此可和三叉链表对应。假设每个指针域占4个字节的存储空间,每个信息占K个字节的存储空间。试问对于一棵有n个结点的二叉树,且在顺序存储结构中最后一个结点的下标为m,在什么条件下顺序存储结构比二叉链表更节省
6、空间?解:(K+4)*n<(m+1)*45.9假定用两个一维数组L(1:n)和R(1:n)作为有n个结点的二叉树的存储结构,L(i)和R(i)分别指示结点i的左孩子和右孩子,0表示空。⑴试写一个算法判别结点u是否为结点v的子孙;⑵先由L和R建立一维数组T(1:n),使T中第i(i=1,2,...,n)个分量指示结点i的双亲,然后写判别结点u是否为结点v的子孙的算法。解:(1)、intIs_Descendant_C(intu,intv)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0{
7、if(u==v)return1;else{if(L[v])if(Is_Descendant(u,L[v]))return1;if(R[v])if(Is_Descendant(u,R[v]))return1;//这是个递归算法}return0;}//Is_Descendant_C(2)、intIs_Descendant_P(intu,intv)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0{for(p=u;p!=v&&p;p=T[p]);if(p==v)return1;elseret
8、urn0;}//Is_Descendant_P5.10假设n和m为二叉树中的两结点,用“1”、“0”“Φ”(分别表示肯定、恰恰相反和不一定)填写下表:前序遍历时中序遍历时后序遍历时已知n在m前?n在m前?n在m前?n在m的左方111n在m的右方000n是m的祖先1Φ0n是m的子孙0Φ1注:⑴如果离a和b最近的共同祖先p存在,且⑵a在p的左子树中,b在p的右子树中,则称a在b的左方(即b在a的右方)。5.11假设以二叉链表作存储结构,试分别写出前序和后序遍历的非递归算法,可直接利用栈