数据结构章节练习题及答案3.docx

《数据结构章节练习题及答案3.docx》由会员分享，可在线阅读，更多相关《数据结构章节练习题及答案3.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章栈和队列1 .具有什么特征的数据结构被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么?栈：一种插入和删除都只能在表的同一端进行的线性表。队列：一种只允许在表的一端进行插入操作，而在表的另一端进 行删除操作的线性表。先进后出：元素是以生，e2,声顺序进入数据结构，以相反 的顺序即en.i, ei离开数据结构。栈顶：允许进行插入和删除操作的一端。栈底：栈中与栈顶相对的另一端。先进先出：元素是以白，e2,品顺序进入数据结构，以相同 的顺序即ei, e2,eno离开数据结构。队头：允许删除操作的一端。队尾：允许插入操作的一端。2 .简述在顺序栈的栈顶插入一个元素的操作过程。

2、在插入元素之前，首先要判断栈是否为满，如果栈满，返回“沾 满无法插入”等错误提示信息；否那么让top指针（指向当前顺序栈的 栈顶）向后移动一个元素空间（元素大小），将要插入的元素放入top 指针指向的内存单元中。3 . 一个栈的输入序列为1、2、3,试给出全部可能的出栈序列。可分为三种情况：当只有一个存储空间时，只有一种出栈序列：1、2、3.、当有两个存储空间时，有：1、2、3,2、1、3,2、3、1等3种出栈序列、当存储空间大于等于三个时，有：1、2、3,2、1、3,2、3、1,3、2、1等4种出栈序列。4 .循环队列的优点是什么？在循环队列中，仅依据头尾指针相 等，无法判断队列是“空”还是

3、“满”。要解决这个问题，常用的两种方 法是什么？循环队列的优点有两点：一是可以防止发生顺序队列的“假上溢” 现象；二是充分利用队列的存储空间。两种判断队列是“空”还是“满”的方法：一是约定少用一个元素空 间；二是使用计数器size记录当前队列的实际长度。5 .简述在链接栈中插入一个元素的操作过程。链接栈的插入操作，先将待进栈结点的指针域指向原来的栈顶结 点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的 栈顶结点。6,请列举出一些可以用栈和队列表示的实际问题。所有“后进先出”(LIFO, Last In First Out)的实际问题都可以用栈 表示。栈的应用主要有：数制的转换、括号的匹配检查、行编辑处理、 表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现所有“先进先出”(FIFO, First In First Out)的实际问题都可以用队 列表示。如日常中的排队问题，队列的应用主要有：操作系统中各种 资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件 规划和事件模拟，树的层次遍历和图的广度优先遍历等。