上海大学2000数据结构考研试题

《上海大学2000数据结构考研试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

消息来自上海大学考研论坛——启弘教育上海大学2000考研题一请完善下列程序,每小题在Pascal语言(a),c语言(b)中任选一题（共40分）注意：每个空格填一个表示式或一个语句。1下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[j]进行比较,第二趟对所有偶数的i,将a[i]和a[j]进行比较每次比较时若a[i]>a[i+1],.将二者交换,以后重复上述二趟过程,直至整个数组有序程序.(a)Procedureoeseort(vara:array[1..n]ofinteger);Varflag:boolean;i,t:integer;BeginRepeatFlag:=false;Fori:=1tonstep2doIf(a[i]>a[i+1])then[flag:=(1);t:=a[i+1];a[i+1]:=a[j];(2)]fori:=(3)doif(a[i]>a[i+1])then[flag:=(4);t:=a[i+1];a[i+1]:=a[i];a[i]:=t;]until(5)end;程序（b）Voidoesort(inta[n]){intflag,i,t;do{flag:=0;for(i=1;ia[i+1]){flag=(4);t=a[i+1];a[i+1]=a[i];a[i]=t;}}while(5); 消息来自上海大学考研论坛——启弘教育}2下列算法实现求采用顺序结构存储的串和串的一个最长公共子串。程序（a）Proceduremaxcomstr(vars,t:orderstring;varindex,length:integer);Vari,j,klength1:integer;con:boolean;While(i<=s.len)do[J:=1;While(j<=t.len)do[If(s[i]=t[j]then[K:=1;length1:=1;con:=true;WhilecondoIf(1)then[Length1:=length1+1;k:=k+1;]else(2);if(length1>length)then[index:=i;length:=length1;](3)]else(4)](5)]end.程序(b)Voidmaxconstr(orderstring*s,*t;intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while((ilength){index=i;length=length1;}(3);}else(4);} 消息来自上海大学考研论坛——启弘教育(5)}}3设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数和叶子结点个数N0.N2NLNR,N0都是全局量，且在调用count(t)之前都置为0.程序(a)typenodeptr=^nodetype;nodetype=recorddata:integer;lchild,rchild:nodeptr;end;varN2,NL,NR,N0:integer;procedurecount(t:nodeptr);beginift^lchild<>nilthenif(1)thenN2:=N2+1ElseNL:=NL+1ElseIf(2)thenNR:=NR+1ELSE(3);ift^.lchild<.nilthen(4);ift^.rchild<.nilthen(5);end;(*callform:ift<>nilthencount(t);*)程序(b)typedefstructnode{intdata;structnode*lchild,*rchild;}NODE;intN2,NL,NR,N0;voidcount(NODE*t){if(t->lchild!=NULL)if(1)N2++; 消息来自上海大学考研论坛——启弘教育ElseNL++;ElseIf(2)NR++;Else(3);if(t->lchild!=NULL)(4);if(t->rchild!=NULL)(5);}/*callform:if(t!=NULL)count(t);*/4.下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空：操作完成后A，B保持不变，C中元素递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针指向的结点的后面并返回新结点的地址：函数实现集合运算，并返回表示结果集合C的链表的首结点的地址。在执行运算A-B之前，用于表示结果集合的链表首先增加一个附加的表头结点以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链表的表头结点。程序(a)typenodeptr=^nodetype;nodetype=recordelement:integer;link:nodeptr;end;varA,B,C:nodeptr;Functionappend(last:nodeptr;e:integer):nodeptr:BeginNew(last^.link);last^.link^.element:=e;Append:=last^.linkEnd;Functiondifference(A,B:nodeptr):nodeptr;VarC,last:nodeptr;BeginNew(C);last:=C;While(1)doIfA^.elementlink=(NODE*)malloc(sizeof(NODE));last->link->element=e;return(last->link);}NODE*difference(NODE*A,NODE*B){NODE*C,*last;C=last=(NODE*)malloc(sizeof(NODE));While(2)If(A->elementelement);A=A->link;}elseif(2){A=A->link;B=B->link;}else(3);while(4){last=append(last,A->element); 消息来自上海大学考研论坛——启弘教育A=A->link;}(5);last=C;C=C-.link;free(last);return(C);}/*callform:c=difference(a,b);*/二请完善下列算法。（共24分）注意每个空格填一个表达式或一个语句1已知一个循环单链表如图所示下列算法图所示实现将该链表所有箭头方向取反。图1循环单链表结构图图2循环单链表逆置算法2设t是一棵非空的查找树,a和b是树t中某两个结点的值。下面的非递归算法（如图3所示）用于判别值为a和b的两个结点是否同在查找树t中的一根树枝上.若同在一根树枝上，则返回1(true);否则返回0(false).所谓两个结点在同一根树枝上是指两个结点同在树中一条自上而下的路径上。注：查找树采用二叉链表表示法与第一题中第3题的表示法相同。 消息来自上海大学考研论坛——启弘教育图3判别两个结点是否同在查找树的一根树枝上的算法三请编写完整的程序。（共20分）如果矩阵中存在这样的一个元素满足条件是第行中值最小的元素且又是第列中最大的元素，则称之为该矩阵的一个马鞍点。请编写出的矩阵的所有马鞍点。四请用流程图或类高级语言(pascal或c)表示算法。（16分）已知有向图有个n顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的个头结点（其结点数值域从1到n）.