内容发布更新时间 : 2024/6/3 13:36:23星期一 下面是文章的全部内容请认真阅读。

D)以上三种说法均不正确

C【解析】在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在大小关系。

42.下列叙述中正确的是

A)结点中具有两个指针域的链表一定是二叉链表

B)结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构

C)循环链表是循环队列的链式存储结构 D)循环链表是非线性结构

B【解析】结点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。

43.带链的栈与顺序存储的栈相比，其优点是 A)入栈与退栈操作方便 B)可以省略栈底指针

C)入栈操作时不会受栈存储空间的限制而发生溢出 D)所占存储空间相同

C【解析】带链的栈就是用一个线性链表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空间的限制而发生溢出（不需考虑栈满的问题）。

44.下列叙述中正确的是

A)带链栈的栈底指针是随栈的操作而动态变化的 B)若带链队列的队头指针与队尾指针相同，则队列为空

C)若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素 D)不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的

A【解析】由于带链栈利用的是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。

45.带链栈空的条件是 A)top=bottom=NULL B)top=-1且bottom=NULL C)top=NULL且bottom=-1 D)top=bottom=-1

A【解析】在带链的栈中，只会出现栈空和非空两种状态。当栈为空时，有top=bottom=NULL；当栈非空时，top指向链表的第一个结点（栈顶）。

46.在带链栈中，经过一系列正常的操作后，如果top=bottom，则栈中的元素个数为 A)0或1

B)0 C)1 D)栈满

A【解析】带链栈就是没有附加头结点、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底指针指向的存储单元中存有一个元素，则当top=bottom时，栈中的元素个数为1；如果栈底指针指向的存储单元中没有元素，则当top=bottom时，栈中的元素个数为0。

47.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为 A)0 B)1 C)20 D)不确定

B【解析】带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为NULL；栈中只有一个元素时，头指针和尾指针都指向这个元素。

48.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为 A)0 B)1 C)10 D)不确定

D【解析】带链的栈使用了链表来表示栈，而链表中的元素存储在不连续的地址中，因此当top=10，bottom=20时，不能确定栈中元素的个数。

49.带链队列空的条件是 A)front=rear=NULL B)front=-1且rear=NULL C)front=NULL且rear=-1 D)front=rear=-1

A【解析】带链的队列就是用一个单链表来表示的队列，队列中的每一个元素对应链表中的一个结点。队列空时，头指针和尾指针都为NULL。

50.在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为 A)0 B)1 C)0或1 D)队列满

C【解析】带链队列空时，头指针和尾指针都为NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。

51.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为 A)0 B)1 C)1或0 D)不确定

B【解析】带链队列空时，头指针和尾指针都为null；队列中只有一个元素时，头指针和尾指针都指向这个元素。

52.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=10,rear=5。该队列中的元素个数为 A)4 B)5 C)6 D)不确定

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

53.下列叙述中错误的是 A)循环链表中有一个表头结点 B)循环链表是循环队列的存储结构

C)循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 D)循环链表实现了空表与非空表运算的统一

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

54.从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是 A)循环链表 B)双向链表 C)单向链表 D)二叉链表

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

55.非空循环链表所表示的数据结构 A)有根结点也有叶子结点 B)没有根结点但有叶子结点

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

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

6.树与二叉树

56.下列结构中为非线性结构的是 A)树 B)向量 C)二维表 D)矩阵

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

57.某棵树中共有25个结点，且只有度为3的结点和叶子结点，其中叶子结点有7个，则该树中度为3的结点数为 A)6 B)7 C)8

D)不存在这样的树

D【解析】根据题意，树中只有度为3的结点和叶子结点（7个），则度为3的结点有25-7=18个；又根据树中的结点数=树中所有结点的度之和+1，设度为3的结点数为n,则3n+1=25,得n=8。两种方式得到的度为3的结点数不同，故不存在这样的树。

58.某棵树的度为4，且度为4、3、2、1的结点个数分别为1、2、3、4，则该树中的叶子结点数为 A)11 B)9 C)10 D)8

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

59.设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为 A)11 B)12 C)13

D)不可能有这样的树

B【解析】设度为1的结点数为n，根据树中的结点数=树中所有结点的度之和+1，得3×4+2×1+1×n+0×10+1=27，则n=12。

60.设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为 A)1 B)2 C)3

D)不可能有这样的树

A【解析】设树的结点数为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。

61.设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为 A)3 B)1 C)2

D)不可能有这样的树

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

62.度为3的一棵树共有30个结点，其中度为3,1的结点个数分别为3,4。则该树中的叶子结点数为 A)14 B)15 C)16

D)不可能有这样的树

B【解析】设叶子结点数为n，则度为2的结点数为30-3-4-n=23-n，根据树中的结点数=树中所有结点的度之和+1，得3×3+2×（23-n）+1×4+0×n+1=30，则n=15。

63.设某棵树的度为3，其中度为2,1,0的结点个数分别为3,4,15。则该树中总结点数为 A)不可能有这样的树 B)30 C)22 D)35

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

64.某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为 A)400 B)754