数据结构（山东联盟-滨州学院）答案2023

第三章测试

1.

设abcdef以所给次序进栈，若在进栈操作时允许退栈，则下列得不到的序列为（）

A:fedcba   B:cabdef C:dcefba   D:bcafed  
答案:B
2.

若已知一个栈的进栈序列是1，2，3……n，其输出序列是p₁，p₂，p₃，p_n， 若p₁=3，

则p₂为（）

A:一定是2 B:可能是1
C:可能是2
D:一定是1 3.

假定循环队列的队首和队尾指针分别为front和rear，则判断队满的条件为（ ）。

A:front+1 = = rear       B:front = = 0      C:(rear＋1) mod MAXSIZE = = front D:front= =rear 4.

队列和栈都是运算受限的线性表，只允许在表的两端进行运算。

A:对 B:错 5.

循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(      )。

A:rear-front-1     B:rear-front+1  C:(rear-front+m)%m D:rear-front 6.

不论栈是用数组实现，还是用链表实现，入栈和出栈的时间复杂度均为O(n)。

A:错 B:对 7.

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

A: top[1]+1=top[2]
B:|top[2]-top[1]|=0  
C:top[1]+top[2]=m 
D:top[1]=top[2]
8.

输入序列为ABC，若出栈的顺序为CBA时，经过的栈操作为（  ） 。      

A:push,pop,push,pop,push,pop     B:push,push,push,pop,pop,pop C:push,pop,push,push,pop,pop D:push,push,pop,pop,push,pop 9.

链栈与顺序栈相比，有一个比较明显的优点是（ ）。

A:删除操作更方便 B:会出现栈空的情况    C:通常不会出现栈满的情况 D: 插入操作更方便  10.

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

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

某队列允许在其两端进行入队操作，但只允许在一端进行出队操作，若有元素a, b, c, d, e依次入队后再进行出队操作，则不可能得到的出队序列是（）。

A:d,b,a,c,e B:d,b,c,a,e C:e,c,b,a,d D:b,a,c,d,e 12.

有如下递归算法：

int fact(int n){//n大于等于0    if(n<=0)  return 1;    else        return n*fact(n-1);}

则计算fact(n)需调用该函数的次数是（）。

A:n+1 B:n C:n+2 D:n-1 13.

设有一个递归算法如下

        int fact(int n) {  //n大于等于0

             if(n<=0) return 1;

             else return n*fact(n-1);        }

则计算fact(n)需要调用该函数的次数为（  ）。

A:n+2
B:n-1
C:n+1 D:n 14.

（  ）的一个重要应用是在程序设计语言中实现递归。

A:栈 B:顺序表    C:数组     D:队列     15.

通常使用队列来处理函数或过程的调用。

A:错 B:对 16.

栈和队列的存储方式，既可以是顺序方式，又可以是链式方式

A:错 B:对 17.

若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：（　 ）。

A:4->1->2 B:2->3->4 C:1->2->3 D:状态不唯一