(0012)数据结构复习思考题.doc

(0012)《数据结构》复****思考题一、选择题1、某二叉树的先序序列和后序序列正好相同,则该二叉树一定是()的二叉树。 ,时间复杂度不受数据初始状态影响,恒为O(log2n)的是() ,()算法可能会出现下面情况:初始数据有序时,花费的时间反而最多。 ,则下列序列中不可能是栈的输出序列的是() ~n,其头尾指针分别为f和r,则其元素个数为()-f -f+1C.(r-f)modn+1 D.(r-f+n),则采用()存储方式最节省时间。 ,值为非空的链域的个数为()-1 -+1 +,其空指针域数为() [5][6]的每个元素占5个单元,将其按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A[5,5]的地址为() ()(n) (n+e)(n2) (n×e),则查找A[3]的比较序列的下标依次为(),2,3 ,5,2,,5,3 ,4,2,()(n) (nlog2n)(n2) (log2n),某一趟结束后未必能选出一个元素放在其最终位置上的是() ,仍不能有效求解的问题是()()(n) (n3)(n2) (n+e)() ()(根的层次为1)。 ,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则应作()型调整以使其平衡。 ,如果仅要求求出其中最大的10个元素,则采用()排序算法最节省时间。 、,一定得到不同的二叉排序树。(),因此前者一定比后者花费的时间多。(),不会改变front指针的值。()…n,其输出序列的第一个元素为n,则其输出序列的每个元素ai一定满足ai=n-i+1(i=1,2...,n)()。()。(),顶点i的人度等于邻接矩阵中第i列的元素个数。。(),再重新插入上去,一定能得到原来的二叉排序树。(),则其弧数必为n-1(其中n为G的顶点数)。()11、二路归并排序的核心操作是将两个有序序列归并为一个有序序列。()12、二叉树只能采用二叉链表来存储。()13、数据项是数据基本单位()14、一个无环有向图的拓扑序列必然是唯一的()15、任何一个无向连通图的最小生成树只有一个()16、已知完全二叉树有64个结点,则整个二叉树没有度为1结点。()17、线性表的插入和删除的时间复杂度和存储结构没有关系()18、空格串和空串是一样的()19、哈夫曼树一定是满二叉树。()20、队列只能采用链式存储方式。()三、填空题1、在有n个叶子结点的哈夫曼树中,其结点总数为。2、将下三角矩阵A「1..8,1..8」的下三角部分逐行地存储到起始地址为1000的内存单元中