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

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

1、下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（  ）。

A、 c和e

B、 d和e

C、 f和d

D、 f和h

2、下面程序段的时间复杂度为（）。i=0; s=0; while(s<n){ i++; s=s+i;}

A、

B、

C、O(n)

D、O(n²)

3、采用开放定址法解决冲突的数列查找，发生聚集的主要原因为（）。

A、数据元素过多

B、表长过短

C、函数选择不当

D、解决冲突方法不当

5、若一棵度为3的树T中，有A个度为1的结点，B个度为2的结点，C个度为3的结点，则该树有（）个叶结点。

A、1+2B+3C

B、A+2B+3C

C、2B+3C

D、1+B+2C

1、试题答案：C

试题解析：

【考点】本题考查关键路径。
【解析】AOE网指在一个带权有向图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径。利用关键路径算法可以求出上图中的关键路径有三条，分别为（b，d，c，g），（b，d，e，h），（b，f，h）。只有在关键路径上的活动加快才能使整个活动加快。因此选项中的活动必须包含在三个关键路径中。A选项不在（b，f，h），B选项不在（b，f，h），D 选项不在（b，d，c，g），故本题选C。

2、试题答案：A

试题解析：

3、试题答案：D

试题解析：

采用开地址法解决冲突的数列查找，发生聚集的主要原因为解决冲突方法不当。例如用线性探测法使得大量元素在相邻地址出现“聚集”现象，其主要原因是解决冲突算法选择不好，如果选择平方探测法，则可以避免堆积问题。故本题选D。

5、试题答案：D

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2+n3（结点数量）=n1+2n2+3n3+1（边数量+1）。则树T中的叶子结点n0的个数是n2+2n3+1=1+B+2C。故本题选D。