考研数据结构及程序设计在线题库每日一练（七）

本文提供考研数据结构及程序设计在线题库每日一练，以下为具体内容

1、判定一个循环队列qu（最多元素为MaxSize）为空的条件是（ ）。

A、qu→rear-qu→front==MaxSize

B、qu→rear-qu→front-1==MaxSize

C、qu→rear==qu→front

D、qu→rear=qu→front-1

2、一个入栈序列是a，b，c，d，e，则出栈的序列可能是（ ）。I.e，d，c，b，a； II.d，e，c，b，a； III.d，c，f，a，b； IV.a，b，c，d，e

A、I、II

B、III、IV

C、I、II、IV

D、 II、III、IV

3、最不适合用做队列的链表（ ）。

A、只带队首指针的非循环双链表

B、只带队首指针的循环双链链表

C、只带队尾指针的循环双链表

D、只带队尾指针的循环单链表

4、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个序列施加同样的排序操作。直到子序列为空或只剩一个元素为止。这样的排序算法是（ ）。

A、直接选择排序

B、直接插入排序

C、快速排序

D、起泡排序

5、如下图1，从顶点1出发，按照广度优先规则遍历，可能得到的序列为（ ）。

A、1352467

B、142375

C、1234576

D、1354672

1、试题答案：C

试题解析：

【考点】本题考查判定一个循环队列的队空条件。
【解析】为了方便起见，约定初始化建空队时，令front=rear=0。但是，当队空时：front=rear；当队满时：front=rear亦成立。因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）牺牲一个存储空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志（front指向队首元素，rear指向队尾元素的下一个元素）。即：
① 队空时：front=rear；
② 队满时：(rear+1)%maxsize=front。
综上所述，本题选C。

2、试题答案：C

试题解析：

【考点】本题考查正确的出栈序列。
【解析】I：a、b、c、d、e均依次入栈，随即e、d、c、b、a依次出栈，则可得到出栈序列e，d，c，b，a。
II：a、b、c、d均依次入栈，随即d出栈，接着e进栈，随即e、c、b、a依次出栈，则可得到出栈序列d，e，c，b，a。
III：栈的特点是“先进后出”，a先于b进栈，那么b先于a出栈。而III中的序列a先于b，不符合出栈要求，所以d，c，f，a，b不可能是出栈序列。
IV：a进栈随即出栈，b进栈随即出栈，c进栈随即出栈，d进栈随即出栈，e进栈随即出栈，由此可得出栈结果为a，b，c，d，e。
综上所述，出栈的可能序列是I、II、IV。故本题选C。

3、试题答案：A

试题解析：

【考点】本题考查链队列。
【解析】队列的特点是在队头出队元素，队尾入队元素。A选项中的只带队首指针的非循环双链表查找队尾的时间复杂度最长为O(n)，其他选项中的链表只需要O(1)的时间复杂度即可查找到队尾元素，所以只带队首指针的非循环双链表不适合做队列的链表。故本题选A。 

4、试题答案：C

试题解析：

【考点】本题考查快速排序的思想过程。
【解析】
（1）直接选择排序：每一趟在待排序元素中选取关键字最小的元素加入有序子序列中。
（2）直接插入排序：把n个待排序的元素看成一个有序表和一个无序表，开始时有序表只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
（3）快速排序：在待排序序列中选择一个基准值，然后将小于基准值的数字放在基准值左边，大于基准值的数字放在基准值右边，第一趟排序后基准元素将整个序列划分成两个子序列。接着继续对这两部分序列递归排序，直到子序列为空或者只剩一个元素为止。
（4）起泡排序：重复走访要排序的序列，对所有相邻记录的关键字值进行比较，如果是逆顺（a[j]>a[j+1]），则将其交换位置。排序过程中每次从后往前冒一个最小值，且每次能确定一个关键字在序列中的最终位置。
综上所述，对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个序列施加同样的排序操作。直到子序列为空或只剩一个元素为止。这样的排序算法是快速排序算法。故本题选C。

5、试题答案：C

试题解析：

【考点】本题考查图的广度优先遍历。
【解析】从1出发访问与1相邻的所有顶点，即2453（顺序可以有所不同）。因此，B和D可以排除，不满足遍历要求。A：若访问完13524，此时与顶点3和顶点5相邻的顶点均已访问完，与顶点2相邻的顶点还剩顶点7未访问，所以接下来访问顶点7，而不是顶点6。因此，A排除。C：若访问完12345，此时与顶点2相邻的顶点还剩顶点7未访问，所以接着访问顶点7。与顶点3相邻的顶点均已访问，继续看检查顶点4，与其相邻的顶点还剩顶点6未访问，所以接着访问顶点6。最终整个图按照广度优先遍历得到的序列为1234576。故本题选C。