1、栈和队列模拟试卷 2 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 假设循环单链表表示的队列长度为 n，队头固定在链表表尾，若只设头指针，则进队操作的时间复杂度为（ ）。（A）O(n)（B） O(1)（C） O(n2)（D）O(nlog 2n)2 已知输入序列为 abed，经过输出受限的双端队列后能得到的输出序列是（ ）。（A）dacb（B） cadb（C） dbca（D）以上序列都不能得到3 若以 1、2、3、4 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（ ）。（A）1、2、3、4（B） 4、1、3、2（
2、C） 4、2、3、1（D）4、2、1、34 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。（A）bacde（B） dbace（C） dbcae（D）ecbad5 已知循环队列存储在一维数组 A0n1中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A0处，则初始时 front 和 rear 的值分别是（ ）。（A）0，0（B） 0，n-1（C） n-1，0（D）n-1 ，n-16 栈的应用不包括（ ）。（A）递归（B）进制
3、转换（C）迷宫求解（D）缓冲区7 下面（ ）用到了队列。（A）括号匹配（B）迷宫求解（C）页面替换算法（D）递归8 表达式 a*(b+c)-d 的后缀表达式是（ ）。（A）abed*+-（B） abc+*d-（C） abc*+d-（D）-+*abcd9 利用栈求表达式的值时，设立运算数栈 OPEN。假设 OPEN 要两个存储单元，则在下列表达式中，不会发生溢出的是（ ）。（A）A-B*(C-D)（B） (A-B)*C-D（C） (A-B*C)-D（D）(A-B)+(C-D)10 在表达式 32(4+22-63)-5 求值过程中当扫描到 6 时，操作数栈和操作符栈为（ ）( 表示乘方)。（A）3
4、，2，4，1，1：#，“ ，(，+，-（B） 3，2，8：；#， ，-（C） 3，2，4，2，2：#，(，-（D）3，2，8：#，(，-11 当执行函数时，其局部变量的存储一般采用（ ）进行存储。（A）树形结构（B）静态链表（C）栈结构（D）队列结构12 下列说法中正确的是（ ）。（A）消除递归不一定需要使用栈（B）对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同（C）通常使用队列来处理函数或过程调用（D）队列和栈都是运算受限的线性表，只允许在表的两端进行运算13 一个问题的递归算法求解和其相对应的非递归算法求解，（ ）。（A）递归算法通常效率高一些（B）非递归算法
5、通常效率高一些（C）两者相同（D）无法比较14 为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（A）栈（B）队列（C）树（D）图15 执行（ ）操作时，需要使用队列作为辅助存储空间。（A）查找散列(哈希) 表（B）广度优先搜索图（C）前序 (根)遍历二叉树（D）深度优先搜索图16 对 n 阶对称矩阵压缩存储时，需要表长为（ ）的顺序表。（A）n2（B） n,n2（C） n(n+1)2（D）n(n-1)217 对特殊矩阵采用压缩存储的主要目的是（ ）。（A）表达变得
6、简单（B）对矩阵元素的存取变得简单（C）去掉矩阵中的多余元素（D）减少不必要的存储空间18 设有一个 nn 的对称矩阵 A，将其下三角部分按行存放在一维数组 B 中，而A00存放于 B0中，那么第 i 行的对角元素 Aii存放于 B 中（ ）处。（A）(i+3)i2（B） (i+1)i2（C） (2n-i+1)i2（D）(2n-i-1)i219 若将 n 阶上三角矩阵 A 按列优先级压缩存放在一维数组 B1n(n+1)2中，则存放到 Bk中的非零元素 aiJ(1i，jn)的下标 i、j 与 k 的对应关系是（ ）。（A）i(i+1)2+j（B） i(i-1)2+j-1（C） j(j-1)2+i
7、（D）j(j-1)2+i-120 在一个二维数组 A 中，假设每个数组元素的长度为 3 个存储单元，行下标 i 为08，列下标 j 为 09，从首地址 SA 开始连续存放。在这种情况下，元素 A85的起始地址为（ ）。（A）SA+141（B） SA+144（C） SA+222（D）SA+25521 若将 n 阶下三角矩阵 A 按列优先顺序压缩存放在一维数组 B1n(n+1)2中，则存放到 Bk中的非零元素 aij(1i，jn)的下标 i、 j 与 k 的对应关系是（ ）。（A）(i-1)(2n-j+1)2+i-j（B） (j-1)(2n-j+2)2+i-j+1（C） (j-1)(2n-j+2)
8、2+i1（D）(j-1)(2n1+1)2+i-j-1二、综合题22 利用顺序表的操作，实现以下函数：1)从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2)从顺序表中删除第 i 个元素并由函数返回被删除元素的值。如果 j 不合理或顺序表为空则显示出错信息并退出运行。3)向顺序表中第 i 个位置插入一个新的元素 x。如果 i 不合理则显示出错信息并退出运行。4)从顺序表中删除具有给定值 x 的所有元素。5)从顺序表删除其值在给定值 s 与 t 之间(要求 s 小于 t)的所有元素。如果 s 或 t 不合理或者顺序表为空
9、，则显示错误信息并退出。6)从有序顺序表中删除其值在给定值 s 与 t 之间(要求 s 小于 t)的所有元素。如果 s或 t 不合理或顺序表为空，则显示错误信息并退出。7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。8)从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。23 请设计算法将不带头结点的单链表就地逆置。24 有一个单链表 L(至少有 1 个结点)，其头结点指针为 head，编写一个过程将 L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。25 设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：1)找出
10、最小值结点，且打印该数值。2)若该数值是奇数，则将其与直接后继结点的数值交换。3) 若该数值是偶数，则将其直接后继结点删除。26 给定(已生成) 一个带表头结点的单链表，设 head 为头指针，结点的结构为(data， next)，data 为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间;27 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。28 假定无向图以邻接矩阵形式存储，邻接矩阵的定义如下：#define
11、 MAX 20typedef char ElemType ;strUCt MGraphElemType vexsMAX； 顶点数组int arcsMAXMAX； 邻接矩阵int vexnum; 顶点数；试用 C 语言编写算法函数并分析时间复杂度。1)intDeleteNode(structMGraphG，ElemTypee) ；从图 G 中删除顶点值为 e 的顶点，成功返回 1，否则返回 0。2)intDeleteEdge(strUCtMGraphG，ElemTypea，ElemTypeb)；从图 G 中删除边(a， b)，成功返回 1，否则返回 0。栈和队列模拟试卷 2 答案与解析一、单项选
12、择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 A【试题解析】 进队操作是在表尾进行的，在只带头指针的循环单链表中寻找表尾结点的时间复杂度为 O(n)。【知识模块】 栈和队列2 【正确答案】 B【知识模块】 栈和队列3 【正确答案】 C【知识模块】 栈和队列4 【正确答案】 C【知识模块】 栈和队列5 【正确答案】 B【知识模块】 栈和队列6 【正确答案】 D【试题解析】 缓冲区是用队列实现的，A、B、C 都是栈的典型应用。【知识模块】 栈和队列7 【正确答案】 C【试题解析】 页面替换算法中的 FIFO 用 JUT 队列。其余的都只用到了栈。【知识模块】 栈和队列8 【正确
13、答案】 B【试题解析】 后缀表达式中，每一个计算符号均位于它两个操作数的直接后面，按照这样的方式逐步根据计算的优先级将每个计算式进行变换，即可得到后缀表达式。【知识模块】 栈和队列9 【正确答案】 B【知识模块】 栈和队列10 【正确答案】 D【知识模块】 栈和队列11 【正确答案】 C【试题解析】 调用函数时，系统会将调用者构造一个由参数表和返回地址组成的活动记录，并将记录压入系统提供的栈中，若被调用函数有局部变量，也要压入栈中。【知识模块】 栈和队列12 【正确答案】 A【试题解析】 通常使用栈来处理函数或过程调用，c 错；使用栈可以模拟递归的过程，以此来消除递归，但对于单向递归和尾递归而
14、言，可以用迭代的方式来消除递归，A 对；不同的进栈和出栈组合操作，会产生许多不同的输出序列， B 错；队列和栈都是操作受限的线性表，但只有队列允许在表的两端进行运算，而栈只允许在栈顶方向进行操作，D 错。【知识模块】 栈和队列13 【正确答案】 B【试题解析】 通常情况下，递归算法在计算机实际执行的过程中包含很多的重复计算，所以效率会低。【知识模块】 栈和队列14 【正确答案】 B【试题解析】 在提取数据的时候必须保持原来数据的顺序，所以缓冲区的特性是先进先出，故排除 A、C、D，答案只能是 B。【知识模块】 栈和队列15 【正确答案】 B【试题解析】 图的广度优先搜索类似于树的层序遍历，同样
15、需要借助于队列。【知识模块】 栈和队列16 【正确答案】 C【试题解析】 对于对称矩阵的压缩存储，只需存储其对应的上三角或者下三角矩阵即可，元素个数为 n+(n-1)+(n-2)+1=n(n+1)2。【知识模块】 栈和队列17 【正确答案】 D【试题解析】 由于特殊矩阵中含有很多相同的元素或零元素，故可以不给他们分配存储空间，从而达到节省内存的目的。【知识模块】 栈和队列18 【正确答案】 A【试题解析】 此题要注意 3 个细节：矩阵的最小下标为 0；数组下标也是从 0 开始的；矩阵按行优先存在数组中。注意到此三点答案不难得到为 A。此外，本类题建议采用特殊值代入法求解，例如，A11对应的下标
16、应为 2，代入后只有 A 满足条件。【知识模块】 栈和队列19 【正确答案】 C【知识模块】 栈和队列20 【正确答案】 D【知识模块】 栈和队列21 【正确答案】 B【知识模块】 栈和队列二、综合题22 【正确答案】 1)实现删除具有最小值元素的函数。算法的基本设计思想：从前向后遍历线性表，用个变量记录最小值，同时用另一个变量记录最小值位置。遍历之后将最小值删除。算法的代码：DataType deleteMin(SeqL 5st 假定 0 号元素的值最小int i，pos=0；for(i=1；iLn)return false; 表空或者 i 不合理，终止操作value=Ldatai ；for
17、(int j=i+1；jLn)return false; 表空或者 i 不合理，终止操作value=Ldatai ；for(int j=i+1；jLn)return falSe; 表满或者参数不合理，终止操作for(int J=Ln; Ji ；J-)LdataJ=LdataJ-1jLdatai=value， 从第 i 个位置插入Ln+ ；retUrn true ;insertnoi4)从顺序表中删除具有给定值 X 的所有元素。算法的基本设计思想：从后向前遍历，一直找到具有 x 值的元素，然后依次将此后的元素前移。算法的代码：void deleteValue(SeqLiStL，DataType
18、value)int i，J ；for(i=Ln-1;i=0ji-) 循环，寻找具有 X 值的元素并删除if(Ldatai=value) 删除具有 x 值的元素for(J=i+1；J=t)return false；int i，j，for(i=Ln-1；i=0；i-) 循环，寻找在给定范围内的元素并删除它if(Ldatai=s L datai=t)return false；int i，J ，k，u；for(i=0j i=Ln)return false；for(J=i；JLn)return false，for(k=j，u=i；knextj p 为工作指针。本文中所有未定义指针都假设为全局定义L-ne
19、xt=NULL； 第一个结点成为尾结点while(P!=NULL)r=P-next；p-next=L； 将 P 结点插到 L 结点前面。L=pj L 指向新的链表“第一”元素结点。p=r；return L; invert【知识模块】 栈和队列24 【正确答案】 算法的基本设计思想：将头结点摘下，然后从第一个结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。算法的代码：LinkList invert(LinkList la)la 是带头结点的单链表p=la-next， p 为工作指针1a-next=NULL；while(p!=NULL)r=p-next; 暂存 P 的后
20、继p-next=la 一next; 将 P 结点前插入头结点后la-next=p;p=r;return 1a； invert【知识模块】 栈和队列25 【正确答案】 算法的基本设计思想：通过遍历的方式查找最小值结点，当找到最小值结点之后，判断是奇数还是偶数。若是奇数，通过赋值语句交换数值：若是偶数，删除后继结点。算法的代码：VOid MiniValue(LinkLiSt 1a)la 是数据域为正整数且无序的单链表，本算法查找最小值结点且打印若最小值结点的数值是奇数，则与后继结点值交换；否则，删除其直接后继结点p=la-next; 设 la 为头指针， P 为：p 作指针pre=p； pre 指
21、向最小值结点，初始假定首元结点值最小while(p-next!=NULL) p-next 是待比较的当前结点【知识模块】 栈和队列26 【正确答案】 VOid MiniDelete(LinkLiSt head)head 为带头结点的单链表的头指针，本算法按递增顺序输出单链表中各结点的数据元素，并释放结点所占的存储空间while(head-next!=NULL) 循环到仅剩头结点pre=head； pre 为元素最小值结点的前驱结点的指针p=pre-next； p 为工作指针while(P-next!=NULL)if(p-next-datanext-data)pre=p； 记住当前最小值结点的前
22、驱P=P-next；printf(pre-next-data)；输出元素最小值结点的数据u=pre-next， 删除元素值最小的结点，释放结点空间pre-next=u-next；free(u)； while(head-next!=NULL)free(head)； 释放头结点 MiniDelete【知识模块】 栈和队列27 【正确答案】 LinkList Union(LinkList la，LinkList ib)本算法将两链表合并成一个按元素值递减次序排列的单链表pa=la-next；pb=ib-next； pa，pb 分别为链表 la 和 ib 的工作指针la-next=NULL； la 作
23、结果链表的头指针，先将结果链表初始化为空while(pa!=NULLpb!=NULL) 当两链表均不为空时if(pa-datadata、r=pa-next； 将 pa 的后继结点暂存于 rpa-next=la-next； 将 pa 结点链入结果表中，同时逆置1a-next=pa；pa=r; 恢复 pa 为当前待比较结点elser=pb-next； 将 pb 的后继结点暂存于 rpb-next=la-next； 将 pb 结点链入结果表中，同时逆置la-next=pb ;pb=r； 恢复 pb 为当前待比较结点while(pa!=NULL) 将 la 表的剩余部分链入结果表中，并逆置r=pa-n
24、ext；pa-next=la-next ;la-next=pa，Pa=r；while(pb!=NULL)r=pb-next ;pb-next=la-next；la-next=pb；pb=r；retUrn a； Union【知识模块】 栈和队列28 【正确答案】 1)算法的基本设计思想：查找值为 e 的顶点，若未找到则返回 0，找到则进行后面的处理。找到值为 e 的顶点之后，删除顶点数组中的顶点。根据顶点对应的下标，删除邻接矩阵中对应的行和列。顶点数的值自减 1。算法的代码：int DeleteNode(struct MGraphG，ElemType e)从图 G 中删除顶点值为 e 的顶点，成
25、功返回 1，否则返回 0。可删除多个值为 e 的顶点int i，J t k；for(i=0； ivexnum; i+)f查找值为 e 的顶点，查找成功时 i 小于 vexnum，查找失败时 i 等于 vexnumif(vexsi=e)for(J=i；Jvexnum-1 ；j+) 查找成功时删除对应的顶点和边fvexsJ：vexsJ+1；for(k=0; kvexnum；k+)arcsJk=arcSJ+lk;arcskJ=arcskJ+1；vexnum-; 顶点数自减 1return 1；if(i=vexnum) 查找顶点失败返回 0retUrn 0；DeleteNode2)算法的基本设计思想：
26、查找值为 a 的顶点，若未找到则返回 0，找到则记录对应的顶点数组下标。查找值为 b 的顶点，若未找到则返回 0，找到则记录对应的顶点数组下标。根据顶点 a、b 对应的数组下标，将邻接矩阵中对应的元素置为0。算法的代码：int DeleteEdge(struct MGraphG，ElemType a，ElemType b) 从图 G 中删除边(a，b)，成功返回 1，否则返回 0int i，ta=0，tb=0； ta、tb 分别记录 a 和 b 对应的顶点数组下标for(i=0;ivexnum; i+)if(vexsi=a)ta=i;else if(vexSi=b)tb=i；if(tatb) ta、tb 皆不为 0 意味着已找到 a、b 两个顶点break， 查找失败则 i 等于 vexnumif(i=vexnum) 查找顶点失败返回 0retUrn 0，arcstatb=0；arcstbta=0；return 1；DeleteEdge【知识模块】 栈和队列
