山东大学数据结构课程试卷及参考答案.docx

山东大学数据结构课程试卷及参考答案

选择题（每题2分，共20分）

1.下列哪一个不是线性结构的特点？

A.有且只有一个根结点

B.每个结点最多有一个前驱和一个后继

C.至少有一个结点

D.第一个结点没有前驱，最后一个结点没有后继

答案：C

2.在链表中，元素之间的关系是（）。

A.物理相邻

B.逻辑相邻

C.顺序存储

D.随机存储

答案：B

3.下面关于栈的叙述中，错误的是（）。

A.栈是一种先进后出的线性表

B.栈的插入和删除操作都是在线性表的一端进行

C.栈的插入和删除操作都是在线性表的另一端进行

D.栈的底端是固定的

答案：C

4.下列哪种排序算法的时间复杂度是O(nlogn)？

A.冒泡排序

B.快速排序

C.插入排序

D.选择排序

答案：B

5.在二叉树中，具有3个结点的二叉树有（）种形态。

A.1

B.2

C.3

D.4

答案：D

填空题（每题2分，共20分）

6.在链表中，存储元素的数据域称为______，存储元素前驱结点地址的域称为______。

答案：数据域，指针域

7.栈和队列的共同特点是______。

答案：先进先出

8.在二叉树中，度为0的结点数n0与度为2的结点数n2之间的关系是______。

答案：n0=n2+1

9.线性表的顺序存储结构称为______，链式存储结构称为______。

答案：顺序表，链表

10.快速排序算法的基本思想是______。

答案：分而治之

判断题（每题2分，共20分）

11.线性表是n个数据元素的有限序列，其中n可以是0。（）

答案：√

12.在链表中，最后一个结点的指针域为NULL，表示没有后继结点。（）

答案：√

13.栈和队列都是特殊的线性表，它们的操作只能在表的端点进行。（）

答案：√

14.二叉树中的每个结点最多有两个子结点。（）

答案：√

15.任何排序算法的时间复杂度都不可能低于O(nlogn)。（）

答案：×（冒泡排序、插入排序等的时间复杂度可以达到O(n^2)）