一个队列的入列序号是1、2、3、4,则队列的输出系列是______。A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、1
一个队列的入列序号是1、2、3、4,则队列的输出系列是______。
A.4、3、2、1
B.1、2、3、4
C.1、4、3、2
D.3、2、4、1
一个队列的入列序号是1、2、3、4,则队列的输出系列是______。
A.4、3、2、1
B.1、2、3、4
C.1、4、3、2
D.3、2、4、1
A.6
B.5
C.3
D.2
一个队列的入列序号是1,2,3,4,则队列的输出系列是______。
A.4,3,2,1
B.1,2,3,4
C.1,4,3,2
D.3,2,4,1
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。
[说明]
链式存储的队列称为链队。根据队列的FIFO原则,为了操作上的方便,可以使用带头指针front和尾指针rear的单链表来实现链队。若链队元素的数据类型为datatype,则链队结构描述如下:
typedef struct node
{ datatypedata;
structnode *next;
} QNode; /*链队结点的类型*/
typedef struct
{ QNnode *front,*rear;
} LQueue; /*将头尾指针封装在一起的链队*/
以下这种链队的几个例子:
设q是一个指向链队的指针,即LQueue *q。下面各函数的功能说明如下:
(1) LQueue *Init_LQueue():创建并返回一个带头尾结点的空链队;
(2) intEmpty_LQueue(LQueue *q):判断链队q是否空;
(3) void In_LQueue(LQueue *q, datatypex):将数据x压入链队q;
(4) int Out_LQueue(LQuere *q, datatype *x):弹出链队q的第一个元素x,若成功则返回返回1否则返回0。
[函数]
LQueae *Init_LQueue()
{ LQueue *q, *p;
q=malloc(sizeof(LQueue)); /*申请链队指针*/
P=malloc(sized(QNode));/*申请头尾指针结点*/
p->next=NULL;
(1)=p;
return q;
}
int Empty_LQueue(LQueue *q)
{ if(q->front (2) q>rear) return 0;
else return 1;
}
void In_LQueue(LQueue *q, datatype x)
{ QNoda *p;
p=malloc(sizeof(QNnode));/*申请新接点*/
p->data=x;
p->next=NULL;
(3)=p;
q->rear=p;
}
int Out_LQueue(LQueue *q, datatype *x)
{ QNnode *p;
if(Empty_LQueue(q)) return 0; /*队空,操作失败*/
else{
p=q->front->next;
*x=(4);
(5)=p->next;
free(p);
if (q->front->next= =NULL)q->rear=q->front;
return 1;
}
}
阅读以下说明和C语言函数,将应填入(n)处的字句写在答题纸的对应栏内。
[说明]
求树的宽度,所谓宽度是指在二叉树的各层上,具有结点数最多的那一层的结点总数。本算法是按层次遍历二叉树,采用一个队列q,让根结点入队列,若有左右子树,则左右子树根结点入队列,如此反复,直到队列为空。
[函数]
int Width (BinTree *T
{
int front=-1, rear=-1; /*队列初始化*/
int flag=0, count=0, p; /*p用于指向树中层的最右边的结点, flag 记录层中结点数的最大值*/
if (T!=Null)
{
rear++;
(1);
flag=1;
p=rear;
}
while ((2))
{
front++;
T=q [front]];
if (T->lchild!=Null )
{
roar+-+;
(3);
count++;
}
if (T->rchild!=Null )
{
rear++; q[rear]=T->rchild;
(4);
}
if (front==p ) // 当前层已遍历完毕
{
if((5))
flag=count;
count=0;
p=rear, //p 指向下一层最右边的结点
}
}
return (flag );
}
阅读下列函数说明和C函数,将应填入(n)处的字句写对应栏内。
[说明]
二叉树的二叉链表存储结构描述如下:
typedef struct BiTNode
{ datatype data;
struct BiTNode *lchild, * rchild; /*左右孩子指针*/
}BiTNode,* BiTree;
对二叉树进行层次遍历时,可设置一个队列结构,遍历从二叉树的根结点开始,首先将根结点指针入队列,然后从队首取出一个元素,执行下面两个操作:
(1) 访问该元素所指结点;
(2) 若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
此过程不断进行,当队列为空时,二叉树的层次遍历结束。
下面的函数实现了这一遍历算法,其中Visit(datatype a)函数实现了对结点数据域的访问,数组queue[MAXNODE]用以实现队列的功能,变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。
[函数]
void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/
{ BiTree Queue[MAXNODE];
int front,rear;
if(bt= =NULL)return;
front=-1;
rear=0;
queue[rear]=(1);
while(front (2) ){
(3);
Visit(queue[front]->data); /*访问队首结点的数据域*/
if(queue[front]—>lchild!:NULL)
{ rear++;
queue[rear]=(4);
}
if(queue[front]->rchild! =NULL)
{ rear++;
queue[rear]=(5);
}
}
}
A、1
B、2
C、3
D、4
栈和队列都是(2)。若进栈序列为1,2,3,4,则(3) 不可能是一个出栈序列。若进队列的序列为1,2,3,4,则(4)是一个进队列序列。
A.顺序存储的线性结构
B.链式存储的线性结构
C.限制存取点的线性结构
D.限制存取点的非线性结构