问答题给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
问答题高度为4的3阶B一树中，最多有__________个关键字。【合肥工业大学2000三、9(2分)】
问答题用算法说明在对称序线索树中，如何对任意给定的结点直接找出该结点的对称序后继。【山东大学1999六、3(10分)】
问答题二部图(biparite graph)G=(V，E)是一个能将其结点集V分为两个不相交子集V1和V2= V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何两个结点在图G中也均不相邻。(1)请各举一个结点个数为5的二部图和非二部图的例子。(2)请用C或Pascal编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【浙江大学1998八(15分)】
问答题组织成循环链表的可利用空间表附加什么条件时，首次适配策略就转变为最佳适配策略?【北方交通大学1998四(8分)】
问答题假设稀疏矩阵只存放其非0元素的行号、列号和数值，以一维数组顺次存放，行号-1作结束标志。例如，如下所示的稀疏矩阵M，存放在一维数组D中，D的元素如下：D[0]=0，D[1]=0，D[2]=1，D[3]=0，D[4]=4，D[5]=10，D[6]=2，D[7]=8，D[8]=5，D[9]=-1。现有两个如上方法存储的稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，编写求矩阵加法C=A+B的算法，C亦放在数组C中。
问答题设有关键码序列10，20，35，40，44，51，65，70，85，91，93，95。试按照最大关键码复写原则绘出相应的2阶B+树。【山东工业大学1 996二、1(6分)】
问答题用单链表保存m个整数，结点的结构为(data，link)，且｜data｜
要求：
(1)给出算法的基本思想。
(2)使用C或C++语言，给出单链表结点的数据类型定义。
(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(4)说明所涉及算法的时间复杂度和空间复杂度。
问答题已知带头结点的单链表有data和next两个域，设计一个算法，将该链表中的重复元素结点删除。【北京邮电大学2005五、2(10分)】【苏州大学2005三(15分)】
问答题n个顶点e条边的图采用邻接表存储，则空间复杂度是__________。【东南大学2005数据结构部分二、8(1分)】
问答题试给出有向图的所有拓扑序列。【北京交通大学2005五、3(5分)】
问答题辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设用K[1]，K[2]，…，K[n]表示n个结点的值，用T[1]，T[2]，…，T[n]表示辅助地址表。初始时T[i]：=i，在排序中，凡需对结点交换就用它的地址来进行。例如当n=3时，对K(31，11，19)则有T(2，3，1)。试编写实现辅助地址表排序(按非递减序)算法的语句序列。【重庆大学2000四、2】
问答题已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有，则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的运算要自己实现。(尽量采用非递归算法，否则满分15分)【北京工业大学2000六(20分)】
问答题利用BCLA加法器和CLA电路设计20位加法器，要求： (1)构建20位单级先行进位加法器： ①使用5个四位的BCLA加法器； ②使用4个五位的BCLA加法器； 分别画出连接简图(请特别标明进位信号)。比较这两种方法得到的最长进位延迟时间有无区别。 (2)构建20位二级先行进位加法器： ①使用5个四位的BCLA加法器和1个五位的CLA电路； ②使用4个五位的BcLA加法器和1个四位的CLA电路； 分别画出连接简图(请特别标明进位信号)。比较这两种方法得到的最长进位延迟时间有无区别。
问答题在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。【中国科技大学1998一、4(3分)】
问答题高度为五的堆中，最多有__________个元素，最少有__________个元素。【哈尔滨工业大学2005一、4(1分)】
问答题给定一个关键字集合{25，18，34，9，14，27，42，51，38}，假定查找各关键字的概率相同，请画出其最佳二叉排序树。
问答题在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质?为什么?【上海交通大学2003五(10分)】
问答题试设计一个C算法(或C程序)：用单链表作存储结构，以回车符为结束标志，输入一个任意长度的字符串；然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”)，输出信息“Yes”或“No”；最后删除字符串并释放全部空间。例如：若输入“ABCDl2321DCBA”，是回文，则输出“YeS”；若输入“ABCDl23DCBA”，不是回文，则输出“No”。要求：定义相关数据类型，不得使用数组(顺序表)作字符串的存诸结构和辅助存储空间。假定字符串的长度为n，试分析上述算法的时间复杂度。【华中科技大学2004五(10分)】
问答题由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序中所缺的语句。
#define MAX 100
typedef struct Node
{char info；struct Node*llink，*rlink；)TNODE；
char pred[MAX]，inod[MAX];
main(int argc，int**argv)
{TNODE*rootj
if(argcinfo=(1) ;
for((2) ；rposllink=restore(ppos+1，(4) ，k)；
ptr->rlink=restore((5) +k，rpos+l，n一1一k);
return ptr；
}
postorder(TNODE*ptr)
{if(ptr=NULL)return；
postorder(ptr->iiink)；
postorder(ptr一>rlink)；
printf(“％c”，ptr一>info);
}
【中科院计算所2000三(10分)】