数据结构课程课后习题集答案解析 下载本文

A.5 答:C

B.4 C.3 D.2

2. 填空题

(1)栈是一种特殊的线性表,允许插入和删除运算的一端称为( ① )。不允许插入和删除运算的一端称为( ② )。

答:①栈顶 ②栈底

(2)一个栈的输入序列是12345,的输出序列为12345,其进栈出栈的操作为( )。 答:1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,4进栈,4出栈,5进栈,5出栈。

(3)有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第二个出栈)的次序有( )。

答:CDBAE、CDEBA、CDBEA。

(4)顺序栈用data[0..n-1]存储数据,栈顶指针为top,其初始值为0,则元素x进栈的操作是( )。

答:data[top]=x; top++;

(5)顺序栈用data[0..n-1]存储数据,栈顶指针为top,其初始值为0,则出栈元素x的操作是( )。

答:top--; x=data[top]; (6)( )是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。

答:队列

(7)设有数组A[0..m]作为循环队列的存储空间,front为队头指针(它指向队首元素的前一位置),rear为队尾指针(它指向队尾元素的位置),则元素x执行入队的操作是( )。

答:rear=(rear+1)%(m+1); A[rear]=x;

(8)设有数组A[0..m]作为循环队列的存储空间,front为队头指针(它指向队首元素的前一位置),rear为队尾指针(它指向队尾元素的位置),则元素出队并保存到x中的操作是( )。

答:front=(front+1)%(m+1); x=A[rear];

3. 简答题

(1)简要说明线性表、栈与队的异同点。

答:相同点:都属地线性结构,都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表,只是对插入、删除运算加以限制。

不同点:①运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入、删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。②用途不同,栈用于子程调用和保护现场等,队列用于多道作业处理、指令寄存及其他运算等等。

(2)顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?

数据结构简明教程

答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有进队操作,但其实数组中还有空位置,这就叫“假溢出”。

采用循环队列是解决假溢出的途径。另外,解决循环队列是空还是满的办法如下: ① 设置一个布尔变量以区别队满还是队空;

② 浪费一个元素的空间,用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数(即队列长度)。

通常采用法②,让队头指针front指向队首元素的前一位置,队尾指针rear指向队尾元素的位置,这样判断循环队列队空标志是:front=rear,队满标志是:(rear+1)%MaxSize=front。

4. 算法设计题

(1)假设采用顺序栈存储结构,设计一个算法,利用栈的基本运算返回指定栈中栈底元素,要求仍保持栈中元素不变。这里只能使用栈st的基本运算来完成,不能直接用st.data[0]来得到栈底元素。

解:假定采用顺序栈结构。先退栈st中所有元素,利用一个临时栈tmpst存放从st栈中退栈的元素,最后的一个元素即为所求,然后将临时栈tmpst中的元素逐一出栈并进栈到st中,这样恢复st栈中原来的元素。对应算法如下:

int GetBottom(SqStack st,ElemType &x) { }

ElemType e; SqStack tmpst;

//定义临时栈 //空栈返回0

InitStack(tmpst); if (StackEmpty(st)) { }

while (!StackEmpty(tmpst)) { } return 1;

//返回1表示成功

Pop(tmpst,e); Push(st,e);

//恢复st栈中原来的内容

return 0;

//临时栈tmpst中包含st栈中逆转元素

Pop(st,x); Push(tmpst,x);

//初始化临时栈

while (!StackEmpty(st))

(2)设计一个算法,采用一个顺序栈逆向输出单链表L中所有元素。

解:本题并不需要改变单链表L的结构。设置一个顺序栈st,先遍历单链表并将所有元素进栈,然后栈不空循环并输出栈中所有元素。对应算法如下:

void ReverseDisp(SLink *L) {

ElemType x; struct node {

ElemType data[MaxSize]; int top;

//定义一个顺序栈

} st;

}

st.top=-1; SLink *p=L->next; while (p!=NULL) { }

while (st.top!=-1) { }

printf(\

x=st.data[st.top]; st.top--; printf(\

//栈不空循环,输出栈中所有元素

st.top++;

st.data[st.top]=p->data; p=p->next;

//遍历单链表,将所有元素进栈

(3)设计一个循环队列,用front和rear分别作为队头和队尾指针,另外用一个标志tag标识队列可能空(0)或可能满(1),这样加上front==rear可以作为队空或队满的条件。要求设计队列的相关基本运算算法。

解:设计的队列的类型如下:

typedef struct {

ElemType data[MaxSize]; int front,rear; int tag;

//队头和队尾指针

//为0表示队空,为1时表示不空

} QueueType;

初始时tag=0,进行成功的插入操作后tag=1,进行成功的删除操作后tag=0;因为只有在插入操作后队列才有可能满,只有在删除操作后队列才有可能空,因此,这样的队列的基本要素如下:

初始时:tag=0,front=rear

队空条件:qu.front==qu.rear && qu.tag==0 队满条件:qu.front==qu.rear && qu.tag==1 对应的算法如下:

//-----初始化队列算法----- void InitQueue1(QueueType &qu) { }

//-----判队空算法-----

int QueueEmpty1(QueueType qu) {

return(qu.front==qu.rear && qu.tag==0); qu.front=qu.rear=0; qu.tag=0;

//为0表示队空可能为空

数据结构简明教程

}

//-----判队满算法----- int QueueFull1(QueueType qu) { }

//-----进队算法-----

int enQueue1(QueueType &qu,ElemType x) { }

//-----出队算法-----

int deQueue1(QueueType &qu,ElemType &x)//出队 { }

if (QueueEmpty1(qu)==1) //队空

return 0;

qu.front=(qu.front+1)%MaxSize; x=qu.data[qu.front]; qu.tag=0; return 1;

//出队一个元素,可能空

if (QueueFull1(qu)==1) //队满

return 0;

qu.rear=(qu.rear+1)%MaxSize; qu.data[qu.rear]=x; qu.tag=1; return 1;

//至少有一个元素,可能满

return(qu.tag==1 && qu.front==qu.rear);

(4)假设用一个循环单链表表示队列,并且只设一个指针rear指向队尾结点,但不设

头指针,设计出相应的队初始化、进队、出队和判队空的算法。

解:假设链队是不带头结点的循环单链表,其示意图如图3.1所示。队空条件:rear==NULL;进队操作:在*rear结点之后插入结点并让rear指向该结点;出队操作:删除*rear结点之后的一个结点。对应的算法如下:

队首 a1 a2 … rear an 队尾 图3.1 不带头结点的循环单链表表示队列

typedef struct node {

ElemType data; struct node *next;

//链队结点类型

} QNode;

//-----初始化队列----- void InitQueue(QNode *&rear) {