408数据结构：栈、队列和数组选择题做题笔记
408数据结构
第一章 绪论
第二章 线性表
绪论、线性表选择题做题笔记
第三章 栈、队列和数组
栈、队列和数组选择题做题笔记
前言
本篇文章为针对王道25数据结构课后习题的栈、队列和数组的做题笔记，后续做其他数据结构练习会进行更新！
一、队列
11、与顺序队列相比，链式队列（）
A.优点是队列的长度不受限制
B.优点是进队和出队的效率更高
C.缺点是不能进行顺序访问
D.缺点是不能根据队首指针和队尾指针计算队列的长度
- 正确答案：D
- 解析
A.即使链式队列采用的是动态分配，但长度也收内存空间的限制，无法无限制增长
B.顺序队列和链式队列的进出队时间复杂度均为O（1）
C.顺序队列和链式队列均可进行顺序访问
D.顺序队列可以通过对头指针和队尾指针计算队列中的元素个数，而链式队列不能 - 疑惑
链式队列知道对头指针和队尾指针，不能直接遍历得到元素个数吗 - 疑惑解答
题目应该是说要根据两个指针直接得到
最适合用作队列的链表是___________
A.带队首指针和队尾指针的循环单链表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的非循环单链表
D.只带队首指针的循环单链表
- 答案：B.带队首指针和队尾指针的非循环单链表
- 分析
（1）顺序还是链式
答：包链式的啊
（2）带什么指针（头/尾/头和尾）
（3）要不要循环
答：队列的主要操作是入队和出队，入队时，如果没有队尾指针则得遍历，因此需要队尾指针，因此排除CD
；出队时，只需要让队首指针指向下一个即可，不需要循环，因此选B
（4）单链表还是双链表
答：题目不涉及此项的讨论
在用单链表实现队列时，对头应设在链表的____位置
A.链头
B.链尾
C.链中
- 答案：A.链头
- 分析：队列指针是对头指向队尾的，和链表一样（链头指向链尾）
用链式存储方式的队列进行删除操作时需要_______–
A.仅修改头指针
B.仅修改尾指针
C.头尾指针都要修改
D.头尾指针可能都要修改
- 答案：D
- 分析：当不止一个元素时仅修改头指针，当只有一个元素时两个都要修改
假设输入序列为1，2，3，4，5，利用两个队列纪念性出入队操作，不可能的输出序列为________-
A.1,2,3,4,5
B.5,2,3,4,1
C.1,3,2,4,5
D.4,1,5,2,3
- 答案:B
- 分析
题目是指：1，2，3，4，5按照顺序分别进入两个队列，然后输出，例如C，则1,3,5入队列1号，2，4入队列2号，则可实现1，3，2，4，5的输出序列，原理和拿到火车题一样、
已知循环队列存储在一维数组A【0…n-1】中，且队列非空时
front和rear分别指向对头元素和队尾元素。若初始化时队列为空，且要求第一个进入队列的元素存储在A【0】处，则初始时front和rear的值分别是_____和_______
- 答案：B
- 分析：首先不可能指向同一个地方，因为这样说明有一个元素，由于初始化后队列为空，而空时应该为(rear+1)%n=front，因此front应在rear前面，故选择B
- 注意：（1）循环队列的循环指顺序存储结构上的循环，而不是逻辑上的循环（2）front和rear的初始值并不是固定的
二、栈和队列的应用
对于一个问题的递归算法求解和其对应的非递归算法求解________-
A.递归算法通常效率高一些
B.非递归算法通常效率高一些
C.两者相同
D.无法比较
- 答案：B
- 分析
通常情况下，递归由于包含很多的重复计算，所以效率很低 - 补充
递归转化为非递归时，未必要使用栈
对特殊矩阵采用压缩存储的主要目的_______
- 答案：减少不必要的存储空间
判断题：稀疏矩阵的特点是矩阵中的元素较少（ ）
- 答案：错，是非0元素较少
总结
本章节题目多为逻辑思考题，相对有趣，题目固定但细节繁多！
原文地址：https://blog.csdn.net/m0_74983085/article/details/144026572
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！