数据结构(本科)期末综合练习一(单选题)

数据结构(本科)期末综合练习一(单选题)

单选题

1.一个数组元素]]与(A)的表示等价。

A.*(a+i)B.a+iC.*a+iD.&a+i

2.若需要利用形参直接访问实参，则应把形参变量说明为(B)参数。

A.指针B.引用C.传值D.常值

3.下面程序段的时间复杂度为(C)。

for(inti=0;i<m;i++)

for(intj=0;j<n;j++)a[i][j]=i*j;

A.O(m2)B.O(nz)C.O(m*n)D.O(m+n)

4.执行下面程序段时，执行S语句的次数为()。

for(inti=l;i<=n;i++)

for(intj=l;j<=i;j++)S;

A.nsB.m/2C.n(n+l)D.n(n+l)/2

5.下面算法的时间复杂度为()o

intf(unsignedintn){

if(n==O||n==l)return1;

elsereturnn*f(n-1);

A.0(1)B.0(n)C.0(n2)D.0(n!)

6.一种抽象数据类型包括数据和()两个部份。

A.数据类型B.操作C.数据抽象D.类型说明

7.当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为()，

以节省参数值的传输时间和存储参数的空间。

A.基本类型B.引用型C.指针型D.常值引用型

8.当需要进行标准I/O操作时，则应在程叙文件中包含iostream.h头文件，当需要进行文件

I/O操作时，则应在程叙文件中包含()头文件。

A.fstream.hB.stdlib.hC.iomanip.hD.string.h

9.一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空

间的大小即记录长度为()o

A.所有域长度之和B.最大域所占字节长度

C.任意一个域长度D.sizeof(r)的值

10.输出一个二维数组b|m|[n]中所有元素值的时间复杂度为(

A.O(n)B.O(m+n)C.O(m)D.O(m*n)

11.一个算法的时间复杂度为(3n2+2nlogn+4n-7)/(5n),其数量级形式的复杂度表示为

2

()。

A.O(n)B.O(nlogn)C.O(n?)D.O(logn)2

12.某算法的时间代价为T(n)=100n+10nlogn4；n2+10,其时间复杂度为()»

A.O(n)B.O(nlogn)C.O(m)D.0(1)2

13.某算法仅含程序段1和程序段2,程序段1的执行次数3n%程序段2的执行次数为O.Oln.',

则该算法的时间复杂度为()。

A.O(n)B.O(m)C.O(m)D.0(1)

14.以下说法错误的是()。

A.抽象数据类型具有封装性。

B.抽象数据类型具有信息隐蔽性。

C.使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。

D.抽象数据类型的一个特点是使用与实现分离。

15.在二维数组中，每一个数组元素同时处于()个向量中。

A.0个B.1个C.2个D.n个

16.多维数组实际上是由嵌套的()实现的。

A.一维数组B.多项式C.三元组表D.简单变量

17.在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功

时的数据平均比较次数为()。

A.nB,n/2C.(n+l)/2D.(n-l)/2

18.在一个长度为n的顺序表中向第i个元素(OWiWn-l)位置插入一个新元素时，需要从后向前挨

次后移()个元素。

A.n-iB.n-i+1C.n-i-1D.i

19.在一个长度为n的顺序表中删除第i个元素(OWi.l)时，需要从前向后挨次前移()

个元素。

A.n-iB.n-i+lC.n-i-1D.i

2

20.在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和挪移元素的总次数为

()。

A.(n+l)/2B.n/2C.nD.n+1

21.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为()。

A.O(n)B.0(1)C.O(m)D.O(logn)2

22.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为()。

A.O(n)B.O(n/2)C.0(1)D.O(m)

23.在一个长度为n的有序顺序表中搜索值为x元素的时间效率最高的算法的渐进时间复杂度

为()=

A.0(1)B.0(C.O(logn)2D.O(n)

24.在二维数组A[8][10]中，每一个数组元素占用3个存储空间，所有数组元素相继存

放于一个连续的存储空间中，则存放该数组至少需要的存储空间是()。

A.80B.100C.240D.270

25.设有一个nn的对称矩阵A,将其下三角部份按行存放在一个一维数组B中，A[0]⑼存放

于B[0]中，那末第i行的对角元素存放于8中()处。

A.(i+3)*i/2B.(i+l)*i/2

C.(2n-i+l)*i/2D.(2n-i-l)*i/2

26.设有一个nn的对称矩阵A,将其上三角部份按行存放在一个一维数组B中，A[0][0]存放

于B|0]中，那末第i行的对角元素A[iHi]存放于8中()处。

A.(i+3)*i/2B.(i+l)*i/2C.(2n-i+l)*i/2D.(2n-i-l)*i/2

27.设有两个串t和p,求p在t中首次浮现的位置的运算叫做()。

A.求子串B.模式匹配C.串替换D.串联接

28.不带头结点的单链表first为空的判定条件是()。

A.first==NULL;B.first->link==NULL;

C.first->link==first;D.first!=NULL;

29.带头结点的单链表first为空的判定条件是()。

A.first==NULL;B.first->link==NULL;

C.first->link==first;D.first!=NULL;

30.设单链表中结点的结构为(data,link)。已知指针q所指结点是指针p所指结点的直接

前驱，若在*q与*p之间插入结点*s,则应执行的操作是()o

A.s->link=p->link;p->link=s;B.q->link=s;s->link=p;

3

C.p->link=s->]ink;s->link=p;D.p->link=s;s->link=q;

31.设单链表中结点的结构为(data,link)。已知指针p所指结点不是尾结点，若在*p之后插入

结点*s,则应执行的操作是()。

A.s->link=p;p->link=s;B.p->link=s;s->link=p;

C.s->link=p->link;p=s;D.s->link=p->link;p->link=s;

32.设单链表中结点的结构为(data,link)。若想摘除p->link所指向的结点，则应执行的操作

是()°

A.p->link=p->link->link;B.p=p->link;p->link=p->link->link;

C.p->link=p;D.p=p->link->link;

33.非空的循环单链表first的尾结点(由p所指向)满足的条件是()o

A.p->link==NULL;B.p==NULL;

C.p->link==first;D.p==first;

34.设单循环链表中结点的结构为(data,link),且rear是指向非空的带表头结点的单循环

链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是()。

A.s=rear;rear=rear->link;deletes;

B.rear=rear->link;deleterear;

C.rear=rear->link->link;deleterear;

D.s=rear->link->link;rear->link->link=s->link;deletes;

35.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比

较的结点数是()o

A.nB.n/2

C.(n-l)/2D.(n+l)/2

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

()o

A.0(1)B.0(n)C.0(n2)D.O(nlogn)2

37.给定有n个元素的向量，建立一个有序单链表的时间复杂度是()。

A.0(1)B.O(n)

C.0(n2)D.0(nk)g,n)

