2001－2003年数据结构研究生入学考题选讲4.广义表（（））的表头是（），表尾是（）。A（）BNILC（（））D（（（）））7.下列有关二叉排序树正确的描述是（）。A对二叉排序树中序遍历可以得到结点的有序序列；B二叉排序树上插入的新结点总是作为叶结点；C二叉排序树的查找性能与树的平衡度无关；D若二叉树的左右子树均为二叉排序树，且左子树根结点的值小于二叉树根结点的值，右子树根结点的值大于二叉树根结点的值，则该二叉树一定是二叉排序树；E若中序遍历一棵二叉树得到结点的有序序列，则该棵二叉树一定是二叉排序树；9.若表R再排序前已经按关键字值递增排列，则（）算法的比较次数最少。A直接插入排序；B快速排序；C归并排序；D选择排序；已知二叉树中叶结点数为50，仅有一个孩子的结点数为30，则总结点数为（）A81；B129；C110；D130；三、简答题下列广义表，可以唯一对应一棵二叉树的有哪些？并归纳出唯一对应的条件。a.(A(B(D,E),C(F)))b.(A(B(D,E),C))c.(A)d.(A(B(C,D(E))))e.()以权值分别为3、4、7、9、20的a,b,c,d,e五个元素作为叶结点构造二叉树，回答：(1)如何构造路径长度最短的二叉树，图示出一颗路径长度最短的二叉树，并计算出路径长度；(2)如何构造带权路径长度最短的二叉树，图示出一棵带权路径长度最短的二叉树，并计算出带权路径长度；6.试画出满足下列条件的所有可能的二叉树。(1)树的高度为3，中序访问第一个结点为C，先序序列为A、B、C、D、E;(2)中序和先序序列均为A、B、C、D、E;(3)树的高度为5，先序序列为A、B、C、D、E;四、算法题（2000年）四、算法题（2000年）参考答案：PROCHEAD(ls:glist;VARh:glst;x:elemtp);IF(ls=NIL)THENERROR(“空表”）ELSEIF(ls^.hp^.tag=0)THEN[x:=ls^.hp^.data;h:=NIL]ELSE[h:=ls^.hp^.hp];ENDP;{HEAD}PROCTAIL(ls:glist;VARh:glist);h:=ls^.tp;ENDP;{TAIL}四、算法题（2000年）四、算法题（2000年）四、算法题（2000年）PROCbt_to_adj(bt:bitree;n:integer;adjlist:ARRAY[1..n]OFvexnode);IFbt<>NILTHEN[iniqueue(Q);enqueue(Q,bt);i:=1;WHILENOTEMPTY(Q)DO[p:=dlqueue(Q);adjlist[i].data:=p^.data;IFp^.lchild<>NILTHEN[enqueue(Q,p^.lchild);new(s);s^.data:=p^.lchild^.data;s^.next:=NIL;adjlist[i].firstarc:=s;]IFp^.rchild<>NILTHEN[enqueue(Q,p^.rchild);new(s);s^.data:=p^.lchild^.data;s^.next:=adjlist[i].firstarc;adjlist[i].firstarc:=s;]i:=i+1;]]ENDP;四、算法题（2001年）四、算法题（2001年）x1:=-maxint;PROCinorder(bt:bitreptr);IFbt<>NILTHEN[inorder(bt^.lchild);x2:=bt^.data;IF(x1>=x2)THEN[write(“无序”）；EXIT；]x1:=x2;inorder(bt^.rchild);]ENDP;四、算法题（2001年）四、算法题（2001年）PROClevel(bt:bitreptr);IFbt<>NILTHEN[iniqueue(Q);enqueue(Q,bt);a:=0;b:=0;c:=0;d:=0;WHILENOTEMPTY(Q)DO[p:=dequeue(Q);IFp^.lchild<>NILTHENenqueue(Q,p^.lchild)ELSEb:=a+1;IF(b<>0)AND(b=a)THEN[write(“不是完全二叉树”）；EXIT;]a:=b;IFp^.rchild<>NILTHENenqueue(Q,p^.rchild)ELSEd:=c+1;IF(d<>0)AND(c=d)THEN[write(“不是完全二叉树”）；EXIT;]c:=d;]write(“是完全二叉树”）]ENDP;四、算