else { q=p->next;/*q指向p的后继*/ p->next=q->next; /*删除q所指向的结点*/ free(q); /*释放结点空间*/ } } /*while*/ } /*if*/ } /*deldy_list*/

7．在带头结点的单链表中，设计算法dellistmaxmin，删除所有数据域大于min，而小于max的元素。

void dellist_maxmin(LinkList head, int min, int max ) { LinkList p, q; q=head; p=head->next; while(p!=NULL) /*结点不空*/ if ((p->data<=min) || (p->data>=max)) /*不满足删除条件*/ { q=p; p=p->next; } else /*满足删除条件*/ { q->next=p->next; free(p); p=q->next; }

} /*dellist_maxmin*/

8．设计一个将双链表逆置的算法invert．dbLinkList（），其中头指针为L，结点数据域为data，两个指针域分别为prior和next。

void invert_dblinklist(DLinkList head )//不带头结点的双向链表 { /*将head指向的双链表逆置*/ DLinkList p, q; p=head; while( p->next ) { q=p->next;. p->next=p->prior; p->prior=q; p=q;

9

} q=p; p->next=p->prior; p->next=NULL; head=q;

} /*invert_dblinklist*/

10

习题三

一、选择题

l．一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。

A．a，b，c，d，e B．d，e，c，b，a C．d，c，e，a，b D．e，d，c，b，a 2．若一个栈的输人序列是1，2，3，?，n，输出序列的第一个元素是n，则第k个输出元素是（ C ）。

A．k B．n-k-1 C．n-k+1 D．不确定 3．判定一个栈S（最多有n个元素）为空的条件是（B ）。

A．S->top！＝0 B．S->top= =0 C．S->top!=n D．S->top= =n 4．判定一个栈S（最多有n个元素）为满的条件是（D）。

A．S->top!=0 B．S->top= =0 C．S->top!=n D．S->top= =n 5．向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（B）。 A．top->next=S； B．S->next=top；top=S；

C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next；

6．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（C）。

A．top->next=S； B．S->next=top；top=S；

C．S->next=top->next；top->next=S； D．S->next=top；top=S->next； 7．判定一个队列Q（最多有n个元素）为空的条件是（ C ）。

A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 8．判定一个队列Q（最多有n个元素）为满的条件是（A）。

A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 9．判定一个循环队列Q（最多有n个元素）为空的条件是（A）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 10．判定一个循环队列Q（最多有n个元素）为满的条件是（ C ）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n

11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ C ）。

A．front＝front->next B．S->next=rear；rear=S C．rear->next=S；rear=S D．S->next=front；front＝S

12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。

A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13．栈与队列都是（ C ）。

A．链式存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 14．若进栈序列为l，2，3，4，则（ C）不可能是一个出栈序列。

A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l 15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲

11

区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。

A．堆栈 B．队列 C．数组 D．线性表

二、填空

1．栈（stack）是限定在__表尾_一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶_，而另一端称为__栈底__。不含元素的栈称为_空栈__。

2．在栈的运算中，栈的插人操作称为__进栈_或__入栈_，栈的删除操作称为__退栈_或__出栈__。

3．根据栈的定义，每一次进栈的元素都在原__栈顶元素_之上，并成为新的__栈顶元素__；每一次出栈的元素总是当前的__栈顶元素_，因此最后进栈的元素总是__最后出栈__，所以栈也称为_后进先出_线性表，简称为__LIFO__表。

4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_顺序_和__链式__两种存储结构，分别称为__顺序栈__和___链栈__。

5．当栈满的时候，再进行人栈操作就会产生___溢出_，这种情况的溢出称为__上溢_；当栈空的时候，如果再进行出栈操作，也会__溢出__，这种情况下的溢出称为__下溢___。

6．栈的链式存储结构简称为__链栈_，是一种___特殊的单链表__。

7．人们日常计算用到的表达式都被称为__中缀表达式__，这是由于这种算术表达式的运算符被置于两个操作数中间。

8．计算机中通常使用__后缀表达式_，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为__逆波兰式__。

9．队列（Queue）也是一种__特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_队尾_，允许删除的一端称为___队头__。

10．队列的特点是_先进先出_，因此队列又被称为___先进先出_．的线性表，或称为__FIFO__表。

11．队列的__顺序存储结构__又称为__数序队列_，是用一组地址连续的存储单元依次存放队列中的元素。

12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向_队头元素__和_队尾元素_，这两个指针又称为_队头指针__和__队尾指针__。

13．循环顺序队列（CircuLar Sequence Queue）经常简称为__循环队列_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的___取模运算__来实现的。

14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为递归函数，也称为__自调用函数___。函数直接调用自己，则称为__直接递归调用_；当一个函数通过另一个函数来调用自己则称为___间接递归调用_。

15．在循环队列中规定：当Q->rear= =Q->front的时候循环队列为__空___， 当（Q->rear+1）％MAXSIZE＝front的时候循环队列为___满____。

16．用链表方式表示的队列称为___链队列___。

17．已知栈的输人序列为1，2，3，?，n，输出序列为a1，a2，?，an，符合a2= =n的输出序列共有___n-1_个_。

18．一个栈的输人序列是12345，则栈的输出序列为43512是__不可能__（填是否可能）。 19．一个栈的输人序列是12345，则栈的输出序列为12345是___可能的_（填是否可能）。

12