考研计算机－习题精炼和重点回顾 栈、队列、数组

考研计算机－习题精炼和重点回顾 栈、队列、数组内容摘要：

考研计算机－习题精炼和重点回顾 栈、队列、数组 1栈和队列的相同之处是 正确答案是：【C 】解析：栈和队列都是特殊的线性表。 栈和队列中的数据元素之间的逻辑关系与线性表中的数据元素之间的逻辑关系完全相同，但它们的运算时不同的。 栈将插入和删除操作限制在表的一端进行，而队列将插入和删除操作分别限制在表的两端进行。 它们的共同点是只允许在表的端点处进行插入和删除操作。 2某栈的输入序列为 1，2，3，4 ，下面的四个序列中不可能是它的输出序列为 ，2，4 ，4 ，1 ，1，2 ，2，1 正确答案是：【C 】解析：若某栈的输入序列为 1，2，3 ，4，按照出栈操作的原则，不可能得到出栈序列4，3 ， 1，2。 这是由于出栈序列的第一个元素为 4，则必须首先一次将1，2 ， 3，4 进栈，然后将此时的栈顶元素 4 出栈，此时新的栈顶元素为 3，继续将 3 出栈（注意，此时的出栈序列为 4，3 ），按照题目的要求，出栈序列的下一个元素应该是 1，而此时新的栈顶元素为 2，而不是 1，因此，得不到元素1，导致不能够得到序列 4，3 ，1，2。 3设栈的初始状态为空，当字符序列 出长度为 3 的且可用作 C 语言标识符的序列的数目是 正确答案是：【A】解析：本题主要考查的内容有两个：C 语言关于标识符的规定和栈的先进后出的特性。 标识符的第一个字符必须是大小写英文字符或者下划线，而不能是数字。 按照上述规定 1，_1n，_种形式。 字符按照 据栈的先进后出的特性，输出的顺序只能出现前三种形式：第一种输出 n 进栈再出栈，1 进栈再出栈， _进栈再出栈；第二种输出 的实现：n 进栈再出栈，1 进栈_进栈，_出栈 1 出栈；第三种输出_1n 的实现：n 进栈 1 进栈_进栈，_ 出栈 1 出栈 n 出栈。 而输出_情况不可能实现。 4若某栈的输入序列是 1，2 ，3，n，输出序列的第 1 个元素为 i，则第 j 个输出元素为 正确答案是：【D】解析：当 i 第一个出栈时，1,2，压在栈内，之后还可能有 i 之后的元素进栈，究竟第 j 个出栈元素是哪一个是不确定的。 5设栈的输入序列为 p1，p2， ，出序列为 1，2，3，n ，若存在 3，则当 正确答案是：【B】解析：当 时，输入序列为 p1，因为输出的第 3 个元素是 3，则有多种可能：当 ， 时，允许的进栈、出栈的顺序是 栈 栈 栈。 当 ， 时，允许的进栈、出栈的顺序是 栈 栈 栈。 如果 p1、 进栈不出，当 ，时，允许的进栈、出栈的顺序是 栈 栈 栈 栈。 因此可以断定 或 是可能的选择，但不是一定的选择。 6若进栈序列为 a，b ，c，则通过出栈操作可能得到的 a，b，c 的不同排列的数目为 正确答案是：【C 】解析：这里需要注意的是：a，b，c 这 3 个字母不一定要全部进栈以后再出栈，为此就有了多种排列的可能。 本题如果按照正向思维来解的话，我们要考虑各种进栈出栈的可能性，这样很同意漏解，而且思维比较乱。 我们可以逆向的解此题，3 个字母最多的排列个数也就是 3*2*1=6 种可能性，然后这 6 种可能情况一一考虑是否符合进栈出栈的场景，这样比较清晰地得到答案。 （1）出栈序列为 a，b，c：a 进栈，a 出栈，b 进栈， b 出栈，c 进栈，c 出栈。 （2）出栈序列为 a，c ，b：a 进栈，a 出栈，b 进栈， c 进栈，c 出栈，b 出栈。 （3）出栈序列为 b，c ，a ：a 进栈，b 进栈，b 出栈，c 进栈，c 出栈，a 出栈，。 （4）出栈序列为 b，a，c：a 进栈，b 进栈，b 出栈，a 出栈，c 进栈，c 出栈。 （5）出栈序列为 c，a，b：不可能出现该顺序。 （6）出栈序列为 c，b，a ：a 进栈，b 进栈，c 进栈，c 出栈，b 出栈，a 出栈，。 7若元素 a,b,c,d,e,f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是 A.d,c,e,b,f,a B.c,b,d,a,e,f C.b,c,a,e,f,d D.a,f,e,d,c,b 正确答案是：【D】解析：本题考查栈的基本概念，是一种常见的考查方式。 4 个选项所给序列的进、出栈操作序列分别为：选项 A. 项 B. 项 C. 项 D. 项 D 所给序列为不可能得到的出栈顺序。 8若栈采用顺序存储方式存储，现两栈共享空间 V1.i代表第 i 个栈（i=1，2）的栈顶，栈 1 的底在 V1，栈 2 的底在 Vm，则栈满的条件是 = = 0 +1= = + = = m = = 正确答案是：【B】解析：两个栈共享一个空间的时候，由于栈底是固定的且有两个，所以栈底一定的是该空间的两端，然后数据存放在中间。 所以栈满的条件是两个栈顶相邻，也就是 +1= =。 9最不适合用作链栈的链表是 正确答案是：【D】解析：链栈一般不带头结点，进栈和出栈操作均在表头进行。 对于选项 A 只有表头指针没有表尾指针的循环双链表，在表头插入和删除一个结点的时间复杂度为 O(1)和 O(1)。 对于选项 B 只有表尾指针没有表头指针的循环双链表，在表头插入和删除一个结点的时间复杂度为 O(1)和 O(1)。 对于选项 C 只有表尾指针没有表头指针的循环单链表，在表头插入和删除一个结点的时间复杂度为 O(1)和 O(1)。 对于选项 D 只有表头指针没有表尾指针的循环单链表，在表头插入和删除一个结点的时间复杂度为 O(n)和 O(n)（在表头插入和删除一个结点仍需将其变为一个循环单链表，这时通过查找到尾结点，再将其 置为第一个结点来实现）。 注意：若所有链表带头结点，则其结果完全相同。 10当执行函数时，其局部变量的存储一般采用下列哪个结构进行存储 正确答案是：【C 】解析：调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将记录压入系统提供的栈中，若被调用函数有局部变量，也要压入栈中。 11表达式 a*(b+c)后缀表达式是 - 正确答案是：【B】解析：答案显然是 B。 考生需熟悉中缀表达式转变为后缀表达式的算法，这是一种常考题型，也可以出程序题。 其基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。 只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）。 表达式 a*(b+c)生后缀表达式的过程如下表所示：但是对于选择题，也可以将后缀表达式转变为中缀表达式，以 其转换成中缀表达式的过程如下：从左向右扫描，遇到的第一个操作符是+，前面最靠近的操作数是 该是 b+c；此刻将 b+c 作为一个操作数，继续扫描得到操作符是*，前面最靠近的操作数是 a 和（b+c），则得到a*（b+c ）；此时 a*（b+c ）是一个操作数，继续扫描得到-，前面操作数为a*（b+c ）和 d，最终得到 a*（b+c）2解决 问题的递归算法，其时间复杂度是 A.O(n) B. C. D.O(n!) 正确答案是：【C 】解析：本题主要考查递归函数时间复杂度的计算。 法的时间复杂度的递推关系式是 T(n)=2T(1，解此关系式得到 T(n)= 2n 此时间复杂度为O(2n)13若用一个大小为 6 的数组来实现循环队列，且当前 值分别为0 和 3，当从队列中删除一个元素，再加入两个元素后， 值分别为 5 4 2 1 正确答案是：【B】解析：本题主要考查循环队列的基本操作，删除一个元素后，；加入两个元素后，14循环队列用数组 A0.放其元素值，已知其队头指针 向队头元素，队尾指针 向队尾元素，则当前队列的元素的个数是 A.（m ）m C.（m+1）m D.（OD m 正确答案是：【C 】解析：注意本题需注意，队尾指针 向队尾元素，并非指向队尾元素的下一个位置。 当 ，队列的元素个数是 ；当 情况，则说明要将 到 上，也就是在 栈之后 能出栈。 这就说明，对于 ，指向待处理结点s); /初始化栈 p!= /循环到头结点为止 p->(: s,p-> ): s)|s)!=() 括号不配对n”); ; s);: s,p-> : s)| s)!=) 括号不配对n”); ; s);: s,p-> : s)| s)!=) 括号不配对n”); ;s); p=s) 括号配对n”。