问答题证明：高为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分)】
问答题编写一个实现连通图G的深度优先遍历(从顶点v出发)的非递归函数，可以用伪代码描述。
问答题已知某有向图(n个结点)的邻接表，求该图各结点的入度数。【天津大学2001五(10分)2006二、1(7分)】【南京理工大学1997四、2(10分)】
问答题设有求解线性方程组Ax=b的迭代格式Bx(k+1)+Cx(k)=b，k=0，1，…，(A)其中试确定实参数ξ和η的取值范围，使迭代格式(A)收敛．
问答题若有N个元素已构成一个小根堆，那么如果增加一个元素为K
n+1
请用文字简要说明你如何在log
2
n的时间内将其重新调整为一个堆?【中科院计算所1999三、2(5分)】
问答题已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false。 【西安电子科技大学2000软件二(10分)】
问答题设f(x)∈C3[a，b]．1)写出f(x)以a，，b为插值节点的2次插值多项式L2(x)以及插值余项f(x)-L2(x)的表达式；2)证明：其中h=(b-a)/2，ξ∈(a，b)．
问答题设二叉排序树中关键字由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分)】
问答题如下指令片段的功能是什么? PUSH FD PUSH 0 PUSH CS PUSH DWORD PTR 1234H IRETD
问答题设计将带表头的链表逆置算法。
问答题假设K
1
，…，K
n
是n个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K
1
，K
2
，…，K
n
时，用算法建立一棵以LLINK-RLINK链接表示的二叉查找树。
(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E))。
问答题如果一棵有n个结点的满二叉树的高度为h(根结点所在的层次为1)，则：
问答题设已知n个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这n个关键字散列到初始为空的地址空间中，一共发生了__________次散列冲突。【北京航空航天大学2006一、9(1分)】【西安电子科技大学2001软件一、7(2分)】
问答题请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。【北京大学1998三、2(5分)】【南京大学2000】【苏州大学2004五(15分)】【中国海洋大学2005八(15分)】
问答题编写程序，实现用拓扑排序方法求最长路径的算法。【南京航空航天大学2003七(10分)】