数据结构真题题库及答案.docVIP

数据结构真题题库及答案

单项选择题（每题2分，共10题）

1.下列数据结构中，属于非线性结构的是（）

A.循环队列B.带链队列C.二叉树D.带链栈

答案：C

解析：线性结构满足有且仅有一个根节点和每个节点最多有一个前驱和一个后继。二叉树每个节点可以有两个子节点，是非线性结构。循环队列、带链队列、带链栈都属于线性结构。

2.设循环队列的存储空间为Q(1:35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为（）

A.15B.16C.20D.0或35

答案：D

解析：当front=rear时，有两种情况，一是队列为空，此时元素个数为0；二是队列满，此时元素个数为队列容量35。

3.下列排序方法中，最坏情况下比较次数最少的是（）

A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序

答案：D

解析：冒泡排序、简单选择排序、直接插入排序最坏情况比较次数都是n(n-1)/2，堆排序最坏情况比较次数是O(nlog?n)，所以堆排序比较次数最少。

4.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）

A.12345ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA

答案：B

解析：栈是先进后出的结构，所以入栈顺序为1、2、3、4、5、A、B、C、D、E，出栈顺序则是EDCBA54321。

5.下列叙述中正确的是（）

A.有一个以上根节点的数据结构不一定是非线性结构

B.只有一个根节点的数据结构不一定是线性结构

C.循环链表是非线性结构

D.双向链表是非线性结构

答案：B

解析：有一个以上根节点的数据结构一定是非线性结构，A错误；只有一个根节点的数据结构不一定是线性结构，如二叉树，B正确；循环链表和双向链表都属于线性结构，C、D错误。

6.某二叉树共有7个节点，其中叶子节点只有1个，则该二叉树的深度为（假设根节点在第1层）（）

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

答案：D

解析：叶子节点只有1个，说明该二叉树每层只有一个节点，共7个节点，所以深度为7。

7.下列关于栈的叙述正确的是（）

A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据

C.只能在栈底插入数据D.不能删除数据

答案：B

解析：栈的特点是先进后出，在栈顶进行插入和删除操作。

8.算法的空间复杂度是指（）

A.算法在执行过程中所需要的计算机存储空间

B.算法所处理的数据量

C.算法程序中的语句或指令条数

D.算法在执行过程中所需要的临时工作单元数

答案：A

解析：算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。

9.下列叙述中正确的是（）

A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C.顺序存储结构能存储有序表，链式存储结构不能存储有序表

D.链式存储结构比顺序存储结构节省存储空间

答案：A

解析：顺序存储结构存储一定连续，链式存储结构存储空间不一定连续，A正确；顺序和链式存储结构都可用于线性和非线性结构，B错误；两者都能存储有序表，C错误；顺序存储结构可能更节省存储空间，D错误。

10.下列排序方法中，属于稳定排序的是（）

A.快速排序B.堆排序C.冒泡排序D.简单选择排序

答案：C

解析：冒泡排序是稳定排序，快速排序、堆排序、简单选择排序都是不稳定排序。

多项选择题（每题2分，共10题）

1.下列数据结构中，属于线性结构的有（）

A.顺序表B.链表C.栈D.队列E.二叉树

答案：ABCD

解析：顺序表、链表、栈、队列都满足线性结构特点，二叉树是非线性结构。

2.以下哪些是常见的查找算法（）

A.顺序查找B.二分查找C.哈希查找D.冒泡查找E.选择查找

答案：ABC

解析：顺序查找、二分查找、哈希查找是常见查找算法，冒泡查找和选择查找是排序算法。

3.关于二叉树的遍历，正确的有（）

A.前序遍历根左右B.中序遍历左根右C.后序遍历左右根

D.层序遍历按层次E.先序遍历根右左

答案：ABCD

解析：二叉树遍历方式包括前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层序遍历（按层次）。

4.下列属于内部排序算法的有（）

A.插入排序B.归并