数据结构第三章习题.pdf

"数据结构第三章习题.pdf" 本文档是一个关于数据结构第三章的习题集，涵盖了栈和队列的相关知识点。下面是对每个习题的详细解释： 3.1 单项选择题 1. 一个栈的入栈序列a, b, c, d, e, 则栈的不可能的输出序列是。 这个问题考察了栈的基本特点，即“后进先出”。由于栈的入栈序列是a, b, c, d, e，因此输出序列只能是e, d, c, b, a。如果输出序列是其他的，那么就违背了栈的特点。 2. 若已知一个栈的入栈序列是1, 2, 3, ⋯, n, 其输出序列为p1, p2, p3, ⋯, pn, 若p1=n, 则pi为。 这个问题考察了栈的输出序列的特点。当p1=n时，pi=n-i+1。这是因为栈的输出序列是逆序的，即最后入栈的元素最先出栈。 3. 栈结构通常采用的两种存储结构是。 这个问题考察了栈的存储结构。栈可以使用顺序存储结构和链表存储结构两种方式来实现。 4. 判定一个栈ST（最多元素为m0）为空的条件是。 这个问题考察了栈的判空条件。栈为空的条件是ST->top=0，即栈顶指针为空。 5. 判定一个栈ST（最多元素为m0）为栈满的条件是。 这个问题考察了栈的判满条件。栈为满的条件是ST->top=m0，即栈顶指针指向了栈的最后一个元素。 6. 栈的特点是，队列的特点是。 这个问题考察了栈和队列的特点。栈的特点是“后进先出”，队列的特点是“先进先出”。 7. 一个队列的入队序列是1, 2, 3, 4, 则队列的输出序列是。 这个问题考察了队列的输出序列。当入队序列是1, 2, 3, 4时，队列的输出序列是1, 2, 3, 4。 8. 判定一个队列QU（最多元素为m0）为空的条件是。 这个问题考察了队列的判空条件。队列为空的条件是QU->front==QU->rear，或者QU->front-QU->rear==m0。 9. 判定一个队列QU（最多元素为m0）为满队列的条件是。 这个问题考察了队列的判满条件。队列为满的条件是QU->rear-QU->front==m0。 10. 判定一个循环队列QU（最多元素为m0）为空的条件是。 这个问题考察了循环队列的判空条件。循环队列为空的条件是QU->front==（QU->rear+1）%m0。 11. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。 这个问题考察了循环队列的判满条件。循环队列为满的条件是QU->front==（QU->rear+1）%m0。 12. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 这个问题考察了链栈的插入操作。当插入一个s所指结点时，需要将s->next=HS->next，然后将HS->next=s。 13. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。 这个问题考察了链栈的删除操作。当删除一个结点时，需要将x=HS->data，然后将HS=HS->next。 14. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时。 这个问题考察了链队的插入操作。当插入一个s所指结点时，需要将s->next=r，然后将r=s。 15. 在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时。 这个问题考察了链队的删除操作。当删除一个结点时，需要将r=f->next，然后将f=f->next。 3.2 填空题 4. 向栈中压入元素的操作是。 这个问题考察了栈的压入操作。栈的压入操作是将元素压入栈顶。 5. 对栈进行退栈的操作是。 这个问题考察了栈的退栈操作。栈的退栈操作是将栈顶元素出栈。 6. 在一个循环队列中，队首指针指向队首元素的。 这个问题考察了循环队列的队首指针。队首指针指向队首元素。 7. 从循环队列中删除一个元素时，其操作是。 这个问题考察了循环队列的删除操作。从循环队列中删除一个元素时，需要将队首指针指向下一个元素。 8. 在具有n个单元的循环队列中，队满时共有n个元素。 这个问题考察了循环队列的队满条件。循环队列满时共有n个元素。 9. 在栈顶指针为HS的链栈中，判定栈空的条件是。 这个问题考察了链栈的判空条件。链栈为空的条件是HS->next==NULL。 10. 在栈顶指针为HS的链栈中，计算该链站中结点个数的函数时。 这个问题考察了链栈的结点个数计算。链栈的结点个数可以通过遍历链栈来计算。 11. 在HQ的链队中，判定只有一个结点的条件是。 这个问题考察了链队的判空条件。链队只有一个结点的条件是HQ->front==HQ->rear。 12. 在HQ的链队中，计算该链队中结点个数的函数是。 这个问题考察了链队的结点个数计算。链队的结点个数可以通过遍历链队来计算。 3.3 顺序栈习题解析 1. 对于一个栈，给出输入项A, B, C. 如果输入项序列由A, B, C所组成，是给出全部可能的输出序列。 这个问题考察了栈的输出序列。由于栈的入栈序列是A, B, C，因此输出序列可以是ABC, ACB, BAC, BCA, CAB, CBA。这6种情况都是可能的输出序列。