头元素是（ 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 Λ D．s->next=top；top=s；
（16）带头结点的链队列LQ示意图如下，链队列的队头元素是（ A ）
LQ->rear A．A B．B C．C D．D
（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 21 C D Λ LQ->rear
A．始终不改变 B．有时改变 C．进队时改变 D．出队时改变 （19）队列Q，经过下列运算后，再执行QEmpty(Q) 的值是（ C ）。 InitQueue(Q) 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
(
初
始
化
队
列
);InQueue(Q,a);
InQueue(Q,b);OutQueue(Q,x);
四． 写出程序运行的结果
写出下列程序段的输出结果（队列中的元素类型为char）。 void main( ) {
Queue Q; InitQueue (Q); // 初始化队列 char x=\InQueue (Q, \InQueue (Q, \InQueue (Q, y);
OutQueue (Q,x); InQueue (Q,x); OutQueue (Q,x); InQueue (Q, \while (!QEmpty(Q)) {
OutQueue (Q,y); printf(y);
};
printf(x); }
答：输出为“CHAR”。
五．程序填空
假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。
typedef struct queuenode // 定义队列的存储结构 { int data;
struct queuenode *next; }QueueNode;
InQueue(QueueNode *rear,int x) // 向队列插入元素为x的函数 { QueueNode *rear; QueueNode *head,*s;
22
s= new QueueNode ; 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，试写出相应的入队算法和出队算法。 解：
//入队算法：
void inqueqe(int x) { int temp;
if (count==n)
printf(\队列上溢出\\n\else
{ count++
temp=(front+count)%n; Queue[temp]=x }
} //出队算法：
int outqueue() { int temp;
if(count==0)
printf(\队列下溢出\\n\else
{ temp=Queue[front]; front=(front+1)%n; count--; return temp; }
}
（2）用一个循环数组Q[0..MAXLEN-1]表示队列时，该队列只有一个头指针front，不设尾指针，而改置一个记数器count用以记录队列中结点的个数。试编写一个能实现：初始化队列、判队空、读队头元素、入队操作和出队操作的算法。
解：//用一个循环数组Queue[0，n-1]表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。
//队列为空：count==0
//队列为满：count=MAXLEN
//队尾第一个元素位置==(front+count)%MAXLEN //队首第一个元素位置==(front+1)%MAXLEN const MAXLEN=100; int queue[MAXLEN];
int front,count; // 定义队头和计数器count
23
①初始化队列
void init() {
front=1; count=0; }
②判定队空
int QEmpty() {
if (count==0)
return(1);
else
return(0);}
③读队头元素
void ReadFront(int queue[],x)
{
if (count==0)
printf(\下溢出\\n\
else {
front=(front+1)%MAXLEN; x=queue[front];
} } ④入队操作
void InQueue(int queue[],int x) {
int place;
if (count==MAXLEN)
printf(\上溢出\\n\
else {
count++;
place=(front+count)%MAXLEN; queue[MAXLEN]=x;
} } ⑤出队操作
void OutQueue(int queue[]) // 删除队列头元素 {
if (count==0)
printf(\队列下溢出\\n\
else {
front=(front+1)%MAXLEN; count--;
} }
（3）一个用单链表组成的循环队列，只设一个尾指针rear，不设头指针，请编写他如下算法：
①向循环队列中插入一个元素为x的结点； ②从循环队列中删除一个结点。 ①解：//定义本题队列的结点类型如下：
typedef struct linknode {
int data;
24