38.单链表A长度为m,单链表B长度为n,若将B联接在A的末尾，其时间复杂度应为()。

A.0(1)B.0(m)

C.0(n)D.0(m+n)

39.利用双向链表作线性表的存储结构的优点是()。

A,便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作

4

C.节省空间D.便于销毁结构释放空间

40.带表头的双向循环链表的空表满足（）o

A.first=NULL;B.first->rLink==first

C.first->lLink==NULLD.first->rLink==NULL

41.已知L是一个不带表头的单链表,在表首插入结点*p的操作是（）。

A.p=L;p->link=L;B.p->link=L;p=L;

C.p->link=L;L=p;D.L=p;p->link=L;

42.已知L是带表头的单链表,删除首元结点的语句是（）.

A.L=L->link;B.L->link=L->link->link;

C.L=L;D.L->link=L;

43.栈的插入和删除操作在（）进行。

A.栈顶B.栈底C.任意位置D.指定位置

44.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一

个元素时，首先应执行（）语句修改top指针。

A.top++;B.top—;C.top=0;D.top;

45.若让元素1,2,3挨次进栈，则出栈次序不可能浮现（）种情况。

A.3,2,1B.2,1,3C.3,1,2D.1,3,2

46.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。

A.前一个B.后一个C.当前D.后面

