严蔚敏版数据结构复习题

数据结构复习题集 一、判断题 1.线性表的长度是线性表所占用的存储空间的大小。 ( F ) 2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。( F ) 3.在对链队列做出队操作时，不会改变 front指针的值。( F ) 4.如果两个串含有相同的字符，则说它们相等。( F ) 5.如果二叉树中某结点的度为 1，则说该结点只有一棵子树。( T ) 6.已知一棵树的先序序列和后序序列，一定能构造出该树。( F ) 7.图 G的一棵最小代价生成树的代价未必小于 G的其它任何一棵生成树的代价。( T ) 8.图 G的拓扑序列唯一，则其弧数必为 n-1（其中 n为顶点数）。( F ) 9.对一个堆按层次遍历，不一定能得到一个有序序列。( T ) 10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为 O(n2)。( T ) 11. 线性表的逻辑顺序与物理顺序总是一致的。 ( F ) 12. 线性表的顺序存储表示优于链式存储表示。 ( F ) 13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。 ( T ) 14. 二维数组是其数组元素为线性表的线性表。 ( F ) 15. 每种数据结构都应具备三种基本运算：插入、删除和搜索。 ( T ) 16.（101，88，46，70，34，39，45，58，66，10）是堆；( T ) 17.将一棵树转换成二叉树后，根结点没有左子树；( F ) 18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；( F ) 19.哈夫曼树是带权外部路径长度最短的树，路径上权值较大的结点离根较近( T ) 20.用一组地址连续的存储单元存放的元素一定构成线性表。( F ) 21.堆栈、队列和数组的逻辑结构都是线性表结构。( T ) 22.给定一组权值，可以唯一构造出一棵哈夫曼树。( F ) 23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。索引表可以常驻内存。( T ) 24.在平均情况下，快速排序法最快，堆积排序法最节省空间。( T ) 25.快速排序法是一种稳定性排序法。( F ) 二.选择题: 1.一个栈的输入序列为 12345，则下列序列中是栈的输出序列的是（A）。 A.23415 B.54132 C.31245 D.14253 2． 设循环队列中数组的下标范围是 1~n，其头尾指针分别为 f和 r，则其元素个数为（D）。 A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n 3． 二叉树在线索化后，仍不能有效求解的问题是（D）。 A.先序线索二叉树中求先序后...