问答题设计算法以求解从集合{1。n)中选取k(k≤n)个元素的所有组合。例如，从集合{1．4)中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3，2 4，3 4。【合肥工业大学2000五、5(8分)】

问答题设x 0 ，x 1 ，x 2 为互异节点，a，b，m为已知实数．试确定x 0 ，x 1 ，x 2 的关系，使满足如下三个条件p(x 0 )=a， p"(x 1 )=m，p(x 2 )=b的二次多项式p(x)存在且唯一，并求出这个插值多项式p(x)．

问答题冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学2001二、3(9分)】【北京邮电大学1992六(10分)】

问答题最小最大堆(minmaxHeap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。(1)画出在图中插入关键字为5的结点后的最小最大堆。(2)画出在图中插入关键字为80的结点后的最小最大堆。(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。

问答题下面是一个求两个集合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运算执行完毕，再删除并释放表示结果集合的链表的表头结点。 typedef struct node{int element； struct node *link；}NODE; NODE *A，*B，*C； NODE *append(NODE*la8t， int e) {last一>1ink=(NODE*) malloc (sizeof(NODE))； 1a8t一>1ink一>element=e； return(last一>link)； } NODE*difference(NODE*A，NODE*B) (NODE*c，*1ast； C=la8t=(NODE*)malloc (sizeof(NODE))； while (1) if (A一>elementelement) { 1a8t=append(last，A一>element)； A=A一>link； ) else if (2) {A=A一>1ink； B=B一>link;}ELSE (3)； while (4) {1ast=append(1ast，A一>element)；A=A一>link; ) (5) ； last=c； c=c一>link； free (last)； return(C)； } ／*call form：c=difference(A，B)；*／【上海大学2000一、4(10分)】

问答题给定一个由英文字母组成的字符串S(假设S用数组实现)，编制一个递归函数，测试S是否为回文串。“回文串”是指该字符串从左向右读和从右向左读完全相同，如“noon”， “radar”等。【南京大学2005】

问答题一棵有n个结点的满二叉树有(1)个度为1的结点、有(2)个分支(非终端)结点和(3)个叶子，该满二叉树的深度为(4)。【华中理工大学2000一、6(3分)】

问答题分析用Jacobi迭代格式和Gauss-Seidel迭代格式解线性方程组的收敛性．

问答题已知关键字序列F={78，19，63，30，89，84，55，69，28，83}。要求：

问答题构造连通网最小生成树的两个典型算法是__________。【北京科技大学1998一、5】

问答题冯·诺依曼计算机结构的特点是什么?

问答题在有序表A[1．．20】中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________。【合肥工业大学2000三、10(2分)】

问答题证明：高为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分)】