1、若用数组A[0…5]来实现循环队列，且当前rear和front的值分别为1和5，当从队列中删除一个元素，再加上两个元素后，rear和front的值分别为（）。
- A：3和4
- B：3和0
- C：5和0
- D：5和1
解析
循环队列中，每删除一个元素，队首指针front=(front+1)%6，每插入一个元素，队尾指针rear=(rear+1)%6。上述操作后，front=0，rear=3。
答案：B
2、在一个链队列中，假设队头指针为front，队尾指针为rear，x所指向的元素需要入队，则需要执行的操作为（）。
- A：front=x, front=front->next
- B：x->next=front->next, front=x
- C：rear->next=x, rear=x
- D：rear->next=x,x->next=null, rear=x
解析
插入操作时，先将结点x插入到链表尾部，再让rear指向这个结点x。C的做法不够严密，因为是队尾，所以队尾x->next必须置为空。
答案：D
3、若以1，2，3，4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是（）。
- A：1，2，3，4
- B：4，1，3，2
- C：4，2，3，1
- D：4，2，1，3
解析
使用排除法。先看可由输入受限的双端队列产生的序列：设右端输入受限，1，2，3，4依次左入，则依次左出可得4，3，2，1，排除A；右出、左出、右出、右出可得到4，1，3，2，排除B；再看可由输出受限的双端队列产生的序列：设右端输出受限，1，2，3，4依次左入、左入、右入、左入，依次左出可得到4，2，1，3，排除D。
答案：C
4、已知循环队列存储在一维数组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
解析
根据题意，第一个元素进入队列后存储在A[0]处，此时front和rear值都为0。入队时由于要执行（rear+1）%n操作，所以若入队后指针指向0，则rear初值为n-1，而由于第一个元素在A[0]中，插入操作只改变rear指针，所以front为0不变。
答案：B
5、循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（）。
-
A：队空：
end1==end2;
队满：
end1==(end2+1) mod M
-
B：队空：
end1==end2;
队满：
end2==(end1+1) mod (M-1)
-
C：队空：
end2==(end1+1) mod M；
队满：
end1==(end2+1) mod M
-
D：队空：
end1==(end2+1) mod M；
队满：
end2==(end1+1) mod (M-1)
解析
end1指向队头元素，可知出队操作是先从A[end1]读数，然后end1再加1。end2指向队尾元素的后一个位置，可知入队操作是先存数到A[end2]，然后end2再加1.若用A[0]存储第一个元素，队列初始时，入队操作是先把数据放到A[0]中，然后end2自增，即可知end2初值为0；而end1指向的是队头元素，队头元素在数组A中的下标为0，所以得知end1的初值也为0，可知队空条件
为end1==end2
；然后考虑队列满时，因为队列最多能容纳M-1个元素，假设队列存储在下标为0到M-2的M-1个区域，队头为A[0]，队尾为A[M-2]，此时队列满，考虑在这种情况下end1和end2的状态，end1指向队头元素，可知end1=0,end2指向队尾元素的后一个位置，可知end2=M-2+1=M-1，所以队满的条件为
end1==(end2+1) mod M
。
答案;A
6、执行（）操作时，需要使用队列作为辅助存储空间。
- A：查找散列（哈希）表
- B：广度优先搜索图
- C：前序（根）遍历二叉树
- D：深度优先搜索图
解析
图的广度优先搜索类似于树的层序遍历，都要借助于队列。
答案：B
7、串’ababaaababaa’的nextval数组为（）。
- A：0，1，0，1，1，2，0，1，0，1，0，2
- B：0，1，0，1，1，4，1，1，0，1，0，2
- C：0，1，0，1，0，4，2，1，0，1，0，4
- D：0，1，1，1，0，2，1，1，0，1，0，4
解析
nextval从0开始，可知串的位序从1开始。第一步，令nextval[1]=next[1]=0。
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 | 0 | 4 |
从j=2开始，依次判断
P
j
P_j
P
j
是否等于
P
n
e
x
t
[
j
]
P_{next[j]}
P
n
e
x
t
[
j
]
？若是则将next[j]修正为next[next[j]]，直至两者不相等为止。
答案：C
8、一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）。
- A：41
- B：82
- C：113
- D：122
解析
设树中度为i（i=0,1,2,3,4）的结点数分别为
n
i
n_i
n
i
，树中结点总数为n，则n=分支数+1，而分支数又等于树中各结点的度之和，即n=1+
n
1
n_1
n
1
+2
n
2
n_2
n
2
+3
n
3
n_3
n
3
+4
n
4
n_4
n
4
=
n
0
n_0
n
0
+
n
1
n_1
n
1
+
n
2
n_2
n
2
+
n
3
n_3
n
3
+
n
4
n_4
n
4
。依题意，
n
1
n_1
n
1
+2
n
2
n_2
n
2
+3
n
3
n_3
n
3
+4
n
4
n_4
n
4
=10+2+30+80=122，
n
1
n_1
n
1
+
n
2
n_2
n
2
+
n
3
n_3
n
3
+
n
4
n_4
n
4
=10+1+10+20=41，可得出
n
0
n_0
n
0
=82，即树T的叶结点的个数是82。
答案：B
学海无涯苦作舟
