数据结构第三章习题(8页).doc

-数据结构第三章习题31 单项选择题2.一个栈的入栈序列a, b, c, d, e, 则栈的不可能的输出序列是 。A. edcbaB. DecbaC. DceabD. abcde3. 若已知一个栈的入栈序列是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=0C.ST->top<>m0D.ST->top=m06判定一个栈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->front=m0B.QU->rear- QU->front-1=m0C.QU->front= QU->rearD. QU->front= QU->rear+1 10.判定一个队列QU（最多元素为m0）为满队列的条件是 。A.QU->rear- QU->front=m0B.QU->rear- QU->front-1=m0C.QU->front= QU->rearD.QU->front= QU->rear+111. 判定一个循环队列QU(最多元素为m0)为空的条件是 。A. QU->front= （QU->rear+1）%m0B. QU->front！= （QU->rear+1）%m0C.QU->front= QU->rearD.QU->front！= QU->rear 12. 判定一个循环队列QU（最多元素为m0）为满队列的条件是 。A. QU->front= （QU->rear+1）%m0B. QU->front！= （QU->rear+1）%m0C.QU->front= QU->rearD.QU->front！= QU->rear+112. 向一个栈顶指针为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保存被删结点的值，则执行 。A x=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;32 填空题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出 产生输出序列ABCA进A出B进C进C出B出 产生输出序列ACBA进B进B出 A出 C进C出 产生输出序列BACA进B进B出C进C出A出 产生输出序列BCAA进B进C进C出B出 A出 产生输出序列CBA不可能产生的输出序列CAB2.有两个栈s1和s2共享存储空间c1,m, 其中一个栈底设在c1处， 另一个栈底设在cm0处， 分别编写s1和s2的进栈push( i,x)、退栈pop(i)和设置栈空setnull(i)的函数，其中i=1,2。 注意：仅当整个空间c1,m0占满时才产生上溢。解：该共享栈的结构如图2.3所示， 两栈的最多元素个数为m0, top1是栈1的栈指针，top2 是栈2的栈指针， 当top2=top1+1时出现上溢出， 当top1=0时栈1出现下溢出， 当top2=m0+1时栈2出现下溢出。根据上述原理得到如下函数： top1 top2c的元素序号1 2 . n . m0-1 m0a1a2a n.bm b2b1 栈1底 栈1顶 栈2顶 栈2底 图2.3 共享栈/*top1,top2 和m0均为已赋初值的int型全局变量*/void push(x,i)int x,I if (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(top1=0)printf(“栈1下溢出！n”);elsepop=ctop1; top1-;else /*对第二个栈进行出栈操作*/if (top2=m0+1) printf(“栈2下溢出！n”);elsepop=ctop2;top2+; /*函数setnull*/setnull(i)int i ;if(i =1 )top1=0;else top2=m0+1; 4.证明：有可能从初始输入序列1，2，.n, 利用一个栈得到输出序列p1,p2,.,pn(p1,p2pn是1，2，.n 的一种排列)的充分必要条件是：不存在这样的i , j, k, 满足 i <j<k同时 pj<pk<pi. 证明：【充分条件】如果不存在这样的i ,j,k 满足 i<j<k同时pj<pk<pi, 即对于输入序列： ，pj pk，pi， (pj<pk<pi)不存在这样的输出序列：，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<j<k同时pj<pk<pi，即对于输入序列：，pj pk，pi， (pj<pk<pi)存在这样的输出序列：，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的末尾。实现本题功能的函数如下： void union(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->data<q->data) s=(node*)malloc(sizeof(node);s->data=p->data;r->next=s;r=s;p=p->next;else if (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);-第 8 页-