广工数据结构mooc第3章

数据结构第三章的习题答案数据结构第三章的习题答案在学习数据结构的过程中，习题是巩固知识和提高能力的重要方式。

第三章的习题主要涉及线性表、栈和队列的实现和操作。

本文将对这些习题进行解答，并给出详细的步骤和思路。

1. 第一题要求实现一个线性表的插入操作。

线性表是一种常用的数据结构，它的特点是元素之间存在一对一的关系。

要实现插入操作，首先需要定义线性表的数据结构，可以使用数组或链表来实现。

然后，根据插入位置，将插入位置之后的元素依次后移，为要插入的元素腾出空间。

最后，将要插入的元素放入插入位置。

2. 第二题要求实现一个栈的压栈和出栈操作。

栈是一种后进先出（LIFO）的数据结构，可以使用数组或链表来实现。

压栈操作就是将元素放入栈顶，出栈操作就是将栈顶元素取出并删除。

要实现这两个操作，可以使用一个指针来指示栈顶位置，每次压栈时将指针加一，出栈时将指针减一。

需要注意的是，栈满时不能再进行压栈操作，栈空时不能进行出栈操作。

3. 第三题要求实现一个队列的入队和出队操作。

队列是一种先进先出（FIFO）的数据结构，同样可以使用数组或链表来实现。

入队操作就是将元素放入队尾，出队操作就是将队头元素取出并删除。

与栈不同的是，队列需要维护队头和队尾两个指针。

每次入队时将元素放入队尾，并将队尾指针后移一位；出队时将队头元素取出，并将队头指针后移一位。

需要注意的是，队列满时不能再进行入队操作，队列空时不能进行出队操作。

4. 第四题要求实现一个栈的括号匹配算法。

括号匹配是一种常见的应用场景，例如编程语言中的括号匹配。

要实现这个算法，可以使用栈来辅助。

遍历字符串中的每个字符，如果是左括号，则将其压入栈中；如果是右括号，则将栈顶元素取出并判断是否与右括号匹配。

如果匹配，则继续遍历下一个字符；如果不匹配，则说明括号不匹配，返回错误。

最后，如果栈为空，则说明括号匹配成功；如果栈不为空，则说明括号不匹配，返回错误。

5. 第五题要求使用栈实现一个逆波兰表达式的计算器。

第3章作业答案一、填空1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。

不允许插入和删除运算的一端称为栈底。

3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4.在具有n个单元的循环队列中，队满时共有n-1 个元素。

设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。

在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。

假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。

经操作后，最后在栈中或队中的元素还有E个。

供选择的答案：A～D：①a1 ②a2 ③a3 ④a4E：①1 ②2 ③3 ④0答：ABCDE＝2, 4, 1, 2, 2栈是一种线性表，它的特点是 A 。

设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。

往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。

设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。

供选择的答案：A：①先进先出②后进先出③进优于出④出优于进⑤随机进出B，C：①加1 ②减1 ③不变④清0 ⑤加2 ⑥减2D：①a,b ②b,c ③c,a ④b,a ⑤c,b ⑥a,cE：①n+1 ②n+2 ③n ④n-1 ⑤n-2答案：ABCDE=2, 2, 1, 6, 4在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。

第 3 章特殊线性表——栈、队列和串(2005-07-14) -第 3 章特殊线性表——栈、队列和串课后习题讲解1. 填空⑴设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。

【解答】23，1003H⑵栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。

【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间⑶（）可作为实现递归函数调用的一种数据结构。

【解答】栈【分析】递归函数的调用和返回正好符合后进先出性。

⑷表达式a*(b+c)-d的后缀表达式是（）。

【解答】abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。

【解答】后进先出，先进先出，对插入和删除操作限定的位置不同⑹循环队列的引入是为了克服（）。

【解答】假溢出⑺数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。

page: 2The Home of jetmambo - 第 3 章特殊线性表——栈、队列和串【解答】（rear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

⑻用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。

