考研数据结构与程序设计在线题库每日一练（二十八）

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

1、在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ ）。

A、

B、

C、

D、

2、按二叉树的定义，具有三个结点的二叉树有（ ）种。

A、3

B、4

C、5

D、6

3、以下正确的C语言标识符是（ ）。

A、0XG

B、_80

C、main#

D、A$

4、为求取无向图的各连通分量，可利用（ ）。

A、深度优先搜索遍历

B、拓扑排序

C、最短路径

D、最小生成树

5、若执行以下程序段：int x=10, y=20, a, b=12;a=(x>y)&&b++;执行后b的值是（ ）。

A、10

B、11

C、12

D、13

1、试题答案：B

试题解析：

在该单链表中插入结点时，需要从头开始遍历链表，找到结点待插入的位置，这个操作的时间复杂度为O(n)，之后在该位置插入结点，这个操作的时间复杂度为O(1)，上述操作的综合时间复杂度为O(n)。注意，折半查找仅适用于有序的顺序表，不适用于链表，因此本题不能采用折半查找。故本题选B。

2、试题答案：C

试题解析：

画出具有三个结点的二叉树的所有形态如下：

由上图可知，具有三个结点的二叉树共有5种形态，故本题选C。

3、试题答案：B

试题解析：

C语言的标识符是用来对变量名、函数名、标号及其它各种用户定义的对象命名的。标识符的第一个字符是字母或下划线，随后的字符可以是字母、数字或下划线。在标识符中，大小写是有区别的。对于A，第一个字母是数字，不符合标识符的命名规则，因此A错误；对于B，符合标识符的规则，因此B正确；对于C，标识符中无#符号，因此C错误；对于D，标识符中无$符号，因此D错误。故本题选B。

4、试题答案：A

试题解析：

在对无向图进行遍历时，对于连通图，从任意一点出发，进行深度或广度优先搜索后可访问图中所有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的顶点出发进行搜索的过程中得到的顶点访问序列即为其各个连通分量的顶点集，因此A正确。对于B，拓扑排序是针对有向图的算法，因此B错误。对于C，最短路径算法是求顶点之间的最短路径，与题干所求不符，因此C错误。对于D，只有连通图才存在最小生成树，而本题中图的连通分量不止一个则证明图是非连通图，最小生成树算法不适用，因此D错误。故本题选A。

5、试题答案：B

试题解析：

在该表达式中比较变量x和y的值，因为x的值小于y，所以结果为0。&&是短路运算符，因此不会执行后面的b++，而是直接将0赋值给变量a，变量b的值仍然为12，故本题选B。