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

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

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

1、散列函数有一个共同性质,即函数值应当以()取其值域的每个值。（1.0）

A、最大概率

B、最小概率

C、同等概率

D、平均概率

正确答案：C

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

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

A、6

B、10

C、25

D、625

正确答案：C

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

A、0

B、1

C、2

D、3

正确答案：A

4、某串的长度小于一个常数,则采用()存储方式最节省空间。（1.0）

A、链式

B、顺序

C、堆结构

D、无法确定

正确答案：B

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

A、现实性

B、难度

C、效率

D、时间复杂度

正确答案：D

6、*下列程序的时间复杂度是()

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

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

c[i][j]=0;

}

}（1.0）

2

A、O(n)

B、O(n)

C、O(2n)

2

D、O(2n)

正确答案：A

7、带头结点的链队列LQ示意图如下,链队列的队头元素是()。

（1.0）

A、A

B、B

C、C

D、D

正确答案：A

8、一个循环队列一旦说明,其占用空间的大小()。（1.0）

A、已固定

B、可以变动

C、不固定

D、动态变化

正确答案：A

9、已知二维数组A[6][10],每个数组元素占4个存储单元,若按行优先顺序存放数组元素a[3][5]

的存储地址是1000,则a[0][0]的存储地址是()。（1.0）

A、872

B、860

C、868

D、864

正确答案：B

10、对下述矩阵进行压缩存储后,失去随机存取功能是()。（1.0）

A、对称矩阵

B、三角矩阵

C、三对角矩阵

D、稀疏矩阵

正确答案：D

11、直接插入排序的方法是从第()个元素开始,插入到前边适当位置的排序方法。（1.0）

A、1

B、2

C、3

D、n

正确答案：B

12、排序是根据()的大小重新安排各元素的顺序。（1.0）

A、关键字

B、数组

C、元素件

D、结点

正确答案：A

13、把一棵树转换为二叉树后,这棵二叉树的形态是()。（1.0）

A、唯一的

B、有多种

C、有多种,但根结点都没有左孩子

D、有多种,但根结点都没有右孩子

正确答案：A

14、有100个结点的完全二叉树从上到下,从左到右依次对结点编号,根结点的编号为1,则编号

为45的结点的左孩子编号为()。（1.0）

A、46

B、47

C、90

D、91

正确答案：C

15、深度优先遍历类似于二叉树的()。（1.0）

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

正确答案：A

16、求最短路径的Dijkstra算法的时间复杂度为()。（1.0）

A、O(n)

B、O(n+e)

2

C、O(n)

D、O(n×e)

正确答案：C

17、单向链表的存储密度()。（1.0）

A、大于1

B、等于1

C、小于1

D、不能确定

正确答案：C

18、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为()。（1.0）

A、O(1)

B、O(n)

2

C、O(n)

D、O(logn)

2

正确答案：B

19、带头结点的链栈LS的示意图如下,栈顶元素是()。

（1.0）

A、A

B、B

C、C

D、D

正确答案：A

20、经过下列栈的运算后,再执行ReadTop(s)的值是()。

ssasbs

InitStack();Push(,);Push(,);Pop();（