数据结构：栈和队列

单选题：1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为_____。A.top不变B.top＝-nC.top＝top-1D.top=top+12.向顺序栈中压入元素时，是_____。A.先移动栈顶指针，后存入元素B.先存入元素，后移动栈顶指针3.在一个顺序存储的循环队列中，队首指针指向队首元素的_____。A.前一个位置B.后一个位置C.队首元素位置4.若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。A.3,4,2,1B.2,4,3,1C.1,4,3,2D.3,2,1,45.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是_____。A.front==rear+1B.front+1==rearC.front==rearD.front==06.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是_____。A.\rear%n==frontB.(rear-1)%n==frontC.(rear-1)%n==rearD.(rear+1)%n==front7.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。A.hs-next=s;B.s-next=hs-next;hs-next=s;C.s-next=hs；hs=s;D.s-next=hs;hs=hs-next;8.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行_____。A.front-next=s;front=s;B.rear-next=s;rear=s;C.front=front-next;D.front=rear-next;9.栈的特点是_______队的特点是______A.先进先出B.先进后出B|A10.栈和队列的共同点是_______。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点11.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。A.edcbaB.decbaC.dceabD.abcde12.若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1i=n)为________。A.iB.n=IC.n-i+1D.不确定13.若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若pn=n,则pi(i=in)为_______。A.iB.n=IC.n-i+1D.不确定14.若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn，若p1=3,则p2_______。A.可能是2B.一定不是2C.可能是1D.一定是115.若己知一个栈的进栈序列p1,p2,p3,…,pn,输出序列是1,2,3,…,n,若p3=1,则p1________。A.可能是2B.一定是2C.不可能是2D.不可能是316.若己知一个栈的进栈序列p1,p2,p3,…,pn,输出序列是1,2,3,…,n,若p3=1,则p1________。A.n-i+1B.n-iC.iD.有多种可能17.判定一个顺序栈st(最多元素为MaxSize)为空的条件是_______。A.st-top!=-1B.st-top==-1C.st-top!=MaxSize-1D.st-top==MaxSize-118.判定一个顺序栈st(最多元素为MaxSize)为栈满的条件是_______。A.st-top!=-1B.st-top==-1C.st-top!=MaxSize-1D.st-top==MaxSize-119.最不适合用作链栈的链表是________。A.只有表头指针没有表尾指针的循环双链表B.只有表尾指针没有表头指针的循环双链表C.只有表尾指针没有表头指针的循环单链表D.只有表头指针没有表尾指针的循环单链表20.向一个栈项指针为hs的链栈中插入一个s所指结点时，则执行_______。A.hs-next=s;B.s-next=hs-next;hs-next=s;C.s-next=hs;hs=s;D.s-next=hs;hs=hs-next;21.从一个栈项指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行______。A.x=hs;hs=hs-next;B.x=hs-data;C.hs=hs-next;x=hs-data;D.x=hs-data;hs=hs-next;22.一个队列的入队序列是1,2,3,4,则队列的输出序列是_______。A.4,3,2,1B.1,2,3,4,C.1,4,3,2D.3,2,4,123.判定一个环形队列qu(最多元素为MaxSize)为空的条件是________。A.qu-rear-qu-front==MaxSizeB.qu-rear-qu-front-1==MaxSizeC.qu-front==qu-rearD.qu-front==qu-rear+124.判定一个环形队列qi(最多元素为MaxSize)为满队列的条件是________。A.(qu-rear+1)%MaxSize==qu-frontB.qu-rear-qu-front-1==MaxSizeC.qu-front==qu-rearD.qu-front==qu-rear+125.环形顺序队列中是否可以插入下一个元素,________。A.与队头指针的队尾指针的值有关B.只与队尾指针的值有关,与队头指针的值无关C.只与数组大小有关,与队首指针和队尾指针的值无关D.与曾经进行过多少次插入操作有关26.环形队列用数组A[0...MaxSize-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列的元素个数是_______。A.(rear-front+MaxSize)%MaxSizeB.rear-front+1C.(rear-front-1)%MaxSizeD.(rear-front)%MaxSize27.若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是______。A.1和5B.2和4C.4和2D.5和128.最不适合用作链队的链表是______。A.只带队头指针的非循环双链表B.只带队头指针的循环双链表C.只带队尾指针的循环双链表D.只带队尾指针的循环单链表29.在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是_______。A.f-next=s;f=s;B.r-next=s;r=s;C.s-next=r;r=s;D.s-next=f;f=s;30.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是_______。A.r=f-next;B.r=r-next;C.f=f-next;D.f=r-next;31.用单链表表示的链队的队头在链用不着的________位置。A.链头B.链尾C.链中D.任意32.中缀表达式A*(B+C)/(D-E+F)的后缀表达式是________。A.A*B+C/D-E+FB.AB*C+D/E-F+C.ABC+*DE-+/D.ABCDEF*+/-+33.己知一个栈的进栈序列是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,pop34.判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为______。A.st.top==-1B.st.top!=-1C.st.top!=MaxSizeD.st.top==MaxSize35.判定一个顺序栈st(元素个数最多为MaxSize)为栈满的条件是______。A.st.top!=-1B.st.top==-1C.st.top!=MaxSize-1D.st.top==MaxSize-136.表达式a*(b+c)-d的后缀表达式是______。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd37.表达式(2+2*3)*2+6*3/2的后缀表达式是______。A.223*+2*63*2/+B.22*3+2*63*2/+C.223*2*63*+2/+D.223*+263*2/+*38.链栈与顺序栈相比有一个明显的优点,即______。A.插入操作更方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便39.最不适合用作链栈的链表是______。A.只有表头指针没有表尾指针的循环双链表B.只有表尾指针没有表头指针的循环双链表C.只有表尾指针没有表头指针的循环单链表D.只有表头指针没有表尾指针的循环单链表40.如果以链表作为栈的存储结构,则退链栈操作时______。A.必须判别栈是否满B.判别链栈元素的类型C.必须差别链栈是否空D.对链栈不作任何差别41.向一个不带头结点的栈指针为1st的链栈中插入一个s所指结点时,则执行______。A.1st-next=s;B.s-next=1st-next;1st-next=s;C.s-next=1st;1st=s;D.s-next=1st;1st=1st-next;42.从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行______。A.x=1st;1st=1st-next;B.x=1st-data;C.1st=1st-next;x=1st-data;D.x=1st-data;1st=1st-next;43.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是______.A.edcbaB.decbaC.dceabD.abcde44.在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为_________。A.nB.n/2C.(n+1)/2D.(n-1)/245.在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为_________。A.O(1)B.O(n)C.O(n*n)D.O(lbn)46.已知一个元素x不属于一个长度为n的顺序或链接存储的集合Ｓ中的元素，把它插入集合Ｓ时不进行比较过程，则插入过程的时间复杂度为_________。A.O(1)B.O(lbn)C.O(n)D.O(n*n)47.设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为_________。A.O(m)B.O(n)C.O(n+t)D.O(n*t)判断题：1.栈底元素是不能删除的元素。F2.顺序栈中元素值的大小是有序的。F3.在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反。T4.栈顶元素和栈底元素有可能是同一个元素。T5.若用S[1]-S[m]表示顺序栈的存储空间,则对栈的进栈、出栈操作最多只能进行m次。F6.栈没有栈顶指针。F填空题：1.在具有n个单元、顺序存储的循环队列中，队满时共有______个元素。n-12.栈和队列的区别仅在于________。删除运算的不同3.通常元素进栈的操作是________。先移动栈顶指针，后存入元素4.通常元素退栈的操作是________。先取出元素，后移动栈顶指针5.一个栈的输入序列是12345,则栈的输出序列432512是__________。不可能的6.一个栈的输入序列是12345,则栈的输出序列12345是________。可能的7.设