正文描述:《数据结构(c语言版)第6章练习 清华大学出版社》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第六章数据结构作业第六章树选择题1.已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为()A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE2.算术表达式a+b*(c+d/e)转为后缀表达式后为()A.ab+cde/*B.abcde/+*+C.abcde/*++D.abcde*/++3.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数为()A.5B.6C.7D.84.设森林F对应的二叉树为B,它有m个结点,B的根为
2、p,p的右子树结点个数为n,森林F中第一棵树的结点个数是()A.m-nB.m-n-1C.n+1D.条件不足,无法确定5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()A.9B.11C.15D.不确定6.具有10个叶结点的二叉树中有()个度为2的结点,A.8B.9C.10D.ll7.一棵完全二叉树上有1001个结点,其中叶子结点的个数为()A.250B.500C.254D.505E.以上答案都不对8.有n个叶子的哈夫曼树的结点总数为()。A.不确定B.2nC.2n+1D.2n-19.一棵具有n个
3、结点的完全二叉树的树高度(深度)是()A.ëlognû+1B.logn+1C.ëlognûD.logn-110.深度为h的满m叉树的第k层有()个结点。(1=
4、次遍历13.树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列14.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是()。A.acbedB.decabC.deabcD.cedba15.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG。该二叉树根的右子树的根是:A、EB、F C、G D、H16.n个结点的线索二叉树上含有的线索数为()A.2nB.n-lC.n+lD.n17.下述编码中哪一个不是前缀码()。A.(00,01,10,1
5、1)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001)18.从下列有关树的叙述中,选出5条正确的叙述()A.二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B.当K≥1时高度为K的二叉树至多有2k-1个结点。3C.用树的前序周游和中序周游可以导出树的后序周游。D.线索二叉树的优点是便于在中序下查找前驱结点和后继结点。E.将一棵树转换成二叉树后,根结点没有左子树。F.一棵含有N个结点的完全二叉树,它的高度是ëLOG2Nû+1。G.在二叉树中插入结点,该二叉树便不再是
6、二叉树。H.采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。I.哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。J.用一维数组存储二叉树时,总是以前序周游存储结点。判断题:1.完全二叉树中,若一个结点没有左孩子,则它必是树叶。2.二叉树只能用二叉链表表示。3.在二叉树的第i层上至少有2i-1个结点(i>=1)4.度为二的树就是二叉树。5.在中序线索二叉树中,每一非空的线索均指向其祖先结点。填空题:1.具有256个结点的完全二叉树的深度为______。2.已知一棵度为3的树有2个度
7、为1的结点,3个度为2的结点,4个度为3的结点,则该树有______个叶子结点。3.在一棵二叉树中,度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______4.已知二叉树有50个叶子结点,则该二叉树的总结点数至少是______。5.设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点,右子树中有_(2)__个结点。6.如某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点数为______。
8、算法应用题1、已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,问该树中有多少个叶子结点?2、已知一棵满二叉树的结点个数为20到40之间的素数,此二叉树的叶子结点有多少个?(请给出具体的推理过程)3、请采用顺序存储方式和链式存储方式,分别写出下图所示二
显示全部收起