问答题设要将线性表(45，86，99，76，43，19，67，26，65，72，85，14)从小到大进行排序，则使用冒泡排序、初始步长为4的Shell排序、归并排序和以第一个元素为分界元素的快速排序进行第一趟扫描的结果分别为(1)，(2)，(3)，(4)。【上海海事大学2005二、5(5分)】

问答题已知一棵二叉树，该二叉树中结点的形式为(data，left，right)。其中data域为结点的数据域，且它的数据类型为int；left域和fight域分别给出本结点的左孩子和右孩子的地址，又已知该排序二叉树的根结点地址为root。请设计一个非递归的函数，给出该二叉树的前序遍历序列的最后一个结点的地址，另外要求所使用的额外空间必须为O(1)。【上海交通大学2006】

问答题说明下列程序功能，用图示给出子程序crt_pre的结果，并给出输出结果。 #include“malloc.h” #include“stdio．h” typedef struct BinNode {chardata; struct BinNode*ich，*rch；)BinNode，*Bintree； struct chtp(int len；char ch[100]；)S； struct queue {struct BinNode*elem[100]；int front，rear；)q； struct BinNode*bt； int ii=0; void crt_pre(Bintree*t) {char c; c=s．ch[ii]； ii=ii+1； if(c==‘．’) *t=0； else{*t=(BinNode*)malloc(sizeof(BinNode)); (*t)一>data=c； crt_pre( crt_pre( if(p) {q．elem[q．rear++]=p; q．elem[q．rear++]：0； while(q．front!=q．rear) {t=q．elemcq．front++]； if(t){w++； if(t一>ich)q．elem[q．rear++]=t一>ich; if(t一>rch)q．elem[q．rear++]：=t一>rch； } else(if(q．front!=q．rear)q．elem[q．rear++]=0; if(w>max)max=w; w=0： } } } return max； } main() {char c[]={“abd..eh.cf．i.．g!”);int i=0，num； for(i=0，s.1en=0；c[i]!=‘!’; i++，S．1en++)s．ch[i]=c[i]； crt_pre( num=unknown(bt)； printf(“＼n w=％d＼n”，num); } 【北京交通大学2006六、1(8分)】

问答题设x i (0≤j≤n)是(n+1)个不同的点，a j (O≤j≤n)是已知常数．作一个(2n+1)次多项式p(x)，使得p(x j )=0，p"(x j )=a j ，0≤j≤n．

问答题设测量一个长方体的长、宽、高的相对误差限分别为ε，由测量的数据计算该长方体的体积V,所得结果的相对误差限为多少?

问答题写出用堆排序算法对文件F=(12，3，15，30，9，28)进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个主要区别。【东南大学1998二(8分)】

问答题设x=0．43980，y=1．5324，z=11．5012均是具有4位有效数字的近似值，试分析xyz的绝对误差限、相对误差限和有效数字．

问答题若AL中的内容为2位压缩的BCD数，即6AH，试编程实现下列功能。 (1) 将其拆开成非压缩的BCD码，高低位分别存人BH和BL中。 (2) 将上述已求出的2位BCD码变换成对应的ASCII码，并存入CH和CL中。

问答题设键盘输入n个英语单词，输入格式为n，w 1 ，w 2 ，…，w n ，其中n表示随后输入英语单词的个数，试编一程序，建立一个单向链表，实现：(1)如果单词重复出现，则只在链表上保留一个(单考生做)。(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k≤n)个单词(统考生做)。【南京航空航天大学1998九(10分)】

问答题请简要列出影响一个算法(或程序)时间效率的主要因素，并指出其中与算法(或程序)本身直接有关的因素。【北京航空航天大学2008一、1(4分)】

问答题已知方程x3+2x-1=0在[0，1]上有唯一实根x*．证明：对任意初值x0∈[0，1]，迭代格式均收敛于x*，并分析该迭代格式的收敛阶数．

问答题阶B树中(如图所示)，插入关键字87，试画出插入调整后树的形状。【东南大学1999五(15分)】

问答题若某堆栈初始为空，PUSH与POP分别表示对栈进行一次进栈与出栈操作，那么，对于输入序列a，b，c，d，e，经过PUSH，PUSH，POP,PUSH，POP,PUSH，PUSH以后，输出序列是__________。【北京航空航天大学2006一、3(1分)】

问答题证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。

问答题按由大到小的顺序对一含有N个元素的数组A[N]进行排序，利用如下改进的简单选择排序方法：第一次选出最大者存入A[1]，第二次选出最小者存入A[N]，第三次选出次大者存入A[2]，第四次选出次小者存入A[N-1]，如此大小交替地选择，直到排序完毕。【东华大学2001十(10分)】

问答题在一个无向图的的邻接表中，若表结点的个数是m，则图中边的条数是__________条。【西安电子科技大学2003一、3(2分)】

问答题已知一个森林的先序序列和后序序列如下，请构造出该森林。1)先序序列：ABCDEFGHIJKLMNO。2)后序序列：CDEBFHIJGAMLONK。【合肥工业大学2000年】

问答题已知一棵二叉树的前序序列为：A，B，D，G，J，E，H，C，F，I，K，L；中序序列为：D，J，G，B，E，H，A，C，K，I，I，F。

问答题顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__________次；当使用监视哨时，若查找失败，则比较关键字的次数为__________。【华中理工大学2000一、8(2分)】

问答题用一维数组B与列优先存放带状矩阵A中的非零元素A[i，f](1≤i，i-2≤i+2)，B中的第8个元素是A中的第 (1) 行，第 (2) 列的元素。【北京邮电大学2001二、3(4分)】