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

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

1、某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（ ）。

A、43

B、79

C、198

D、200

2、程序段如下：for(i=n-1;i>1;i--) for(j=1;j<i;j++) if(A[j]>A[j+1]) A[j]与A[j+1]对换;其中n为正整数，则最后一行语句的频度在最坏情况下是（ ）。

A、O(n)

B、O(nlogn)

C、O(n³)

D、O(n²)

3、静态链表中next域表示的是（ ）。

A、下一个元素的地址

B、下一个元素的值

C、当前元素的值

D、下一个元素在数组中的位置

4、一个栈的输入序列为：1，2，3，…，n，若输出序列的第1个元素是n，则输出序列第i（1≤i≤n）个元素是（ ）。

A、不确定

B、n-i

C、i

D、n-i+1

5、设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（ ）。

A、m-n

B、m-n-1

C、n+1

D、条件不足，无法确定

1、试题答案：A

试题解析：

2、试题答案：D

试题解析：

3、试题答案：D

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--静态链表--静态链表的特点。
【解析】静态链表一般保存在数组中，它与链表最大的区别是静态链表占用一段固定的区间，所以next域只需要表示下一个元素在数组中的下标，而不是表示下一个元素的地址。故本题选D。

4、试题答案：D

试题解析：

【考点】本题考查数据结构--栈和队列--栈--栈的基本概念--栈的基本操作。
【解析】出栈序列第一个元素是n，说明元素1~n-1已经压入栈中，出栈序列唯一：n，n-1，..，1，第i个出栈的元素是n-i+1。故本题选D。

5、试题答案：A

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--森林转换为二叉树。
【解析】森林转换成二叉树时采用孩子兄弟表示法，根结点及其左子树为森林中的第一棵树。右子树为其他剩余的树。所以，第一棵树的结点个数为m-n。故本题选A。