47.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。

A.n-2B.n-1C.nD.n+l

48.从一个顺序存储的循环队列中删除一个元素时，首先需要（）。

A.队头指针加一B.队头指针减一

C.取出队头指针所指的元素D.取出队尾指针所指的元素

49.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear,则判断队空的条件

为（）。

A.front+1==rearB.rear+1==front

C.front==0D.front==rear

50.假定一个链式队列的队头和队尾指针分别为front和rear,则判断队空的条件为（）。

A.front==rearB.front!=NULL

C.rear!=NULLD.front==NULL

5

51.设链式栈中结点的结构为（data,link）,且top是指向栈顶的指针。若想在链式栈的栈

顶插入一个由指针s所指的结点，则应执行（）操作。

A.top->link=s;B.s->link=top->link;top->link=s;

C.s->link=top;top=s;D.s->Iink=top;top=top->Iink;

52.设链式栈中结点的结构为（data,link）,且top是指向栈顶的指针。若想摘除链式栈的

栈顶结点，并将被摘除结点的值保存到x中，则应执行（）操作。

A.x=top->data;top=top->link;B.top=top->link;x=top->data;

C.x=top;top=top->link;D.x=top->data;

53.设循环队列的结构是

typedefstruct{

DataTypedata[MaxSize];

intfront,rear;

}Queue;

若有一个Queue类型的队列Q,试问判断队列满的条件应为（）。

A.Q.front==Q.rear;B.Q.front-Q.rear==MaxSize;

C.Q.front+Q.rear==MaxSize;D.Q.front==（Q.rear+1）%MaxSize;

54.设循环队列的结构是

constintMaxSize=100;

typedefintDataType;

typedefstruct{

DataTypedata[MaxSize];

intfront,rear;

}Queue;

若有一个Queue类型的队列Q,则应用（）表达式计算队列元素的个数。

A.（Q.rear-Q.front+MaxSize）%MaxSize;B.Q.rear-Q.front+1;

C.Q.rear-Q.front-1;D.Q.rear-Qfront;

55.为增加内存空间的利用率和减少溢出的可能性，由两个栈共享一块连续的内存空间时,

应将两栈的（）分别设在这块内存空间的两端。

A.长度B.深度C.栈顶D.栈底

56.递归是将一个较复杂的（规模较大的）问题转化为一个稍为简单的（规模较小的）与原问

题（）的问题来解决，使之比原问题更挨近可直接求解的条件。

A.相关B.子类型相关C.同类型D.不相关

57.递归调用时系统需要利用一个（）来实现数据的传递和控制的转移。

A.队列B.优先级队列C.双端队列D.栈

6

58.在系统实现递归调用时需利用递归工作记录保存()，当递归调用程序执行结束时通

过它将控制转到上层调用程序。

A.调用地址B.递归入口C.返回地址D.递归出口

59.在递归执行过程中，当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶

记录，称之为()记录。

A.活动B.当前C.日志D.标记

60.将递归求解过程改变为非递归求解过程的目的是()。

A.提高速度B.改善可读性C.增强茁壮性D.提高可维护性

61.如果一个递归函数过程中惟独一个递归语句，而且它是过程体的最后语句，则这种递归属

于(),它很容易被改写为非递归过程。

A.单向递归B.回溯递归C.间接递归D.尾递归

62.设有一个递归算法如下

intfact(intn){//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

)

则计算fact(n)需要函数调用的次数为()次。

A.nB.n+1C.n+2D.n-1

63.设有一个递归算法如下

