2024年4月12日发(作者：)

单元测验4

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打

╳

）

（）（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） 顺序队列初始化后，front=rear= 。

（8） 解决顺序队列“假溢出”的方法是采用 。

（9） 循环队列的队首指针为front，队尾指针为rear，则队空的条件为 。

（10） 链队列LQ为空时，LQ->front->next= 。

（11） 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复

杂度为 。

（12） 设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复

杂度为 。

（13） 在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为 。

（14） 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个

空闲元素，队列的最大空间为MAXLEN，则队满标志为： 。

79

（15） 在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有

一个结点的条件为： 。

（16） 向一个循环队列中插入元素时，首先要判断 ，然后再向指针所指的位

置写入新的数据。

（17） 读队首元素的操作 队列元素的个数。

（18） 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

front=11，rear=19，则循环队列中还有 8 个元素。

（19）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a);

InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 。

（20）队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);

ReadFront(Q,x)后，x的值是 。

三．选择题

（1）队列是限定在（ ）进行操作的线性表。

A．中间

A．不变的

B．队首

B．可变的

C．队尾

C．任意的

D．端点

D．0

D．不限制

D．非

（2）队列中的元素个数是( )。

（3）同一队列内各元素的类型( )。

A．必须一致

A．不加限制的

（ ）。

A．n-2 B．n-1 C．n D．n+1

C．不能固定 D．动态变化

C．不能连续 D．可以不连续

C．1..9 D．1..10

B．A，C，B，D

D．C，B，D，A

（6）一个循环队列一旦说明，其占用空间的大小（ ）。

A．已固定 B．可以变动

（7）循环队列占用的空间( )。

A．必须连续 B．不必连续

（8）存放循环队列元素的数组data有10个元素，则data数组的下标范围是( )。

A．0..10 B．0..9

A．B，C，D，A

C．A，B，C，D

（9）若进队的序列为：A，B，C，D，则出队的序列是（ ）。

B．不能一致 C．可以不一致

B．推广了的 C．加了限制的

（4）队列是一个( )线性表结构。

（5）当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为

80

（10）四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是（ ）。

A． A

C． C

B． B

D． D

（11）四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队

头元素是（ ）。

A． A B． B C． C D． D

（12）四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q)操作后，再

执行QEmpty(Q);后的值是（ ）。

A． 0 B． 1 C． 2 D． 3

（13）队列Q，经过下列运算后，x 的值是（ ）。

InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x);

ReadFront (Q,x);

A．a B．b C．0 D．1

（14）循环队列SQ队满的条件是( )。

A．SQ->rear==SQ->front B．(SQ->rear+1)% MAXLEN ==SQ->front

D．SQ->front==0 C．SQ->rear==0

（15）设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若

想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（ ）操作。

A．s->next=top->next；top->next=s； B．top->next=s；

C．s->next=top；top=top->next；

LQ->front

H A B C D Λ

D．s->next=top；top=s；

（16）带头结点的链队列LQ示意图如下，链队列的队头元素是（ ）

LQ->rear

A．A B．B C．C D．D

（17）带头结点的链队列LQ示意图如下，指向链队列的队头指针是（ ）

LQ->front

H

A B C D Λ

81

LQ->rear

A．LQ->front B．LQ->rear

C．LQ->front->next D．LQ->rear->next

（18）带头结点的链队列LQ示意图如下，在进行进队运算时指针LQ->front（ ）

LQ->front

H A B C D Λ

LQ->rear

A．始终不改变 B．有时改变 C．进队时改变 D．出队时改变

（19）队列Q，经过下列运算后，再执行QEmpty(Q) 的值是（ ）。

InitQueue(Q) (初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x);

ReadQueue(Q,x);

A．a B．b C．0 D．1

（20）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当

从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。

A．5和1 B．4和2 C．2和4 D．1和5

四． 写出程序运行的结果

写出下列程序段的输出结果（队列中的元素类型为char）。

void main( )

{

Queue Q; InitQueue (Q);

// 初始化队列

char x="E"; y="C";

InQueue (Q, "H");

InQueue (Q, "R");

InQueue (Q, y);

OutQueue (Q,x); InQueue (Q,x);

OutQueue (Q,x); InQueue (Q, "A");

while (!QEmpty(Q))

{

OutQueue (Q,y);

printf(y);

};

printf(x);

82

}

五．程序填空

1．假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成

向循环队列中插入一个元素为x的结点的函数。

typedef struct queuenode

// 定义队列的存储结构

{ int data;

struct queuenode *next;

}qu;

InQueue(rear,x)

// 向队列插入元素为x的函数

{ qu *rear；

int x；

{ qu *head,*s;

s= ;

s->data= ;

if (rear==NULL)

// 循环队列为空，则建立一个结点的循环队列

{ rear=s; rear->next;}

else

{ head= ;

// 循环队列非空，则将s插到后面

rear->next= ;

rear=s;

=head;}

}

六. 算法设计题

1．设一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个

数的记数器cont，试写出相应的入队算法和出队算法。

2．用一个循环数组Q[0..MAXLEN-1]表示队列时，该队列只有一个头指针front，不

设尾指针，而改置一个记数器count用以记录队列中结点的个数。试编写一个能实

现：初始化队列、判队空、读队头元素、入队操作和出队操作的算法。

3．一个用单链表组成的循环队列，只设一个尾指针rear，不设头指针，请编写他

如下算法：

（1） 向循环队列中插入一个元素为x的结点；

（2） 从循环队列中删除一个结点。

83