抽象数据类型

(1)【◆题库问题◆】：[名词解释] 抽象数据类型

【◆参考答案◆】：
是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(2)【◆题库问题◆】：[判断题] 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。
A．正确
B．错误

【◆参考答案◆】：正确

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(3)【◆题库问题◆】：[判断题] 子串在主串中的位置指的是该子串的最后一个字符在主串中的位置。
A．正确
B．错误

【◆参考答案◆】：正确

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(4)【◆题库问题◆】：[判断题] 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
A．正确
B．错误

【◆参考答案◆】：正确

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(5)【◆题库问题◆】：[问答题] 对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于O（n2）的排序方法；（2）所需辅助空间最多的排序方法；

【◆参考答案◆】：(1) 希尔、快速、堆、归并(2) 归并

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(6)【◆题库问题◆】：[单选] 把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A．唯一的
B．有多种
C．有多种，但根结点都没有左孩子
D．有多种，但根结点都没有右孩子

【◆参考答案◆】：A

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(7)【◆题库问题◆】：[单选] 下列排序算法中（）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A．快速排序
B．shell排序
C．堆排序
D．冒泡排序

【◆参考答案◆】：B

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(8)【◆题库问题◆】：[问答题] 对链表设置头结点的作用是什么？（至少说出两条好处）

【◆参考答案◆】：
（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(9)【◆题库问题◆】：[填空题] 图的深度优先遍历序列（）惟一的

【◆参考答案◆】：不是

·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。·ℳ°．·※°∴ ╰☆╮ 。

(10)【◆题库问题◆】：[判断题] 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。
A．正确
B．错误

【◆参考答案◆】：正确