问答题证明：高为h(不含叶子层)的m阶B一树上最多有m
h
一1个关键字。【北京交通大学2006四、2(5分)】
问答题索引顺序存取方法(ISAM)中，主文件已按关键字排序，为何还需要主关键字索引?【东南大学1995四(6分)】
问答题结点类型和存储结构如下：typedef 8truct {int key； datatype data； int count； }node；node R[n]；试设计一个排序算法，要求不移动结点的存储位置，只在结点的count字段记录结点在排序中的序号，并将排序结果按升序输出。【哈尔滨工业大学2005五、2(12分)】
问答题对长度为n的线性表采用顺序查找，在等概率的条件下，查找成功的平均检索长度为__________。在长度为n的顺序表中删除第i(1≤i≤n)个数据元素需要移动__________个数据元素。在长度为n的顺序表中的第i(1≤i≤n)个数据元素之前插入一个新元素，需要移动__________个数据元素。【大连理工大学2005一、1(3分)】
问答题已知某有向图(n个结点)的邻接表，求该图各结点的入度数。【天津大学2001五(10分)2006二、1(7分)】【南京理工大学1997四、2(10分)】
问答题若有N个元素已构成一个小根堆，那么如果增加一个元素为K
n+1
请用文字简要说明你如何在log
2
n的时间内将其重新调整为一个堆?【中科院计算所1999三、2(5分)】
问答题已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false。 【西安电子科技大学2000软件二(10分)】
问答题设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列?说明原因。(1)51，250，501，390，320，340，382，363(2)24，877，125，342，501，623，421，363【东北大学2002一、3(4分)】
问答题有一种简单的排序算法，叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。(1)(3分)给出适用于计数排序的数据表定义；(2)(7分)使用Pascal或C语言编写实现计数排序的算法；(3)(4分)对于有n个记录的表，关键字比较次数是多少?(4)(3分)与简单选择排序相比较，这种方法是否更好?为什么?【清华大学2000三(17分)】
问答题已知树的广义表表示如下T=(A(B(E(K,L))，C(G)，D(H(M),I,J))，画出该广义表所对应的树。【天津大学2006二(10分)】
问答题如果一棵有n个结点的满二叉树的高度为h(根结点所在的层次为1)，则：
问答题设已知n个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这n个关键字散列到初始为空的地址空间中，一共发生了__________次散列冲突。【北京航空航天大学2006一、9(1分)】【西安电子科技大学2001软件一、7(2分)】
问答题请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。【北京大学1998三、2(5分)】【南京大学2000】【苏州大学2004五(15分)】【中国海洋大学2005八(15分)】
问答题编写程序，实现用拓扑排序方法求最长路径的算法。【南京航空航天大学2003七(10分)】
问答题设散列函数H(K)=3Kmod11，散列地址空间为0～10，对关键字序列(32，13，49，24，38，21，4，12)按下述两种解决冲突的方法构造散列表：
问答题
问答题假设二叉树采用链接存储方式存储，编写一个后序遍历二叉树的非递归算法。
问答题下图是5阶B树，画出删去P后的B树，再画出删去D后的B树。【厦门大学2000七、3(20／3分)】
问答题按照大顶堆积的定义，对序列(26，5，77，1，61，11，59，15，48，19)进行堆积排序，第二趟排序结束时序列的状态是__________。【北京航空航天大学2006一、10(1分)】
问答题数据结构DEAP的定义如下：DEAP是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：(1)树根不包含元素。(2)其左子树是一小堆(MINHEAP)，其右子树是一大堆(MAXHEAP)。(3)若右子树非空，设i是左子树的任一结点，j是右子树中与i相应的结点，若这样的j结点不存在，则取j为右子树中与i的父结点相应的结点；结点i的关键字总值是小于或等于结点j的关键字值。一个DEAP的例子如右图所示，与结点15相对应的结点为20，与结点19相对应的结点为25。(1)给出在该DEAP中插入结点4后的结果。(2)写出在DEAP中插入新结点的算法。(3)编写实现上述算法的程序。