数据结构习题集(总)

A. 直接插入排序 B. 直接选择排序 C. 快速排序 D. 不确定 9．41以下排序方法中，稳定的排序方法是__________。

A. 直接插入排序和冒泡排序 B. 直接插入排序和希尔排序 C. 希尔排序和快速排序 D. 冒泡排序和快速排序

名词解释

1． 数据结构 数据逻辑结构 数据物理结构 算法 2． 线性表 顺序存储 链式存储 3． 栈 队列

4． 二叉树 满二叉树 完全二叉树 哈夫曼树 5． 查找 静态查找 排序 内部排序

三、判断题(对的打?,错的打?)

（ ） 1.数据项是数据处理的最小单位。

（ ） 2.线性表的顺序存储和链式存储都必须占用内存中的连续存储单元。 （ ） 3.栈的特点是后进先出,队列的特点是先进先出。 （ ） 4.空串是任意串的子串。

（ ） 5.在满二叉树中,存在度为1的结点。 （ ） 6.数据元素是数据处理的最小单位。

（ ） 7.顺序存储的线性表可以随机访问,链式存储的线性表只能顺序访问。 （ ） 8.栈和队列都是操作受限制的线性表。

（ ） 9.串中任意个字符组成的子序列称为该串的子串。

（ ） 10.二叉树中每个结点的度最大为2,因此二叉树是一种特殊的树。 （ ） 11.数据元素是数据处理的基本单位。

（ ） 12.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。 （ ） 13.栈和队列的存储方式,既可以顺序存储也可以链式存储。

（ ） 14.衡量排序算法的两个主要性能指标是执行排序算法所需要的时间和执行排序算法所需要的附加空间。

（ ） 15.在任意一棵二叉树中,叶子结点的个数等于度为2结点的个数加1。 （ ） 16.由树转化为二叉树,其根结点的右子树总是空的。

（ ） 17.树的先根遍历序列等同于该树对应的二叉树中序遍历序列。

（ ） 18.中序线索二叉树的优点是便于在中序遍历二叉树时查找前驱结点和后继结点。 （ ） 19.哈夫曼树是带权值的树,且权值较大的结点离树较近。 （ ） 20.一棵哈夫曼树有m 个叶子结点,则其结点总数为2m-1。

9.12对于同一组待输入的关键值集合，虽然个关键值的输入顺序不同，但得到的二叉排序树是相同的。( ) 9.13对于两棵就有相同数据元素二形状不同的二叉排序树，按中序遍历它们得到的数据元素的排列是一样的。（ ）

9.14 在二叉排序树中插入新结点时，不必移动其他结点，仅需改动某个结点的指针，是它由空变为非空即可。（ ）

9.15在二叉排序树上删除一个结点时，不必移动其它结点，只需将其双亲结点相应的指针域置空即可。（ ） 9.16平衡的二叉排序树的任何子树都是平衡的二叉排序树。（ ）

6.只有最下面的两层结点的度数可以小于２，其他结点的度必须等于２的二叉树才是平衡的二叉树。（ ）

17

7.任意一棵二叉树的平均查找时间都小于用顺序查找算法搜索同一结点的顺序表的平均查找时间。（ ）

18