数据结构第三章习题答案

数据结构第三章习题答案

【篇一：数据结构(c语言版)第三章习题解答】

分别写出对链栈的入栈和出栈操作的算法。 链栈的结点类型定义如下： typedef struct stacknode { selemtype data;

struct stacknode *next; }stacknode, *linkstack; 入栈操作：

status push( linkstack s, selemtype e)

{ p=(linkstack)malloc(sizeof(stacknode)); if (!p) return error; p-data=e; p-next=s; s=p;

return ok; }

出栈操作：

status pop(linkstack s, selemtype e) { if (!s) return error; p=s;

s=p-next; free(p); return ok; }

p24/3.15

假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws),入栈

push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点。 双栈的结构类型定义如下： typedef struct{

elemtype *base[2]; elemtype *top[2];

}bdstacktype; //双向栈类型 栈的初始化操作：

status init_stack(bdstacktype tws,int m) //初始化一个大小为m的双向栈tws

{ tws.base[0]=(elemtype*)malloc(m*sizeof(elemtype)); tws.base[1]=tws.base[0]+m-1; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return ok; }

入栈操作：

status push(bdstacktype tws,int i,elemtype x) // x入栈,i=0表示低端栈,i=1表示高端栈

{ if (tws.top[0]tws.top[1]) return overflow; //注意此时的栈满条件

if (i==0) *tws.top[0]++=x; else

if (i==1) *tws.top[1]--=x; else return error; return ok; }

出栈操作：

status pop(bdstacktype tws, int i, elemtype x) // x出栈,i=0表示低端栈,i=1表示高端栈 { if (i==0)

{ if (tws.top[0]==tws.base[0]) return overflow; x=*--tws.top[0]; }

else if (i==1)

{ if (tws.top[1]==tws.base[1]) return overflow; x=*++tws.top[1]; }

else return error; return ok; }

p24/3.18

试写一个判别表达式中开、闭括号是否配对出现的算法。 status bracket_test(char *exp) //判别表达式中小括号是否匹配

{

count=0;

for (p=exp; *p; p++) {

if (*p== ( ) count++;

else if (*p== ) ) count--; if (count0) return error; }

if (count) return error; //注意括号不匹配的两种情况 return ok; }

p25/3.28

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、八队列和出队列的算法。

依题意，定义本题队列的结点类型如下typedef struct cqnode { int data;

struct linknode *next; }cqnode ，*cqlink; 初始化操作：

void initciqueue(cqlink rear)

rear=(cqnode*)malloc(sizeof(cqnode)); //产生一个头结点，并使队尾指针指向它 rear-next=rear;//形成循环 }

入队操作：

void enciqueue(ciqueue rear, int x)

//把元素x插入循环链表表示的队列rear, rear指向队尾元素, //rear-next指向头结点, rear-next-next指向队头元素

【篇二：数据结构第三章习题】

3．1 单项选择题

2.一个栈的入栈序列a, b, c, d, e, 则栈的不可能的输出序列是 a. edcba b. decba c. dceab d. abcde

3. 若已知一个栈的入栈序列是1，2，3，………..n, 其输出序列为p1, p2, p3,……,pn, 若p1=n, 则pi为 。 a.i. b. n=i c. n- i+1 d.不确定

4．栈结构通常采用的两种存储结构是 。

a. 顺序存储结构和链表存储结构 b. 散链方式和索引方式 c.链表存储结构和数组 d. 线性存储结构和非线性存储结构 5．判定一个栈st（最多元素为m0）为空的条件是。 a. st-top0 b. st-top=0 c.st-topm0 d.st-top=m0

6．判定一个栈st（最多元素为m0）为栈满的条件是。 a. st-top!=0 b.st-top==0

c.st-top!=m0 d.st-top==m0 7.栈的特点是 。

a先进先出 b. 先进后出

8. 一个队列的入栈序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1 b. 1,2,3,4 c. 1,4,3,2 d. 3,2,4,1

9. 判定一个队列qu(最多元素为m0)为空的条件是 。 a.qu-rear- qu-front==m0 b.qu-rear- qu-front-1==m0 c.qu-front== qu-rear

d. qu-front== qu-rear+1

10.判定一个队列qu（最多元素为m0）为满队列的条件是。 a.qu-rear- qu-front==m0 b.qu-rear- qu-front-1==m0 c.qu-front== qu-rear d.qu-front== qu-rear+1

11. 判定一个循环队列qu(最多元素为m0)为空的条件是 。 a. qu-front== （qu-rear+1）%m0 b. qu-front！= （qu-rear+1）%m0 c.qu-front== qu-rear d.qu-front！= qu-rear

12. 判定一个循环队列qu（最多元素为m0）为满队列的条件是。 a. qu-front== （qu-rear+1）%m0 b. qu-front！= （qu-rear+1）%m0 c.qu-front== qu-rear

d.qu-front！= qu-rear+1

12. 向一个栈顶指针为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; 3．2 填空题

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出 产生输出序列abc a进a出b进c进c出b出 产生输出序列acb a进b进b出 a出 c进c出 产生输出序列bac a进b进b出c进c出a出 产生输出序列bca