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、深度为７的完全二叉树中共有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)双向链表

【解析】二叉树的链式存储结构也称为二叉链表，二叉树是树的一种，属于非线性结构。