intX(intn){

if(n<=3)return1;

elsereturnX(n-2)+X(n-4)+1;

)

试问计算X(X(5))时需要调用()次*函数。

A.2次B.3次C.4次D.5次

64.设有一个广义表A(a),其表尾为()。

A.aB.(())C.()D.(a)

65.设有一个广义表A((x,(a,b)),(x,(a,b),y)),运算Head(Head(Tail(A)))

的执行结果为()。

A.xB.(a,b)C.(x,(a,b))D.y

66.下列广义表中的线性表是()0

A.E(a,(b,c))B.E(a,E)C.E(a,b)D.E(a,L())

67.对于一组广义表A(),B(a,b),C(c,(e,f,g)),D(B,A,C),E(B,D),其中的£是()。

7

A.线性表B.纯表C.递归表D.再入表

68.已知广义表A((a,b,c),(d,e,f))，从A中取出原子e的运算是()。

A.Tail(Head(A))B.Head(Tail(A))

C.Head(Tail(Head(Tail(A))))D.Head(Head(Tail(Tail(A))))

69.树中所有结点的度之和等于所有结点数加()。

A.0B.1C.1D.2

70.在一棵树中，()没有前驱结点。

A.树枝结点B.叶子结点C.树根结点D.空结点

71.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加()。

A.2B.1C.0D.1

72.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于()。

A.nB.n-1C.n+1D.2*n

73.在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于

树的高度)，最多具有()个结点。

A.2iB.2i+lC.2ilD.2n

74.在一棵高度为h(假定树根结点的层号为0)的彻底二叉树中，所含结点个数不小于(

)。

A.2H-IB.2h*iC.2h-1D.2h

75.一棵具有35个结点的彻底二叉树的高度为()。假定空树的高度为-1。

A.5B.6C.7D.8

76.在一棵具有n个结点的彻底二叉树中，树枝结点的最大编号为()。假定树根结点的

编号为0。

A.(n-1)/2B.n/2C.n/2D.n/2-1

77.在一棵彻底二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为()。

假定树根结点的编号为0。

A2iB2i-1C2i+1D2i+2

78.在一棵彻底二叉树中，假定树根结点的编号为0,对于编号为i(i>0)的结点，其双亲结点的

编号为()。

A.(i+l)/2B.(i-l)/2C.i/2D.i/2-1

79.在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的()结点。

8

A.兄弟B.父子C.祖先D.子孙

80.在一棵树的静态双亲表示中，每一个存储结点包含()个域。

A1B2C3D4

81.已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f)),则该二叉树的高度为()。

假定树根结点的高度为0。

A.3B.4C.5D.6

82.已知一棵树的边集表示为{<A,B>,<A,C>,<B,D>,<C,E>,<C,F>,<C,G>,<F,H>,<F,I>},

则该树的深度为()o假定树根结点的高度为0。

A.2B.3C.4D.5

83.利用n个值作为叶结点的权生成的霍夫曼树中共包含有()个结点。

A.nB.n+lC.2*nD.2*n-l

84.利用3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为

()。

A55B29C58D38

85.一棵树的广义表表示为a(b,c(e,f(g)),d),当用左子女-右兄弟链表表示时，右指针域非空的

结点个数为()。

A1B2C3D4

86.向具有n个结点的堆中插入一个新元素的时间复杂度为()。

A.0(1)B.O(n)C.O(logn)D.O(nlogn)22

87.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度

为()。

A.nB.n+lC.(n-l)/2D.(n+l)/2

88.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8,搜索后面5

个元素的概率相同，均为3/40,则搜索任一元素的平均搜索长度为()。

A.5.5B.5C.39/8D.19/4

89.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2,搜索第二个元素的概率

为1/3,搜索第三个元素的概率为1/6,则搜索任一元素的平均搜索长度为()。

A.5/3B.2C.7/3D.4/3

