2021年9月计算机二级公共基础知识押题41-50

41、某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=10, rear=5。该队列中的元素个数为（ ）

A)4 B)5 C)6 D)不确定

【解析】带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当front=10,rear=5时，不能确定队列中元素的个数。

42、下列叙述中错误的是（ ）

A)循环链表中有一个表头结点

B)循环链表是循环队列的存储结构

C)循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点

D)循环链表实现了空表与非空表运算的统一

【解析】循环链表是指在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由NULL改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。

43、从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是（ ）

A)循环链表 B)双向链表

C)单向链表 D)二叉链表

【解析】在循环链表中，所有结点的指针构成了一个环状链，只要指出表中任何一个结点的位置，就可以从它出发不重复地访问到表中其他所有结点。

44、非空循环链表所表示的数据结构（ ）

A)有根结点也有叶子结点

B)没有根结点但有叶子结点

C)有根结点但没有叶子结点

D)没有根结点也没有叶子结点

【解析】循环链表表头结点为根结点，链表的最后一个结点为叶子节点，虽然它含有一个指向表头结点的指针，但是表头结点并不是它的一个后件。

45、下列结构中为非线性结构的是（ ）

A)树 B)向量 C)二维表 D)矩阵

【解析】由定义可以知道，树为一种简单的非线性结构。在数这种数据结构中，所有数据元素之间的关系具有明显的层次特性。

46、某棵树的度为4，且度为4、3、2、1的结点个数分别为1、2、3、4，则该树中的叶子结点数为（ ）

A)11 B)9 C)10 D)8

【解析】根据树中的结点数=树中所有结点的度之和+1，设叶子结点数为n，得4×1+3×2+2×3+1×4+n×0+1=21,则n=21-1-2-3-4=11。

47、设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为（ ）

A)1 B)2 C)3 D)不可能有这样的树

【解析】设树的结点数为n，则度为3的结点数为n-3-1-6=n-10，根据树中的结点数=树中所有结点的度之和+1，得3×（n-10）+2×3+1×1+0×6+1=n，解得n=11，则度为3的结点数为n-10=11-10=1。

48、设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为（ ）

A) 3 B)1 C) 2 D)不可能有这样的树

【解析】设树的结点数为m，度为3的结点数为n，则度为1的结点数为m-n-5, 根据树中的结点数=树中所有结点的度之和+1，得3×n+1×（m-n-5）+5×0+1=m，则n=2。

49、设某棵树的度为3，其中度为2,1,0的结点个数分别为3,4,15。则该树中总结点数为（ ）

A)不可能有这样的树 B)30 C)22 D)35

【解析】设树的总结点数为n，则度为3的结点数为n-3-4-15=n-22，根据树中的结点数=树中所有结点的度之和+1，得3×（n-22）+2×3+1×4+0×15+1=n，则n=27.5，求出的结点数不为整数，故不可能有这样的树存在。

50、某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为（ ）

A)400 B)754 C)756 D)不确定

【解析】叶子结点有45个，根据在二叉树中度为0的结点（叶子结点）总比度为2的结点多一个，则度为2的结点数为44个，因此度为1的结点数为845-45-44=756个。