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

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

1、散列函数有一个共同性质，即函数值应按（ ）取其值域的每一个值。

A、最大概率

B、最小概率

C、同等概率

D、平均概率

2、一个入栈序列是a，b，c，d，e，则出栈的序列可能是（ ）。I.e，d，c，b，a； II.d，e，c，b，a； III.d，c，f，a，b； IV.a，b，c，d，e

A、I、II

B、III、IV

C、I、II、IV

D、 II、III、IV

3、下列关于二叉排序树的说法正确的是（ ）。I.向二叉排序树插入一个结点，所需要的比较次数可能大于此排序树的高度II.二叉排序树一定是平衡二叉树III.删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树IV.平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树

A、I、II、IV

B、II、III、IV

C、I. IV

D、只有IV

4、已知有向图G=( V，E)，如右图所示，G的可能的拓扑排序为（ ）。

A、V1，V3，V4，V6，V2，V5，V7

B、V1，V3，V5，V6，V4，V2，V7

C、V1，V3，V4，V5，V2，V6，V7

D、V1，V2，V5，V3，V4，V6，V7

5、有n（n>0）个分支结点的满二叉树的深度是（ ）。

A、

B、

C、

D、

1、试题答案：C

试题解析：

【考点】本题考查散列函数的性质。
【解析】构造哈希函数的原则是：① 函数本身便于计算；② 计算出来的地址分布均匀，即对任一关键字，哈希值对应不同地址的概率相等，目的是尽可能减少冲突。故本题选C。

2、试题答案：C

试题解析：

【考点】本题考查正确的出栈序列。
【解析】I：a、b、c、d、e均依次入栈，随即e、d、c、b、a依次出栈，则可得到出栈序列e，d，c，b，a。
II：a、b、c、d均依次入栈，随即d出栈，接着e进栈，随即e、c、b、a依次出栈，则可得到出栈序列d，e，c，b，a。
III：栈的特点是“先进后出”，a先于b进栈，那么b先于a出栈。而III中的序列a先于b，不符合出栈要求，所以d，c，f，a，b不可能是出栈序列。
IV：a进栈随即出栈，b进栈随即出栈，c进栈随即出栈，d进栈随即出栈，e进栈随即出栈，由此可得出栈结果为a，b，c，d，e。
综上所述，出栈的可能序列是I、II、IV。故本题选C。

3、试题答案：D

试题解析：

【考点】本题考查二叉排序树的特点。
【解析】
I.向二叉排序树中插入新的结点所需要的比较次数最多为该树的高度，所以I说法错误。
II.二叉排序树不一定是平衡叉树，如下所示，该二叉树是一颗二叉排序树，但不是平衡二叉树。

III.删除二叉排序树中的一个结点，再重新插入，不一定能得到原来的二叉排序树，如下所示：

IV.平衡二叉树也叫AVL树，它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和左子树的高度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树，所以IV说法正确。
综上所述，本题选D。

4、试题答案：A

试题解析：

【考点】本题考查拓扑排序。
【解析】首先，选择入度为0的顶点v1加入拓扑序列，然后删除该结点以及从该结点出发的边，此时入度为0的顶点有v2、v3。若选择v3加入拓扑序列后，则删除顶点v3以及从v3出发的所有边，此时入度为0的顶点有v2、v4，第三个加入拓扑序列的顶点不可能是v5，所以B中序列不可能是拓扑序列。若将v4加入拓扑序列，此时入度为0的顶点有v2、v6，第四个加入拓扑序列的顶点不可能为v5，所以C中序列不可能是拓扑序列。若将v6加入拓扑序列，此时入度为0的顶点只有v2，将其加入拓扑序列，并删除该结点以及从该结点出发的所有边，此时入度为0的顶点只有v5。将v5加入拓扑序列，并删除该结点以及从该结点出发的所有边，此时入度为0的顶点只有v7。将v7加入拓扑序列，并删除该结点以及从该结点出发的所有边，此时图中所有结点均已纳入拓扑序列，最终得到的拓扑序列为V1，V3，V4，V6，V2，V5，V7。故本题选A。

5、试题答案：B

试题解析：