数据结构第三章知识题.docx
《数据结构第三章知识题.docx》由会员分享，可在线阅读，更多相关《数据结构第三章知识题.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构第三章知识题
数据结构第三章习题
3．1单项选择题
2.一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是。
A.edcbaB.DecbaC.DceabD.abcde
3.若已知一个栈的入栈序列是1，2，3，………..n,其输出序列为p1,p2,p3,……,pn,若p1=n,则pi为。
A.i.B.n=IC.n-i+1D.不确定
4．栈结构通常采用的两种存储结构是。
A.顺序存储结构和链表存储结构B.散链方式和索引方式
C.链表存储结构和数组D.线性存储结构和非线性存储结构
5．判定一个栈ST（最多元素为m0）为空的条件是。
A.ST->top<>0B.ST->top=0
C.ST->top<>m0D.ST->top=m0
6．判定一个栈ST（最多元素为m0）为栈满的条件是。
A.ST->top!
=0B.ST->top==0
C.ST->top!
=m0D.ST->top==m0
7.栈的特点是，队列的特点是。
A先进先出B.先进后出
8.一个队列的入栈序列是1，2，3，4，则队列的输出序列是。
A.4,3,2,1B.1,2,3,4
C.1,4,3,2D.3,2,4,1
9.判定一个队列QU（最多元素为m0）为空的条件是。
A.QU->rear-QU->front==m0
B.QU->rear-QU->front-1==m0
C.QU->front==QU->rear
D.QU->front==QU->rear+1
10.判定一个队列QU（最多元素为m0）为满队列的条件是。
A.QU->rear-QU->front==m0
B.QU->rear-QU->front-1==m0
C.QU->front==QU->rear
D.QU->front==QU->rear+1
11.判定一个循环队列QU（最多元素为m0）为空的条件是。
A.QU->front==（QU->rear+1）%m0
B.QU->front！
=（QU->rear+1）%m0
C.QU->front==QU->rear
D.QU->front！
=QU->rear
12.判定一个循环队列QU（最多元素为m0）为满队列的条件是。
A.QU->front==（QU->rear+1）%m0
B.QU->front！
=（QU->rear+1）%m0
C.QU->front==QU->rear
D.QU->front！
=QU->rear+1
12.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。
HS->next=s;
A.s->next=HS->next;HS->next=s;
B.s->next=HS;HS=s;
C.s->next=HS;HS=HS->next;
13.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。
Ax=HS;HS=HS->next;
B.x=HS->data;
C.HS=HS->next;x=HS->data;
D.x=HS->data;HS=HS->next;
14.在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时。
A.f->next=s;f=s;
B.r->next=s;r=s;
C.s->next=r;r=s;
D.s->next=f;f=s;
15.在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时。
A.r=f->next;
B.r=r->next;
C.f=f->next;
D.f=r-next;
3．2填空题
4．向栈中压入元素的操作是
5．对栈进行退栈的操作是
6．在一个循环队列中，队首指针指向队首元素的
7．从循环队列中删除一个元素时，其操作是
8．在具有个单元的循环队列中，队满时共有个元素
9.在栈顶指针为HS的链栈中，判定栈空的条件是。
10.在栈顶指针为HS的链栈中，计算该链站中结点个数的函数时。
11.在HQ的链队中，判定只有一个结点的条件是。
12.在HQ的链队中，计算该链队中结点个数的函数是。
3.3顺序栈习题解析
1.对于一个栈，给出输入项A,B,C.如果输入项序列由A,B,C所组成，是给出全部可能的输出序列。
解：
本题利用栈的“后进先出”的特点，有如下几种情况：
A进A出B进B出C进C出产生输出序列ABC
A进A出B进C进C出B出产生输出序列ACB
A进B进B出A出C进C出产生输出序列BAC
A进B进B出C进C出A出产生输出序列BCA
A进B进C进C出B出A出产生输出序列CBA
不可能产生的输出序列CAB
2.有两个栈s1和s2共享存储空间c[1,m],其中一个栈底设在c[1]处，另一个栈底设在c[m0]处，分别编写s1和s2的进栈push（i,x）、退栈pop（i）和设置栈空setnull（i）的函数，其中i=1,2。
注意：
仅当整个空间c[1,m0]占满时才产生上溢。
解：
该共享栈的结构如图2.3所示，两栈的最多元素个数为m0,top1是栈1的栈指针，
top2是栈2的栈指针，当top2=top1+1时出现上溢出，当top1=0时栈1出现下溢出，当top2=m0+1时栈2出现下溢出。
根据上述原理得到如下
函数：
top1top2
c的元素序号12……..n……..m0-1m0
a1
a2
……
an
……….
bm
………
b2
b1
栈1底栈1顶栈2顶栈2底
图2.3共享栈
/*top1,top2和m0均为已赋初值的int型全局变量*/
voidpush（x,i）
intx,I
{
if（top1==top2-1）printf（“上溢出！
\n”）;
else
if（i==1）/*对第一个栈进行入栈操作*/
{
top1++;c[top1]=x;
}
else/*对第二个栈进行入栈操作*/
{
top2--;c[top2]=x;
}
}
/*函数pop*/
voidpop（i）
inti;
{
if（i==1）/*对第一个栈进行出栈操作*/
if（top1==0）printf（“栈1下溢出！
\n”）;
else
{
pop=c[top1];top1--;
}
else/*对第二个栈进行出栈操作*/
if（top2==m0+1）printf（“栈2下溢出！
\n”）;
else
{
pop=c[top2];top2++;
}
}
/*函数setnull*/
setnull（i）
inti;
{
if（i==1）top1=0;
elsetop2=m0+1;
}
4.证明：
有可能从初始输入序列1，2，…….n,利用一个栈得到输出序列p1,p2,…..,pn（p1,p2……pn是1，2，…..n的一种排列）的充分必要条件是：
不存在这样的i,j,k,满足i证明：
【充分条件】如果不存在这样的i,j,k满足i…，pj…pk，…pi，…，（pj不存在这样的输出序列：
…，pi…pj，…pk，…，
（或简单地对于输入序列1，2，3不存在输出序列3，1，2）
从中看到，pi 后进先出，是满足栈的特点，因为pi最大也就是在pj和pk之后进入，却在输出序列中排在pj和pk之前，同时也说明,在pk之前先进入的pj不可能在pk之后出来，反过来说明满足先进后出的特点，所以构成一个栈。
【必要条件】如果初始输入序列是1，2，…，n,假设是进栈，又同时存在i,j,k
满足i…，pj…pk，…pi，…，（pj存在这样的输出序列：
…，pi…pj，…pk，…，
从中看到，pi 先进后出，是满足栈的特点，因为pi最大也就是在pj和pk之后进入，同时看到在pk之前先进入的pj却在pk之前出来，反过来说明不满足先进后出的特点，与前面的假设是栈不一致，本题即证。
6.已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C，并要求表示集合C的链表的结点仍依元素值递增有序存放。
解：
假设HA和HB的头指针分别为ha和hb，先设置一个空的循环单链表HC，头指针为hc，之后依次比较HA和HB的当前结点的元素值，将较小元素值的结点复制一个并链接到HC的末尾，若相等，则将其中之一复制一个并链接到HC的末尾。
当HA或HB为空后，把另一个链表的余下结点都复制并链接到HC的末尾。
实现本题功能的函数如下：
voidunion（ha,hb,hc）
node*ha,*hb,*hc;
{
node*p,*q,*r,*s;
hc={node*}malloc（sizeof（node））;
/*建立一个头结点，r总是指向HC链表的最后一个结点*/
r=hc;p=ha;q=hb;
while（p!
=NULL&&q!
=NULL）
{
if（p->datadata）
{
s=（node*）malloc（sizeof（node））;
s->data=p->data;
r->next=s;
r=s;
p=p->next;
}
elseif（p->data>q->data）
{
s=（node*）malloc（sizeof（node））;
s->data=q->data;
r->next=s;
r=s;
q=q->next;
}
else/*p->data==q->data的情况/
{
s={node*}malloc（sizeof（node））;
q=q->next;
}
}
if（p==NULL）/*把q及之后的结点复制到HC中*/
while（q!
=NULL）
{
s=（node*）malloc（sizeof（node））;
s->data=p->data;
r->next=s;
r=s;
p=p->next;
}
r->next=NULL;
s=hc;
hc=hc->next;
free（s）;/*删除头结点*/
}
15.假设在长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某个结点的指针，编写一个函数删除该结点的前驱结点。
解：
本题利用循环单链表的特点，通过p指针可循环找到其前驱结点q及q的前驱结点r,然后将其删除。
实现本题功能的函数如下：
node*del（p）
node*p;
{
node*q,*r;
q=p;/*查找p结点的前驱结点，用q指针指向*/
while（q->next!
=p）q=q->next;
r=q;/*查找q结点的前驱结点，用r指针指向*/
while（r->next!
=q）r=r->next;
r->next=p;/*删除q所指的结点*/
free（q）;
return（p）;
}
升级会员 