栈和队列练习题

选择题 选择题 1 设 abcdef 以所给的次序进栈 若在进栈操作时 允许退栈操作 则下面得 不到的序列为 D A fedcba B bcafed C dcefba D cabdef 2 若已知一个栈的入栈序列是 1 2 3 n 其输出序列为 p1 p2 p3 pN 若 pN 是 n 则 pi 是 D A i B n i C n i 1 D 不确定 3 设计一个判别表达式中左 右括号是否配对出现的算法 采用 D 数 据结构最佳 A 线性表的顺序存储结构 B 队列 C 线性表的链式存储结构 D 栈 4 用链接方式存储的队列 在进行删除运算时 D A 仅修改头指针 B 仅修改尾指针 C 头 尾指针都要修改 D 头 尾指针可能都要修改 5 递归过程或函数调用时 处理参数及返回地址 要用一种称为 C 的 数据结构 A 队列 B 多维数组 C 栈 D 线性 表 6 假设以数组 A m 存放循环队列的元素 其头尾指针分别为 front 和 rear 则当前队列中的元素个数为 A A rear front m m B rear front 1 C front rear m m D rear front m 7 若用一个大小为 6 的数组来实现循环队列 且当前 rear 和 front 的值分 别为 0 和 3 当从队列中删除一个元素 再加入两个元素后 rear 和 front 的值分别为多少 B A 1 和 5 B 2 和 4 C 4 和 2 D 5 和 1 8 最大容量为 n 的循环队列 队尾指针是 rear 队头是 front 则队空的条 件是 A A rear 1 MOD n front B rear front C rear 1 front D rear l MOD n front 9 栈和队列的共同点是 C A 都是先进先出 B 都是先进后出 C 只允许在端点处插入和删除元素 D 没有共同点 10 设栈 S 和队列 Q 的初始状态为空 元素 e1 e2 e3 e4 e5 和 e6 依次 通过栈 S 一个元素出栈后即进队列 Q 若 6 个元素出队的序列是 e2 e4 e3 e6 e5 e1 则栈 S 的容量至少应该是 C A 6 B 4 C 3 D 2 判断题 判断题 栈和队列都是限制存取点的线性结构 消除递归不一定需要使用栈 此说法 任何一个递归过程都可以转换成非递归过程 两个栈共享一片连续内存空间时 为提高内存利用率 减少溢出机会 应把两 个栈的栈底分别设在这片内存空间的两端 名词解释 名词解释 栈 队列 循环队列 1 什么是递归程序 2 递归程序的优 缺点是什么 3 递归程序在执行时 应借助于什么来完成 4 递归程序的入口语句 出口语句一般用什么语句实现 算法题 算法题 1 已知数组 a 有 n 个元素 用递归实现以下算法 求和 求最大值 求平均数 判断是否为一个递增数组 大则继续 否则返回 false 结束 2 试将下列递归过程改写为非递归过程 void test int sum int x scanf d sum x printf d sum 3 请利用两个栈 S1 和 S2 来模拟一个队列 已知栈的三个运算定义如下 PUSH ST x 元素 x 入 ST 栈 POP ST returnreturn 0 s1 满 s2 非空 这时 s1 不能再入栈 ifif top1 n PUSH s2 x PUSH s1 x returnreturn 1 x 入栈 实现了队列元素的入队 2 voidvoid dequeue stack s2 s1 s2 是输出栈 本算法将 s2 栈顶元素退栈 实现队列元素的出队 ifif Sempty s2 栈 s2 不空 则直接出队 POP s2 x printf 出队元素为 x elseelse 处理 s2 空栈 ifif Sempty s1 printf 队列空 exit 0 若输入栈也为空 则判 定队空 elseelse 先将栈 s1 倒入 s2 中 再作出队操作 whilewhile Sempty s1 POP s1 x PUSH s2 x POP s2 x s2 退栈相当队列出队 printf 出队元素 x 结束算法 dequue 3 intint queue empty 本算法判用栈 s1 和 s2 模拟的队列是否为空 ifif Sempty s1 队列空 elseelse returnreturn 0 队列不空 D D D D C A B A C C T T T T 1 栈是只准在一端进行插入和删除操作的线性表 允许插入和删除的一端叫栈 顶 另一端叫栈底 最后插入的元素最先删除 故栈也称后进先出 LIFO 表 2 队列是允许在一端插入而在另一端删除的线性表 允许插入的一端叫队尾 允许删除的一端叫队头 最先插入队的元素最先离开 删除 故队列也常称先 进先出 FIFO 表 3 用常规意义下顺序存储结构的一维数组表示队列 由于队列的性质 队尾插 入和队头删除 容易造成 假溢出 现象 即队尾已到达一维数组的高下标 不能再插入 然而队中元素个数小于队列的长度 容量 循环队列是解决 假 溢出 的一种方法 通常把一维数组看成首尾相接 在循环队列下 通常采用 牺牲一个存储单元 或 作标记 的方法解决 队满 和 队空 的判定问 题 1 一个函数在结束本函数之前 直接或间接调用函数自身 称为递归 例如 函数 f 在执行中 又调用函数 f 自身 这称为直接递归 若函数 f 在执行中 调用函数 g 而 g 在执行中 又调用函数 f 这称为间接递归 在实际应用中 多为直接递归 也常简称为递归 2 递归程序的优点是程序结构简单 清晰 易证明其正确性 缺点是执行中 占内存空间较多 运行效率低 3 递归程序执行中需借助栈这种数