2021年9月计算机二级公共基础知识押题51-60
51、某二叉树中有15个度为1的结点,16个度为2的结点,则该二叉树中总的结点数为( )
A)32 B)46 C)48 D)49
【解析】根据在二叉树中度为0的结点(叶子结点)总比度为2的结点多一个,得度为0的结点数为16+1=17个,故总的结点数=17+15+16=48个。
52、某二叉树共有730个结点,其中度为1的结点有30个,则叶子结点个数为( )
A) 1 B)351 C) 350 D)不存在这样的二叉树
【解析】设叶子结点数为n,根据在二叉树中度为0的结点(叶子结点)总比度为2的结点多一个,则度为2的结点数为n-1,n+n-1+30=730,得n=350.5。由于结点数只能为整数,所以不存在这样的二叉树。
53、某二叉树中共有350个结点,其中200个为叶子结点,则该二叉树中度为2的结点数为( )
A)不可能有这样的二叉树 B)150 C)199 D)149
【解析】叶子结点数为200,根据在二叉树中度为0的结点(叶子结点)总比度为2的结点多一个,则度为2的结点数为199,199+200>350,故不存在这样的二叉树。
54、某二叉树的深度为7,其中有64个叶子结点,则该二叉树中度为1的结点数为( )
A)0 B)1 C)2 D)63
【解析】叶子结点有64个,根据在二叉树中度为0的结点(叶子结点)总比度为2的结点多一个,则度为2的结点数为63个;又深度为m的二叉树最多有2^m-1个结点,则该二叉树最多有2^7-1=127个结点。64+63=127,因此该树不存在度为1的结点。
55、深度为7的二叉树共有127个结点,则下列说法中错误的是( )
A)该二叉树是满二叉树 B)该二叉树有一个度为1的结点
C)该二叉树是完全二叉树 D)该二叉树有64个叶子结点
【解析】满二叉树满足深度为m的二叉树最多有2^m-1个结点,本题中二叉树深度为7且有127个结点,满足2^7-1=127,达到最大值,故此二叉树为满二叉树,也是完全二叉树。满二叉树第k层上有2^(k-1)结点,则该二叉树的叶子结点数为27-1=64个。满二叉树不存在度为1的结点。
56、深度为5的完全二叉树的结点数不可能是( )
A)15 B)16 C)17 D)18
【解析】设完全二叉树的结点数为n,根据深度为k的二叉树至多有2^(k-1)个结点,再根据完全二叉树的定义可知,2^(k-1)-1<n≤2^(k-1)。本题中完全二叉树的深度为5,则2^(5-1)-1<n≤2^5-1,15<n≤31。因此,结点数不能为15。
57、某完全二叉树共有256个结点,则该完全二叉树的深度为( )
A)7 B)8 C)9 D)10
【解析】根据完全二叉树的性质:具有n个结点的完全二叉树的深度为[log₂n]+1。本题中完全二叉树共有256个结点,则深度为[log₂256]+1=8+1=9。
58、深度为7的完全二叉树中共有125个结点,则该完全二叉树中的叶子结点数为
A)62 B)63 C)64 D)65
【解析】在满二叉树的第k层上有2^(k-1)个结点、且深度为m的满二叉树有2^m-1个结点,则深度为6的满二叉树共有2^6-1=63个结点,第6层上有2^(6-1)=32个结点。本题是深度为7的完全二叉树,则前6层共有63个结点,第7层的结点数为125-63=62个且全为叶子结点。由于第6层上有32个结点,第7层上有62个结点,则第6层上有1个结点无左右子树(该结点为叶子结点)。因此,该完全二叉树中共有叶子结点62+1=63个。
59、在具有2n个结点的完全二叉树中,叶子结点个数为( )
A)n B)n+1 C)n-1 D)n/2
【解析】由二叉树的定义可知,树中必定存在度为0的结点和度为2的结点,设度为0结点有a个,根据度为0的结点(即叶子结点)总比度为2的结点多一个,得度为2的结点有a-1个。再根据完全二叉树的定义,度为1的结点有0个或1个,假设度1结点为0个,a+0+a-1=2n,得2a=2n-1,由于结点个数必须为整数,假设不成立;当度为1的结点为1个时,a+1+a-1=2n,得a=n,即叶子结点个数为n。
60、下列数据结构中为非线性结构的是( )
A)二叉链表 B)循环队列 C)循环链表 D)双向链表
【解析】二叉树的链式存储结构也称为二叉链表,二叉树是树的一种,属于非线性结构。