第3课栈队列和数组

第三课栈、队列和数组一选择题1．对于栈操作数据的原则是（）。A．先进先出B．后进先出C．后进后出D．不分顺序2．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A．不确定B．n-i+1C．iD．n-i3．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。A．i-j-1B．i-jC．j-i+1D．不确定的4．设abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的出栈序列为（）。A．fedcbaB．bcafedC．dcefbaD．cabdef5．输入序列为ABC，可以变为CBA时，经过的栈操作为（）A．push,pop,push,pop,push,popB．push,push,push,pop,pop,popC．push,push,pop,pop,push,popD．push,pop,push,push,pop,pop6．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）。A．top=top+1;V[top]=xB．V[top]=x;top=top+1C．top=top-1;V[top]=xD．V[top]=x;top=top-17．若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A．|top[2]-top[1]|==0B．top[1]+1==top[2]C．top[1]+top[2]==mD．top[1]==top[2]8．执行完下列语句段后，i值为：（）。intf(intx){return((x0)?x*f(x-1):2);}inti;i=f(f(1));A．2B．4C．8D．无限递归9．表达式a*(b+c)-d的后缀表达式是（）。A．abcd*+-B．abc+*d-C．abc*+d-D．-+*abcd10．表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。A．3,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[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A．(rear-front+m)%mB．rear-front+1C．rear-front-1D．rear-front14．循环队列存储在数组A[0..m]中，则入队时的操作为（）。A．rear=rear+1B．rear=(rear+1)mod(m-1)C．rear=(rear+1)modmD．rear=(rear+1)mod(m+1)15．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（）A．1和5B．2和4C．4和2D．5和116．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A．(rear+1)MODn==frontB．rear==frontC．rear+1==frontD．(rear-l)MODn==front17．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（）。A．6B．4C．3D．218．数组A[0..4,-1..-3,5..7]中含有元素的个数（）。A．55B．45C．36D．1619．设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（）。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D．j*m+i-120．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A．13B．33C．18D．4021．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。A．BA+141B．BA+180C．BA+222D．BA+22522．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（）。A．1175B．1180C．1205D．121023．将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（）。A．198B．195C．197D．19624．对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度25．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A．60B．66C．18000D．33二、应用题1．有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？2．如果输入序列为123456，试问能否通过栈结构得到以下两个序列:435612和135426，请说明为什么不能或如何才能得到。3．试证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着ijk,使PjPkPi。参考答案：如果ij，则对于pipj情况，说明pi在pj入栈前先出栈。而对于pipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于ijk，不可能出现pjpkpi的输出序列。换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。4．用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。参考答案：中缀表达式8-(3+5)*(5-6/2）的后缀表达式是：835+562/-*-表达式生成过程为：中缀表达式exp1转为后缀表达式exp2的规则如下：设操作符栈s，初始为空栈后，压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。（1）w为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。（2）w为左括号（’（’），w入栈。（3）w为右括号（’）’），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。（4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到‘#’，退栈，整个操作结束。这里，再介绍一种简单方法。中缀表达式转为后缀表达式有三步：首先，将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来；接着，顺序将每对括号中的运算符移到相应括号的后面；最后，删除所有括号。例如，将中缀表达式8-(3+5)*(5-6/2）转为后缀表达式。按如上步骤：执行完上面第一步后为：(8-((3+5)*(5-(6/2))))；（2）835+562#*#（3）835+562/-（4）835+562/-*--#*（/）--）（1）835#（+-执行完上面第二步后为：(8((35)+(5(62)/)-)*)-；执行完上面第三步后为：835+562/-*-。可用类似方法将中缀表达式转为前缀表达式。5．设输入元素为1、2、3、P和A，输入次序为123PA。元素经过栈后达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名。6．简述如下算法功能。Statusex1(StackS,inte){InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}//ex17．写出如下程序段输出结果。voidex3(){charx='e',y='c';InitQueue(Q);EnQueue(Q,'h');EnQueue(Q,'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,'a');while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}//whileprintf(x);}//ex38．将如下递归过程改写为非递归过程。⑴voidtest(int&sum){intx;scanf(x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}⑵intack(intm,intn){if(!m)returnn+1;elseif(!n)returnack(m-1,1);elsereturnack(m-1,ack(m,n-1));}//ack9．三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7]的存贮首地址。10．若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，⑴A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？⑵A中任一个下三角元素aij(i≤j),在数组B中的下标位置k是什么？11．设有三对角矩阵(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=ai,j，求：⑴用i,j表示k的下标变换公式；⑵若n=103，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元。12．设有矩阵ａ且a=121133312，执行下列语句后，矩阵ｃ和ａ的结果分别是什么？⑴for(i=1;i=3;i++)for(j=1;j=3;j++)c[i][j]=a[a[i][j],a[j][i]];⑵for(i=1;i=3;i++)for(j=1;j=3;j++)a[i][j]=a[a[i][j],a[j][i]];三、算法设计题1．设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[0..maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。2．设从键盘输入一列整数：a1,a2,a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。3．假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。⑴下面所示的序