《《数据结构与算法》第三章-堆栈与队列习题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》第三章-堆栈与队列习题.docx（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法第二部分习题精选一、填空题.向量、栈和队列都是 结构，可以在向量的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入和 删除元素。1 .栈是一种特殊的线性表，允许插入和删除运算的一端称为 o不允许插入和删除运算的i端称为 O2 . 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性 表。3 .在一个循环队列中，队首指针指向队首元素的 位置。4 .在具有n个单元的循环队列中，队满时共有 个元素。5 .向栈中压入元素的操作是先 ，后 。6 .从循环队列中删除一个元素时，其操作是先,后 o.带表头结点的空循环双向链表的长度等于。二、判断正误（判断
2、下列概念的正确性，并作出简要的说明。）（）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2.在表结构中最常用的是线性表，栈和队列不太常用。（）3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型 结构。（）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.栈和链表是两种不同的数据结构。（）6.栈和队列是一种非线性数据结构。（）7.栈和队列的存储方式既可是顺序方式，也可是链接方式。（）8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈 的栈底分别设在这片内存空间的两端。（）9.队是
3、一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）10. 一个栈的输入序列是12345,则栈的输出序列不可能是12345。三、单项选择题（）1.栈中元素的进出原则是A.先进先出 B.后进先出C.栈空则进D.枝满则出（）2.若已知一个栈的入栈序列是1, 2, 3,，n,其输出序列为pl, p2, p3,，pn, 若p1=n,则pi为A. i B. n=i C. n-i+1 D.不确定（）3.判定一个栈ST （最多元素为mO）为空的条件是A. ST-top0 B. ST-top=0 C. ST-topmO D. ST-top=mO（）4.判定一个队列QU （最多元素为mO）为
4、满队列的条件是A . QU-rear QU-front = = mO B . QU-rear QU-front 1= mOC . QU-front = = QU-rearD . QU-front = = QU-rear+l（）5.数组Q n用来表示一个循环队列，f为当前队列头元素的前一位置.，r为队尾 元素的位置，假定队列中元素的个数小于n,计算队列中元素的公式为（A ） rf;（ B ） （n+fr） % n; （ C ） n + rf; （D） （n + rf） % n四、简答题.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？1 .设循环队列的容量为40 (序号从0到39),
5、现经过一系列的入队和出队运算后，有front=ll, rear=19; front=19, rear=ll；问在这两种情况下，循环队列中各有元素 多少个？习题精选答案一、填空题I.线性任何栈顶队尾 队首 2.栈顶栈底3.队列4.前一个5.n-l6.移动栈顶指针存入元素7.移动队首指针取出元素8. 0.、1. (X)错，线性表是逻辑结构概念，可以顺序存储或链式存储，叮元素数据类型无关。2. (X)错，不一定吧？调用子程序或函数常用，CPU中也用队列。3. ( J)( V)正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。4. (X)错，栈是逻辑结构的概念，是特殊殊线性
6、表，而链表是存储结构概念，二者不是同类项。5. (X)错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。6. ( V) 8. ( J ) 9. ( X )错，后半句不对。10. (X)错，有可能。三、单项选择题1. (B) 2. (C) 3. (B) 4. (A) 5. (D)四、简答题4.答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数 组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三： 设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空。使用一个计数器记录队列中元素个数(即队列长度)。我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：f=rear队满标志是：f=(r+l)%N