《数据结构与算法》(清华)典型例题

学习必备 欢迎下载

{

r—> next = pb； r=pb；

pb = pb—> next; r—>next= pa； }

else //pa->data = = Pb—>data的情况 {

r=pa； //将原La表结点插入，原Lb表结点删除 pa = pa—> next； s=pb；

pb = pb—>next； free(s)； }

}

if(pa==NULL) //将Lb表剩余结点链到新表 r—>next=pb；

return La； //返回新表头结点地址 }

(例7-27) 设计——个将循环双链表中结点*p与其后继结点交换位置的算法。解析：本题应充分利用双向链表可对前驱结点和后继结点进行操作的特点。

具体算法如下：

int swap(dlinklist * p) {

dlinklist * q；

if(p—>next= = p—>prior) //只有一个数据结点，不能交换 return 0； //交换失败

q=p—>next； //q指向 * p的后继 p—>next=q—>next； //删除 * q q—>next—>prior= p；

q—>prior= p—>prior； //把*q插入*p前 q—>next=p；

p—>prior—>next=q； p—>prior=q；

return 1； //交换成功 }

学习必备 欢迎下载

8.3 典型例题

一、单项选择题

[例8-1] 在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top为栈顶指针，则向栈中压入一个元素时top的变化是( )。

A．top不变 B．top=n C．top=top-1 D．top=top+1 解析：本题答案为：C。

(例8-2) 一个栈的进栈序列是a，b，c，d，e，则不可能的出栈序列是( )。 A．edcba B．decba C。dceab D．abcde

解析：栈的特点是先进后出。在选项C中，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈顶到栈底应该是b、a，不可能a先出栈。本题答案为：C。

[例8-3] 若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若pl＝3，则p2为( )。

A．可能是2 B．不一定是2 C．可能是1 D．一定是1

解析：当p1＝3时，表示3最先出栈，前面l、2应该在栈中。此时若出栈，则p2为2； 此时若进栈，则p2可能为3，4，5，…，n的任何一个。本题答案为：A。

[例 8-4] 若一个栈的输入序列为1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是( )。

A．n—i B．n—i—1 C．i D．n—i+1 解析：本题答案为：D。

(例8-5) 栈和队列的共同点是( )。

A．都是先进后出 B．都是先进先出 C．只允许在表端点处插入和删除元素 D．没有共同点

解析：栈和队列都是操作受限的线性表，只允许在表端点处进行插入和删除操作。本 题答案为：C。

(例8-6) 向一个栈顶指针为top的链栈中插入一个s所指的结点时，操作语句序列为( )。

A．top—>next=top； B．s—>next=top—>next；top—>next=s； C．s—>next＝top；top＝s； D．s—>next=top；top＝top—>next；

解析：向链栈中插入一个结点，就是在不带头结点的单链表的表头插入一个结点。本 题答案为：C。

[例8-7] 在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据进行打印。该缓冲区应该是一个( )结构。

A．栈 B．队列 C．数组 D．线性表 解析：本题答案为：B。

(例8-8) 一个队列的入队序列是1，2，3，4，则队列的输出序列是( )。

A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．4，1，3，2 解析：本题答案为B。

[例8-9] 判断一个循环队列Q为满队列的条件是( )。 A．Q一>front= =Q—>rear B．Q一>front!＝Q—>rear

C．Q一>front= =(Q一>rear+1)％MaxSize D．Q—>front!＝(Q—>rear+1)％MaxSize

解析：由循环队列的结构可知，本题答案为：C。

学习必备 欢迎下载

[例8-10] 循环队列用数组A[0，MaxSize-1]存放其元素，已知其头尾指针分别是front和rear，则当前队列元素个数为( )。

A．(rear—front + MaxSize)％MaxSize B．rear—front+1 C．rear—front—l D．rear—front 解析：本题答案为：A。

(例8-11) 在一个链队列中，假设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；

解析：向链队列插入一个结点即在单链表表尾插入一个结点。本题答案为：B。 二、判断题

[例8-12] 栈是一种先进先出的线性结构。

解析：错误。栈是一种先进后出的线性结构。 [例8-13] 栈和队列都是线性表。

解析：正确。栈和队列都是操作受限的线性表。

[例8-14] 即使对不含相同元素的同一输入序列进行两组不同的但合法的人栈和出栈组合操作，所得的输出序列也一定相同。

解析：错误。根据栈的特性，不同的人栈和出栈组合操作所得的输出序列是不相同的。 [例8-15] 循环队列也存在空间溢出问题。

解析：正确。循环队列的引入只是解决了一般顺序队列的假溢问题，并没有解决溢出 问题。

[例8-16] 循环队列通常用指针来实现队列的头尾相接。

解析：错误。循环队列的首尾相接是假想的，事实上并没有实质上的相接，只是在指针时实现了从最大下标向最小下标的过渡。 三、填空题

[例8-17] 栈的特点是 ，队列的特点是 ，栈和队列都是 。 解析：本题答案为：先进后出／FILO(或后进先出／LIFO)；先进先出／FIFO；操作受限的线性表。

[例8-18] 一个栈的输入序列是：l，2，3，则不可能的栈输出序列是 。 解析：在栈的操作中，如果输入序列按递增排序号，则在输出序列中，某一个元素后 所有比它序号小的元素序号肯定是逆序的。本题答案为：3，1，2。 [例8-19] 队列是限制了插入操作只能在表的一端，而删除操作只能在表的另一端进行的线性表，其特点是 。

解析：本题答案为：先进先出。

(例8-20) 若用不带头结点的单链表来表示链栈s，则创建一个空栈所要执行的操作是 。

解析：由链栈的运算过程可知，本题答案为：s＝NULL。

(例8-21) 在链队列Q中，判定其只有一个结点的条件是 。 解析：只有一个结点时，队头指针和队尾指针都指向链表头结点。 本题答案为：Q—>front＝＝Q—>rear。 四、应用题

[例8-22] 为什么说栈是一种先进后出表?

解析：栈是一种线性表，如果把所有元素都放人栈中再出栈，则最后插入栈中的那个元素总是最先从栈中移出，因此说栈是一种先进后出表。

学习必备 欢迎下载

(例8-23) 对于一个栈，按顺序输入A，B，C。如果不限制出栈时机(即栈中元素不必等所有输入元素都进栈再输出)，试给出全部可能的输出序列。 解析：本题利用栈的后进先出的特点，有如下几种情况：

(1)A进，A出，B进，B出，C进，C出，产生输出序列ABC。 (2)A进，A出，B进，C进，B出，C出，产生输出序列ACB。 (3)A进，B进，B出，A出，C进，C出，产生输出序列BAC。 (4)A进，B进，C进，C出，B出，A出，产生输出序列CBA。 (5)A进，B进，B出，C进，C出，A出，产生输出序列BCA。 不可能产生的序列为：CAB。

(例8-24) 有一字符串次序为-3 * y - a/y^2，试利用栈将该字符串次序改为3y-ay^2/ * -，写出操作步骤。(可用X代表扫描该字符串并顺序取一字符进栈的操作，用S代表从栈中取出一字符加到新字符串尾的出栈操作)

解析：实现上述转换的进、出栈操作如下：

-进 3进 3出 *进 y进 y出 -进 -出 a进

a出 ／进 y进 y出 ^进 ^出 2进 2出 /出 *出 -出

所以操作步骤为：XXSXXSXSXSXXSXSXSSSS。

(例8-25) 什么是顺序队列的上溢现象?什么是假溢现象?解决假溢现象的方法有哪些? 解析：在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队的容量为 MaxSize。当有元素加入队列时，若rear＝＝MaxSize-1(初始时rear＝＝-1)，则发生队列的上溢现象，该元素不能加入队列。

队列的假溢现象是指队列中尚有空余空间，但此时rear＝＝MaxSize-1，元素不能入队。解决队列假溢的方法如下：

(1)建立一个足够大的存储空间，但这样做会造成空间浪费。 (2)采用循环队列方式。原理参照8.2.5中的介绍。

(3)采用平移元素的方法，即每当队列中删除一个元素肘，依次移动队中元素，始终使front＝＝—1。

(例8-26) 假设Q[0．．11]是一个循环队列，初始状态为front＝＝rear＝0，画出做完下列操作后队列的头、尾指针的状态变化情况。若不能人队，请指出其元素，并说明理由。 d，e，b，g，h入队 d，e出队

i，j，k，l，m人队 b出队

n，o，p，q人队

解析：本题入队和出队的变化如图8.7所示。队列没有产生上溢。