电子科大from知博书店数据结构习题

数据结构典型习题知博书店1、下面程序段的时间复杂度为（）

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

for(intj=0;j<n;j++)

a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)答案：C设n为正整数,分析下列各程序段中加下划线的语句的程序步数。for(inti=1;i<=n;i++) for(intj=1;j<=n;j++){

c[i][j]=0.0; for(intk=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];

}（2）x=0;y=0; for(inti=1;i<=n;i++)for(intj=1;j<=i;j++) for(intk=1;k<=j;k++)

x=x+y;

(3)inti=1,j=1; while(i<=n&&j<=n){

i=i+1;j=j+i; }

i=1时，i=2，j=j+i=1+2=2+1，i=2时，i=3，j=j+i=(2+1)+3=3+1+2，i=3时，i=4，j=j+i=(3+1+2)+4=4+1+2+3，i=4时，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4，……

i=k时，i=k+1，j=j+i=(k+1)+(1+2+3+4+…+k)，2、下面算法的时间复杂度为（）

int

f(unsigned

intn){

if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.On!)答案：B栈是一种线性表，它的特点是

A。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值

B；从栈中弹出（POP）一个元素时，变量T的值

C。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是

D，变量T的值是

E。供选择的答案：A：①先进先出②后进先出 ③进优于出 ④出优于进 ⑤随机进出B，C： ①加1②减1③不变 ④清0⑤加2⑥减2D：①a,b②b,c ③c,a ④b,a⑤c,b⑥a,cE：①n+1②n+2③n ④n-1⑤n-2ABCDE=2,2,1,6,4

在做进栈运算时，应先判别栈是否

A；在做退栈运算时，应先判别栈是否

B。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为

C。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的

D分别设在这片内存空间的两端，这样，只有当

E时，才产生上溢。供选择的答案：A，B：①空②满③上溢④下溢C： ①n-1②n③n+1④n/2D：①长度②深度③栈顶④栈底E：①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底ABCDE＝2,1,2,4,3

从一维数组a[n]中顺序查找出一最大值元素的时间复杂度为（），输出一个二维数组b[m][n]中所有元素的时间复杂度为（）在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。O(n)O(m*n)何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。为什么在单循环链表中设置尾指针比设置头指针更好？答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。

在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?答：我们分别讨论三种链表的情况。

1.单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。

2.双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。

3.单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。

下述算法的功能是什么?

LinkList

Demo(LinkListL){//L是无头结点单链表

ListNode*Q,*P;

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;

Q->next=NULL;

}

returnL;

}//Demo答：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。

链栈中为何不设置头结点?

答：链栈不需要在头部附加头结点，因为栈都是在尾部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

循环队列的优点是什么?如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的“假溢出”现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（

）

A．front=front+1

B．front=(front+1)%(m-1)

C．front=(front-1)%m

D．front=(front+1)%mD设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢?答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_____。p－>next－>next数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%nD为了提高内存的利用效率，减少溢出机会，可以让两个栈共享一段连续内存空间，应如何设置两个栈？栈底分别设在内存的两端设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有4种，2,4,3,12,3,4,12,1,3,42,1,4,3④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为多少？3指出下述程序段的功能是什么?voidDemo1(SeqStack*S){

inti;arr[64];n=0;

while(!StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr);

}答：程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。

SeqStackS1,S2,tmp;

DataTypex;

...//假设栈tmp和S2已做过初始化

while(!StackEmpty(&S1))

{

x=Pop(&S1);

Push(&tmp,x);

}

while(!StackEmpty(&tmp))

{

x=Pop(&tmp);

Push(&S1,x);

Push(&S2,x);

}

答：程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去。

voidDemo2(SeqStack*S,intm)

{

//设DataType

为int

型

SeqStackT;inti;

InitStack(&T);

while(!StackEmpty(S))

if((i=Pop(S))!=m)Push(&T,i);

while(!StackEmpty(&T))

{

i=Pop(&T);Push(S,i);

}

}

答：程序段的功能是将一个非空栈中值等于m的元素全部删去。

voidDemo3(CirQueue*Q)

{

//设DataType

为int

型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

{x=DeQueue(Q);Push(&S,x);}

while(!StackEmpty(&s))

{x=Pop(&S);EnQueue(Q,x);}

}//Demo3

答：程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。

CirQueueQ1,Q2;//设DataType

为int

型

intx,i,m=0;

...

//设Q1已有内容，Q2已初始化过

while(!QueueEmpty(&Q1))

