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

31、下列结构中属于线性结构链式存储的是（ ）

A)双向链表

B)循环队列

C)二叉链表

D)二维数组

【解析】双向链表也叫双链表，是链表（采用链式存储结构）的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。循环队列是队列的一种顺序存储结构。二叉链表和二维数组属于非线性结构。

32、在线性表的链式存储结构中，其存储空间一般是不连续的，并且（ ）

A)前件结点的存储序号小于后件结点的存储序号

B)前件结点的存储序号大于后件结点的存储序号

C)前件结点的存储序号可以小于也可以大于后件结点的存储序号

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

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

33、下列叙述中正确的是（ ）

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

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

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

D)循环链表是非线性结构

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

34、带链的栈与顺序存储的栈相比，其优点是（ ）

A)入栈与退栈操作方便

B)可以省略栈底指针

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

D)所占存储空间相同

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

35、下列叙述中正确的是（ ）

A)带链栈的栈底指针是随栈的操作而动态变化的

B)若带链队列的队头指针与队尾指针相同，则队列为空

C)若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素

D)不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的

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

36、带链栈空的条件是 （ ）

A)top=bottom=NULL

B)top=-1 且 bottom=NULL

C)top=NULL 且 bottom=-1

D)top=bottom=-1

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

37、某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为（ ）

A)0

B)1

C)20

D)不确定

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

38、某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为（ ）

A)0

B)1

C)10

D)不确定

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

39、带链队列空的条件是（ ）

A)front=rear=NULL

B)front=-1 且 rear=NULL

C)front=NULL 且 rear=-1

D)front=rear=-1

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

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

A)0

B)1

C)1或0

D)不确定

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