数据结构习题及答案(3)

head->next=p; p->next=s; }

else /*p不指向头结点*/ { r=head; /*定位p所指向结点的前驱*/ while (r->next != p) r=r->next; r->next=q; /*交换p和q所指向的结点*/ p->next=q->next; q->next=p; } return(head); } else /*p不存在后继*/ return(NULL); }/*swapin_list*/

有一个带头结点的单链表，所有元素值以非递减有序排列，head为其头指针，编写算法deldy．list（）将linklist *deldy_list(linklist *head) { /*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/ linklist *q; if (head->next!= NULL)/*判断链表是否为空*/ { p=head->next; while (p->next != NULL )

6．

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

该链表中多余元素值相同的结点删除。

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

linklist *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); q=q->next; }

} /*dellist_maxmin*/

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

将双链表逆置的算法invert_dblinklist的算法如下所示：

void invert_dblinklist( *head ) { /*将head指向的双链表逆置*/ dblinklist *p, *q; p=head; do { q=p->next; p->next=p->prior; p->prior=q; p=q; }while( p!=head )

} /*invert_dblinklist*/

linklist

习题三 一、选择题

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．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲

区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ 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是可能的（填是否可能）。 20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构习题及答案(3)在线全文阅读。