问答题前序遍历树林正好等同于按(1)遍历对应的二叉树，后序遍历树林正好等同于按(2)遍历对应的二又树。【山东工业大学1999二、1(4分)】
问答题设用希尔排序对数组{98，36，一9，0，47，23，1，8，10，7)进行排序，给出的步长(也称增量序列)依次是4，2，1，则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。【南京理工大学1997三、5(2分)】
问答题已知深度为h的二叉树，以一维数组BT[0．．2
h
-2]作为其存储结构，试编写一算法，求该二叉树中叶子结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。【中南大学2003八(10分)】
问答题给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data，next)，data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求：不允许使用数组作辅助空间)。【华中科技大学2000年】
问答题对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【厦门大学2006三、3(25／3分)】
问答题证明对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全零的充要条件是该图是无环图。【北京邮电大学2002三(10分)】
问答题设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。【南京航空航天大学1996九、1(4分)】
问答题已知L1、L2分别为两循环单链表的头结点指针，m，n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
问答题试写出复制一棵二叉树的算法。二叉树采用标准链接结构。【山东大学2000二(10分)】
问答题一棵高度为h的满k叉树有如下性质：根结点所在层次为0；第h层上的结点都是叶子结点；其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：
问答题若无向图满足__________，则该图是树。【中国科学技术大学2004】
问答题设栈S和队列Q的初始状态为空，元素1、2、3、4、5、6依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是2、4、3、6、5、1，则栈的容量至少应该是多少?【厦门大学2006一、1(20／3分)】
问答题设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针)域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Loga,te(L，x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学1997年】
问答题一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。【浙江大学1994五(8分)】
问答题设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。
问答题设有一组数据black，blue，green，purple，red，white，yellow，它们的查找概率分别为0．10，0．08，0．12，0．05，0．20，0．25，0．20。试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。【清华大学1997七(12分)】
问答题考虑下图：(1)从顶点A出发，求它的深度优先生成树。(2)从顶点E出发，求它的广度优先生成树。(3)根据普利姆(Prim)算法，求它的最小生成树。【上海交通大学1999六(12分)】
问答题一棵2-3树的形状定义如下：
·一个结点包含一个关键字或两个关键字。
·每个结点最少有两个子女(如果它包含一个关键字)，最多有三个子女(如果它包含两个关键字)。
·每个结点的结构是(leftChild,leftKey,midChild,rightKey,rightChild)。
其中，关键字leftKey＜rightKey，且指针leftChild所指子树上所有结点包含的关键字均小于leftKey；指针midChild所指子树上所有结点包含的关键字均大于leftKey，小于rightKey；指针：rightChild所指子树上所有结点包含的关键字均大于rightKey。
·所有失败结点都在树的同一层上，它们都是查找失败到达的结点，指向它们的指针都是空的。因此树的高度总是平衡的。
根据以上定义，试回答下列问题，并说明理由：
问答题回答问题并填空。(1)(2分)散列表存储的基本思想是什么?(2)(4分)散列表存储中解决碰撞的基本方法有哪些?其基本思想是什么?(3)(4分)用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方法?他们各有何特点?(4)(3分)用线性探查法解决碰撞时，如何处理被删除的结点?为什么?(5)(2分)散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。【山东工业大学1999四(15分)】
问答题设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：1)找出最小值结点，且打印该数值。2)若该数值是奇数，则将其与直接后继结点的数值交换。3)若该数值是偶数，则将其直接后继结点删除。【东北大学2000年】