1、 如果数据是在程序运行过程中逐步产生的，并且要求先产生的数据元素后处理，后产生的数据元素先处理，则最适合的数据结构是（     ）

A. 顺序表        B. 顺序栈   C. 顺序队列    D. 堆

2、队和栈的共同点是（       ）

 A. FIFO        B. 都是线性表   C. LIFO     D. 没有共同点

3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（    ）。

A. 不确定          B. n-i+1          C.  i           D. n-i

4、两个栈共享一个向量空间的好处是（         ）

A.减少存取时间，降低上溢发生的几率     

B.节省存储空间，降低上溢发生的几率         

C.减少存取时间，降低下溢发生的几率          

D.节省存储空间，降低下溢发生的几率

5、执行（         ）操作时，需要使用队列做辅助存储空间。

A. 查找哈希（Hash）表          B.广度优先搜索图         

C.  先序（根）遍历二叉树       D.深度优先搜索图

6、 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(    )。

    A. i            B. n-i        C. n-i+1       D. 不确定

7、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（    ）

A. 5 4 3 6 1 2     B. 4 5 3 1 2 6     C. 3 4 6 5 2 1    D. 2 3 4 1 5 6

8、输入序列为ABC，可以变为CBA时，经过的栈操作为（    ）【中山大学 1999 一、8(1分)】

A. push,pop,push,pop,push,pop       B. push,push,push,pop,pop,pop

    C. push,push,pop,pop,push,pop       D. push,pop,push,push,pop,pop

9、 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（    ）。

A. |top[2]-top[1]|=0       B. top[1]+1=top[2]  

 C. top[1]+top[2]=m         D. top[1]=top[2]

10、 设计一个判别表达式中左，右括号是否配对出现的算法，采用（    ）数据结构最佳。

A．线性表的顺序存储结构   B. 队列    C. 线性表的链式存储结构   D. 栈

【西安电子科技大学 1996 一、6（2分）】

11、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(     )。【北京理工大学 2001 六、3（2分）】

A．仅修改队头指针            B. 仅修改队尾指针

C. 队头、队尾指针都要修改    D. 队头,队尾指针都可能要修改

12、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(    )。【南京理工大学 2001 一、5（1.5分）】

A. (rear-front+m)%m       B. rear-front+1 

 C.  rear-front-1          D.  rear-front

13、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？(  )【浙江大学1999 四、1(4分)】

A. 1和 5         B. 2和4          C. 4和2         D. 5和1 

14、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是(    )。

A． 6          B. 4          C. 3          D. 2

15、利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是（       ）

A． A-B*(C-D)     B. (A-B)*C-D     C. (A-B*C)-D     D. (A-B)*(C-D)

16、(       )不是栈的基本运算。

A． 删除栈顶元素         B. 删除栈底元素   

C. 判断栈是否为空        D. 将栈置为空栈

17、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（         ）

A．rear%n=front          B. (front+1)%n=rear  

C. rear%n-1=front        D. (rear+1)%n=front

18、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程要比非递归过程（     ）。

A． 较快     B. 较慢     C. 相同     D. 无法比较

19、向一个栈顶指针为top的链栈中插入一个s节点，则执行（     ）。

A． top->next=s;             B. s->next=top->next;top->next=s;   

C. s->next=top;top=s;        D. s->next=top; top=top->next;

20、单循环链表表示的队列长度为n，若只设头指针，则进队的时间复杂度为（ ）。

A． O(n)     B. O(1)     C. O(n²)     D. O(nlogn)

21、 栈和队列的共同点是（    ）。【燕山大学 2001 一、1（2分）】

A. 都是先进先出                        B. 都是先进后出  

C. 只允许在端点处插入和删除元素        D. 没有共同点

22、 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是  （    ）。

     A. (rear+1)% n=front                      B. rear=front                                                         

C．rear+1=front                           D. (rear-l)% n=front

【南京理工大学 1999  一、16（2分）】

23、已知循环队列的存储空间为数组a[21]，且当前队列的头指针和尾指针的值分为8和3，则该队列的当前长度为（     ）

A． 5     B. 6     C. 16     D. 17

24、 递归过程或函数调用时，处理参数及返回地址，要用一种称为（    ）的数据结构。

A．队列         B．多维数组          C．栈           D. 线性表

【福州大学 1998 一、1（2分）】

25、 栈在（    ）中应用。【中山大学 1998 二、3（2分）】

A. 递归调用        B. 子程序调用       C. 表达式求值    D. A，Ｂ，Ｃ

26、 一个递归算法必须包括（    ）。【武汉大学 2000 二、2】

A. 递归部分           B. 终止条件和递归部分    

C. 迭代部分           D.终止条件和迭代部分

27、 表达式a*(b+c)-d的后缀表达式是(    )。【南京理工大学 2001 一、2（1.5分）】

A．abcd*+-     B. abc+*d-    C. abc*+d-     D. -+*abcd

28、 表达式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；(*^(-

【青岛大学 2000 五、5（2分）】

29、 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是(   )。【西安电子科技大学 1996 一、5（2分）】课本P60.

A. 1234         B. 4132          C. 4231         D. 4213

30、已知一循环队列的容量为70（序号从1到70），现经过一系列入队与出队运算后，有front=20，rear=11，则队列中元素个数为（   ）。

31、循环队列用数组V[m…n]存放其元素值，且n>m，已知其头尾指针分别是f和r，f指向队首元素，r指向队尾元素的后一位置，则当前队列中的元素个数是（   ）。

32、假设用一个大小为8的数组来实现循环队列，当前rear和front的值分别是0和5.当从队列中增加2个元素，再删除3个元素后，rear和front的值分别为（      ）。

33、设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为（      ）。

34、如果一个队列有N个数，首先，a，b，c，d依次进入该队列，然后又有6个数出队列，这时c位于队头，则N=（     ）。

35、 栈的特点是（  ①  ）,队列的特点是（  ②  ）,栈和队列都是（  ③  ）。若进栈序列为1,2,3,4 则（  ④  ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（  ⑤  ）是一个出队列序列。【北方交通大学 1999 一、1（5分）】

①, ②: A. 先进先出          B. 后进先出        C. 进优于出      D. 出优于进

③: A.顺序存储的线性结构     B.链式存储的线性结构 

C.限制存取点的线性结构   D.限制存取点的非线性结构

④, ⑤: A. 3,2,1,4    B. 3,2,4,1    C. 4,2,3,1   D. 4,3,2,1    F. 1,2,3,4    G. 1,3,2,4

36、任何一个递归过程都可以转换成非递归过程。（　　）【上海交通大学 1998一、3（1分）】

37、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。【西安电子科技大学 1998 二、1（4分）】

38、两个栈共享空间时栈满的条件_______。

39、在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。【山东工业大学 1994 一、1（5分）】

40、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。【西南交通大学 2000 一、5】

41、设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。

sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；(sq.rear+1)%(M+1)==sq.front；