数据结构Ch3习题答案

1Ch3栈和队列一．选择和填空：1．一个栈的入栈序列是a，b，c，d，e，则栈的可能的出栈序列是(D)。A．edcabB．decabC．dceabD．abcde2．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为(n-i+1)。3．栈结构通常采用的两种存储结构是(顺序存储结构和链式存储结构)。4．判定一个顺序栈S为空的条件是(最多元素为m)(S.top=0或S.top=S.base)。5．判定一个顺序栈S为满的条件是(最多元素为m)(S.top=m或S.top-S.base=m)。6．栈的特点是(先进后出)，队列的特点是(先进先出)。7．一个队列的入对序列是a，b，c，d，e，则出队序列是(a，b，c，d，e)。8．判定一个顺序队列Q(最多元素为m)为空的条件是(Q.front=Q.rear=0，…，m)。9．判定一个顺序队列Q(最多元素为m)为满的条件是(Q.rear-Q.front=m或Q.rear=m，Q.front=0)。10．判定一个循环队列Q(最多元素为m)为空的条件是(Q.front=Q.rear=0，…m-1)。11．判定一个循环队列Q(最多元素为m)为满的条件是(Q.front=(Q.rear+1)%m)。12．循环队列用数组Q[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是((Q.rear-Q.front+m)%m)。13．栈和队列的共同点是(是限定性的线性结构，只能在端点处进行插入删除操作)。14．线性表、栈和队列都是(线性)结构，可以在线性表的(任何)位置插入和删除元素，对于栈，只能在(栈顶)位置插入和删除元素，对于队列只能在(队尾)插入元素和在(队头)删除元素。15．向栈中压入元素的操作是(先压入元素，后移动指针或*S.top++=e)。16．从栈中弹出元素的操作是(先移动指针，后弹出元素或e=--*S.top)。17．在具有n个单元的循环队列中，队满时共有(n-1)个元素。18．对于一个栈，若输入序列是A，B，C，则全部可能的输出序列是(ABC、ACB、BAC、BCA、CBA)。19．栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。20．队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。221．在一个循环队列中，队尾指针指向队尾元素的下一个位置。22．在做进栈运算时，应先判别栈是否满；在做退栈运算时，应先判别栈是否空。23．为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，只有当两个栈的栈顶在达栈空间的某一位置相遇时，才产生上溢。二．判断正误(×)1．线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。(×)2．在表结构中最常用的是线性表，栈和队列不太常用。(√)3．栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。(√)4．对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。(×)5．栈和链表是两种不同的数据结构。(×)6．栈和队列是一种非线性数据结构。(√)7．栈和队列的存储方式既可是顺序方式，也可是链接方式。(√)8．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。(×)9．队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。(×)10．一个栈的输入序列是12345，则栈的输出序列不可能是12345。三、阅读理解1.写出下列程序段的输出结果(栈的元素类型SElemType为Char)。voidmain(){StackS；charx，y；InitStack(S)；x=’C’；y=’k’；Push(S，x)；Push(S，’a’)；Push(S，y)；Pop(S，x)；Push(S，’t’)；Push(S，x)；Pop(S，x)；Push(S，’s’)；while(!StackEmpty(S)){Pop(S，y)；printf(y)；}；Printf(x)；}输出结果为staCk2.写出下列程序段的输出结果(队列中的元素类型QElemType为Char)。voidmain(){QueueQ；InitQueue(Q)；charx=’e’，y=’C’；3EnQueue(Q，’h’)；EnQueue(Q，’r’)；EnQueue(Q，’y’)；DeQueue(Q，x)；EnQueue(Q，x)；DeQueue(Q，x)；EnQueue(Q，’a’)；while(!QueueEmpty(Q)){DeQueue(Q，y)；printf(y)；}printf(x)；}输出结果为yhar四．假设一个算术表达式包含圆括号、方括号和花括号三种类型的括号。编写一个判别表达式中括号是否配对的函数。typedefcharElemtype；intCheck()4{STACKS；//定义栈结构Scharch；InitStack(&S)；//初始化栈Swhile((ch=getchar())!=‘\n’){//以字符序列的形式输入表达式switch(ch){case(ch==‘(’||ch==‘[’||ch==‘{’):Push(&S，ch)；break；//遇左括号入栈//在遇到右括号时，分别检测匹配情况case(ch==')'):if(StackEmpty(S))retrunFALSE；else{Pop(&S，&ch)；if(ch!='(')returnFALSE；}break；case(ch==']'):if(StackEmpty(S))retrunFALSE；else{Pop(&S，&ch)；if(ch!='[')returnFALSE；}break；case(ch=='}'):if(StackEmpty(S))retrunFALSE；else{Pop(&S，&ch)；if(ch!='{')returnFALSE；}break；default:break；}}if(StackEmpty(S))returnTRUE；elsereturnFALSE；}五．假设Q[10]是一个顺序队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的变化情况若不能入队，请指出其元素，并说明理由。d，e，b，g，h入队d，e出队i，j，k，l，m入队b出队n，o，p，q，r入队初始队列d，e，b，g，h入队d，e出队i，j，k，l，m入队b出队n，o，p，q，r无法入队，队列尾指针已经溢出假设Q[10]是一个循环队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的变化情况若不能入队，5请指出其元素，并说明理由。d，e，b，g，h入队d，e出队i，j，k，l，m入队b出队n，o，p，q，r入队初始队列d，e，b，g，h入队d，e出队i，j，k，l，m入队b出队n，o入队p，q，r无法入队，队列已经满了