问答题已知三个字符串分别为．s=~ab…abcaabcbca…a’，s"="caab"，s”=Ibcb’。利用所学字符串基本运算的函数得到结果串为：s""="caabcbca，…aca…a’，要求写出得到以上结果串s """ 所用的函数及执行算法。【东北大学1998一、1(10分)】

问答题已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1：2 h 一1】中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child，data，rchild)，根结点所在链结点的指针由T给出。【北京师范大学2005六、3(15分)】【北京航空航天大学1999七(15分)】

问答题设计一个算法，统计一个采用邻接矩阵存储，具有n个顶点的无向无权图所有顶点的度。【天津大学2005六(10分)】

问答题线性表(a 1 ，a 2 ，…，a n )用顺序映射表示时，a i 和a i+1 (1≤i≤n n )的物理位置相邻吗?链接表示时呢?【东南大学1996一、1(5分)】

问答题下列函数是在无向图的邻接表中删除一条边的算法，请完善该程序。 V0id deledge(ALGraph*G，int i， int j) {EdgeNode*p，*q; p=G一>adj list[i]．firstedge； if(①)fG一>adjlist[i]．firstedge=p一>next; free(p)；) else{while(p一>next一>adjvex!=j ) } p=G一>adj lis[j]．firstedge ； if(p一>adjvex= =i){G一>adj list[j]．firstedge=p一>12ext； free(p)；) elsefwhile(p一>12ext一>adlvex!=i ＆＆ p一>next) ④； if(p一>next!=null){q=p一>next；⑤；free(q)；) } } 【东南大学2005数据结构部分三(10分)】

问答题应用Prim算法求解连通网络的最小生成树问题。(1)针对右图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(每边1分，共5分)(始顶点号，终顶点号，权值)(2)下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。constintMaxInt=INTMAX；／／INTMAX的值在中constintn：6；／／图的顶点数，应由用户定义typedefintAdjMatrix[n][n]；／／用二维数组作为邻接矩阵表示typedefstruct{／／生成树的边结点intfromVex，toVex；／／边的起点与终点intweight；／／边上的权值}TreeEdgeNode；typedefTreeEdgeNodeMST[n一1]；／／最小生成树定义voidPrimMST(AdjMatrixG，MSTT，intrt){／／从顶点rt出发构造图G的最小生成树T，rt成为树的根结点TreeEdgeN0dee；inti，k=0，min，minpos，V；for(i=0；i

问答题设A[1．．100]是一个记录构成的数组，B[1．．100]是一个整数数组，其值介于1～100之间，现要求按B[1．．100]的内容调整A中记录的次序，比如当B[1]=11时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。【中科院计算所2000七(15分)】

问答题已知p是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(a 1 ，a 2 ，…，a n-1 ，a n )改造为(a 1 ，a 2 ，…，a n-1 ，a n ，a n-1 ，…，a 2 ，a 1 )。【北京理工大学2005十四、1(5分)】

问答题设要将线性表(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分)】

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

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

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

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

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

问答题按由大到小的顺序对一含有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。