数据结构错题收录（五）

2022-11-19 本文已影响0人程序员丶星霖

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_{next[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，则n=分支数+1，而分支数又等于树中各结点的度之和，即n=1+ $n_1$ +2 $n_2$ +3 $n_3$ +4 $n_4$ = $n_0$ + $n_1$ + $n_2$ + $n_3$ + $n_4$ 。依题意， $n_1$ +2 $n_2$ +3 $n_3$ +4 $n_4$ =10+2+30+80=122， $n_1$ + $n_2$ + $n_3$ + $n_4$ =10+1+10+20=41，可得出 $n_0$ =82，即树T的叶结点的个数是82。