2021-2022-1数据结构期末考试卷B .pdfVIP

2021-2022-1数据结构期末考试卷B

一、单项选择题（共20题，20分）

1、采用分块查找时,若线性表共有625个元素,查找每个元素的概率相等,假设采用顺序查找来

确定结点所在的块时,每块分()个结点最佳。（1.0）

A、6

B、10

C、25

D、625

正确答案：C

2、计算出的地址分布最均匀的散列函数是()。（1.0）

A、数字分析法

B、除留余数法

C、平方取中法

D、折叠法

正确答案：B

3、设S=,则LenStr(S)=()。（1.0）

A、0

B、1

C、2

D、3

正确答案：A

4、设目标串T=aabaababaabaa,模式P=abab,模式匹配算法的外层循环进行了()次。（1.0）

A、1

B、4

C、5

D、9

正确答案：C

5、*下列程序的空间复杂度是()

for(i=1;i=n;++i){

for(j=1;j=m;++j){

c[i][j]=0;

}

}（1.0）

A、O(m*n)

B、O(m+n)

C、O(m-n)

D、O(m/n)

正确答案：A

6、算法的计算量大小称为算法的()。（1.0）

A、现实性

B、难度

C、效率

D、时间复杂度

正确答案：D

7、设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出

队操作后其头指针front的值为()（1.0）

A、front=front+1

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

C、front=(front-1)%m

D、front=(front+1)%m

正确答案：D

8、以下哪一个不是队列的基本运算。()（1.0）

A、从队尾插入一个新元素

B、从队列中删除第i个元素

C、判断一个队列是否为空

D、读取队头元素

正确答案：B

9、广义表((a,b),c,d)的表头是()。（1.0）

A、a

B、d

C、(a,b)

D、(c,d)

正确答案：C

10、下列矩阵是一个()。

（1.0）

A、对称矩阵

B、三角矩阵

C、稀疏矩阵

D、带状矩阵

正确答案：B

11、直接插入排序的方法要求被排序的数据()存储。（1.0）

A、必须链表

B、必须顺序

C、顺序或链表

D、可以任意

正确答案：B

12、内排序是指在排序的整个过程中,全部数据都在计算机的()中完成的排序。（1.0）

A、内存

B、外存

C、内存和外存

D、寄存器

正确答案：A

13、在树结构中,若结点B有4个兄弟,A是B的父亲结点,则A的度为()。（1.0）

A、3

B、4

C、5

D、6

正确答案：C

14、线索二叉树是一种()结构。（1.0）

A、线性

B、逻辑

C、逻辑和存储

D、物理

正确答案：D

15、在一个具有n个顶点的无向图中,要连通全部顶点至少需要()条边。（1.0）

A、n

B、n+1

C、n-1

D、n/2

正确答案：C

16、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。（1.0）

A、1/2

B、1

C、2

D、4

正确答案：B

17、线性表是()。（1.0）

A、一个有限序列,可以为空

B、一个有限序列,不能为空

C、一个无限序列,可以为空

D、一个无限序列,不能为空

正确答案：A

18、*在单链表L中,指针p所指结点有后继结点的条件是()（1.0）

A、p=p.next

B、p.next!=null

C、p.next=null

D、p.next=p.next.next

正确答案：B

19、栈的插入、删除操作在()进行。（1.0）

A、任意位置

B、指定位置

C、栈顶

D、栈底

正确答案：C

20、设有编号为1,2,3,4的4辆列车,顺序进入一个栈结构的站台,下列不可能的出站顺序为()。

（1.0）

A、1234

B、1243

C、1324

D、1423

正确答案：D

二、基础填空题（共10题，10分）

1、散列表的查找效率主要取决于散列表造表时选取的散列函数和处理___