问答题
问答题给定一个整数数组b[0．N-1]，6中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【中科院计算所1999五、2(20分)】
问答题设计一个求两个集合A和B之差C=A—B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是c中的一个元素。集合用有序链表实现，初始时，A、B集合中的元素按递增排列，C为空；操作完成后，A、B保持不变，C中元素按递增排列。下面的函数append(1ast，e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A，B)实现集合运算A—B，并返回表示结果集合C的链表的首结点的地址。在执行A—B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A—B运算执行完毕后，再删除并释放表示结果集合的链表的表头结点。【上海大学2000年】 typedef struct node( int element； struct node*link； }NODEj NODE*A，*B，*C； NODE *append (NODE *last，in七e) { last一>link=(NODE*)malloc(sizeof(NODE))； last一>link一>element=e； return (1ast一>link); } NODE*dlf ference(NOI)E*A，N0 L)E*B) { }
问答题编写算法，将自然数1～n2按“蛇形”填入n×n矩阵中。例(1～42)如图所示(用程序实现)。【南京航空航天大学1997八(12分)】【中科院计算所1996】
问答题如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(1flag，left，data，right，rflag)，其中：1flag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子，rflag=1，right指向其后继。 prior(node，x) {if(node!=null) if((1) )*x=node一>right； else*x=node一>left ; } next(bt，node，x) ／*bt是二叉树的树根*／ {(2) ； if(node!=bt＆(4)； while(*x==node)； *x=t； } }【南京航空航天大学1996十(8分)】
问答题设待排序的关键字分别为28，13，72，85，39，41，6，20。按二分法插入排序算法已使前7个记录有序，中间结果如下：试在此基础上，沿用上述表达方式，给出继续采用二分法插入第8个记录的比较过程。
问答题Hash方法的平均查找路长决定于什么?是否与结点个数N有关?处理冲突的方法主要有哪些? 【中国人民大学2000一、4(4分)】
问答题用单链表存储多项式的结构定义如下：
Typedef struct Term{ //多项式的项
float coef; //系数
int exp; //指数
struct Term
*
link;//链指针
}
*
Polynomial;
试编写一个算法，输入一组多项式的系数和指数，按指数降幂的方式建立多项式链表，要求该链表具有表头结点。如果输入的指数与链表中已有的某一个项的指数相等，则新的项不加入，并报告作废信息。整个输入序列以输入系数为0标志结束。算法的首部为Polynomial createPoly()；
问答题设有一个正整数序列组成的有序单链表(按递增次序有序，且允许有相等的整数存在)，试编写能实现下列功能的算法：(要求用最少的时间和最小的空间。)(1)确定在序列中比正整数x大的数有几个(相同的数只计算一次，如序列{20，20，17，16，15，15，11，10，8，7，7，5，4}中比10大的数有5个)；(2)在单链表中将比正整数x小的数按递减次序排列；(3)将正整数(比)x大的偶数从单链表中删除。【东北大学2001二(17分)】
问答题试编写求倒排循环链表元素的算法。【南京航空航天大学1995十二(10分)】
问答题分析ISAM文件(INDEXED SEQUENTIAL ACCESS METHORD)和VSAM文件(VIRTUALSTORAGE ACCESS METHORD)的应用场合、优缺点等。【华南理工大学2001一、4(4分)】
问答题对于下图所示的AOE网络：
问答题已知一棵度为M的树中有n1个度为1的结点，n2个度为2结点，…，nm个度为m的结点，证明其叶结点个数为【中国海洋大学2004五(15分)】【山东大学1993一、2(4分)】【西安交通大学1996四、1(5分)】【东南大学1999一、4(8分)】
问答题编写递归算法，依据树的双亲表示法及其根结点创建树的孩子兄弟链表存储结构。要求写算法以前先写出这两种存储结构的类型说明。【清华大学1995六(20分)】
问答题带头结点的双循环链表L中只有一个元素结点的条件是：__________。【合肥工业大学1999三、3 2000三、2(2分)】
问答题设二叉树BT的存储结构如下：其中BT为树根结点的指针，其值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为结点的数据域。试完成下列各题：
问答题设开放定址哈希表的表长为10，表中元素的编号从0到9，设初始时表为空。作图表示出采用二次探测处理冲突时，将关键词89，1 8，49，58，69依次插入到该表中的过程。同时要求对每一步给出简要的说明。【中南大学2005四、5(10分)】
问答题对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。【北方交通大学2001二、8】
问答题为什么文件的倒排表比多重表组织方式节省空间? 【东南大学2001一、2(6分)】
问答题已知A[1．．N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先?【中国人民大学2001二、5(4分)】