90.对长度为n的单链有序表，若搜索每一个元素的概率相等，则搜索任一元素的搜索成功的平

均搜索长度为()。

A.n/2B.(n+l)/2C.(n-l)/2D.n/4

9

91.对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的

为()的值向上取整。

A.log(n+1)B.lognC.n/2D.(n+l)/222

92.对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的

为()的值的向下取整加1。

A.log(n+1)B.lognC.n/2D.(n+l)/222

93.对于长度为9的顺序存储的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜

索长度为()除以9。

A.20B.18C.25D.22

94.对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索第15个元素的搜索长度为(

)°

A.3B.4C.5D.6

95.对具有n个元素的有序表进行折半搜索，则搜索任一元素的时间复杂度为()o

A.O(n)B.O(m)C.0(1)D.O(logn)2

96.在一棵高度为h的具有n个元素的二叉搜索树中，搜索一个元素的最大搜索长度为(

)。

A.nB.lognC.(h+l)/2D.h+12

97.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复

杂度大致为()。

A.0(n)B.0(1)C.O(logn)D.0(m)2

98.向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为()o

A.0(1)B.O(Iogn)C.O(n)D.O(nlogn)2

99.在一棵AVL树中，每一个结点的平衡因子的取值范围是()o

A.-1IB.-22C.12D.01

100.向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为()

种旋转类型。

A.2B.3C.4D.5

101.向一棵AVL树插入元素时，可能引起对最小不平衡子树的左单或者右单旋转的调整过程,

此时需要修改相关()个指针域的值。

A.2B.3C.4D,5

10

102.向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需

要修改相关（）个指针域的值。

A.2B.3C.4D.5

103.设G=,（Y，£）和6彳（,、产）为两个图，如果VV,EE,则称（）。，i।2

A.q坤GM字图B:G嵬G的子图।2

C.d息G的连通分量D.G是G的连通分量I2

21

104.有向图的一个顶点的度数等于该顶点的（）。

A.入度B.出度C.入度与出度之和D.（入度+出度）/2

105.一个连通图的生成树是包含图中所有顶点的一个（）。

A.极小子图B.连通子图C.极小连通子图D.无环子图

106.n个顶点的连通图中至少含有（）。

A.n-1条边B.n条边C.n（n-l）/2条边D.n（n-l）条边

107.n个顶点的强连通图中至少含有（）.

A.n-1条有向边B.n条有向边C.n（n-l）/2条有向边D.n（n-l）条有向边

108.在一个带权连通图G中，权值最小的边一定包含在6的（）中。

A.最小生成树B.生成树

C.广度优先生成树D.深度优先生成树

109.对于具有e条边的无向图，它的邻接表中有（）个边结点。

A.e-1B.eC.2（e-l）D.2e

110.具有n个顶点的有向无环图最多可包含（）条有向边。

A.n-1B.nC.n（n-1）/2D.n（n-l）

111.一个有n个顶点和n条边的无向图一定是（）。

A.连通的B.不连通的C.无环的D.有环的

112.在n个顶点的有向无环图的邻接矩阵中至少有（）个零元素。

A.nB.n（n-l）/2C.n（n+1）/2D.n（n-l）

113.对于有向图，其邻接矩阵表示比邻接表表示更易于（）。

A.查找一条边B.求一个顶点的邻接点

C.进行图的深度优先遍历D.进行图的广度优先遍历

114.在一个有向图的邻接矩阵表示中，删除一条边＜,匕＞需要耗费的时间是（）。

A.0（1）B.O（i）C.O（j）D.O（i+j）

II

115.与邻接矩阵相比，邻接表更适合于存储（）。

A.无向图B.连通图C.稀疏图D.稠密图

116.设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度

所耗费的时间是（）。

A.0（n）B.O（e）C.O（n+e）D.0（m）

117.为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（）。

A.栈B.队列C.二叉树D.树

118.设无向图的顶点个数为n,则该图最多有（）条边。

