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

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

2、对于含有n个记录的顺序表，假定每个记录的查找概率相等，则顺序查找的平均长度为（）。

A、不确定

B、(n+1)/2

C、(n-1)/2

D、n/2

3、若a是int类型变量，则计算表达式a=25/3%3的值是（）。

A、3

B、2

C、1

D、0

4、已知一棵完全二叉树有2017个结点，则该二叉树中叶子结点的个数是（）。

A、1009

B、1008

C、504

D、505

5、直接插入排序在最好的情况下的时间复杂度为（）。

A、

B、

C、

D、

2、试题答案：B

试题解析：

在含有n个结点的顺序表中，查找第i个结点的查找长度为i，因此平均查找长度=(1+2+…+n)/n=(n+1)/2，故本题选B。

3、试题答案：B

试题解析：

由题，先运算25/3=8，再运算8%3=2；故本题选B。
除法运算：'/'运算符两个整数相除的结果是整数，如13/4的结果值为3，舍去小数部分。
'%'运算符要求参加运算的运算对象（即操作数）为整数，结果也是整数。

4、试题答案：A

试题解析：

对任何一棵二叉树，若终端结点为n0，度为2的结点为n2，则n0=n2+1。对于一棵完全二叉树，树的度为1的结点为n1，n1或者为0或者为1。n=n0+n1+n2=n0+n1+n0-1=2017，由于n0为整数，因此n1=0，解得n0=1009，故本题选A。

5、试题答案：A

试题解析：

直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。在序列完全有序的情况下，仅需要一趟插入排序即可完成，因此在最好情况下的时间复杂度为O(n)，故本题选A。