数据结构课后习题(第6章)

《数据结构课后习题(第6章)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第6章）【课后习题】第6章树和二叉树 网络工程2010级（）班学号：姓名：题号一二三四五总分得分一、填空题（每空1分，共16分)1.从逻辑结构看，树是典型的。2.设一棵完全二叉树具有999个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个度为1的结点。3.由n个权值构成的哈夫曼树共有个结点。4.在线索化二叉树中，T所指结点没有左子树的充要条件是。5.在非空树上，_____没有直接前趋。6.深度为k的二叉树最多有结点，最少有个结点。7.若按层次顺序将一棵有n个结点的完

2、全二叉树的所有结点从1到n编号，那么当i为且小于n时，结点i的右兄弟是结点，否则结点i没有右兄弟。8.N个结点的二叉树采用二叉链表存放，共有空链域个数为         。 9.一棵深度为7的满二叉树有______个非终端结点。10.将一棵树转换为二叉树表示后,该二叉树的根结点没有        。11.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的遍历结果是一样的。12.一棵Huffman树是带权路径长度最短的二叉树，权值的外结点离根较远。二、判断题（如果正确，在对应位置打“Ö”，否则打“´”。每题0.5分，共5分)

3、123456789101.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。2.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该二叉树的根结点是那一个，则可以确定这棵二叉树。3.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。4.度≤2的树就是二叉树。5.一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。第9页楚雄师院计科系网络工程2010级《算法与数据结构》课后习题（第6章）1.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一

4、样的。2.不存在有偶数个结点的满二叉树。3.满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。4.已知二叉树的前序遍历顺序和中序遍历顺序，可以惟一确定一棵二叉树；  5.已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树；  三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1分，共30分)题号123456789101112131415答案　　　　　　　　　　题号161718192021222324252627282930答案　　　　　　　　　　1.树的后根遍历序列等同于该树对应的二叉树的().A).先序

5、序列B).中序序列C).后序序列D)层次序列2.设一棵二叉树中，度为1的结点数为9，则该二叉树的叶结点的数目是()。A)10B)11C)12D)不确定3.哈夫曼算法可以用于（）。A)动态存储管理B)表达式求值C)数据通信的二进制编码D)城市间的交通网设计4.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）。A．队列B．栈C．线性表D．有序表5.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）。A．不一定相同B．都相同C．都不相同D．互为逆序6.由下列三棵树组成的森林换成一棵二叉树为（）。第9页楚雄师院计科

6、系网络工程2010级《算法与数据结构》课后习题（第6章）1.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）。A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法2.哈夫曼树是访问叶结点的外部路径长（ ）的二叉树。A.最短；     B.最长     C.可变     D.不定；3.三个结点可以构成（ ）种不同形状的树。A.2；     B.3     C.4    D.5；4.三个结点可以构成（ ）种不同形状的二叉树。A.无穷    B.3     C.4    D.5；5.一棵有16个结点的完全二

7、叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）。A.2，14   B.2，15   C.3，14   D.3，15；6.深度为k的二叉树最多有（ ）结点。A.2k     B.2k-1；     C.2k-1     D.k2；7.具有100个结点的完全二叉树的深度为（ ）。A.6      B.7；      C.8    D.9；8.叶结点个数比度为2的结点的个数多一个，该性质只适用于（ ）。A.完全二叉树   B.满二叉树   C.树   D.所有二叉树；9.具有n个结点的完全二叉树的深度

8、为（ ）。A.élog2nù+1 B.ëlog2nû+1；       C.log2n    D.ëlog2nû；10.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结