【解答】Ｏ(1)，Ｏ(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

广东工业大学数据结构Aniview第三章参考答案◆3.17③试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如'序列1&序列2'模式的字符序列。

其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。

例如，'a+b&b+a'是属该模式的字符序列，而'1+3&3-1'则不是。

实现下列函数:Status match(char *str);/* 若str是属该模式的字符序列，*//* 则返回TRUE，否则返回FALSE */Stack是一个已实现的栈。

可使用的相关类型和函数：typedef char SElemType; // 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType&e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType&e);Status match(char *str)/* 若str是属该模式的字符序列，*//* 则返回TRUE，否则返回FALSE */{ Stack S;inti;SElemType e;InitStack(S);for(i=0;str[i]!='&';i++){ Push(S,str[i]); }for(i=i+1;!StackEmpty(S)&&str[i]!='@';i++){Pop(S,e);if(e!=str[i]){ return FALSE;}}if(StackEmpty(S)&&str[i]=='@'){ return TRUE;}}3.18②试写一个判别表达式中开、闭括号是否配对出现的算法。

数据结构第3章答案(已核)数据结构第3章答案(已核)数据结构是计算机科学中非常重要的一门课程，它研究如何组织和存储数据，以便于高效地访问和处理。

在第3章中，我们学习了一些与树相关的重要概念和算法。

本文将对该章节的内容进行总结和解答。

一、树(Tree)树是一种非线性的数据结构，它由一组节点（Node）和一组连接这些节点的边（Edge）组成。

树的一个节点被称为根节点，它没有父节点；其他节点可以有一个或多个子节点。

树的每个节点除了根节点外都有且只有一个父节点。

树有许多种类，如二叉树、平衡树等。

二、二叉树(Binary Tree)二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

在二叉树中，左子树和右子树也是二叉树。

二叉树有许多重要的性质和应用，比如二叉搜索树、平衡二叉树等。

三、二叉搜索树(Binary Search Tree)二叉搜索树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，而右子树中的所有节点的值都大于根节点的值。

这个特性使得在二叉搜索树中进行插入、删除和查找操作非常高效。

四、平衡二叉树(AVL Tree)平衡二叉树也是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1。

通过对插入和删除操作进行树的旋转，可以保持平衡二叉树的平衡性，使得操作的时间复杂度保持在O(log n)。

五、堆(Heap)堆是一种特殊的树结构，它可以分为最大堆和最小堆。

最大堆中，父节点的值大于等于子节点的值；最小堆中，父节点的值小于等于子节点的值。

堆常用于实现优先队列等数据结构，有助于高效地找出最大或最小元素。

六、哈夫曼树(Huffman Tree)哈夫曼树是一种特殊的二叉树，用于实现哈夫曼编码。

在哈夫曼树中，频率较高的字符具有较短的编码，而频率较低的字符具有较长的编码。

哈夫曼树常用于数据压缩领域，可以有效地减少数据的存储空间。

七、图(Graph)图是一种复杂的数据结构，它由节点和连接节点的边组成。

数据结构第三章习题答案解析第三章习题1. 按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴ 如进站的车厢序列为123 ，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456 ，能否得到435612 和135426 的出站序列，并说明原因。

（即写出以“S”表示进栈、以“ X”表示出栈的栈操作序列）。

2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。

如果对这个队列重复执行下列4步操作：1) 输出队首元素；2) 把队首元素值插入到队尾；3) 删除队首元素；4) 再次删除队首元素。

直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2）A、C、E（3）A、C、E、C、C、 C （4）A、C、E、C3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4. 按照四则运算加、减、乘、除和幕运算（T）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A —B *C/D+EfF5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2' 模式的字符序列。

其中序列1 和序列2 中都不含字符' &'且，序列2 是序列1 的逆序列。

例如，‘a+b&b+a '是属该模式的字符序列，而’1+ 3 &3 —1'则不是。

6. 假设表达式由单字母变量和双目四则运算算符构成。

试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。

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

8. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag ,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。

