严蔚敏版数据结构复习题.docVIP

数据结构复习题集 一、判断题线性表的长度是线性表所占用的存储空间的大小。?(???) 2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。(???)? 3.在对链队列做出队操作时，不会改变front指针的值。(???) 4.如果两个串含有相同的字符，则说它们相等。(???)? 5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。(???)? 6.已知一棵树的先序序列和后序序列，一定能构造出该树。(???)? 7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。(???) 8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。(???)? 9.对一个堆按层次遍历，不一定能得到一个有序序列。(???)? 10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n)。(???)? 11.? 线性表的逻辑顺序与物理顺序总是一致的。??(???)? 12.? 线性表的顺序存储表示优于链式存储表示。??(???)? 13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。???(???) 14.? 二维数组是其数组元素为线性表的线性表。??(???) 15.? 每种数据结构都应具备三种基本运算：插入、删除和有哪些信誉好的足球投注网站。??(???)? 16.（101，88，46，70，34，39，45，58，66，10）是堆；(???) 17.将一棵树转换成二叉树后，根结点没有左子树；(???) 18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；(???) 19.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离较近(??) 20.用一组地址连续的存储单元存放的元素一定构成线性表。(??) 21.堆栈、队列和数组的逻辑结构都是线性表结构。(?) 22.给定一组权值，可以唯一构造出一棵哈夫曼树。(??) 23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。索引表可以常驻内存。(???) 24.在平均情况下，快速排序法最快，堆积排序法最节省空间。(?) 25.快速排序法是一种稳定性排序法。(???)? 二.选择题: 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.先序线索二叉树中求先序后继????B.?中序线索二叉树中求中序后继??C.中序线索二叉树中求中序前驱????D.?后序线索二叉树中求后序后继?4．求最短路径的FLOYD算法的时间复杂度为（D）。?A.O(n)??????????B.O(n+e)????????C.O(n2)??????????D.O(n3)? 5．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。? A.0??????????B.1???????C.2??????D.不确定?6．????数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（A）。???????A.1140????????B.1145???????C.1120??????D.1125? 7．????在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（A）。? A.快速排序??????????B.希尔排序???????C.冒泡排序??????????D.堆排序? 某算法的空间花费s(n)=100nlog2n+1000n+2000,其空间复杂度为 [??? ]　　A.O(1)?????????????????????? B.O(n)???? C.O(n1.5)??????????????????? D.O(nlog2n)9．????下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D）。?A.堆排序??????????B.冒泡排序???????C.快速排序??????D.直接插入排序?10．????在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（B）型调整以使其平衡。?A.LL??????????B.LR???????C.RL??????D.RR? 设单链表中结点的结构为??? typedef?? struct