数据结构第三章习题0001

1、数据结构第三章习题欢迎下载83. 1单项选择题2. 个栈的入栈序列A. edcbaB. Decba3. 若已知一个栈的入栈序列是1,2, 3,若p1= n,贝卩pi为。A.i.B. n=l4. 栈结构通常采用的两种存储结构是A. 顺序存储结构和链表存储结构C.链表存储结构和数组a, b, c, d, e,则栈的不可能的输出序列是C. DceabD. abcde.n,其输出序列为p1, p2, p3,C. n- i+1D.不确定B. 散链方式和索引方式D.线性存储结构和非线性存储结构,pn,5. 判定一个栈ST （最多元素为 m0）为空的条件是B. ST->top=0 D.ST->t

2、op=mOA. ST->top<>0C. ST->topv>mO6. 判定一个栈ST （最多元素为m0）为栈满的条件是A. ST->top!=0B.ST->top=0C.ST->top!=m0D.ST->top=m07. 栈的特点是队列的特点是。A先进先出B.先进后出8. 一个队列的入栈序列是1, 2, 3, 4,则队列的输出序列是 A. 4,3,2,1B.1,2,3,4C. 1,4,3,2D.3,2,4,19. 判定一个队列QU（最多元素为m0）为空的条件是。A. QU->rear- QU->fro nt=m0B. QU-&g

3、t;rear- QU->fro nt-1=m0C. QU->fro nt= QU->rearD. QU->fro nt= QU->rea 叶110. 判定一个队列QU (最多元素为m0)为满队列的条件是A. QU->rear- QU->fro nt=m0B. QU->rear- QU->fro nt-1=m0C. QU->fro nt= QU->rearD. QU->fro nt= QU->rea 叶111. 判定一个循环队列QU(最多元素为m0)为空的条件是A. QU->front=(QU->rea叶1

4、) %m0B. QU->front! =(QU->rear+1) %m0C. QU->fro nt= QU->rearD. QU->front ! = QU->rear12. 判定一个循环队列QU (最多元素为m0)为满队列的条件是A. QU->front=(QU->rea叶1) %m0B. QU->front! =(QU->rear+1) %m0C. QU->fro nt= QU->rearD. QU->front ! = QU->rea叶112. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行 。

5、HS->n ext=s;A. s->n ext=HS->n ext; HS->n ext=s;B. s->n ext=HS; HS=s;C. s->n ext=HS; HS=HS->n ext;13. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值， 则执行 。A x=HS; HS=HS->n ext;B. x=HS->data;C. HS=HS->n ext; x=HS->data;D. x=HS->data; HS=HS->n ext;14. 在一个链队中，假设f和r分别为队首和队尾指针，则插入

6、 s所指结点的运 算时 。A. f->n ext=s; f=s;B. r->n ext=s;r=s;C. s->n ext=r; r=s;D. s->n ext=f; f=s;15. 在一个链队中，假设f和r分别为队首和队尾指针，贝U删除一个结点的运算 时 。A. r=f->n ext;B. r=r- >n ext;C. f=f->n ext;D. f=r-n ext;3. 2填空题4. 向栈中压入元素的操作是5. 对栈进行退栈的操作是6. 在一个循环队列中，队首指针指向队首元素的 7. 从循环队列中删除一个元素时，其操作是 8. 在具有个单元的循环队

7、列中，队满时共有个元素9. 在栈顶指针为HS的链栈中，判定栈空的条件是。10. 在栈顶指针为HS的链栈中，计算该链站中结点个数的函数时 。11. 在HQ的链队中，判定只有一个结点的条件是 。12. 在HQ的链队中，计算该链队中结点个数的函数是.3.3 顺序栈习题解析1.对于一个栈，给出输入项A,B,C.如果输入项序列由A,B,C所组成，是给出有如下几种情况： 产生输出序列ABC 产生输出序列ACB产生输出序列BAC 产生输出序列BCA 产生输出序列CBA全部可能的输出序列。解：本题利用栈的“后进先出”的特点,A进A出B进B出C进C出A进A出B进C进C出B出A进B进B出A出C进C出A进B进B出C