A.n-1B.n（n-l）/2C.n（n+l）/2D.n（n-l）

119.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。

A.3B.2C.1D.1/2

120.若采用邻接矩阵存储具有n个顶点的无向图，则该邻接矩阵是一个（）。

A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵

121.图的深度优先搜索类似于树的（）次序遍历。

A.先根B.中根C.后根D.层次

122.图的广度优先搜索类似于树的（）次序遍历。

A.先根B.中根C.后根D.层次

123.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）

辅助结构，判断一条边的两个端点是否在同一个连通分量上。

A.位向量B.堆C.并查集D.生成树顶点集合

124.采用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（

）数。

A.非零B,非整C.非负D.非正

125.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计

算时间为（）。

A.O（nloge）B.O（n+e）C.0（n0D.O（m）2

126.若待排序对象序列在排序前已基本按排序码递增顺序罗列，则采用（）方法比较次数

至少。

A.直接插入排序B.快速排序C.归并排序D.直接选择排序

12

127.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样

的排序操作，直到子序列为空或者只剩一个元素为止。这样的排序方法是（）。

A.直接选择排序B.直接插入排序C.快速排序D.起泡排序

128.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。

A.8B.10C.15D.25

129.下列排序算法中，（）算法是不稳定的。

A.起泡排序B.直接插入排序C,基数排序D.快速排序

130.假设某文件经过内部排序得到100个初始归并段，那末如果要求利用多路平衡归并在3趟

内完成排序，则应取的归并路数至少是（）。

A.3B.4C.5D.6

131.在基于排序码比较的排序算法中，（）算法在最坏情况下的时间复杂度不高于

0（nlogn）,

'A.起泡排序B.希尔排序C.堆排序D.快速排序

132.在下列排序算法中，（）算法使用的附加空间与输入序列的长度及初始罗列无关。

A.锦标赛排序B.快速排序C.基数排序D.归并排序

133.一个对象序列的排序码为{46,79,56,38,40,84）,采用快速排序（以位于最左位置

的对象为基准）所得到的第一次划分结果为（）。

A.{38,46,79,56,40,84}B.{38,79,56,46,40,84）

C.{40,38,46,79,56,84}D.{38,46,56,79,40,84）

134.如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那末使用下列排序

算法中（）算法最快。

A.归并排序B.希尔排序C.快速排序D.基数排序

135.设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找

到一个元素的平均探查次数不能超过L5,则散列表的长度应至少为（）。

（注：平均探查次数的计算公式为S={1+1/（1-a）}/2,其中a为装填因子）

A.400B.526C.6241"D.676

136.5阶B树中，每一个结点最多允许有（）个关键码。

A.2B.3C.4D.5

137.在10阶B树中根结点所包含的关键码个数至少为（）。

A.0B.1C.3D.4

138.在一棵高度为h的B树中，叶结点处于第（）层。（注：树根结点为第0层，B树高

13

度为失败结点所处层数）。

A.h-1B.hC.h+1D.h+2

139.在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取（）个

结点。

A.h-1B.hC.h+1D.h+2

140.当对一个线性表R[60]进行索引顺序搜索（分块搜索）时，若共分成为了1（）个子表，每一个

子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为

（）。

A.7B.8C.9D.10

141.当对一个线性表R[60]进行索引顺序搜索（分块搜索）时，若共分成为了8个子表，每一个

子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为

（）。

A.7B.8C.9D.10

142.既希翼较快的搜索又便于线性表动态变化的搜索方法是（）。

A.顺序搜索B.折半搜索C.散列搜索D.索引顺序搜索

143.散列函数应该有这样的性质，即函数值应当以（）概率取其值域范围内的每一个值。

A.最大B.最小C.平均D.同等

144.设散列地址空间为（）m-Lk为表项的关键码，散列函数采用除留余数法，即Hash（k尸k%p。

为了减少发生冲突的频率，普通取p