单元测验4
「判断题(下列各题，正确的请在前面的括号内打√;错误的打 X )
(√) (1)队列是限制在两端进行操作的线性表。
(√) ( 2)判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 (×) ( 3)在链队列上做出队操作时，会改变 front指针的值。
(√) ( 4)在循环队列中，若尾指针 rear大于头指针front ,其元素个数为rear- front (×) ( 5)在单向循环链表中，若头指针为
h,那么P所指结点为尾结点的条件是 P=h。
(√) ( 6)链队列在一定范围内不会出现队满的情况。 (×) ( 7)在循环链队列中无溢出现象。 (×) ( 8)栈和队列都是顺序存储的线性结构。 (×) ( 9)在队列中允许删除的一端称为队尾。
(×) ( 10)顺序队和循环队关于队满和队空的判断条件是一样的。
二?填空题
(1) (2)
在队列中存取数据应遵循的原则是
先进先出
。
队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删 除运算的线性表。
(3) (4) (5) (6) (7) (8) (9)
在队列中，允许插入的一端称为 在队列中，允许删除的一端称为
队尾 。 队首(或队头)
。 空 。
满 。
队列在进行出队操作时，首先要判断队列是否为 顺序队列在进行入队操作时，首先要判断队列是否为 顺序队列初始化后，
fron t=rear= -1 _________ 。
循环队列
解决顺序队列“假溢出”的方法是采用 循环队列的队首指针为 rear 。
front ,队尾指针为
。
front ==
rear ,则队空的条件为
(10) ______________________________________________ 链队列 LQ为空时，LQ->front->next= NU ________________________________ 。 (11)
设长度为n的链队列用单循环链表表示， ( n)。
(12)
只设尾指针，
杂度为 0 ( 1)。
设长度为n的链队列用单循环链表表示， 若则出队操作的时间复
若只设头指针，则入队操作的时间复 杂度为 0 79
(13) 在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为
空 ____ 。 (14) 元素后的一个
空闲元素，队列的最大空间为MAXLEN,则队满标志为 front==(rear+1)%MAXLEN 。
(15)
在一个链队列中，若队首指针为 front ,队尾指针为rear ,则判断该队列只有 一个结点的条件为：
fron t==rear && front !NULL ____________ 。
设循环队列的头指针 front指向队首元素， 尾指针rear指向队尾
( 或 front==rear && front <>NULL ) _______ (16) 先要判断
所指的位置写入新的数据。
(17)
列元素的个数。 (18)
设循环队列的容量为 40 (序号从0到39)，现经过一系列的入队和出队运算后，有
读队首元素的操作 不改变(或不影响) 队
向一个循环队列中插入元素时，首队尾指针
，然后再向指针
front=11 ， rear=19 ,则循环队列中还有 8 __________ 个元素。
(L= (N + rear — front)% N= (40+ 19- 11) % 40=8)
(19) InitQueue(Q)(
队列 Q，经过下列运算：初始化队列);lnQueue(Q,a);
后的值是 0 In QUeUe(Q,b);OUtQUeUe(Q,x); ReadFrO nt(Q,x);QEmPty(Q);
。
(20 )队列 Q 经过 InitQueue(Q)( 初始化队列);lnQueue(Q,a);lnQueue(Q,b); ReadFrOnt(Q,x)后，X 的值是 a 。
三?选择题
(1 )队列是限定在( D )进行操作的线性表。 A . 中间
B . 队首
C .队尾
D . I端点
(2) 队列中的兀素个数是
A . 不变的
(B ) B . 可变的
。
C .任意的
D . 0
(3) 冋一队列内各兀素的类型 A . 必须一致 (4) 队列是一个 A . 不加限制的
(C )
(A )。
C .可以不一致
B . 不能一致
线性表结构。
D . 不限制
B . 推广了的 D . 非 C .加了限制的
n的数组顺序存储一个队列
该队列的最后 个兀素的下标为 (5) 当利用大小为 时，
)。 (B
80
A . n-2 B . n-1 C .n (6) 一个循环队列一旦说明， 其占用空间的大小( A . 已固定 A . 必须连续
B
. 可以变动
D A
.n+1
)。 D D
. 动态变化
C .不能固定
。
C .不能连续
(7)循环队列占用的空间
(A ) B . 不必连续
. 可以不连续
81
data有10个元素，则data数组的下标范围是（8）存放循环队列元素的数
组
D A . 0..10 B . 0..9 C . 1..9
）
（9）若进队的序列为: A, B, C, D,则出队的序列是（ C ）。
.1..10
（B
A . B, C， D, A C . AD , B G (10) 四个兀素
按: A . A C
四个兀素
(11)
按:
头兀素是（B A . C .
B
A, C, B,
D
C, B, D,
B D. D
D
A
A B, G D顺序连续进队 Q, 则队尾兀素是（
D ）。
B .
A, B, G D顺序连续进队 ) 。
Q, 执行一次
OUtQUeUe(Q操作) 后，
队
B . B C . C A
四个兀素
(12) A, B, C D顺序连续进队 Q, 执行四次
按:
）。 执行QEmPty（Q）;后的值是（ B
D . D
OUtQUeUe(Q操作) 后，
再
A .
0
B .
1
C
X的值是（B
. 2
) 。
D
.3
(13) 队列Q,经过下列运算后， Ini
tQueue(Q)( ReadFrO nt (Q,x); A.
初始化队列 );In QUeUe(Q,a); I
nQueue(Q,b);OUtQUeUe(Q,x);
(14) 循环队列 SQ队满的条件是
SQ->rear==SQ->fro nt
(SQ->rear+1)% MAXLEN ==SQ->fro nt D . SQ->front==O
data为数据域， next为指针域，且
则应执行下列（ B . top->next=s D . s->next=top
；top=s ； top是栈顶指针。若 A ）操作。
SQ->rear==0
（15）设链栈中结点的结构： 想在链栈的栈顶插入一个由指针
A . s->next=top->next
S所指的结点,
; top->n ext=s ;
;
C . s->next=top ; top=top->next （16）带头结点的链队列
LQ示意图如下，链队列的队头元素是（
LQ->fro nt
(17)
LQ->rear
带头结点的链队列 LQ示意图如下，指向链队列的队头指针是(
82
LQ->fro nt
LQ->rear
A. LQ->front C. LQ->front->next
D
B. LQ->rear . LQ->rear->next
在进行进队运算时指针
(18)
LQ->fro nt
带头结点的链队列 LQ示意图如下， LQ->front ( A )
LQ->rear
A.始终不改变
B .有时改变 C
.进队时改变
D .出队时改变
(19) 队列Q,经过下列运算后，再执行 QEmPty(Q)的值是(C )。 Ini tQueue(Q)( ReadQUeUe(Q,x); A. a
B . b C
. 0
D . 1
初始化队列 );l nQueue(Q,a); I nQueue(Q,b);OUtQUeUe(Q,x);
(20) 若用一个大小为6的数组来实现循环队列，且当前 front和rear的值分别为3和0,当 从队列中删除一个元素，再加入两个元素后， A . 5 和 1
B . 4 和 2
front和rear的值分别为(B )
C . 2 和 4
D
. 1 和 5
。
四.写出程序运行的结果
写出下列程序段的输出结果(队列中的元素类型为 void mai n() {
QUeUe Q; InitQueue (Q); Char x=\In QUeUe (Q, \In QUeUe (Q, \In QUeUe (Q, y);
OUtQUeUe (Q,x); I nQUeUe (Q,x);
OUtQUeUe (Q,x); InQUeUe (Q, \
〃 初始化队列
Char)O
83
中国铁道出版社数据结构(第二版)单元4练习参考答案