习题答案1.填空题（1）栈（2）队列（3）后进先出（4）先进先出2.选择题（1）A （2）C （3）D （4）D、A （5）C （6）B3.思考题（1）栈是一种运算受限制的线性表，其只允许在表的一端进行插入和删除操作，俗称堆栈。

允许进行操作的一端称为“栈顶”，而另一个固定端称为“栈底”，栈中的数据在进行入栈和出栈时，遵循后进先出的原则。

队列同样是一种运算受限制的线性表，是限制在两端进行插入和删除操作的线性表。

允许进行插入操作的一端称为“队尾”，而允许进行删除操作的一端称为“队头”，队列中的数据在进行入队和出队时，遵循先进先出的原则。

4.编程题（1）//入栈//参数1为栈顶指针（头结点指针），参数2为插入的数据int linkstack_push(linkstack_t *s, datatype_t value){linkstack_t *temp;//使用malloc函数为新插入的结点申请内存空间temp = (linkstack_t *)malloc(sizeof(linkstack_t));//为新插入的结点赋值temp->data = value;//用头插法实现入栈temp->next = s->next;s->next = temp;return 0;}//判断栈是否为空int linkstack_empty(linkstack_t *s){return s->next == NULL ? 1 : 0; //判断下一个结点是否为空}//出栈datatype_t linkstack_pop(linkstack_t *s){linkstack_t *temp;datatype_t value;if(linkstack_empty(s)){printf("linkstack empty\n");return -1;}//头删法表示出栈，后入先出temp = s->next;s->next = temp->next;//保存出栈的数据value = temp->data;//释放出栈的结点的内存空间free(temp);temp = NULL;//返回出栈的数据return value;}（2）//入队//参数1为存放队列头尾结点指针的结构体地址，参数2为新入队的数据int linkqueue_enter(linkqueue_t *lq, datatype_t value){ linknode_t *temp;//使用malloc函数为头结点申请内存空间temp = (linknode_t *)malloc(sizeof(linknode_t));//采用尾插法的设计思想temp->data = value; //为新结点赋值temp->next = NULL; //将新结点的指针指向NULLlq->rear->next = temp; //入队，将新结点加入队列尾部lq->rear = temp; //移动rear指针，指向新加入的结点 return 0;}//判断队列是否为空int linkqueue_empty(linkqueue_t *lq){//当front与rear指向同一个结点时，判断队列为空return lq->front == lq->rear ? 1 : 0;}//出队//从头结点开始删除，包括头结点datatype_t linkqueue_out(linkqueue_t *lq){linknode_t *temp;datatype_t value;if(linkqueue_empty(lq)){printf("linkqueue empty\n");return -1;}temp = lq->front; //获取删除结点//移动front指针到下一个结点lq->front = lq->front->next;//获取下一个结点的数据value = lq->front->data;free(temp); //释放需要删除结点的内存空间 temp = NULL; //避免出现野指针//返回结点数据return value;}。

数据结构(第二版)习题答案第3章3.1 选择题第3章线性表的链式存储（1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（ A ）。

A．n B．m C．n− 1D．m + n（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找x应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;if (p->info==x) return p else return NULL;B．node *p=head; while (p&& p->info!=x) p=p->next; return p;C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p;D．node *p=head; while (p->info!=x) p=p->next ; return p;（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。

A．必须是连续的C．一定是不连续的B．部分地址必须是连续的D．连续不连续都可以（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ B ）。

A．O(1) B．O(n) C．O(n2) D．O(n log2n)（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ D ）。

A．仅修改队头指针C．队头、队尾指针都要修改B．仅修改队尾指针D．队头,队尾指针都可能要修改（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。

《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

head 11级计本、信本第3章 栈和队列 自测卷答案一、填空题（每空1分，共15分）1.向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。

不允许插入和删除运算的一端称为 栈底 。

3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。

5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。

6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。

7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。

8.带表头结点的空循环双向链表的长度等于 0 。

解：二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分）（ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU 中也用队列。

（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ × ）5. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

（ × ）6. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。