{x=DeQueue(&Q1);EnQueue(&Q2,x);m++;}

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

{x=DeQueue(&Q2);

EnQueue(&Q1,x);EnQueue(&Q2,x);}

答：这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。

假设有如下的串说明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

(1)在执行如下的每个语句后p的值是什么?

p=index(s1,'t‘,2);p=index(s2,'9‘,1);p=index(s2,'6‘,1);

答：index(*s,*c,pos)函数的功能是查找在串s第pos个字符后第一次出现串c的位置，若找到，则返回该位置，否则返回NULL。因此:

执行p=index(s1,'t‘,1);后p的值是指向字符t的位置,也就是p=6。

执行p=index(s2,'9‘,1);后p的值是指向s2串中第一个9所在的位置,也就是p=10。

执行p=index(s2,'6‘,1);之后，p的返回值是0。

假设有如下的串说明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

在执行下列语句后，s3的值是什么?

strcpy(s3,s1);strcat(s3,",");strcat(s3,s2);

答：strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以:

在执行strcpy(s3,s1);后，s3的值是"Stocktom,CA"

在执行strcat(s3,",");后，s3的值变成"Stocktom,Ca,"

在执行完strcat(s3,s2);后，s3的值就成了"Stocktom,Ca,March5,1999"

假设有如下的串说明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

调用函数strcmp(s1,s2)的返回值是什么?

答：函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2大，串1等于串2，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)

假设有如下的串说明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

调用函数strcmp(&s1[5],"ton")的返回值是什么?

答：首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp(&s1[5],"ton")中，前一个字符串值是"tom,CA",用它和"ton"比较，应该是后者更大，所以返回值是小于0的数。

假设有如下的串说明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

调用函数strlen(strcat(s1,s2))的返回值是什么?

答：strlen是求串长的函数，我们先将s1,s2联接起来，值是"Stocktom,CAMarch5,1999",数一数有几个字符,返回值是23。

若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（

）

A．O（1）

B．O（n）

C．O（n2）

D．O（n3）C设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEFD假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为

；末尾元素A57的第一个字节地址为

；若按行存储时，元素A14的第一个字节地址为

；若按列存储时，元素A47的第一个字节地址为

。288B1282(8+4)×6+1000=1072(6×7＋4)×6＋1000）＝1276设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为

___________________

三元数组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的

、

和

。

[(58-1)*60+(32-1)]*2+2048=8950行下标列下标元素值二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（）个字节；M的第8列和第5行共占（）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（）元素的起始地址一致。A.90 B.180 C.240 D.540A.108 B.114 C.54 D.60A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]答案：DAB数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）

A.SA+141 B.SA+144 C.SA+222 D.SA+225C稀疏矩阵一般的压缩存储方式有两种，即（）答案：三元组和十字链表有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[8][5]的地址是（）答案：42若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）A.正确 B.错误B1.广义表((a),a)的表头是(),表尾是().A.aB.bC.(a)D.((a))2.广义表((a))的表头是(),表尾是().A.aB.(a)C.()D.((a))3.广义表((a,b),c,d)的表头是(),表尾是().A.aB.bC.(a,b)D.(c,d)4.广义表(a,b,c,d)的表头是(),表尾是().A.aB.bC.(a,b)D.(b,c,d)5.广义表((a,b,c,d))的表头是(),表尾是().A.aB.()C.(a,b,c,d)D.((a,b,c,d))6.一个广义表的表头是一个广义表,这个断言是().A.正确的B.错误的7.一个广义表的表尾是一个广义表,这个断言是().A.正确的B.错误的CCBCCDADCBBA利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：

(1)L1(apple,pear,banana,orange) (2)L2((apple,pear),(banana,orange)) (3)L3(((apple),(pear),(banana),(orange))) (4)L4((((apple))),((pear)),(banana),orange) (5)L5((((apple),pear),banana),orange) (6)L6(apple,(pear,(banana),orange))L1(apple,pear,banana,orange)T(L1)L(pear,banban,orange)T(L)L(banana,orange)H(L)bananaH(T(T(L1)))L2((apple,pear),(banana,orange))T(L2)L((banana,orange))H(L)L(banana,orage)H(L)bananaH(H(T(L2)))L3(((apple),(pear),(banana),(orange)))H(L3)L((apple),(pear),(banana),(orange))T(L)L((pear),(banana),(orange))T(L)L((banana),(orange))H(L)L(banana)H(L)bananaH(H(T(T(H(L3)))))L4((((apple))),((pear)),(banana),orange)T(L4)L(((pear)),(banana),orange)T(L)L((banana),orange)H(L)L(banana)H(L)bananaH(H(T(T(L4))))L5((((apple),pear),banana),orange)H(L5)L(((apple),pear),banana)T(L)L(banana)H(L)bananaH(T(H(L5)))(6)L6(apple,(pear,(banana),orange))T(L6)L((pear,(banana),orange))H(L)L(pear,(banana),orange)T(L)L((banana),orange)H(L)L(banana)H(L)bananaH(H(T(H(T()))))如图的4棵树二叉树中，（

）不是完全二叉树。

ABCDC在线索化二叉树中，t所指结点没有左子树的充要条件是（

）A.t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不对二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法（

）A.正确B.错误

用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

A.正确B.错误BBA二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（

）

A.正确B.错误设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（

）

A.2hB.2h-1C2h+1Dh+1AB某二叉树的前序遍历节点访问顺序是ａｂｄｇｃｅｆｈ，中序遍历访问顺序是ｄｇｂａｅｃｈｆ，则其后序遍历的节点访问顺序是

ＡｂｄｇｃｅｆｈａＢｇｄｂｅｃｆｈａＣｂｄｇａｅｃｈｆＤｇｄｂｅｈｆｃａD按照二叉树的定义，具有３个节点的二叉树有

种Ａ３Ｂ４Ｃ５Ｄ６一棵二叉树如图所示，其中序遍历是

ＡａｂｄｇｃｅｆｈＢｄｇｂａｅｃｈｆＣｇｄｂｅｈｆｃａＤａｂｃｄｅｆｇｈCdｈabcｅｇｆB在一非空二叉树的中序遍历序列中，根节点的右边

Ａ只有右子树上的所有节点Ｂ只有右子树上的部分节点Ｃ只有左子树的部分节点Ｄ只有左子树上的所有节点任何一棵二叉树的叶子节点在先序，中序和后序遍历序列中的相对次序

Ａ不发生改变Ｂ发生改变Ｃ不能确定Ｄ以上都不对AA如果某二叉树的前序是ｓｔｕｗｖ，中序是ｕｗｔｖｓ，那么后序为

ＡｕｗｖｔｓＢｖｗｕｔｓＣｗｕｖｔｓＤｗｕｔｓｖ设n，m为一棵二叉树上的两个节点，在中序遍历是，n在m前面的条件是

An在m右方Bn是m祖先Cn在m左方Dn是m子孙CC.线索二叉树是一种

结构。A逻辑B逻辑和存储C物理D线性一棵度为2的树与一棵二叉树有何区别？

C在一个图中，所有顶点的度数之和等于所有边数的（）倍。a.1/2b.1c.2d.4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。a.1/2b.1c.2d.4CB一个有n个顶点的无向图最多有（）条边。a.nb.n(n-1)c.n(n-1)/2d.2n在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边

a.nb.n+1c.n-1d.n-2CC对于一个具有ｎ个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）a.nb.(n-1)2c.n-1d.n

2对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（）。1：a.nb.n+1c.n-1dn+e2:a.e/2b.ec.2ed.n+e

DAC已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为（）按广度搜索法进行遍历，则可能得到的一种顶点序列为（）A.a,b,e,c,d,f

B.a,c,f,e,b,d

C.a,e,b,c,f,d

D.a,e,d,f,c,bAa,b,c,e,d,fB.a,b,c,e,f,d

C.a,e,b,c,f,d

D.a,c,f,d,e,bacefbdDB已知一有向图的邻接表存储结构如图所示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）

a.v1,v2,v3,v5.v4b.v1,v2,v3,v4,v5c.v1,v3,v4,v5,v2d.v1,v4,v3,v5,v2123453244524C已知一有向图的邻接表存储结构如图所示。根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）a.v1,v2,v3,v4,v5b.v1,v3,v2,v4,v5c.v1,v2,v3,v5,v4dv1,v4,v3,v5,v2123453244524B采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）a先序遍历b中序遍历c后序遍历d按层遍历采取邻接表存储的图的广度优先遍历算法类似于二叉树的（）a先序遍历b中序遍历c后续遍历d按层遍历

AD用邻接表表示图进行广度优先遍历时，通常是采用

来实现算法的。A．栈B.队列C.树D.图

用邻接表表示图进行深度优先遍历时，通常是采用

来实现算法的。A．栈B.队列C.树D.图BA判定一个有向图是否存在回路除了可以利用拓扑排序方法之外，还可以利用（）a求关键路径的方法b求最短路径的dijkstra方法C广度优先遍历法d深度优先遍历法任何一个无向连通图的最小生成树（）A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在

DA在无权图G的邻接矩阵A中，若（vi,vj）或<vi,vj>属于图G的边集合，则对应元素A[i][j]等于（）否则等于（）已知一个图用邻接矩阵表示，计算第i个结点的入度的方法是_____________删除所有从第i个结点出发的边的方法是___________10第i列非零元素之和

将矩阵第i行全部置为零

如果n个顶点的图是一个环，则它有

____棵生成树。n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为_______。

n个顶点e条边的图，若采用邻接表存储，则空间复杂度为

。设有一稀疏图G，则G采用

存储较省空间。设有一稠密图G，则G采用

存储较省空间。

nO(n2)O(n+e)邻接表邻接矩阵用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度

的次序来得到最短路径的。拓扑排序算法是通过重复选择具有

个前驱顶点的过程来完成的

递增0在数据的存放无规律而言的线性表中进行检索的最佳方法是__________顺序查找法适合于存储结构为（）的线性表

a散列存储b顺序存储或链接存储

c压缩存储d索引存储对线性表进行二分查找时，要求线性表必须（）a以顺序方式存储b以链接方式存储c以顺序方式存储，且结点按关键字有序排序d以链接方式存储，且结点按关键字有序排序顺序查找

bC采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）a.nb.n/2c(n+1)/2d.(n-1)/2采用二分法查找长度为n的线性表时，每个元素的平均查找长度为（）a.O(n2)bO(nlog2n)cO(n)dO(log2n)二分法查找和二叉排序树的时间性能（）a相同b不相同Cdb有一个有序表为(n=13){1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时（）次比较后查找成功a1b2c4d8设哈希表长m＝14，哈希函数H（key）＝key％11。表中已有4个结点：addr（15）＝4addr（38）＝5addr（61）＝6addr（84）＝7其余地址为空,如用二次探测再散列处理冲突，关键字为49的结点的地址是（）a8b3c5d9Cd有一个长度为12的有序表，按二分查找发对该表进行查找，在表内个元素等概率情况下查找成功所需的平均比较次数为（）a35/12b37/12c39/12d43/12顺序查找法的平均查找长度为（）；二分查找法的平均查找长度（）;分块查找法（以顺序查找确定块）的平均查找长度（）;分块查找法（以二分法查找确定块）的平均查找长度（）b(n+1)/2((n+1)*log2(n+1))/n-1(s+2s+n)/2slog(n/s+1)+s/2在各种查找方法中，平均查找长度与结点个数n无关的查找方法是在分块查找法首先查找（）再查找相应的（）在散列函数Ｈ（key）=key%p中p应取（）假设在有序线性表A[1.20]上进行二分查找，则比较一次查找成功的结点数为(),则比较二次查找成功的结点数为（），则比较三次查找成功的结点数为（）则比较4次查找成功的结点数为（）则比较5次查找成功的结点数为（）平均查找长度为（）哈希表查找法索引块素数1个2个4个8个5个3.7在散列存储中，装填因子α的值越大则存取元素时发生冲突的可能性就（）α值越小则（）

折半查找有序表（4，6，10，12，20，30，50，70，88，100）（n=10）。若查找表中元素58，则它将依次与表中

比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50

越大越小A要进行线性查找，则线性表

A；要进行二分查找，则线性表

B；要进行散列查找，则线性表

C。某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为

D，最大比较次数为

E。供选择的答案：A~C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储④既可以以顺序方式，也可以以链表方式存储⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E：①25000②30000③45000④90000答案：A=④B=⑤C=③D＝③E＝④

在二叉排序树中，每个结点的关键码值

A

，

B一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是

C。供选择的答案A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大③比左右子树的所有结点的关键码值都大④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系B:①前序遍历②中序（对称）遍历③后序遍历④层次遍历C：①除最下二层可以不满外，其余都是充满的②除最下一层可以不满外，其余都是充满的③每个结点的左右子树的高度之差的绝对值不大于1④最下层的叶子必须在最左边答案：A＝①B＝②C＝②散列法存储的基本思想是根据

A

来决定

B

，冲突指的是

C，处理冲突的两类主要方法是

D

。供选择的答案A，B：①存储地址②元素的符号③元素个数④关键码值⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间C:①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同③不同