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= -1 。

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

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

rear 。

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

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

杂度为 O（n）。

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

杂度为 0（1） 。

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

空 。

79

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

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

front==(rear+1)%MAXLEN 。

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

一个结点的条件为： front==rear && front !NULL 。

( 或 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）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a);

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

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

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

三．选择题

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

A．中间

A．不变的

B．队首

B．可变的

C．队尾

C．任意的

D．端点

D．0

D．不限制

D．非

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

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

A．必须一致

A．不加限制的

（ B ）。

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

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

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

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

A．已固定 B．可以变动

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

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

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

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

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

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

80

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

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

A．B，C，D，A

C．A，B，C，D

A． A

C． C

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

B．A，C，B，D

D．C，B，D，A

B． B

D． D

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

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

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

头元素是（ B ）。

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

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

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

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

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

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

ReadFront (Q,x);

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

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

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 ）操作。

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 Λ

LQ->rear

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

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

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

81

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

LQ->front

H A B C D Λ

LQ->rear

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

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

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

LQ->front

H A B C D Λ

LQ->rear

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

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

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的值分别为( B )。

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");

82

while (!QEmpty(Q))

{

OutQueue (Q,y);

printf(y);

};

printf(x);

}

答：输出为“CHAR”。

五．程序填空

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

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

typedef struct queuenode

// 定义队列的存储结构

{ int data;

struct queuenode *next;

}qu;

InQueue(rear,x)

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

{ qu *rear；

int x；

{ qu *head,*s;

s= new qu ;

s->data= x ;

if (rear==NULL)

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

{ rear=s; rear->next;}

else

{ head= rear->next ;

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

rear->next= s ;

rear=s;

rear->next =head;}

}

六. 算法设计题

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

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

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

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

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

83

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

如下算法：

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

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

1． 解：用一个循环数组Queue[0，n-1]表示该循环队列，头指针为front，计数器

count用来记录队列中结点的个数。

（1）入队算法：

void inqueqe(int x)

{ int temp;

if (count==n)

printf(" 队列上溢出n");

else

{ count++

temp=(front+count)%n;

Queue[temp]=x

}

}

（2）出队算法：

int outqueue()

{ int temp;

if (count==0)

printf(" 队列下溢出n");

else

{ temp=Queue[front];

front=(front+1)%n;

count--;

return temp;

}

}

2．解：队列为空：count==0

队列为满：count=MAXLEN

队尾第一个元素位置==(front+count)%MAXLEN

队首第一个元素位置==(front+1)%MAXLEN

const MAXLEN=100;

int queue[MAXLEN];

int front,count;

// 定义队头和计数器count

（1）初始化队列

void init()

{

front=1;

count=0;

}

84

（2）判定队空

int QEmpty()

{

if (count==0)

return(1);

else

return(0);}

（3）读队头元素

void ReadFront(int queue[],x)

{

if (count==0)

printf(" 下溢出n");

else

{

front=(front+1)%MAXLEN;

x=queue[front];

}

}

（4）入队操作

void InQueue(int queue[],int x)

{

int place;

if (count==MAXLEN)

printf(" 上溢出n");

else

{

count++;

place=(front+count)%MAXLEN;

queue[MAXLEN]=x;

}

}

（5）出队操作

void OutQueue(int queue[])

// 删除队列头元素

{

if (count==0)

printf(" 队列下溢出n");

else

{

front=(front+1)%MAXLEN;

count--;

}

}

3．

85

（1）解：定义本题队列的结点类型如下：

typedef struct linknode

{

int data;

struct linknode *next;

}qu;

qu *rear;

inqueue(int x)

// 向队列插入结点x

{

qu *head, *s;

s=(qu *) new qu;

// 创建一个新结点

s->data=x;

if (rear==NUlL)

// 若队空,则建立一个循环队列

{

rear＝s;

rear->next＝s;

}

else

// 若不为空，则将s插到后面

{

head=rear->next；

rear->next＝s;

rear=s;

// rear始终指向最后一个结点

rear->next＝head;

}

}

(2)解：

void delqueue(rear)

{

if (rear==NULL)

printf(" 下溢出!n");

else

{

head=rear->next;

// head指向队首结点

if (head==rear)

rear=NULL

// 只有—个结点则直接删除该结点

else

rear->next=head->next

// 否则删除第一个

结点

delete head；

// 释放队首结点

}

}

86