第 3 章 栈习题.pdf

第第 3 章章 栈 队列和数组栈 队列和数组 一 单选题一 单选题 1 栈中元素的进出原则是 A 先进先出 B 后进先出 C 栈空则进 D 栈满则出 2 栈的插入与删除操作在 进行 A 栈顶 B 栈底 C 任意位置 D 指定位置 3 若让元素 1 2 3 依次进栈 则出栈次序不可能出现 种情况 A 3 2 1 B 2 1 3 C 3 1 2 D 1 3 2 4 若用一个大小为 6 的数组来实现循环队列 且当 rear 和 front 的值分别为 O 和 3 当从队 列中删除一个元素 再加入两个元素后 rear 和 front 的值分别为 A l 和 5 B 2 和 4 C 4 和 2 D 5 和 l 5 一般情况下 将递归算法转换成等价的非递增归算法应该设置 A 堆栈 B 队列 C 堆栈或队列 D 数组 6 链栈与顺序栈相比 有一个比较明显的优点即 A 插入操作更方便 B 通常不会出现栈满的情况 C 不会出现栈空的情况 D 删除操作更方便 7 设 C 语言数组 Data m 1 作为循环队列 SQ 的存储空间 front 为队头指针 rear 为队为 指针 则执行出队操作的语句为 A front front 1 B front front 1 m C rear rear 1 m D front front 1 m 1 8 若已知一个栈的入栈序列是1 2 3 n 其输出序列为p1 p2 p3 pn 若p1 n 则pi为 A i B n i C n i 1 D 不确定 9 设有一顺序栈 T 元素 s1 s2 s3 s4 s5 s6 依次进栈 如果 6 个元素出栈的顺序是 s2 s3 s4 s6 s5 s1 则栈的容量至少应该是 A 2 B 3 C 5 D 6 10 数组 n 用来表示一个循环队列 f为当前队列头元素的前一位置 r为队尾元素的 位置 假定队列中元素的个数小于n 计算队列中元素的公式为 A r f B n f r n C n r f D n r f n 11 中缀表达式A B C D E的后缀形式是 A AB C D E B ABC D E C ABCD E D ABCD E 12 一个算术表达式的中缀形式为 A B C D E 后缀形式为 ABC DE 其前缀形式为 A A B C DE B A B CD E C ABC DE D A BC DE 13 循环队列A 0 m 1 存放其元素 用front和rear分别表示队头和队尾 则循环队列满的条件 是 A Q rear 1 m Q front B Q rear Q front 1 C Q rear 1 Q front D Q rear Q front 14 解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数据缓冲区 主机将 要输出的数据依次写入该缓冲区 而打印机则从该缓冲区中取出数据打印 该缓冲区应该是 一个 结构 A 栈 B 队列 C 线性表 D 数组 15 假设顺序栈的定义为 typedef struct selemtype base 栈底指针 selemtype top 栈顶指针 int stacksize 当前已分配的存储空间 以元素为单位 sqstack 变量 st 的类型为 sqstack 则栈 st 为空的判断条件为 A st base NULL B st top st stacksize C st top st base st stacksize D st top st base 16 对于以行序为主序的存储结构来说 在数组 A c1 d1 c2 d2 中 c1和 d1分别为数组 A 的第一个下标的上 下界 c2 d2分别为第二个下标的上 下界 每个数据元素占 K 个存储 单元 二维数组中任一元素 A i j 的存储位置可由 式确定 A Loc i j d2 c2 1 i c1 j c2 k B Loc i j loc c1 c2 d2 c2 1 i c1 j c2 k C Loc i j A c1 c2 d2 c2 1 i c1 j c2 k D Loc i j loc 0 0 d2 c2 1 i c1 j c2 k 17 对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 A 按照矩阵 A 的列序来进行转置 算法的时间复杂度为 0 nu tu B 按照 A 的三元组 a data 的次序进行转置 算法的时间复杂度为 O nu tu C 按照矩阵 A 的列序来进行转置的方法称快速转置 D 按照矩阵 A 的列序进行转置 对于 tu mu x nu 才有意义 18 稀疏矩阵的压缩存储方法是只存储 A 非零元素 B 三元组 i j aij C aij D i j 19 基于三元组的稀疏矩阵 对每个非零元素 aij 可以用一个 唯一确定 A 非零元素 B 三元组 i j aij C aij D i j 20 三角矩阵可压缩存储到数组 中 A M 1 n n 1 2 1 B M 1 n n 1 2 C M n n 1 2 1 D M n n 1 2 21 二维数组 M i j 的元素是 4 个字符 每个字符占一个存储单元 组成的串 行下标 i 的 范围从 O 到 4 列下标 j 的范围从 O 到 5 M 按行存储时元素 M 3 5 的起始地址与 M 按列 存储时元素 的起始地址相同 A M 2 4 B M 3 4 C M 3 5 D M 4 4 二 判断题二 判断题 1 栈是一种对所有插入 删除操作限于在表的一端进行的线性表 是一种后进先出型结构 2 队列是一种插入与删除操作分别在表的两端进行的线性表 是一种先进后出型结构 3 栈和队列是两种不同的数据结构 4 栈和队列是一种非线性数据结构 5 栈和队列的存储方式既可是顺序方式 也可是链接方式 6 当用户无法预估所用队列的最大长度 则宜采用链队列 7 一个栈的输入序列是12345 则栈的输出序列不可能是12345 8 栈和队列都是限制存储点的线性结构 9 若将链栈看成一个单链表 则作进栈操作时 可以看成在单链表的首结点前插入新的结 点 10 若将链栈看成一个单链表 则作退栈操作时 可以看成在单链表的首结点被删除 三 填空题三 填空题 1 在一个无头结点的链队列中 若队首指针与队尾指针的值相同 则表示该队列为 或 该队列 2 向一个栈顶指针为 T 的链栈中插入一个新结点 p 时 应执行 和 3 从一个栈顶指针为 T 的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时 应 执行 4 假定 front 和 rear 分别为一个无头结点的链队列的队首和队尾指针 则该链队列中只有一 个结点的条件为 5 后缀表达式 45 32 的值为 6 一般地 一个 n 维数组可视为其数据元素为 维数组的线性表 数组通常只 有 和 两种基本运算 7 通常采用 存储结构来存放数组 对二维数组可有两种存储方法 一种是以 为主序的存储方式 另一种是以 为主序的存储方式 C 语言数组用 的是以 序为主序的存储方法 8 需要压缩存储的矩阵可分为 矩阵和 矩阵两种 9 对称方阵中有近半的元素重复 若为每一对元素只分配一个存储空间 则可将 n2 个 元素压缩存储到 个元素的存储空间中 10 假设以一维数组 M 1 n n 1 2 作为 n 阶对称矩阵 A 的存储结构 以行序为主序存 储其下三角 包括对角线 中的元素 数组 M 和矩阵 A 间对应的关系为 11 上三角矩阵中 主对角线上的第 t 行 1 tj 时 aij c c 存放 在 M 中 12 下三角矩阵的存储和对称矩阵类似 M K 和 aij的对应关系是 13 设有二为数组 int M 10 20 注 m 为 0 10 n 为 0 20 每个元素 整数 栈两个存储单 元 数组的起始地址为 2000 元素 M 5 10 的存储位置为 M 8 19 的存储值 为 四 解答题四 解答题 1 若栈或队列采用顺序存储结构 则都存在 溢出 问题 请说明何谓 溢出 2 有人说 采用循环链表作为存储结构的队列就是循环队列 你认为这种说法正确吗 说 明你的理由 3 分别简述如何对一个前缀算术表达式求值的算法和一个后缀算术表达式求值的算法 4 利用两个栈S1 S2模拟一个队列时 如何用栈的运算实现队列的插入 删除运算 请简 述算法思想 5 设循环队列的容量为40 序号从0到39 现经过一系列的入队和出队运算后 有 front 11 rear 19 front 19 rear 11 问在这两种情况下 循环队列中各有元素多少个 9 设有三对角矩阵 aij n n 将其三条对角线上的元素逐行存于数组B 1 3n 2 中 使得B k aij 求 1 用 i j 表示 k 的下标变换公式 2 用 k 表示 i j 的下标变换公式 五 算法设计题五 算法设计题 1 从键盘上输入一批整数 然后按相反的次序打印出来 2 试写一个算法 判别读入的一个以 为结束符的字符序列是否是 回文 例如 abba 和 abcba 是回文 abcde 和 ababab 则不是回文 3 判断算术表达式中的三种括号 圆括号 方括号 花括号 是否正确匹配 4 假设以数组que m 假设数组范围在0 m 存放循环队列的元素 同时设变量rear和quelen分 别指示循环队列中队尾元素位置和内含元素的个数 试给出此循环队列的队满条件 并写出 相应的入队列和出队列的算法 5 用n个单元的一维数组构成的一个循环队列 试写由首指针front和尾指针rear计算出队列 中元素个数的算法 6 算术表达式由数字字母变量和加 减 乘 除 运算符组成 编写 一个函数把中缀表达式转换为后缀表达式 为使问题简化 可不考虑中缀表达式不正确的情 况 7 设算术表达式由数