考研数据结构A在线题库每日一练（六十五）

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

1、对二叉树所有结点进行编号（从1开始），要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现编号。

A、先序

B、中序

C、后序

D、从根开始的层次遍历

2、时间复杂度不受待排序序列初始状态的影响，总是O(n2)的是（ ）。

A、直接插入排序

B、快速排序

C、简单选择排序

D、归并排序

3、下列排序算法中，（ ）算法可能会出现下面情况：初始数据有序时，花费时间反而最多。

A、堆排序

B、冒泡排序

C、快速排序

D、直接插入排序

4、若允许表达式内多种括号混合嵌套，则设计检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（ ）。

A、栈

B、线性表

C、队列

D、二叉排序树

5、数据元素的逻辑结构分为（ ）种基本类型。

A、2

B、3

C、4

D、5

1、试题答案：C

试题解析：

前序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。中序遍历二叉树先遍历左子树，再访问根结点，最后遍历右子树。后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。层次遍历二叉树对二叉树自上而下、从左而右的遍历。根据题干可知，树的结点编号之间的大小关系为左孩子<右孩子<根结点，该关系和后序遍历相对应，故本题选C。

2、试题答案：C

试题解析：

对于A，直接插入排序在序列初始完全有序的情况下时间复杂度为O(n)，平均情况下的时间复杂度为O(n²)，因此A错误；对于B，快速排序在序列初始完全有序的情况下时间复杂度为 O(n²)，平均情况下时间复杂度为O(nlogn)，因此B错误；对于C，简单选择排序在最好、最坏、平均情况下时间复杂度均为 O(n²)，因此C正确；归并排序在最好、最坏、平均情况下的时间复杂度均为O(nlogn)，因此D错误。故本题选C。

3、试题答案：C

试题解析：

快速排序是把序列分块，若序列已经基本有序，则选取第一个数为枢纽时，第一块前面没有数，第二块是除了第一个数以外的所有值，每次分块仅减少一个值。分块的时间复杂度是O(n)，分了n次块，时间复杂度是O(n²)。故本题选C。

4、试题答案：A

试题解析：

栈具有“后进先出”的特点，进行括号匹配检验时，遍历表达式，遇到左括号则进栈，遇到右括号则将栈顶元素出栈，并检验是否与右括号匹配，若匹配则继续遍历；否则判定表达式括号不匹配。遍历结束后检验栈是否为空，若为空，则判定表达式括号匹配，否则括号不匹配。故本题选A。

5、试题答案：C

试题解析：

根据数据元素之间关系的不同特性，通常有下列4类基本结构：
（1）集合，结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；
（2）线性结构，结构中的数据元素之间存在一个对一个的关系；
（3）树形结构，结构中的数据元素之间存在一个对多个的关系；
（4）图状结构或网状结构，结构中的数据元素之间存在多个对多个的关系。
故本题选C。