山东大学2001一判断题1．顺序查找法适用于存储结构为顺序或链接存储的线行表。2．一个广义表可以为其他广义表所共享。3．快速排序是选择排序的算法。4．完全二叉树的某结点若无左子树，则它必是叶子结点。5．最小代价生成树是唯一的。6．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。7．存放在磁盘，磁带上的文件，即可意识顺序文件，也可以是索引文件。8．折半查找法的查找速度一定比顺序查找法快。二选择题1．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.nB.2n-1C.2nD.n-12.在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序B.气泡排序C.简单选择排序D.快速排序3.高度为K的二叉树最的结点数为（）。A.24.一个栈的输入序列是12345，则占的不可能的输出序列是（）A.54321B.45321C.43512D.123455.ISAM文件和VASM文件属于（）A索引非顺序文件B.索引顺序文件C.顺序文件D.散列文件6.任何一棵二叉树的叶子结点在先序，中序和后序遍历序列中的相对次序（）A.不发生变化B.发生变化C.不能确定D.以上都不对7.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A.acbedB.decabC.deabcD.cedba三．填空题1．将下图二叉树按中序线索化，结点的右指针指向（），Y的左指针指向（）ABDCXEY2．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四各度为4的结点和若干叶子结点，则T的叶结点数为（）3．抽象数据类型的定义仅取决与它的一组（），而与（）无关，即不论其内部结构如何变化，只要它的（）不变，都不影响其外部使用。4.VSAM(虚拟存储存取方法)文件的优点是：动态地（），不需要文件进行（），并能较快的（）进行查找。5．快速排序法在（）情况下最不利于发挥其长处，在（）情况下最易发挥其长处。6．利用广义表的GetHead和GetTail操作，从广义表L=（（apple，pear），（banana，，orange））中分离出原子banana的函数表达式是（）。7．N（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是（）。８．有２０００个数据的线性表，分成（）块最理想，每块的理想长度是（），若每块长度为20，平均查找长度是（）。9．广义表(a,(a,b),d,c,((I,j),k))的长度是（），深度是（）。四．(6分)假设一棵二查树的层次序列（按层树递增顺序排列，同一层次自左向右）为BCDAFEHIG。请画出该二查树，并将其转换为对应的树。五．（8分）给出一...
