【数据结构期末试题及答案】样卷6.doc

《【数据结构期末试题及答案】样卷6.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2020学年数据结构期末试题及答案（六）一、选择题1、二叉树的深度为k，则二叉树最多有（C）个结点。A.2kB.2k-1C.2k-1D.2k-12、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（B）。A.R[2i-1]B.R[2i+1]C.R[2i]D.R[2/i]3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（B）。A.a在b的右方B.a在b的左方C.a是b的祖先D.a是b的子孙4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树

2、先序遍历序列为（）。A.adbceB.decabC.debacD.abcde5、在一棵具有5层的满二叉树中结点总数为（A）。A.31B.32C.33D.166、由二叉树的前序和后序遍历序列（B）惟一确定这棵二叉树。A.能B.不能7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（C）。A.3　B.2C.4D.58、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（C）。A.67　B.68C.69D.709、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，

3、则编号为49的结点的左孩子编号为（A）。A.98　B.99C.50D.4810、表达式a*(b+c)-d的后缀表达式是（B）。A.abcd+-　B.abc+*d-C.abc*+d-D.-+*abcd11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（B）。A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC12、树最适合用来表示（C）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据13、表达式A*(B+C)/(D-E+F)的后缀表达式是（C）。A.A*B+C/D-

4、E+FB.AB*C+D/E-F+C.ABC+*DE-F+/D.ABCDED*+/-+14、在线索二叉树中，t所指结点没有左子树的充要条件是（）。A.t->left==NULL　B.t->ltag==1C.t->ltag==1&&t->left==NULLD.以上都不对15、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变　B.发生改变C.不能确定D.以上都不对16、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。A.15B.16C.17D.4717、在下列情况中，可称为二叉树的是（B）。A.每个结

5、点至多有两棵子树的树　B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵子树18、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中，若结点R[i]有左孩子，则其左孩子是（）。A.R[2i-1]B.R[2i+1]C.R[2i]D.R[2/i]19、下面说法中正确的是（）。A.度为2的树是二叉树B.度为2的有序树是二叉树C.子树有严格左右之分的树是二叉树D.子树有严格左右之分，且度不超过2的树是二叉树20、树的先根序列等同于与该树对应的二叉树的（）。A.先序序列B.中序序列C.后序序列D.层序序列21、按照二叉

6、树的定义，具有3个结点的二叉树有（C）种。A.3　B.4C.5D.622、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（A）。A.51B.23C.53D.74二、判断题（）1、存在这样的二叉树，对它采用任何次序的遍历，结果相同。（）2、中序遍历一棵二叉排序树的结点，可得到排好序的结点序列。（）3、对于任意非空二叉树，要设计其后序遍历的非递归算法而不使用堆栈结构，最适合的方法是对该二叉树采用三叉链表。（）4、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。（√）5、一个含有n个结点的完全二叉树，它的高度是

7、log2n＋1。（√）6、完全二叉树的某结点若无左孩子，则它必是叶结点。三、填空题1、具有n个结点的完全二叉树的深度是log2n+1。2、哈夫曼树是其树的带权路径长度最小的二叉树。3、在一棵二叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有n0=N2+1。4、树内各结点度的最大值称为树的度。四、代码填空题1、函数InOrderTraverse(Bitreebt)实现二叉树的中序遍历，请在空格处将算法补充完整。voidInOrderTraverse(BiTreebt){if(){InOrderTraverse(bt->lchild);printf(