问答题一棵高度为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年】
问答题给出一组关键字T=(12，2，16，30，8，28，4，10，20，6，18)，写出用下列算法从小到大排序时第一趟结束时的序列：
问答题证明：具有n个顶点的无向图最多有n{n-1)/2条边。
问答题证明二叉排序树用中序遍历时输出的信息是由小到大排序的。【中国海洋大学2005五(15分)】
问答题一棵有n个结点的二叉树，叶子结点的数量为加，度为2的结点数量为，n2，则n0与n2的关系是(1) ；如果用二叉链表存储该二叉树，则空指针数量为(2)。【电子科技大学2013一、1(2分)】
问答题试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学2001二、2(8分)】
问答题一个有2001个结点的完全二叉树的高度是__________。【南京理工大学1997三、2(1分)】
问答题在基于关键字比较且时间为O(nlog
2
n)的排序中，若要求排序是稳定的，则可选用__________ 排序；若要求就地排序(及辅助空间为O(1))，则可选用__________排序。【中国科学技术大学1998一、7(2分)】
问答题分析下述算法功能 Status A(BiThrTree T，Status(*Visit)(TglemType e)){ p—T一>lchild； while(p!一T){ while(p一>LTag==Link)p=p->lChild； if(!Visit(p-->data))return ERRoR； while(p一>RTag一=Thread&&p->rchild!=T){ p=p->rchild； Visit(p-->data)； } p=p->rchild； } return OK； }
问答题设高为h的m阶B一树上共有k个关键字，则其叶子结点有__________个。【北京交通大学2006二、8(2分)】