数据结构题目收录（五）

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。

从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。

答案：B

学海无涯苦作舟