8、进C出A出A进B进C进C出B出A出不可能产生的输出序列 CAB2.有两个栈si和s2共享存储空间c1,m,其中一个栈底设在c1处，另一个栈 底设在cm0处，分别编写si和s2的进栈push( i,x)、退栈pop(i)和设置栈空 setnull(i)的函数，其中i=1,2。注意：仅当整个空间c1,m0占满时才产生上溢。 解：该共享栈的结构如图2.3所示，两栈的最多元素个数为 mO, top1是栈1的 栈指针，top2是栈2的栈指针，当top2=top1+1时出现上溢出，当top1=0时栈1出现下溢出， 当top2=m0+1时栈2出现下溢出。根据上述原理得到如下函数：top1top2a1a2a

9、nbmb2b1c的元素序号12. nm0-1 m0Jk栈1底栈1顶栈2顶图2.3共享栈/*top1,top2和m0均为已赋初值的int型全局变量*/void push(x,i)int x,Iif (top1=top2-1) printf(上溢出！ n” );elseif（i=1）/*对第一个栈进行入栈操作*/top1+; ctop1=x;else /*对第二个栈进行入栈操作*/ top2-; ctop2=x;/* 函数 pop*/void pop(i)int i ;if (i =1 ”*对第一个栈进行出栈操作*/if(top 1=0)printf(栈 1 下溢出！ n”)；elsepop=ct

10、op1; topi-;else/*对第二个栈进行出栈操作*/if (top2=m0+1) printf(栈 2 下溢出！ n”);elsepop二ctop2;top2+;/* 函数 set null*/set null(i)int i ;if(i =1 )top1=0;else top2=m0+1;4证明：有可能从初始输入序列1, 2,.n,利用一个栈得到输 出序列p1,p2,.,pn(p1,p2 是n1，2，.n的一种排列)的充 分必要条件是：不存在这样的i , j, k,满足i vjvk同时pjvpkvpi.证明：【充分条件】如果不存在这样的i ,j,k 满足ivjvk同时pjvpkvpi

11、,即对于输入序列：，pj pk，pi，, (pjvpkvpi)不存在这样的输出序列：,pipj ,pk,(或简单地对于输入序列1, 2 , 3不存在输出序列3 , 1, 2) 从中看到，pi后进先出，是满足栈的特点， 因为pi最大也就 是在pj和pk之后进入，却在输出序列中排在 pj和pk之前，同 时也说明，在pk之前先进入的pj不可能在pk之后出来，反过来 说明满足先进后出的特点，所以构成一个栈。【必要条件】如果初始输入序列是1, 2,，n,假设是进栈， 又同时存在i ,j,k满足ivjvk同时pjvpkvpi，即对于输入序列：，pj pk，pi， (pjvpkvpi)存在这样的输出序列：，

12、pipj，pk，从中看到，pi先进后出，是满足栈的特点，因为pi最大也就是在pj和pk之后进入，同时看到在pk之前先进入的pj 却在pk之前出来，反过来说明不满足先进后出的特点，与前 面的假设是栈不一致，本题即证。6已知两个整数集合 A和B，它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C，并要求表示集合 C的链表的结点仍依元素值递增有序存放。解：假设HA和HB的头指针分别为ha和hb，先设置一个空的循环单链表HC，头指针为he，之后依次比较HA和HB的当前结点的元素值，将较小元素值的结点复制一个并链接到HC的末尾，若相等，则将其中之一复制一个并链

13、接到HC的末尾。当HA或HB为空后，把另一个链表的余下结点都复制并链接到HC的末尾。实现本题功能的函数如下：void union( ha,hb,hc)node *ha,*hb,*hc;node *p,*q,*r,*s;hc= node *malloc(sizeof( no de);/*建立一个头结点，r总是指向HC链表的最后一个结点*/r=hc;p=ha;q=hb;while(p!=NULL&&q!=NULL)if (p_>data<q_>data)s=(no de*)malloc(sizeof( no de);s->data=p->data;r-

14、>n ext=s;r=s;p=p->n ext;else if (p->data>q->data)s=(no de*)malloc(sizeof( no de);s->data=q->data;r->n ext=s;r=s;q=q_>n ext;else /*p->data=q->data 的情况 /s= no de*malloc(sizeof( no de);q=q_>n ext;if(p=NULL)/* 把q及之后的结点复制到HC中*/while (q!=NULL)s=(no de*)malloc(sizeof( no de);s->data=p->data;r->n ext=s;r=s;p=p->n ext;r->n ext=NULL;s=hc;hc=hc- >n ext;free(s);/*删除头结点*/p为指向该链表中某个结15假设在长度大于1的循环单链表中，既无头结点也无头指针， 点的指针， 编写一个函数删除该结点的前驱结点。q及q的前驱结点r,解：本题利用循环单链表的特点，通过p