的是（A）A提高检索效率B提高存储效率C减少数据的冗余D方便文件的修改二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16数据结构由数据的逻辑结构、存储结构和数据的_运算运算____三部分组成。运算17在单链表中某结点后插入一个新结点，需要修改_____2__2_____个结点指针域的值。18设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是________3__3________。19长度为零的串称为_空串_______________。空串_20广义表Gab，c，d，e，f，G的长度为___4________。421一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是______左右指针域均为空左右指针域均为空__________。左右指针域均为空22一个有
个顶点的无向连通图，最少有__
1_
1____条边。23当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是___直接插入排序直接插入排序__。直接插入排序24在一棵深度为h的具有
个结点的二叉排序树中，查找任一结点的最多比较次数是_____
_
_____。_
25不定长文件指的是文件的__记录含有的信息长度记录含有的信息长度___大小不固定。记录含有的信息长度三、解答题（本大题共4小题，每小题5分，共20分）26已知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG，请回答下列问题：1画出此二叉排序树；2若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。1画出此二叉排序树解：1画出此二叉排序树（2）画出对应的森林27已知有向图的邻接表如图所示，请回答下面问题：1给出该图的邻接矩阵；2从结点A出发，写出该图的深度优先遍历序列。EBACDFHGEBCDAFHG该图的邻接矩阵如下：解：该图的邻接矩阵如下：01100001100000100100100102图的深度优先遍历序列如下图的深度优先遍历序列如下：2图的深度优先遍历序列如下：ABCED28已知待排记录的关键字序列为25，96，11，63，57，78，44，请回答下列问题：
f1画出堆排序的初始堆（大根堆）；2画出第二次重建堆之后的堆。解：1堆排序的初始堆大根堆）堆排序的初始堆（1堆排序的初始堆（大根堆）2第二次重建堆之后的堆2第二次重建堆之后的堆29已知关键字序列为56，23，41，79，38，62，18，用散列函数Hkeykey11将其散列到散列96632557781144786325574411HT010r