实用数据结构基础参考答案 下载本文

头元素是( 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