数据结构-作业4

参考教材：数据结构教程（Java语言描述)        作者：李春葆

1 . 容易 （4分）设固定容量的循环队列中数组的下标是0～N-1，其队头队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为______。

A. r-f

B. r-f-1

C. (r-f)％N+1

D. (r-f+N)％N

2 . 容易 （4分）设固定容量的循环队列的存储空间为a[0..20]，且当前队头指针和队尾指针的值分别为8和3，则该队列中元素个数为______。

A. 5

B. 6

C. 16

D. 17

3 . 容易 （4分）假设用一个不带头结点的单链表表示队列，队尾在链表的______ 位置。

A. 链头

B. 链尾

C. 链中

D. 以上都可以

4 . 容易 （4分）最不适合用做链队的链表是______。

A. 只带头结点指针的非循环双链表

B. 只带队首结点指针的循环双链表

C. 只带队尾结点指针的循环双链表

D. 以上都不适合

5 . 容易 （4分）若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次出栈工作，则不可能得到的出栈序列是______。

A. dcebfa

B. cbdaef

C. bcaefd

D. afedcb

6 . 容易 （4分）一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是______。

A. edcba

B. decba

C. dceab

D. abcde

7 . 容易 （4分）已知一个栈的进栈序列是1，2，3，…，n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是______。

A. i

B. n-i

C. j-i+1

D. 不确定

8 . 容易 （4分）已知一个栈的进栈序列是1，2，3，…，n，其输出序列是p1，p2，…，pn，若p1=n，则pi的值______。

A. i

B. n-i

C. n-i+1

D. 不确定

9 . 容易 （4分）设有5个元素进栈序列是a、b、c、d、e，其输出序列是c、e、d、b、a，则该栈的容量至少是______。

A. 1

B. 2

C. 3

D. 4

10 . 容易 （4分）设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为______。

A. 一定是2

B. 一定是1

C. 不可能是1

D. 以上都不对

11 . 容易 （4分）由两个栈共享一个数组空间的好处是______。

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

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

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

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

12 . 容易 （4分）算术表达式(a+a*b)*a+c*b/a的后缀表达式是______。

A. a a b * + a * c b * a / +

B. a a * b + a * c b * a / +

C. a a b * a * c b * + a / +

D. a a b * + a c b * a / + *

13 . 容易 （4分）将算术表达式“1+6/(8-5)*3”转换成后缀表达式，在求后缀表达式的过程中，当遇到'*'时，运算数栈（从栈顶到栈底次序）为______。

A. 8 6 1

B. 5 8 1

C. 3 2 1

D. 3 6 1

14 . 容易 （4分）当用一个数组data[0..n-1]存放栈中元素时，栈底最好______。

A. 设置在data[0]处

B. 设置在data[n-1]处

C. 设置在data[0]或data[n-1]处

D. 设置在data数组的任何位置

15 . 容易 （4分）若一个栈元素用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进栈最适合的操作是______。

A. top++; data[top]=x;

B. data[top]=x; top++;

C. top--; data[top]=x;

D. data[top]=x; top--;

16 . 容易 （4分）若一个栈元素用数组data[1..n]存储，初始栈顶指针top为n，则以下出栈元素x最适合的操作是______。

A. x=data[top]; top++;

B. top++; x=data[top];

C. x=data[top]=x; top--;

D. top--; x=data[top];

17 . 容易 （3分）若一个栈元素用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈最适合的操作是______。

A. top++; data[top]=x;

B. data[top]=x; top++;

C. top--; data[top]=x;

D. data[top]=x; top--;

18 . 容易 （3分）若一个栈元素用数组data[1..n]存储，初始栈顶指针top为0，则以下出栈元素x最适合的操作是______。

A. x=data[top]; top--;

B. x=data[top]; top++;

C. top--; x=data[top];

D. top++; x=data[top];;

19 . 容易 （3分）有关链栈的叙述中正确的是______。

A. 链栈在进栈操作时一般不需要考虑上溢出

B. 链栈在出栈操作时一般不需要考虑下溢出

C. 链栈和顺序栈相比的缺点是不能随机访问栈中元素

D. 以上都不对

20 . 容易 （3分）以下各链表均不带有头结点，其中最不适合用作链栈的链表是______。

A. 只有表头指针没有表尾指针的循环双链表

B. 只有表尾指针没有表头指针的循环双链表

C. 只有表尾指针没有表头指针的循环单链表

D. 只有表头指针没有表尾指针的循环单链表

21 . 容易 （3分）栈和队列的共同点是______。

A. 都是先进后出

B. 都是后进先出

C. 只允许在端点处插入和删除元素

D. 没有共同点

22 . 容易 （3分）和队列的不同点是______。

A. 都是线性表

B. 都不是线性表

C. 栈只能在同一端进行插入删除操作，而队列在不同端进行插入删除操作

D. 没有不同点

23 . 容易 （3分）循环队列______。

A. 不会产生下溢出

B. 不会产生上溢出

C. 不会产生假溢出

D. 以上都不对

24 . 容易 （3分）某循环队列的元素类型为char，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素，如图1.6所示，则队中从队头到队尾的元素为______。

A. abcd123456

B. abcd123456c

C. dfgbca

D. cdfgbca

25 . 容易 （3分）若某循环队列有队首指针front和队尾指针rear，在队不空时出队操作仅会改变______。

A. front

B. rear

C. front和rear

D. 以上都不对

26 . 容易 （3分）若某循环队列有队头指针front和队尾指针rear，在队不满时进队操作仅会改变______。

A. front

B. rear

C. front和rear

D. 以上都不对

27 . 容易 （3分）已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是______。

A. 0，0

B. 0，n-1

C. n-1，0

D. n-1，n-1

28 . 容易 （3分）设循环队列qu中数组data的下标是0～N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），元素x出队的操作是______ ; x=qu.data[qu.f]。

A. qu.r++

B. qu.r=(qu.r+1)%N

C. qu.f++;

D. qu.f=(qu.f+1)%N