考点基本概念、术语各类基本数据结构(及其变型)

考点基本概念、术语各类基本数据结构（及其变型）的逻辑结构各类基本数据结构（及其变型）的物理结构基本算法的编制及灵活运用算法时间复杂度的分析要求用类pascal语言阅读算法和编制算法的能力递归算法的阅读和编制2001－2003年数据结构研究生入学考题选讲一、不定项选择题1.下列二叉树中，哪些二叉树的所有非叶子结点的度均为2（）。A完全二叉树B满二叉树C平衡二叉树D哈夫曼树E二叉排序树2.下列排序算法中，属于交换排序的排序算法有（）。平均时间复杂度为O(nlog2n)的排序算法有（）。A起泡排序B希尔排序C基数排序D快速排序E归并排序F堆排序G直接插入排序A,FD,E,F3.一个队列的入队序列是a,b,c,d,则它的所有可能的出队序列是（）。Ad,c,b,aBa,d,c,bCa,b,c,dDc,b,d,aC4.广义表（（））的表头是（），表尾是（）。A（）BNILC（（））D（（（）））AA5.有关线索二叉树不正确的描述是（）。A当ltag=0时，该结点的lchild指向其直接前驱；B从任意结点出发沿着指针可以遍历该棵二叉树C线索二叉树中任意一结点均有指向其前驱和后继的线索；D线索二叉树头结点的ltag=0，rtag=1；A，C6.图G是n个顶点的无向完全图，则下列说法正确的有（）。AG的邻接多重表需要n(n-1)个边结点和n个顶点结点；BG的连通分量个数最少；CG为连通图；DG所有顶点的度的总和为n(n-1)；B,C,D7.下列有关二叉排序树正确的描述是（）。A对二叉排序树中序遍历可以得到结点的有序序列；B二叉排序树上插入的新结点总是作为叶结点；C二叉排序树的查找性能与树的平衡度无关；D若二叉树的左右子树均为二叉排序树，且左子树根结点的值小于二叉树根结点的值，右子树根结点的值大于二叉树根结点的值，则该二叉树一定是二叉排序树；E若中序遍历一棵二叉树得到结点的有序序列，则该棵二叉树一定是二叉排序树；A,B,E8.下面关于折半查找的正确叙述有（）。A查找表中的元素必须有序；B查找表中的元素可以是分块有序；C查找表中的元素不必有序；D查找表可以用链式存储结构实现；A9.若表R再排序前已经按关键字值递增排列，则（）算法的比较次数最少。A直接插入排序；B快速排序；C归并排序；D选择排序；A10.链表不具备的特点是（）。A可随机访问任一元素；B插入删除不需要移动元素；C不必事先预分存储空间；D所需空间与线性表长度成正比；A11.若线性表最常用的操作是存取第k个元素及其前驱的值，则采用（）存储方式节省时间。A单链表；B双向链表；C单循环链表；D顺序表；D12.若线性表最常用的操作是在最后一个元素之后插入一个结点和删除最后一个结点，则采用（）存储方式节省时间。A单链表；B双向链表；C单循环链表；D带头结点的双循环链表；D13.已知二叉树中叶结点数为50，仅有一个孩子的结点数为30，则总结点数为（）A81；B129；C110；D130；B二、判断题1.()在顺序表中取第k个元素所花费的时间与k成正比。2.()一个有向图的邻接表和逆邻接表中的结点个数一定相等。3.()直接选择排序算法的时间复杂度为O(n2)，不受数据初始排列的影响。4.()广义表的长度是指广义表的原子个数。三、简答题1.回答满足后序序列和前序序列正好相同的二叉树的树型和正好相反的二叉树的树型各是什么？2.下图既可以看成是一棵二叉树，又可以看成是一个无向图，试回答两者有何差异。0123层次之分有序，左右子树之分度的概念三、简答题3.下列广义表，可以唯一对应一棵二叉树的有哪些？并归纳出唯一对应的条件。a.(A(B(D,E),C(F)))b.(A(B(D,E),C))c.(A)d.(A(B(C,D(E))))e.()空表只有一个元素的表每个子表个数是0或2的表4.无向图G如下图所示，给出G的邻接矩阵，若对邻接矩阵中每行的访问顺序是从右到左，写出该图从顶点V2开始的深度优先搜索遍历的顶点序列。v1v2v3v4v50110110010100110110110110G＝v2,v4,v5,v3,v15.以权值分别为3、4、7、9、20的a,b,c,d,e五个元素作为叶结点构造二叉树，回答：(1)如何构造路径长度最短的二叉树，图示出一颗路径长度最短的二叉树，并计算出路径长度；(2)如何构造带权路径长度最短的二叉树，图示出一棵带权路径长度最短的二叉树，并计算出带权路径长度；(1)9个结点的完全二叉树，一定是路径长度最短的二叉树；或前三层占满，第四层只有两个结点的二叉树其路径长度也为最短。路径长度为：1＋1＋2＋2＋2＋2＋3＋3＝16(2)哈夫曼树一定是带权路径长度最短的二叉树，其带权路径长度为：20＋9×2＋7×3＋（3＋4）×4＝876.试画出满足下列条件的所有可能的二叉树。(1)树的高度为3，中序访问第一个结点为C，先序序列为A、B、C、D、E;(2)中序和先序序列均为A、B、C、D、E;(3)树的高度为5，先序序列为A、B、C、D、E;(1)有三棵二叉树满足条件；(2)A、B、C、D、E为序的右单枝树；(3)A、B、C、D、E为序的右单枝树和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);IFbtNILTHEN[iniqueue(Q);enqueue(Q,bt);i:=1;WHILENOTEMPTY(Q)DO[p:=dlqueue(Q);adjlist[i].data:=p^.data;IFp^.lchildNILTHEN[enqueue(Q,p^.lchild);new(s);s^.data:=p^.lchild^.data;s^.next:=NIL;adjlist[i].firstarc:=s;]IFp^.rchildNILTHEN[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);IFbtNILTHEN[inorder(bt^.lchild);x2:=bt^.data;IF(x1=x2)THEN[write(“无序”）；EXIT；]x1:=x2;inorder(bt^.rchild);]ENDP;四、算法题（2001年）四、算法题（2001年）PROClevel(bt:bitreptr);IFbtNILTHEN[iniqueue(Q);enqueue(Q,bt);a:=0;b:=0;c:=0;d:=0;WHILENOTEMPTY(Q)DO[p:=dequeue(Q);IFp^.lchildNILTHENenqueue(Q,p^.lchild)ELSEb:=a+1;IF(b0)AND(b=a)THEN[write(“不是完全二叉树”）；EXIT;]a:=b;IFp^.rchildNILTHENenqueue(Q,p^.rchild)ELSEd:=c+1;IF(d0)AND(c=d)THEN[write(“不是完全二叉树”）；EXIT;]c:=d;]write(“是完全二叉树”）]ENDP;四、算法题（2002年）四、算法题（2002年）PROCleveltrav(t:bitre);IFtNILTHEN[iniqueue(Q);enqueue(Q,t);WHILENOTEMPTY(Q)DO[p:=dequeue(Q);IF(p^.lchild=NIL)AND(p^.rchlid=NIL)THENc:=c+1;IF(c=1)THENvisit(p^.data);{访问第一个叶子}IFp^.lchildNILTHENenqueue(Q,p^.lchild);IFp^.rchildNILTHENenqueue(Q,p^.rchild);]visit(p^.data);]{访问最后一个叶子}ENDP;四、算法题（2002年）四、算法题（2002年）PROCDELETE(L,x);p:=L^.firstlink;q:=L;WHILEpNILDO[IF(p^data=x)THENCASEL=q:[L^.firstlink:=p^.link;IF(L^.lastlink=p)THENL^.lastlink:=NIL;dispose(p);]L^.lastlink=p:[q^.link:=NIL;L^.lastlink:=q;dispose(p);]Others:[q^.link:=p^.link;dispose(p);p:=q^.link]ENDCELSE[q:=p;p:=p^.link;]ENDP;四、算法题（2003）四、算法题（2003）